＊)基金项目:国家863计划资助项目(2005AA147030)。

蔡晓妍　博士生,主要研究方向为智能信息处理、网络与信息安全;戴冠中　教授,博士生导师,主要研究领域为自动控制、信息安全;杨黎斌　博士生,研究方向为网络与信息安全、嵌入式系统。

计算机科学2008V ol .35№.7　谱聚类算法综述＊)蔡晓妍　戴冠中　杨黎斌(西北工业大学自动化学院　西安710072)摘　要　谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。

谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。

本文首先介绍了图论方法用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向。

关键词　谱聚类,谱图理论,图划分　Survey on Spectral C lustering AlgorithmsCA I Xiao -yan DA I Guan -zho ng YA N G Li -bin(C ollege of Autom ation ,Northw estern Polytechnical University ,Xi 'an 710072,China )A bstract Spectral clustering alg orithms a re new ly dev elo ping technique in recent year s .Unlike the traditional cluste -ring alg orithms ,these apply spect ral g raph theo ry to solve the clustering of no n -co nv ex sphere of sample spaces ,so that they can be conver ged to g lo bal o ptimal solution .In this paper ,the clustering principle based o n g raph theory is first in -troduced ,and then spectra l clustering alg orithms are catego rized acco rding to rules of g raph pa rtition ,and typical alg o -rithms are studied emphatically ,as well as their advantage s and disadvantage s are presented in de tail .F inally ,some v al -uable directions fo r fur ther research are pro po sed .Keywords Spec tral clustering ,Spectral g raph theo ry ,G raph par titio n 1　引言聚类分析是机器学习领域中的一个重要分支[1],是人们认识和探索事物之间内在联系的有效手段。

所谓聚类(clus -te ring )就是将数据对象分组成为多个类或簇(cluste r ),使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。

传统的聚类算法,如k -means 算法、EM 算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。

为了能在任意形状的样本空间上聚类,且收敛于全局最优解,学者们开始研究一类新型的聚类算法,称为谱聚类算法(Spec tral Clustering A lg o rithm )。

该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。

谱聚类算法最初用于计算机视觉[3]、V LSI 设计[4]等领域,最近才开始用于机器学习中[5],并迅速成为国际上机器学习领域的研究热点。

谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。

但由于其涉及的理论知识较多,应用也还处于初级阶段,因此国内这方面的研究报道非常少。

本文作为一篇综述性文章,旨在向读者介绍这种新型的聚类算法,使研究人员尽可能详细地总结该领域的研究现状。

后续篇幅安排如下:第2部分介绍了图论方法用于聚类的基本理论;第3部分根据图划分准则,将谱聚类算法分为两类,详细研究了各类中的代表性算法,并对算法进行了比较分析;最后对本文进行总结,提出了几个有价值的研究方向。

2　基本理论2.1　图划分准则谱聚类算法的思想来源于谱图划分理论[2]。

假定将每个数据样本看作图中的顶点V ,根据样本间的相似度将顶点间的边E 赋权重值W ,这样就得到一个基于样本相似度的无向加权图G =(V ,E )。

那么在图G 中,就可将聚类问题转化为在图G 上的图划分问题。

基于图论的最优划分准则就是使划分成的两个子图内部相似度最大,子图之间的相似度最小[5]。

划分准则的好坏直接影响到聚类结果的优劣。

常见的划分准则有M inimum cut ,A verag e cut ,No rmalized cut ,M in -max cut ,Ratio cut ,M N cut 等。

下面我们将分别介绍这几种准则。

2.1.1　最小割集准则[6](M inimum cut )谱图理论中,将图G 划分为A ,B 两个子图(其中A ∪B =V ,A ∩B = )的代价函数为:cut (A ,B )=∑u ∈A ,v ∈Bw (u ,v )(1)W u 和Leahy 提出最小化上述剪切值来划分图G ,这一划分准则被称为最小割集准则。

他们用这个准则对一些图像进行分割,并产生了较好的效果,同时他们也注意到,该准则容易出现歪斜(即偏向小区域)分割。

Shi 和M a lik 提出的规范割集准则及Hag en 和K ahng 提出的比例割集准则均可避免这种情况的发生。

2.1.2　规范割集准则[5](No rmalized cut )Shi 和M alik 在2000年根据谱图理论建立了2-way 划分的规范割目标函数(N cut ):N cut (A ,B )=cut (A ,B )assoc (A ,V )+cut (A ,B )assoc (B ,V )其中assoc (A ,V )=∑u ∈A ,t ∈Vw (u ,t )(2)最小化N cut 函数被称为规范割集准则。

该准则不仅能够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。

Shi 和M alik 同时还提出了规范关联目标函数(N asso c ):N assoc (A ,B )=assoc (A ,A )assoc (A ,V )+assoc (B ,B )assoc (B ,V )(3)assoc (A ,A )与assoc (B ,B )分别是子图A ,B 内所有顶点之间的连接权值之和。

这一无偏函数进一步反映了类内样本间互相连接的紧密程度。

同时,可以看出N cut 函数与N as -soc 函数是相关的,它们满足关系:N cut (A ,B )=2-N assoc (A ,B )。

因此,最小化N cut 函数等价于最大化Nassoc 函数,但通常情况下都是通过最小化N cut 函数获取图的最优划分。

2.1.3　比例割集准则[7](Ratio cut )Hag en 和K ahng 提出了比例割目标函数(Rcut ):Rcut =cut (A ,B )min ( A , B )(4)其中 A , B 分别表示子图A ,B 中顶点的个数。

最小化Rcut 函数只考虑了类间相似性最小,减小了过分割的可能性,但运行速度较慢。

2.1.4　平均割集准则[8](Av erag e cut )平均割目标函数为:Av cut (A ,B )=cut (A ,B ) A +cut (A ,B )B(5)可以看出A vcut 和N cut 函数都表示无向图G 中边界损失与分割区域相关性的比值之和,因此最小化A vcut 与N cut 目标函数都能产生较准确的划分。

其共同缺点是倾向于欠分割且易分割出只包含几个顶点的较小子图。

文献[5]通过实验发现,当把No rmalized cut 和A verag e cut 准则分别用于同一图像的分割问题时,No rmalized cut 准则能够产生更好的划分结果。

2.1.5　最小最大割集准则[9](M in -max cut )最小最大割集准则要求最小化cut (A ,B )的同时,最大化assoc (A ,A )与assoc (B ,B )。

该准则可通过最小化下面的目标函数得以实现:Mcut =cut (A ,B )assoc (A ,A )+cut (A ,B )assoc (B ,B )(6)我们将这个目标函数称为最小最大割函数,或简称为M cut 函数。

最小化该函数可避免分割出仅包含几个顶点的较小子图,因此它倾向于产生平衡割集,但实现速度较慢。

M cut 与N cut 一样满足类间样本间的相似度小而类内样本间的相似度大的原则,与N cut 具有相似的行为,但当类间重叠较大时,M cut 比N cut 更加高效。

2.1.6　多路规范割集准则[10](M ultiw ay N o rmalized cut )上述五种划分准则所使用的目标函数都是将图G 划分为2个子图的2-w ay 划分函数,M eila 提出一种可以将图G 同时划分为k 个子图的k -w ay 规范割目标函数:MN cut =cut (A 1,V -A 1)assoc (A 1,V )+cut (A 2,V -A 2)assoc (A 2,V )+…+cut (A k ,V -A k )assoc (A k ,V )(7)M elia 指出Ncut 和M Ncut 的差异之处仅在于所使用的谱映射不同,并且当k =2时,M N cut 与N cut 等价。

多路规范割集准则在实际应用中合理有效,但其优化问题通常难以解决。

2.2　相似矩阵、度矩阵及Laplacian 矩阵由于图划分问题的本质,求图划分准则的最优解是一个N P 难问题。

一个很好的求解方法是考虑问题的连续放松形式,这样便可将原问题转换成求解相似矩阵或Laplacian 矩阵的谱分解,因此将这类方法统称为谱聚类,可以认为谱聚类是对图划分准则的逼近[11]。