一种基于自适应相似矩阵的谱聚类算法

王贝贝 杨明 燕慧超 孙笑仙

摘 要：为了消除在构建谱聚类算法的相似矩阵时，高斯核函数中尺度参数的波动影响，构建了一种自适应相似矩阵，并应用到谱聚类算法中。自适应相似矩阵中数据点间的距离度量采用测地距离算法，相距较近的两点间的距离近似于欧氏距离，相距较远的两点则先根据欧氏距离得到每个数据点的k个近邻点，然后累加近邻点的测地距离，由此得到每对数据点间的最短距离。两点间的局部密度用共享近邻的定义来表示，更好地刻画了数据集的本征结构。在5个人工数据集和国际通用UCI数据库中的5个真实数据集上进行实验。实验结果表明，所提算法的聚类准确率高于对比算法的准确率，对复杂分布数据有很强的自适应能力。研究成果为数据挖掘及机器学习提供了思路和方法。

关键词：应用数学;相似矩阵;谱聚类;密度;测地距离

中图分类号：TP391   文献标志码：A

doi： 10.7535/hbgykj.2018yx02001

A spectral clustering algorithm based on

adaptive similarity matrix

WANG Beibei1， YANG Ming1， YAN Huichao1， SUN Xiaoxian2

（1.School of Science， North University of China， Taiyuan， Shanxi  030051， China;

2.Faculty of Science and Technology， Communication University of China， Beijing 100024， China）

Abstract：

In order to eliminate the fluctuation of the scale parameters in gaussian kernel function in constructing the similarity matrix of spectral clustering algorithm， a self-adaptive similarity matrix is constructed and applied in the spectral clustering algorithm. Geodesic distance measure is used in distance measure between data points in the adaptive similarity matrix. Distance between points closer to each other is approximately equal to the Euclidean distance， while for distance between two points farther away， each data's k-nearest neighbors are firstly obtained by Euclidean distance， then the geodesic distances of the nearest neighbors are accumulated， thus， the shortest distance between each pair of data can be get. The local density of two points is defined by the shared neighbor， reflecting the eigen structure of the data set better. Finally， experiments on both five artificial data sets and five UCI data sets show that the proposed method is more accurate than the others， and has a strong adaptive ability for complex distribution data. The research provides idea and method for data mining and machine learning.

Keywords：

applied mathematics; similar matrix; spectral clustering; density; geodesic distance

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

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

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

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

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

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

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

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

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

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

2 基于测地距离和密度的自适应谱聚类算法

2.1 测地距离

在构建相似度测度时，距离函数占着至关重要的地位，没有任何一种距离测度适合所有的数据集。传统的欧式距离做测度度量时，只是单纯的计算连接两点的直线段的长度，如图2 a），如若这两点间存在障碍物或者说存在另一个结构中的样本，此时的欧式距离是没有实际意义的，这就是欧氏距离的局限性，图2 b）是要得到的真实距离效果。越来越多的文献都在做距离测度方法的改进，文献[11]提出用有效距离函数代替传统的地理距离函数，刻画了目标样本和其他所有数据样本之间的距离信息，具有全局特性。文献[12]提出一种基于电阻距离的中文文本谱聚类算法，把文本表示成二分图形式，使用电阻值表示两点间的相似度值，电阻值随着节点间路径减小而减小，从而计算出任意节点间的有效电阻距离更具有实际意义。

测地距离是数学形态学中的一个重要概念，最早是TENENBAUM等[13]在研究非线性降维时提出的，能很好地表示流形结构上样本之间的真实距离。如图3中的点[WTBX]A，B，C位于同一流形结构上，[WTBX]dAB，dAC，dBC分[WTBX]别表示点A和点B，点A和点C，点B和点C之间的欧式距离，[WTBX]gAC，gBC[WTBX]分别表示点A和点C，点B和点C之间的测地距离，假设点A和点B之间存在障碍物不能直接计算欧式距离，在同一结构中，从点A到达点B的路径有很多条，最短的一条测地弧的长度称为点A和点B间的测地距离。由图3可以看出，当A，C两点非常近时，取[WTBX]gAC≈dAC，[WTBX]即认为A，C两点间的测地距离近似等于其欧氏距离。而当A，B两点之间相距较远时，则取两点间的测地距离等于其近邻点间的测地距离累加和，即[WTBX]gAB=gAC+gCB≈dAC+dCB，从而得到待聚类数据集中每对数据点之间的实际最短距离。

