一种基于密度均值的谱聚类算法

李　根，王亚刚，周小伟，张凤登

(上海理工大学 光电信息与计算机工程学院，上海 200093)



一种基于密度均值的谱聚类算法

李根，王亚刚，周小伟，张凤登

(上海理工大学 光电信息与计算机工程学院，上海 200093)

传统谱聚类算法在构造相似度矩阵时，高斯核函数参数选取的无规律性会对聚类结果造成严重影响。针对的这一缺陷，提出一种基于密度均值的谱聚类算法。与传统算法不同，该算法选取样本点到周围K个样本点的平均距离作为尺度参数，并引入样本点的密度信息，使得聚类结果更符合实际样本的分布。同时，由于相似矩阵能自适应不同的局部密度，使得该算法对样本的空间分布并不敏感。在不同类型数据集上的实验验证了算法的有效性和较高的鲁棒性。

谱聚类；平均密度；相似矩阵；多尺度

谱聚类是一种多尺度算法。近年来该算法在语音识别、图像分割[1]和文本检索中应用广泛，尤其是在大数据的分类上越发引起人们的重视。建立在谱图理论上的谱聚类算法具有将非线性不可分的样本点空间转化为凸样本分布的能力，相比于传统的聚类算法(如K-means)，其能在任意形状的样本空间上聚类且收敛于全局最优解[2]。

谱聚类算法具有比其他聚类算法更优越的数据聚类性能，但由于其本身在构造相似度矩阵时对尺度参数(核函数的宽度参数，控制了函数的径向作用范围)比较敏感，在处理多重尺度数据集时也存在结果不理想等问题。针对这一突出缺点，Zelnik-Manor和Perona提出的自调整谱聚类算法[3]，利用局部密度信息来给推导出局部尺度参数，从而形成了基于多尺度参数的相似度矩阵，相比统一尺度参数更能反映真实数据点之间的关系。实验表明，该算法可准确分离出稀疏簇内部包含的紧密簇，更加准确地反映了数据点间的内在联系。但算法对数据点的位置分布没有做全面的考虑, 仍存在不足之处。王玲[4]等人为了实现数据的全局一致性，提出了一种密度可调节的相似性度量矩阵，通过最短路径算法对较高密度区域上的相似性进行改进，形成了完全不同于高斯核的另一种相似性度量方式。

本文在文献[5]的基础上进行了改进, 提出一种基于密度均值的具有自适应性的谱聚类算法。算法将样本点与相邻K个样本点的距离平均值视为核函数尺度参数σ，自适应地调整各个样本之间的相似度,并引入邻域密度信息，充分挖掘出了各样本点内在联系，同时也避免了聚类结果对人为给定参数的影响。仿真结果表明，本文所提算法在处理簇密度相差较大的多重尺度数据集时具有良好的簇类效果，提高了聚类性能和质量，且有一定的自适应性和鲁棒性。

1　谱聚类

1.1谱聚类原理

谱聚类算法来源于谱图的划分。其的核心思想是将样本点聚类的问题转化为一个无向图的多路划分的问题。样本数据点被看成是无向G(V,E)，将其顶点视为集合V，带权值的加权边集合E={Sij}表示基于某一相似性度量，基于此计算的两点间的相似度，用W表示待聚类数据点之间的相似度矩阵。在图G中就把聚类问题转化为在图G上最优图划分的问题，即将图G(V,E)划分为k个互不相交的子图V1,V2,…,Vk，划分后保证每个子集Vi内的相似度程度较高，不同集合Vi和Vj之间的相似度程度较低[6]。

在谱聚类算法中，常用3种反映相似度的连接图：ε邻近连接图、k最近临阶连接图和全连接图。多数文献中均采用全连接图。令sij表示xi和xj两点之间的连接权值，以高斯核函数来定义两个顶点之间的权值，其中参数σ称为尺度参数。sij定义为

(1)

对于最优图谱的划分，一个切实有效的求解方法就是将原有问题转化为求解拉普拉斯矩阵的特征值和对应的特征向量的问题。利用这些特征向量构造出一个简化的数据空间，在该空间中的数据分布结构会更加明显，并与原数据空间分部信息保持一致[7]。

1.2传统谱聚类算法

传统的谱聚类算法有众多，其中最具代表性算法是Ng等人提出的NJW算法。NJW算法本质是是利用相似矩阵的特征向量进行聚类。选取全的谱图划分构造相似矩阵，并求取其对应的拉普拉斯矩阵，然后求出拉普拉斯前K个最大特征值对应的特征向量，这样在K维空间中形成与源数据一一对应的映射，最后利用传统的K-means或其他算法聚类，从而得到聚类结果。NJW算法步骤如下。

输入 数据集经X={x1,x2,…,xn}和聚类数目k。

输出k个聚类结果Y1,Y2,…,Yk。

