基于近邻路径的自适应尺度谱聚类算法研究

摘要

谱聚类作为一种新兴的聚类方法，最近十年得到了广泛的研究和快速的发展，尤其在数据挖掘和机器学习等领域。相比传统聚类方法，谱聚类能够处理任意分布形状的数据集，可以收敛到全局最优并且易于实现，非常适合于很多的实际问题。由于谱聚类算法都是以相似矩阵为基础的，因此建立相似矩阵使用的相似度定义对于谱聚类算法的性能具有非常重要的意义。
　　 本文首先详细阐述了谱聚类相关的知识和方法，然后对经典谱聚类的相似度度量，从高斯核函数、尺度参数选择的影响、数据聚类的一致性三个角度对其进行了详细的分析和研究。发现经典谱聚类的相似度没有充分考虑局部统计信息和全局结构对两个数据点相似度的影响，以致不能充分满足聚类一致性，反映出两点间真实的近似关系，最终导致处理大量复杂结构的数据集时不能得到满意的聚类结果。受此启发，结合近邻思想，首先提出了基于共享近邻加权的自适应尺度，其充分利用了近邻分布统计信息；然后提出了强调全局结构一致性的k近邻路径距离；基于这两者给出了基于近邻路径的自适应尺度相似度，该相似度很好的满足了聚类一致性特征，将其引入谱聚类得到基于近邻路径的自适应尺度谱聚类算法。最后，在8个人工数据集、5个UCI数据集和USPS数据集上对将该算法与经典谱聚类、自调整谱聚类进行了对比实验。实验结果表明，该算法的聚类效果明显优于另两种算法，能够有效识别数据点之间的内在联系，得到正确聚类结果。