测地距离具体算法如下。

1）输入数据集X=[x1，x2，…，xi，…，xn]，根据欧式距离计算点xi的k个近邻。

2）初始化测地距离：

dG（xi，xj）=

d（xi，xj），点xj是点xi的k近邻之一，∞ ，其他，

其中d（xi，xj）表示的是点xi和点xj之间的欧氏距离。

3）计算任意两点间最短路径：

For m=1：n

dG（xi，xj）=min{dG（xi，xj），

dG（xi，xm）+dG（xm，xj）}

End

2.2密度

仅用距离来描述数据之间的相似性远远不够，特别是对密度分布不均的数据集，好的相似性度量不仅不依赖于尺度参数σ，而且能够根据每个点所处邻域的稠密程度得到正确的聚类结果。JARVIS等[14]曾提出一种基于共享近邻相似度测量方法的聚类，本研究借鉴其中的共享近邻的定义来表征两点间的局部密度，进而影响两点间的相似度。共享近邻的定义如下。

定义1数据集X={x1，x2，…，xn}中任意两点xi和xj的共享近邻定义为

SNN（xi，xj）=|n（xi）∩n（xj）|   ，

其中n（xi）表示离点xi距离最近的前p个点，n（xj）表示离点xj距离最近的前p个点。一般地，参数p=20，本研究取数据集中样本点数的5%。

2.3所提算法

谱聚类算法是依托谱图划分理论发展起来的，能在任意形状的样本空间上得到全局最优解。其主要核心是对特征向量的聚类，而特征向量是由样本数据的相似矩阵特征分解得到的，构建一个性能优越的相似矩阵至关重要。本研究构建了一种自适应的相似矩阵，首先选用测地距离函数表征数据间的距离度量，相距较近的两点间的距离近似于欧式度量，相距较远的两点间的距离则是通过最近邻点间的欧式度量叠加得到的，这样得到的距离度量克服了欧式距离的局限性，实际意义较明显。然后根据每个点所处邻域的稠密程度，用两点间的共享近邻数表征其密度，进而得到待聚类数据点的基于测地距离和共享近邻数的相似度，构建对应的相似矩阵，对其特征分解后得到的特征向量进行聚类。算法流程如下。

输入：待聚类数据集X={x1，x2，…，xn}，聚类个数k，共享近邻数p;

1）根据2.1节计算数据集X={x1，x2，…，xn}中数据点之间的测地距离dG（xi，xj）;

2）根据定义1计算任意两点xi和xj的前p个共同近邻数SNN（xi，xj）;

3）计算基于测地距离和共享近邻的数据点之间的相似度，构造相应的相似矩阵W=[wij]n×n，其中：

wij=exp（-d2G（xi，xj）σiσj（SNN（xi，xj）+1）），i≠j，1，i=j，

式中σi和σj分别表示点xi和xj到各自第l个近邻的欧式距离，参见文献[15]，建议l=7。

4）构建规范化Laplacian矩阵L=D-1/2WD-1/2，其中D=diag（d1， d2，…， di，…，dn），di=∑nj=1wij 。

5）计算矩阵L的前k个最大特征值及其对应的特征向量v1，v2，…，vk，可以得到特征矩阵V=[v1，v2，…，vk]∈Rn×k;

6）将矩阵V的行向量规范为单位向量，得到新矩阵为U，则uij=vij/（∑kv2ik）1/2;

7）将矩阵U的每一行对应回原数据集中的相应点，利用kmeans算法将其聚成k类C1，C2，…，Ck。

3实验与分析

为了验证本研究算法的性能，对比算法为k均值算法（kmeans）和基于规范化拉普拉斯矩阵的谱聚类算法（NJW），实验数据集为5个人工数据集和5个真实UCI数据集。

实验的操作平台为64位win7系统、CPU为Intel（R） Core（TM）i52450M（2.50 GHz）、4G内存的计算机和Matlab R2014a。

3.1评价指标

