聚类分析在数据挖掘和机器学习领域都有非常广泛的应用，它是根据数据点之间相似度的不同，将待聚类的数据集划分成不同类的方法，源于很多领域，包括数学、计算机科学、统计学、生物学和经济学[1]。在不同的应用领域，很多聚类技术都得到了发展，这些技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。其中谱聚类算法[2]是在谱图划分理论基础上发展起来的，不仅能识别任意形状的样本空间，应用在非块状和非凸形数据的聚类问题上，而且收敛于全局最优解，目前已在图像分割[3]、文本挖掘[4]、计算机视觉[5]等领域得到较好的应用。

谱聚类算法的核心是对特征向量的聚类，而该特征向量是由待聚类数据集的相似矩阵(拉普拉斯矩阵)特征分解得到的。因此，谱聚类算法性能的好坏取决于构建的相似矩阵。然而传统谱聚类算法中的高斯核函数只考虑数据点间的欧式距离，符合局部一致性，不符合全局一致性。文献[6]提出一种近邻自适应局部尺度的谱聚类算法，局部尺度的值取为样本点k个近邻的距离和，解决了单一全局尺度参数局限的问题。文献[7]用共享近邻表征两两数据点间的局部密度，并应用于相似度度量，提出一种基于共享近邻的自适应谱聚类算法(SNN-ASC)。文献[8]提出一种密度敏感的相似性度量，并结合特征间隙，能根据数据的实际分布情况进行聚类。文献[9]提出一种基于无参相似矩阵的谱聚类，考虑数据集中点的密度、距离、连通性3个信息，然后构造出一个无参相似图并构建相应的相似矩阵。文献[10]采用一种基于k-means算法的密度估计法构造相似矩阵，其过程提高了密度估计的准确性，但是却需要6个超参数，且当数据集中有较相似的结构时，聚类效果不理想。

本研究在分析数据特征的基础上，构建了一种自适应的相似矩阵。选用测地距离函数表征数据间的距离度量，相距较近的两点间的距离近似于欧氏距离，相距较远的两点则先根据欧氏距离得到每个数据点的k个近邻点，然后累加近邻点的测地距离，这样便得到了每对数据点间的最短距离，不仅消除了高斯核函数中尺度参数的波动影响，而且克服了欧式距离的局限性。根据每个点所处邻域的稠密程度，用两点间的共享近邻数来表征，进而得到待聚类数据点的基于测地距离和共享近邻数的相似度，应用到谱聚类算法中。最后在密度分布不均以及非块状(弧形、圆圈形、线形等)的人工数据集上、通用国际UCI实际数据集上都进行实验，并与k-均值算法(k-means)和基于规范化拉普拉斯矩阵的谱聚类算法(NJW)进行比较。结果表明，本文算法对复杂分布数据有更强的自适应能力和更高的准确率。

1 谱聚类算法的基本原理及现存问题

本节以传统的谱聚类算法为基础进行分析，谱聚类的实现方法有很多种，其中主要研究对象是NJW谱聚类算法，其具体实现过程可以归纳为4步：

1)根据某种合适的相似度度量方法，构建聚类数为k的待聚类数据集X={x1,x2,…,xn}的相似矩阵W=[wij]n×n，wij表示点xi与点xj之间的相似度，显然wij=wji，规定W对角线上的值为0。

2)计算规范化拉普拉斯矩阵L=D-1/2WD-1/2的前k个特征值及其对应的特征向量v1,v2,…,vk，其中

3)构建特征空间的向量矩阵V=[v1,v2,…,vk]∈Rn×k，如果记v=[y1,y2,…,yn]T，?得到一个k维数据集合{z1,z2,…,zi,…,zn}。

4)对于数据点z1,z2,…,zn，利用k-均值算法聚成k个类。

谱聚类算法的主要技巧是通过拉普拉斯矩阵将数据点映射到一个较低维的空间。在低维的数据空间中，数据点具有更好的聚类特性且满足一致性假设。

1)局部一致性 在空间位置上相邻的数据点具有更高的相似性；

2)全局一致性 同一结构上(同类中)的数据点具有更高的相似性。

传统谱聚类算法中的高斯核函数只考虑数据点间的欧式距离，符合局部一致性，不符合全局一致性，且当尺度参数σ选取不同值时，聚类结果也不相同。图1显示了在欧氏距离的测度下，选取不同的尺度参数时在“Twomoons”数据集上的测试实验。

可以看出，尺度参数σ取不同数值时得到的聚类结果也不相同。当σ=0.1时，聚类结果是最理想的；当σ=0.22时，聚类结果出现了微小的偏差；当σ=0.3时，聚类结果误差较大；当σ=25时，聚类结果完全错误。针对不同的数据集，尺度参数的选择范围也不相同。

图1 “Twomoons”数据集上的测试实验Fig.1 Test experiment on the “Twomoons” dataset