基于空间向量搜索的密度峰值聚类算法

来源：计算机工程与应用杂志2023年第15期北京时间：

作者：马振明, 安俊秀

单位：成都信息工程大学 软件工程学院, 成都 610200

摘要：针对密度峰值聚类(DPC)算法因构建全局样本点间的相似度矩阵，而导致时间开销过大的问题，提出了一种基于空间向量搜索的密度峰值聚类(VS-DPC)算法。在[n]维正交坐标系中将数据点映射为以原点为起点的空间向量，计算向量的模和与统一坐标轴正方向间的夹角；利用截断距离和截断映射角确定相似范围搜索相似向量；利用相似向量确定有效密度点从而构建稀疏相似度矩阵，降低时间复杂度。在UCI数据库中7个真实数据集和7个形状复杂的人工数据集上的实验结果表明，所提的VS-DPC算法保持了DPC的聚类精度，相较DPC算法减少了约60%的时间开销。并对比于CDPC和GDPC两种提升DPC聚类效率的算法，算法参数更少，且在聚类精度和时间上分别平均提升6和18个百分点。

关键词：密度峰值聚类,稀疏矩阵,时间复杂度,向量搜索,聚类