对聚类结果的评价是检验聚类算法结果好坏的重要环节，不同的评价标准会突出聚类算法不同的特性。本研究选取Rand指标[16]作为评价标准，即根据本研究算法得到的决策数的正确率来评价算法的性能。定义决策数的正确率如下：

RI=a+da+b+c+d。

假设待聚类数据集有n个样本，任意2个样本可组成一个样本对，则有n（n-1）/2个样本对，即有n（n-1）/2个决策数目。式中：a表示同一类的样本对被聚类到同一簇中;b表示不同类的样本对被聚类到同一簇中;c表示同一类的样本对被聚类到不同簇中;d表示不同类的样本对被聚类到不同类的簇中，即a+d表示聚类正确的决策数，a+b+c+d表示总决策数n（n-1）/2。可知RI ∈（0，1），当RI的值越大，则说明决策数的正确率越高。当RI=1时，则说明聚类算法的聚类结果完全正确。

3.2数据集及实验结果分析

3.2.1人工数据集

5个人工实验二维数据集的详细信息如下：

Twomoons数据集：由2个弧形结构构成，1 502个样本，2个类。

LineBlobs数据集：笑脸形，包含266个样本，3个类。

Spiral数据集：螺旋形，包含944个样本，2个类。

Sticks数据集：由4个线形结构构成，包含512个样本，4个类。

Threecircles数据集：由同心圆构成，包含299个样本，3个类。

实验结果在图4中给出，本研究所提算法在密度分布不均和非块状（弧形、圆圈形、线形等）数据集上都得到最优划分，证明了基于自适应相似度矩阵的谱聚类算法的强大聚类功能。而kmeans算法和NJW算法都或多或少的出现了不同程度的聚类错误。试验中NJW算法中σ的取值为数据点距离差值Δd的10%～20%时较理想[17]（Δd=maxi≠j Dij-mini≠j Dij，这里的D为欧式距离矩阵），统一取σ=0.1Δd。

3.2.2标准UCI数据集

5个真实实验数据集来自UCI数据库，分别是：

鸢尾花数据集——Iris Data Set，后文简称Iris;

葡萄酒数据集——Wine Data Set，后文简称Wine;

玻璃鉴定数据集——Glass Identification Data Set，后文简称Glass;

澳大利亚信贷审批数据集——Statlog （Australian Credit Approval） Data Set，后文简称Acd;

钞票验证数据集——Banknote Authentication Data Set，后文简称Bna。

数据特征如表1所示。

表2给出的是k-means、NJW和本研究算法的聚类准确率，在NJW算法中的最后一步会用到k-means算法划分，而在应用该算法时，不同的初始类中心会产生不同的聚类结果，为了降低此影响，本研究的k-means和NJW算法的取值都是程序运行20次的平均值。上节提到NJW算法中σ的取值为数据点距离差值的10%～20%較理想，不失一般性，取δ=0.1d和δ=0.2d两种情况下进行验证实验。

从表2给出的准确率的对比分析可知，在Wine数据集和Bna数据集上的聚类效果k-means算法优于NJW算法，在Iris数据集和Acd数据集上的聚类结果，不论NJW算法取哪个参数都要比k-means算法高，而在Glass数据集上，k-means算法的聚类结果则介于NJW算法的2个不同参数得到的聚类准确率之间，这表明对具有不同结构的数据集，不同算法都有其优缺点。而本研究所提算法在这5个实际数据集上的聚类准确率都是最高的，再一次证明了本研究算法的鲁棒性。

4结语

聚类结果对高斯核函数中尺度参数的选取极其敏感，距离函数在相似矩阵的构建中同样占据至关重要的地位，没有一种距离函数适合所有类型的数据集。本研究在充分分析数据聚类一致性特征的基础上，选用测地距离函数表征数据间的距离度量，同时引入共享近邻的定义来表征两点间的局部密度，进而构建了一种自适应的相似矩阵，更好地刻画数据集的本征结构，应用到谱聚类算法后，在密度分布不均以及非块状（弧形、圆圈形、线形等）的人工数据集上、通用国际UCI实际数据集上进行实验，表明了本文算法对复杂分布数据有很强的自适应能力，且准确率较高。下一步的研究重心将放在运行效率的提高以及在高维数据集上的准确性研究方面。

参考文献/References：