(1)根据高斯核函数构造相似矩阵W;

(3)计算L的前k个最大特征向量u1,u2,…,uk，单位化得到矩阵V;

(4)通过K-means或其他经典聚类算法对V向量进行聚类，得到聚类结果{Y1,Y2,…,Yk}。

尽管NJW算法能将非凸数据空间转化为线性可分的凸数据空间，但在使用高斯核函数构造相似矩阵W时，聚类结果由于受尺度参数σ的影响，使得其结果具有不确定性。当处理多重尺度数据集时，这种不确定性变得更加严重。一个有效的解决方法就是取多组尺度参数，重复多次聚类，最后得到最优解，但这将导致计算机的开销过大。图1显示了同一数据集在选取不同尺度参数时的聚类效果，可看出尺度参数的不同对聚类结果产生的影响。因此，只有选取特定的参数时(在本实验中取0.6或者0.8)，才能得到满意的聚类结果。

图1　不同尺度参数下的聚类结果

2　基于密度平均值的谱聚类算法

2.1算法提出

由于标准的谱聚类算法使用的是全局尺度参数，并未考虑到样本点邻域数据分布对聚类结果产生的影响，当数据集具有多重尺度，密集簇和稀疏簇相互交错时，传统的谱聚类算法就无法得到较好的结果。

图2　多重尺度数据集1

图2显示的是一个多重尺度数据集，其是由两个半圆月亮形组成的密集簇和夹在之间的稀疏簇组成，其中样本点A和B是位于上半弧形数据簇中，C是位于下半弧形数据簇中。在此假设AB和AC的距离相等即d(AB)=d(AC),由于传统谱聚类算法是利用空间欧式距离来表征样本点之间的相似度，由假设即可得出W(A,B)=W(A,C),即AB之间的相似度和AC之间的相似度相等，但客观情况是由于AB位于同一个密集数据簇，其间的相似度应该大于位于不同密度的AC之间的相似度。显然传统谱聚类算法不能较好地处理这类数据集的聚类。

为解决这种由于使用全局参数带来的无法将密集和稀疏数据集带来的问题，学者提出了Self-Tuning(STSC)算法。该算法将每个样本点邻域信息引入到相似矩阵的计算中，由此定义了可随样本点改变的自适应参数，得到了这种情况下的相似度函数

(2)

其中，σi=d(si,sk)，表示样本点si到其第k个最近样本点的欧氏距离。同样对于图2，由于引入了邻域的信息值，有σB>σC，使得σAσB>σAσC，继而有W(A,B)>W(A,C)，这样在同一密集区的样本点更容易被聚集在一起，稀疏区的样本点划分为另一类。

虽然STSC能自动的对位于不同区域的样本点间的相似度进行微调，但其仍有不足之处。

图3　多重尺度数据集2

如图3所示，样本点A位于稀疏区，样本点B,C位于密集区，由STSC的理论却依旧只能得到σB=σC，σAσB=σAσC，A,B和A,C之间的相似度W(A,B)=W(A,C)，这样还是无法获得正确的聚类结果。原因是样本点所在邻域的密度对数据之间的相似性有着严重的影响，两个样本点所在区域的密度相近时，其被划分在一个类的概率越大，密度相差越远时，其被划分在不同类的概率也就越大。

尺度针对这两种算法的不足，在尺度自调整的思想上，提出基于密度均值的谱聚类算法(ADSC)。其基本思想是：在对具有多重尺度的数据聚类问题上，单一用欧氏距离来表征样本点间的相似性无法全面的反映实际样本点的相互联系。在对STSC算法改进的基础上，将待聚类眼样本点的密度值也引入相似度的计算过程中，用密度权值和距离权值综合在一个相似矩阵中。通过数据点的欧式距离大小和密度信息来不断调整相似度的值，这样更加符合实际数据的相互关系。

2.2ADSC算法实现

基于上述分析，本文在文献[3]和文献[5]的基础上重新定义了相似度函数表达式

(3)

输入 数据集X={x1,x2,…,xn}和聚类目k。

输出k个聚类结果{Y1,Y2,…,Yk}。

(4)通过K-means或其他经典聚类算法对V向量进行聚类，得到聚类结果{Y1,Y2,…,Yk}。

选取L前k个最大的特征值和其所对应的特征向量的原因在于：可证明若空间上存在k个严格彼此分离的有限数据簇，矩阵L的前k个最大特征值全为1，第k+1个最大特征值严格小于1，且这两个特征值之间的差值越大，反映出相同类间样本分布越密集，不同类间分布越稀疏[8]。图4显示的是对于文章前面提到的STSC算法不能很好地产生聚类结果，但用ADSC算法就可以准确地被聚合成两个密集类和一个稀疏类，显然更加符合实际。

图4　ADSC在数据集2上的聚类结果

