反向近邻构造连通图的聚类算法

作者：龙建武; 王强

来源：计算机科学与探索, 2022, 1-15.

• 去噪
• 反向邻居
• 反向近邻连通图
• 聚类

大数据时代的发展使得聚类算法的应用越来越广泛，但是当前大多数聚类算法对噪声数据比较敏感，并且不能识别非凸形状等复杂结构的数据集。针对该问题，提出一种反向近邻构造连通图的聚类算法。首先，设计一种密度计算方式得到数据点的密度，并构建一种动态的噪声判别器对数据进行去噪，从而削弱噪点对聚类过程的影响；其次，考虑到反向邻居更能体现数据点与周围各点之间的联系，设计一种对去噪后数据构造反向近邻连通图来识别簇内数据结构信息的聚类方法，并利用给定的聚类数合并聚类；最后，对噪点划分聚类时，考虑到仅仅将其划分到距离最近的簇可能导致划分结果不准确，设计一种噪点划分方式，将密度信息考虑到噪点划分聚类中，得到最终的聚类结果。为验证提出方法的有效性，将本文方法与其他五种聚类算法的聚类结果进行对比，采用外部评价指标Acc（Cluster Accuracy）和NMI（Normalized Mutual Information）进行聚类结果的评价。实验表明，本文算法在非凸形状等复杂结构的含噪数据集上的聚类效果优于对比算法。

• 单位
  重庆理工大学