[1]杨英，李海萍，于向东，等.基于因子和聚类分析的中国各省市竞争力分析与研究[J].河北工业科技， 2013， 30（5）： 347-351.

YANG Ying，LI Haiping，YU Xiangdong，et al. Research of competitive power of provinces and cities in China based on factor analysis and cluster analysis[J]. Hebei Journal of Industrial Science and Technology， 2013， 30（5）： 347-351.

[2]LUXBURG U. A tutorial on spectral clustering[J]. Statistics and Computing， 2007，17（4）： 395-416.

[3]刘仲民， 李战明， 李博皓，等. 基于稀疏矩阵的谱聚类图像分割算法[J].吉林大学学报（工学版）， 2017， 47（4）：1308-1313.

LIU Zhongmin， LI Zhanming， LI Bohao，et al. Spectral clustering image segmentation algorithm based on sparse matrix[J]. Journal of Jilin University（Engineering and Technology Edition）， 2017， 47（4）：1308-1313.

[4]MIJANGOS V， SIERRA G， MONTES A. Sentence level matrix representation for document spectral clustering[J]. Pattern Recognition Letters， 2017， 85：29-34.

[5]RODRGUEZ-PULIDO F J， GORDILLO B， LOURDES GONZLEZ-MIRET M， et al. Analysis of food appearance properties by computer vision applying ellipsoids to colour data[J]. Computers & Electronics in Agriculture， 2013， 99（99）：108-115.

[6]孔万增， 孙昌思核， 张建海，等. 近邻自适应局部尺度的谱聚类算法[J]. 中国图象图形学报， 2012; 17（4）： 523-529.

KONG Wanzeng， SUNCHANG Sihe， ZHANG Jianhai，et al. Spectral clustering based on neighboring adaptive local scale[J]. Journal of Image and Graphics， 2012， 17（4）： 523-529.

[7]刘馨月， 李静伟， 于红，等. 基于共享近邻的自适应谱聚类[J]. 小型微型计算机系统， 2011， 32（9）： 1876-1880.

LIU Xinyue， LI Jingwei， YU Hong，et al. Adaptive spectral clustering based on shared nearest neighbors[J]. Journal of Chinese Mini-Micro Computer Systems， 2011， 32（9）： 1876-1880.

[8]張亚平， 杨明. 一种基于密度敏感的自适应谱聚类算法[J]. 数学的实践与认识， 2013， 43（20）： 150-156.

ZHANG Yaping， YANG Ming. A kind of density sensitive adaptive spectral clusting algorithm[J]. Mathematics in Practice and Theory， 2013， 43（20）： 150-156.

[9]INKAYA T. A parameter-free similarity graph for spectral clustering[J]. Expert Systems with Applications， 2015， 42（24）： 9489-9498.

[10]BEAUCHEMIN M. A density-based similarity matrix construction for spectral clustering[J]. Neurocomputing， 2015， 151（151）： 835-844.

[11]BROCKMANN D， HELBING D. The hidden geometry of complex， network-driven contagion phenomena[J]. Science， 2013， 342（6164）： 1337-1342.

[12]李方源. 基于电阻距离的中文文本谱聚类算法研究[D].广州：华南理工大学， 2013.

LI Fangyuan. Study of Spectral Clustering for Chinese Document Base on Resistance Distance[D]. Guangzhou： South China University of Technology， 2013.

[13]TENENBAUM J B， de SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science， 2000， 290（5500）： 2319-2323.

[14]JARVIS R A， PATRICK E A. Clustering using a similarity measure based on shared nearest neighbors[J]. IEEE Transactions on Computers， 1973， 22（11）： 1025-1034.

[15]ZELNIK-MANOR L， PERONA P. Self-tuning spectral clustering[J]. In Proceeding of NIPS， 2005， 1601-1608.

[16]YEH C C， YANG M S. Evaluation measures for cluster ensembles based on a fuzzy generalized Rand index[J]. Applied Soft Computing， 2017， 57：225-234.

[17]ERTZ L， STEINBACH M， KUMAR V. A new shared nearest neighbor clustering algorithm and its applications[C]// Workshop on Clustering High Dimensional Data and Its Applications， at Siam International Conference on Data Mining.[S.l.]：[s.n.]， 2002， 105-115.