图5显示了在3维空间内运用ADSC算法的实现过程，图5(a)表示原始数据集，在空间中程花瓣状[9]，各坐标值表示实际属性值(下同)；图5(b)表示带有邻域距离和密度信息的相似图；图5(c)表示该数据集在ADSC聚类结果；图5(d)表示Silhoutette聚类性能评价指标[10](幅值越接近1表示与聚类结果原数据集接近程度更高)。

图5　基于密度平均算法的实现过程

3　实验结果

为验证本文所提出算法的有效性和优越性，本文分别在人工数据集和真实数据集上对传统NJW谱聚类算法、共享邻域自适应谱聚类算法(STSC)和基于密度均值的谱聚类算法(ADSC)的聚类结果进行对比实验。

3.1人工数据集

图6给出了一个由两条螺旋线构成的数据集。图6(a)为原始数据集，是由1 000个样本点，2个属性值构成；图6(b)是传统NJW聚类方法聚类出来的结果，算法中高斯核参数σ取0.8，由于参数选取的不确定性导致了结果的不唯一；图6(c)是在具有自动尺度调整的STSC聚类方法下的结果(邻域样本数k=7)，虽然大部分样本点均有效地划分在同一属性的区域，但由于相似矩阵中没有邻域的密度信息，仍有部分的样本点被错误的划分在其他类中。

图6　3种聚类方法结果对比

3.2真实数据集

为近一步验证本文所提出算法的聚类性能，选取UCI数据集上的Cancer、Diabetes、Ionospher、Iris数据集作为测试样本数据。表1给出了真实数据集的样本个数、类的个数和属性的个数。

表1　4类真实数据集特征

表4给出了表列出的4种真实数据集在3种算法(NJW,STSC,ADSC)下的性能指标。聚类性能采用误差率来表示，误差率越小，表示聚类的效果越好。可看出本文提出的基于密度均值的聚类算法有着更好的聚类效果。

表2　不同聚类算法下的误差率

4　结束语

本文在文献的基础上，结合STSC聚类算法，提出了一种基于平均密度的聚类算法ADSC。将数据集邻域密度的信息融合到了相似度矩阵的计算中，通过欧氏空间距离和平均密度来调整每个样本点同其他样本点之间的相似度。在人工数据集和UCI真实数据集上同其他算法作了比较，结果表明该算法在聚类效果上有着明显的提高。但算法在高维数据聚类的过程中，占用计算机资源较大，运算时间较长，下一步将就这一缺陷做进一步的研究。

[1]Agrawal D P,Zeng Q A. Introduction to wireless and mobile systems[M].Canada:Thomson Learning,2002.

[2]Von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing,2007,17(4):395-416.

[3]Zelnik Manor L,Perona P.Self-tuning spectral clustering[J].Advances in Neural Information Processing Systems,2004,17(6):1601-1608.

[4]王玲,薄列峰,焦李成.密度敏感的半监督谱聚类[J].软件学报,2007,18(10):2412-2422.

[5]王雅琳,陈斌,王晓丽,等.基于密度调整的改进自适应谱聚类算法[J].控制与决策,2014,29(9):1681-1687.

[6]Malik J,Belongie S,Leung T,et al. Contour and texture analysis for image segmentation[J].International Journal of Computer Vision,2001,43(1):7-27.

[7]Ng A Y,Jordan M L,Weiss Y. On spectral clustering: analysis and an algorithm[C].Cambridge: Advances in Neural Information Processing Systems, MIT Press,2002.

[8]田铮,李小斌,句彦伟.谱聚类的扰动分析[J].中国科学E辑:信息科学,2007,37(4):527-543.

[9]Hamidian A,Nilsson A.Performance of internet access solutions in mobile ad networks[J].Lecture Notes in Computer Science(LNCS),2004(3427):189-201.

[10] 蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学,2008,35(7):14-18.

A Spectral Clustering Algorithm Based on Average Density

LI Gen, WANG Yagang, ZHOU Xiaowei, ZHANG Fengdeng

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

Choosing the scale parameter of gauss kernel function irregularly has a serious effect on clustering results when using traditional spectral clustering algorithm to construct similarity matrix. A spectral clustering algorithm based on average density is proposed, which usesKaverage neighbourhood distance as the scale parameter and introduces the local data density information, making clustering results in conformity with the practical data distribution. The adaptation of the similarity matrix to different local densities also makes the algorithm relatively insensitive to the spatial distribution of datasets. Experimental results on both different datasets show the effectiveness and good robustness of this proposed algorithm.

spectral clustering; average density; similarity matrix; multiple scales

10.16180/j.cnki.issn1007-7820.2016.08.022

2015-11-22

上海市自然科学基金资助项目(15ZR1429300)

李根(1990-)，男，硕士研究生。研究方向：嵌入式控制等。

TP301.6

A

1007-7820(2016)08-074-05