计算机科学2008Vol.35№.7
谱聚类算法综述*)
蔡晓妍 戴冠中 杨黎斌
(西北工业大学自动化学院 西安710072)
摘 要 谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。本文首先介绍了图论方法
用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向。关键词 谱聚类,谱图理论,图划分
SurveyonSpectralClusteringAlgorithms
CAIXiao-yan DAIGuan-zhong YANGLi-bin
(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi'an710072,China)
Abstract Spectralclusteringalgorithmsarenewlydevelopingtechniqueinrecentyears.Unlikethetraditionalcluste-ringalgorithms,theseapplyspectralgraphtheorytosolvetheclusteringofnon-convexsphereofsamplespaces,sothattheycanbeconvergedtoglobaloptimalsolution.Inthispaper,theclusteringprinciplebasedongraphtheoryisfirstin-troduced,andthenspectralclusteringalgorithmsarecategorizedaccordingtorulesofgraphpartition,andtypicalalgo-rithmsarestudiedemphatically,aswellastheiradvantagesanddisadvantagesarepresentedindetail.Finally,someval-uabledirectionsforfurtherresearchareproposed.
Keywords Spectralclustering,Spectralgraphtheory,Graphpartition
类,详细研究了各类中的代表性算法,并对算法进行了比较分
析;最后对本文进行总结,提出了几个有价值的研究方向。
1 引言
聚类分析是机器学习领域中的一个重要分支[1],是人们
认识和探索事物之间内在联系的有效手段。所谓聚类(clus-tering)就是将数据对象分组成为多个类或簇(cluster),使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。传统的聚类算法,如k-means算法、EM算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。
为了能在任意形状的样本空间上聚类,且收敛于全局最优解,学者们开始研究一类新型的聚类算法,称为谱聚类算法(SpectralClusteringAlgorithm)。该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉[3]、VLSI设计[4]等领域,最近才开始用于机器学习中[5],并迅速成为国际上机器学习领域的研究热点。
谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。但由于其涉及的理论知识较多,应用也还处于初级阶段,因此国内这方面的研究报道非常少。本文作为一篇综述性文章,旨在向读者介绍这种新型的聚类算法,使研究人员尽可能详细地总结该领域的研究现状。后续篇幅安排如下:第2部分介绍了图论方法用于聚类的基本理论;第3部分根据图划分准则,将谱聚类算法分为两
2 基本理论
2.1 图划分准则
谱聚类算法的思想来源于谱图划分理论[2]。假定将每个数据样本看作图中的顶点V,根据样本间的相似度将顶点间的边E赋权重值W,这样就得到一个基于样本相似度的无向加权图G=(V,E)。那么在图G中,就可将聚类问题转化为在图G上的图划分问题。基于图论的最优划分准则就是使划分成的两个子图内部相似度最大,子图之间的相似度最小[5]。划分准则的好坏直接影响到聚类结果的优劣。常见的划分准则有Minimumcut,Averagecut,Normalizedcut,Min-maxcut,Ratiocut,MNcut等。下面我们将分别介绍这几种准则。2.1.1 最小割集准则[6](Minimumcut)
谱图理论中,将图G划分为A,B两个子图(其中A∪B=V,A∩B= )的代价函数为:
cut(A,B)=
u∈A,v∈B
∑w(u,v)(1)
Wu和Leahy提出最小化上述剪切值来划分图G,这一划分准则被称为最小割集准则。他们用这个准则对一些图像进行分割,并产生了较好的效果,同时他们也注意到,该准则容易出现歪斜(即偏向小区域)分割。Shi和Malik提出的规范割集准则及Hagen和Kahng提出的比例割集准则均可避免这种情况的发生。
*)基金项目:国家863计划资助项目(2005AA147030)。蔡晓妍 博士生,主要研究方向为智能信息处理、网络与信息安全;戴冠中 教授,博士生导师,主要研究领域为自动控制、信息安全;杨黎斌 博士生,研究方向为网络与信息安全、嵌入式系统。
2.1.2 规范割集准则[5](Normalizedcut)
Shi和Malik在2000年根据谱图理论建立了2-way划分的规范割目标函数(Ncut):+
assoc(A,V)assoc(B,V)
其中assoc(A,V)=∑w(u,t)
Ncut(A,B)=
u∈A,t∈V
Melia指出Ncut和MNcut的差异之处仅在于所使用的
谱映射不同,并且当k=2时,MNcut与Ncut等价。多路规范割集准则在实际应用中合理有效,但其优化问题通常难以解决。
2.2 相似矩阵、度矩阵及Laplacian矩阵
由于图划分问题的本质,求图划分准则的最优解是一个NP难问题。一个很好的求解方法是考虑问题的连续放松形式,这样便可将原问题转换成求解相似矩阵或Laplacian矩阵的谱分解,因此将这类方法统称为谱聚类,可以认为谱聚类是对图划分准则的逼近[11]。
相似矩阵通常用W或A表示,有时也称为亲合矩阵(Af-finityMatrix)。该矩阵的定义为:
d(si,sj)
Wij=exp(-2
2σ
(2)
最小化Ncut函数被称为规范割集准则。该准则不仅能
够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。
Shi和Malik同时还提出了规范关联目标函数(Nassoc):
assoc(A,A)assoc(B,B)
Nassoc(A,B)=+(3)
assoc(A,V)assoc(B,V)assoc(A,A)与assoc(B,B)分别是子图A,B内所有顶点
之间的连接权值之和。这一无偏函数进一步反映了类内样本间互相连接的紧密程度。同时,可以看出Ncut函数与Nas-soc函数是相关的,它们满足关系:Ncut(A,B)=2-Nassoc(A,B)。因此,最小化Ncut函数等价于最大化Nassoc函数,但通常情况下都是通过最小化Ncut函数获取图的最优划分。2.1.3 比例割集准则[7](Ratiocut)
Hagen和Kahng提出了比例割目标函数(Rcut):Rcut=(4)
min( A , B )
其中 A , B 分别表示子图A,B中顶点的个数。最小化Rcut函数只考虑了类间相似性最小,减小了过分割的可能性,但运行速度较慢。2.1.4 平均割集准则[8](Averagecut)
平均割目标函数为:
Avcut(A,B)=(5)
A B
可以看出Avcut和Ncut函数都表示无向图G中边界损失与分割区域相关性的比值之和,因此最小化Avcut与Ncut目标函数都能产生较准确的划分。其共同缺点是倾向于欠分割且易分割出只包含几个顶点的较小子图。文献[5]通过实验发现,当把Normalizedcut和Averagecut准则分别用于同一图像的分割问题时,Normalizedcut准则能够产生更好的划分结果。2.1.5 最小最大割集准则[9](Min-maxcut)
最小最大割集准则要求最小化cut(A,B)的同时,最大化assoc(A,A)与assoc(B,B)。该准则可通过最小化下面的目标函数得以实现:
cut(A,B)cut(A,B)
Mcut=+(6)
assoc(A,A)assoc(B,B)我们将这个目标函数称为最小最大割函数,或简称为
Mcut函数。最小化该函数可避免分割出仅包含几个顶点的较小子图,因此它倾向于产生平衡割集,但实现速度较慢。Mcut与Ncut一样满足类间样本间的相似度小而类内样本间的相似度大的原则,与Ncut具有相似的行为,但当类间重叠较大时,Mcut比Ncut更加高效。2.1.6 多路规范割集准则[10](MultiwayNormalizedcut)
上述五种划分准则所使用的目标函数都是将图G划分为2个子图的2-way划分函数,Meila提出一种可以将图G同时划分为k个子图的k-way规范割目标函数:
cut(A1,V-A1)cut(A2,V-A2)
MNcut=++…+
assoc(A1,V)assoc(A2,V)cut(A,V-A)
(7)
assoc(Ak,V)
(8)
2
其中si表示每个数据样本点,d(si,sj)一般取 si-sj ,σ为事先指定的参数。
将相似矩阵的每行元素相加,即得到该顶点的度,以所有
度值为对角元素构成的对角矩阵即为度矩阵,度矩阵常用D表示。
Laplacian矩阵分为非规范Laplacian矩阵和规范Lapla-cian矩阵。非规范Laplacian矩阵表示为L=D-W,规范Laplacian矩阵有两种形式,分别是:
Lsym=D-2LD2=I-D-2WDLrw=D-1L=I-D-1W2.3 势函数、Fiedler向量及谱
1
1
1
1
2
(9)
势函数为表示某样本划分归属的指示向量(indicator
vector),其定义为:
qi10
若i∈A若i∈B
(10)
若最终势函数中某样本对应的值为1,则该样本属于集
合A,若为0则属于集合B。但实际划分求解得到的结果qi常为0到1之间的实数值,此时可用k均值聚类等方法进一步决定样本的归属。
许多谱聚类算法都将图划分问题转化为求解Laplacian矩阵的第二小特征向量问题。这里的第二小特征向量就是第二个最小特征值对应的特征向量,它代表了最佳图划分的一个解(即势函数),把这一特征向量称为Fiedler向量。与特征向量(不一定是Fiedler向量)对应的特征值称为谱。
3 谱聚类算法
根据不同的准则函数及谱映射方法,谱聚类算法发展了很多不同的具体实现方法,但是都可以归纳为下面三个主要步骤[12]:
Step1 构建表示样本集的矩阵Z;
Step2 通过计算Z的前k个特征值与特征向量,构建特征向量空间;
Step3 利用k-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。
上述步骤是谱聚类算法的一个框架,在具体实现过程中,不同的算法在数据集矩阵Z的表示上存在着不同。例如根据2-waycut的目标函数,Z=W;根据随机游动关系,则Z=D-1W等。划分准则一般分为2-way和k-way,本文根据所使用的划分准则,将算法分为迭代谱和多路谱两类,并分别讨论了各类中典型的谱聚类算法。
·
3.1 迭代谱聚类算法3.1.1 PF算法[13]
Perona和Freeman提出用相似矩阵W的第一个特征向x1进行聚类(本文中第一个特征向量指的是相应矩阵中最大特征值λ。他们指出对于块对角相似矩1所对应的特征向量)阵,特征向量x1中非零元素对应的点属于同一类,零元素对应的点属于另外一类。PF算法作为最简单的谱聚类算法引起了学术界的广泛关注,在理论研究和应用方面都有很多论文发表。
3.1.2 SM算法[5]
SM算法由美国学者Shi和Malik在2000年提出。他们指出在约束xTWe=xTDe=0条件下,
minNcut(A,B)=min
xTDx
T
Weiss提出了一种将SLH算法和SM算法相结合的新型谱聚类算法[4]。该算法将SLH算法中的原始相似矩阵W用规范相似矩阵N代替。实验表明,此算法能够更加快速地产生正确的聚类结果。3.1.4 KVV算法[15]
KVV算法与SM算法十分相似,不同之处仅在于SM算法是寻找使Ncut(A,B)值最小的划分点,而KVV算法则是寻找使Rcut(A,B)值最小的划分点。KVV算法减少了过分割的可能性,但算法的运行速度相对较慢。3.1.5 Mcut算法[16]
Ding根据谱图理论,将(6)式重新写为:
TTx(D-W)xy(D-W)y
Mcut=+TT
xWxyWy
对于2-way划分,令q为划分指示向量,则:
ai∈A
-bi∈B最小化式(15)可得qiminMcut(A,B)=min
q
q
(15)
(11)
将x松弛到连续域[-1,1],求解minNcut(A,B)的问题
就可以转化为下式:
argmin
xT(D-W)x
T
TxDxxD1=0
(12)
(16)
根据Rayleigh商原理,式(12)的优化问题等于求解下列
等式的第二小特征值问题:
(D-W)x=λDx(13)与第二小特征值对应的特征向量(即Fiedler向量)就包含了图的划分信息。SM算法描述如下:
Step1 通过样本集建立无向加权图G,根据图G构造矩阵W和D;
Step2 计算式(13)第二小特征值及对应的Fiedler向量;
Step3 根据启发式规则在Fiedler向量中寻找划分点i,使在该点上得到的Ncut(A,B)值最小。将Fiedler向量中大于等于该值的点归为一类,小于该值的点归为另一类。
定义规范相似矩阵为:
N=D
-2
JN(A,B)
minJN(A,B)
1-JNq
TJN(A,B)≡JN(q)=(17)
qTDq
在约束xTe=0条件下,将x松弛到连续域[-1,1],根据Rayleigh商原理,(17)式的优化问题等于求解下式的第二小特征值问题:
(D-W)xx(18)
1+λ
因此,将图G划分为两个子图的Mcut算法可以简单描述如下:
Step1 计算(18)式的Fiedler向量。
Step2 在Fiedler向量中,寻找使Mcut值最小的划分点。
Step3 用基于连接的聚类算法进行优化。
Kannan将该算法与SM算法、KVV算法进行了比较,发现Mcut算法能够产生更加平衡的划分结果,尤其当类间重叠较大时,效果更为明显。3.2 多路谱聚类算法
大部分谱聚类算法都是利用2-way划分准则迭代地对样本数据进行聚类。但是近几年研究发现,若使用更多的特征向量并且直接计算k路分割将会得到更好的聚类效果[17,18]。3.2.1 NJW算法[19]
Ng,Jordan等人选取拉氏矩阵Lsym的前k个最大特征值对应的特征向量,使其在Rk空间中构成与原数据一一对应的表述,然后在Rk空间中进行聚类。NJW算法描述如下:Step1 计算矩阵Lsym的前k个最大特征值所对应的特征向量x1,…,xk(必要时需作正交化处理),构造矩阵X=[x1,…,xk]∈Rn×k;
Step2 将矩阵X的行向量转变为单位向量,得到矩阵
Xij
Y,即Yij=
X2ij
j
WD
2
即 N(i,j)=
W(i,j)
(14)
D(i,i)(j,j)
根据正规化定理[4],可以得出矩阵W的Fiedler向量等
于矩阵N的次大与最大特征向量之间的分量方式比值。因此,SM算法与PF算法的不同之处在于:①SM算法用的是规范相似矩阵,而PF算法仅用相似矩阵;②SM算法用的是前两个特征向量,而PF算法只用了第一个特征向量。
Shi和Malik同时还提出将minAvcut的离散形式松弛为连续形式进行聚类。但实验表明,SM算法得出的聚类效果要明显好于用PF算法及最小化Avcut标准得到的聚类效果。3.1.3 SLH算法[14]
SLH重定位算法将相似矩阵W和数字k作为输入,并通过下面的步骤输出一个新的矩阵Q:
Step1 求矩阵W的前k个特征向量x1,…,xk,构造矩阵X=[x1,…,xk]∈Rn×k;
Step2 将矩阵X的行向量规范化为单位长度并构造新矩阵Q=XXT;
Step3 根据Q中的元素聚类相应的点。理想情况下,Q(i,j)=1表示i,j两点属于同一类,Q(i,j)=0表示i,j两点属于不同类。一般情况下,属于同一类的点对应的Q(i,j)值均接近1,属于不同类的点对应的Q(i,j)值接近0。
Step3 将矩阵Y的每一行看作是Rk空间中的一个点,对其使用k均值算法或任意其它经典算法,得到k个聚类;
Step4 将数据点yi划分到聚类j中,当且仅当Y的第i行被划分到聚类j中。
选取矩阵Lsym的前k个最大特征值所对应特征向量的原因在于:对于存在k个理想的彼此分离簇的有限数据集,可以
证明矩阵Lsym的前k个最大特征值为1,第k+1个特征值则严格小于1,二者之间的差距取决于这k个聚类的分布情况[19]。当聚类内部分布得越密,各聚类间分布得越开时,第k+1个特征值就越小,此时,以Y矩阵中的每行作为k维空间中的一个点所形成的k个聚类,它们将彼此正交地分布于k维空间中的单位球上,并且在单位球上形成的这k个聚类对应着原空间中所有点形成的k个聚类。3.2.2 MS算法[20]
Meila将相似性解释为Markov链中的随机游动,分析了这种随机游动的概率转移矩阵P=D-1W的特征向量,并根
据随机游动对MNcut进行了概率解释。在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类算法。算法步骤与NJW算法相似,但该算法是用随机游动矩阵P的前k个特征向量构造矩阵X,并直接将矩阵X中的各行看成Rk空间中的各点进行聚类。MS算法在实际应用中取得了一定的效果,但当度矩阵D中各对角线元素差别较大时,聚类效果较差[19]。
以上对典型的谱聚类算法进行了概述,表1为这些算法的一个简单比较。
表1 典型谱聚类算法的比较
算法PF算法SM算法SLH算法Mcut算法NJW算法MS算法
目标函数cut(A,B)Ncut(A,B)
———Mcut(A,B)
———MNcut
所用方程Wx=λx(D-W)x=λDx
Wx=λxλ
(D-W)x=x
1+λ
D选取的特征向量最大特征向量Fiedler向量前k个特征向量Fiedler向量前k个特征向量前k个特征向量
特点
易产生仅包含几个顶点的较小簇当类间重叠较大时易出现歪斜分割
速度较慢能够产生更加平衡的划分结果,但后置处理需要花费大量时间
需要进行正交初始化当度矩阵D中各对角线元素差别较大时,聚类效果较差
WD
-x=λx
D-1Wx=λx
4 当前的几个热点研究问题
尽管谱聚类相对于其它聚类方法具有许多优势,并在实
践中也取得了很好的效果,但它仍有许多亟需研究和解决的问题,尤其在下述几个方面:
1)如何构造相似矩阵W:谱聚类算法中相似矩阵W的构造依赖于相似函数Wij的构造。本文介绍的算法所使用的相似函数均由式(8)表示,由于尺度参数σ是人为选取的,使得该函数带有一定的局限性。文献[19]通过反复运行NJW算法来自动确定σ的大小,消除了人为因素,却增加了运算时间。当前,绝大部分文献中相似矩阵的构造都依赖于领域知识,而没有给出通用的规则,系统地研究谱聚类中相似矩阵的构造问题将是未来研究的一个热点。
2)如何处理特征向量:在应用谱方法进行聚类问题的研究中,用多少个特征向量进行聚类,如何选取、计算及使用这些特征向量等问题均没有得到很好的理论解释,这些都是未来急需解决的问题。
3)如何自动确定聚类数目:聚类数目的多少直接影响聚类的质量。已有的自动确定聚类数目的谱聚类算法有:基于
[21]
Rcut的谱聚类算法,非线性降维(NLDR,nonlineardimen-sionalityreduction)算法[22]和基于距离的启发式方法[23]。但用这些算法在一些公共数据集上得出的聚类数和相应的聚类结果都不能令人满意[23]。所以,如何自动地确定聚类数目是一个关键的问题,是未来研究的方向。
4)如何选取Laplacian矩阵:谱聚类算法所使用的Lapla-cian矩阵有三种形式(见本文2.2节),但这三种形式的Laplacian矩阵所应用的具体环境还没有得到彻底解决。文献[23]提出应首先分析度矩阵D中各对角线元素dii,若各dii大小大致相同,则用这三种形式的Laplacian矩阵得出的聚类结果基本相同;反之,聚类结果也大相径庭。如何根据具体环境选择合适的Laplacian矩阵,我们还需要进行大量的理论研究和实验工作。
5)如何运用到大规模学习问题中:由于谱聚类算法涉及求解特征值和特征向量问题,计算复杂度较大,不利于进行大规模的计算和扩展,因此,研究高效、可扩展、适宜大规模学习问题的谱聚类算法是我们未来的研究方向。
结束语 谱聚类算法是聚类分析中一个崭新的分支,由于这种算法不用对数据的全局结构作假设,并且具有识别非凸分布聚类的能力,非常适合于许多实际问题,因此在短短的几年时间内,引起了国际学术界的广泛关注。谱聚类算法的研究将极大丰富聚类算法的研究内容,给聚类问题的求解提供了新的思路,具有巨大的科研价值和应用潜力。希望通过本文介绍,使读者对该领域有一个初步的认识,并能将此方法应用到科学和工程领域中的各种聚类问题中去。
参考文献
[1][2][3]
JainA,MurtyM,FlynnP.Dataclustering:AReview[J].ACMComputingSurveys,1999,31(3):264-323
FiedlerM.Algebraicconnectivityofgraphs.Czech,Math.J.,1973,23:298-305
MalikJ,BelongieS,LeungT,etal.Contourandtextureanaly-sisforimagesegmentation.InPerceptualOrganizationforArti-ficialVisionSystems.Kluwer,2000[4][5]
WeissY.Segmentationusingeigenvectors:Aunifiedview∥In-ternationalConferenceonComputerVision.1999
ShiJ,MalikJ.Normalizedcutsandimagesegmentation.IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(8):888-905[6]
WuZ,LeahyR.Anoptimalgraphtheoreticapproachtodataclustering:theoryanditsapplicationtoimagesegmentation[J].IEEETransonPAMI,1993,15(11):1101-1113[7]
HagenL,KahngAB.Newspectralmethodsforratiocutparti-tioningandclustering.IEEETrans.Computer-AidedDesign,1992,11(9):1074-1085[8]
SarkarS,SoundararajanP.Supervisedlearningoflargepercep-
·
tualorganization:Graphspectralpartitioningandlearningau-tomata.IEEETransactiononPatternAnalysisandMachineIn-telligence,2000,22(5):504-525[9]
DingC,HeX,ZhaH,etal.SpectralMin-MaxcutforGraphPartitioningandDataClustering[C]∥Proc.oftheIEEEIntlConf.onDataMining.2001:107-114
[10]MeilaM,XuL.Multiwaycutsandspectralclustering.U.
WashingtonTechReport.2003
[11]ZhouD,BousquetO,LalTN,etal.Scholkppf:Learningwith
LocalandGlobalConsistency.AdvancesinNeuralInformationProcessingSystems∥Thrun,S.L.SaulandB.Scholkopf,eds.MITPress,Cambridge,MA,USA,2004,16:321-328
[12]VermaD,MeilaM.Acomparisonofspectralclusteringalgo-rithms.Technicalreport,2003.UWCSETechnicalreport03-05-01
[13]PeronaP,FreemanWT.Afactorizationapproachtogrouping
∥H.BurkardtandB.Neumann,eds.Proc.ECCV.1998:655-670[14]ScottGL,Longuet-HigginsHC.Featuregroupingbyrelocal-izationofeigenvectorsoftheproximitymatrix∥Proc.BritishMachineVisionConference.1990:103-108
[15]KannanR,VempalaS,VettaA.Onclusterings-good,badand
spectral.InFOCS,2000:367-377
[16]DingC,HeXF,ZhaHY,etal.Amin-maxcutalgorithmfor
graphpartitioninganddataclustering[A]∥The2001IEEEIn-ternationalConferenceonDatamining.SanJose,USA,2001[17]AlpertC,KahnhA,YaoS.Spectralpartitioning:Themoreeig-envectors,thebetter.DiscreteAppliedMath.,1999,90:3-26[18]MalikJ,BelongieS,LeungT,etal.Contourandtextureanaly-sisforimagesegmentation.InPerceptualOrganizationforArti-ficialVisionSystems.Kluwer,2000
[19]NgAY,JordanMI,WeissY.Onspectralclustering:Analysis
andanalgorithm∥T.G.Dietterich,S.Becker,andGhahramani,eds.AdvancesinNeuralInformationProcessingSystems,Cam-bridge,MA,MITPress,2002,14:849-856
[20]MeilaM,ShiJ.Learningsegmentationbyrandomwalks.In
NIPS,2000:873-879
[21]ChanPK,SchlagDF,ZienJ.Spectralk-wayratio-cutpartitio-ningandclustering[J].IEEETranonComputerAidedDesignofIntegratedCircuitsandSystems,1994,13(9):1088-1096[22]LuxburgU.ATutorialonSpectralClustering.Technicalre-port.2006
[23]BrandM,KunH.AUnifyingTheoremforSpectralEmbedding
andClustering[C]∥Proceedingofthe9thInternationalConfer-enceonArtificialIntelligenceandStatistics.KeyWest,Florida,2003
[24]DhillonS,GuanY,KulisB.Aunifiedviewofkernelk-means,
spectralclusteringandgraphcuts.UniversityofTexasatAus-tinUTCSTechnicalReportTR-04-25.2004
[25]ZhangT,AndoR.Analysisofspectralkerneldesignbasedsemi-supervisedlearning∥Y.Weiss,B.ScholkopfandJ.Platt,eds.Advancesinneuralinformationprocessingsystems18.Cam-bridge,MA:MITPress,2006
[26]DavidS,LuxburgU,PalD.Asoberlookonclusteringstability
∥G.LugosiandH.Simon,eds.Proceedingsofthe19thAnnualConferenceonLearningTheory(COLT).Berlin,Springer,2006:5-9
[27]BieTD,CristianiniN.FastSDPrelaxationsofgraphcutclus-tering,transduction,andothercombinatorialproblems.JMRL,2006(7):1409-1436
[28]LangK.Fixingtwoweaknessesofthespectralmethod∥WeissY,
ScholkopfB,PlattJ,eds.AdvancesinNeuralInformationProcess-ingSystems,Cambridge,MA:MITPress,2006,18:715-722[43]KleinM,NoyNF.AComponent-BasedFrameworkforOntol-ogyEvolution[C]∥WorkshoponOntologiesandDistributedSystemsatIJCAI-03.Aeapulco,Mexico,2003
[44]DouDejiang,McDermottD,QiPeishen.OntologyTranslation
ontheSemanticWeb[J]∥ProceedingsInt'lConf.onOntolo-gies,
DatabasesandApplicationsof
Semantics(ODBA-SE2003).LNCS2888,2003:952-969
[45]AIFB.UniversityofKarlscruhe.KAONDemoPage[EB/OL].http://kaon.semanticweb.org/.(AccessedonOct.6,2006)
[46]http://www.daml.org/language/.(AccessedonMar.20,
2004)
[47]DingYing.OntologyManagementSystem[EB/OL].http://
sw-portal.deri.at/papers/deliverables/d17 v01.pdf,2004.8.31.(AccessedonDec21,2006)
[48]HarrisonR,ChanCW.Distributedontologymanagementsys-tem[C]∥CanadianConferenceonElectricalandComputerEn-gineering.2005(5)
[49]Ontoprise.OntoStudio[EB/OL].http://ontoworld.org/wiki/
OntoStudio.(AccessedonDec.16,2006)
[50]EuzenatJ.Evaluatingontologyalignmentmethods[C]∥Dags-tuhlSeminarProceedings.SemanticInteroperabilityandInte-gration.2005
[51]MaedcheA,StaabS.DiscoveringConceptualRelationsfrom
Text[C]∥Proceedingsofthe14thEuropeanConferenceonAr-tificialIntelligence(ECAI2000).Amsterdam:IOSPress,2000:321-325
(上接第13页)
[36]DoanA,MadhavanJ,DomingosP,etal.Ontologymatching:A
machinelearningapproach[C]∥S.Staab&R.Studer,eds.
HandbookonOntologiesinInformationSystems,Springer-Ver-lag,2004:397-416
[37]SchnurrH-P,AngeleJ.DoNotUseThisgearwithaSwitching
Lever!AutomotiveIndustryExperiencewithSemanticGuides[C]
∥
4th
International
Semantic
Web
Conference
(ISWC2005).LNCS3729,2005:1029-1040
[38]魏哲雄,冯志勇.基于字典技术的本体整合系统[J].计算机应
用,2007,27(2):428-430
[39]NoyNF,MusenMA.AnAlgorithmforMergingandAligning
Ontologies:AutomationandToolSupport[C]∥ProceedingsoftheWorkshoponOntologyManagementattheSixteenthNa-tionalConferenceonArtificialIntelligence(AAAI-99).Orlan-do,1999
[40]NoyNF,MusenMA.SMART:AutomatedSupportforOn-tologyMergingandAlignment[C]∥ProceedingsoftheTwelfth
WorkshoponKnowledgeAcquisitionModelingandManage-ment.Banff,Canada,1999(7)
[41]HorridgeM,KnublauchH,etal.Apracticalguidetobuilding
OWLontologyusingtheprotégé-OWLPluginandCO-ODEtools[EB/OL].TheUniversityofManchester,2004(8)[42]NoyNF,KleinM.Ontologyevolution:Notthesameassche-maevolution[J].KnowledgeandInformationSystems,2004,6(4):428-440
计算机科学2008Vol.35№.7
谱聚类算法综述*)
蔡晓妍 戴冠中 杨黎斌
(西北工业大学自动化学院 西安710072)
摘 要 谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。本文首先介绍了图论方法
用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向。关键词 谱聚类,谱图理论,图划分
SurveyonSpectralClusteringAlgorithms
CAIXiao-yan DAIGuan-zhong YANGLi-bin
(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi'an710072,China)
Abstract Spectralclusteringalgorithmsarenewlydevelopingtechniqueinrecentyears.Unlikethetraditionalcluste-ringalgorithms,theseapplyspectralgraphtheorytosolvetheclusteringofnon-convexsphereofsamplespaces,sothattheycanbeconvergedtoglobaloptimalsolution.Inthispaper,theclusteringprinciplebasedongraphtheoryisfirstin-troduced,andthenspectralclusteringalgorithmsarecategorizedaccordingtorulesofgraphpartition,andtypicalalgo-rithmsarestudiedemphatically,aswellastheiradvantagesanddisadvantagesarepresentedindetail.Finally,someval-uabledirectionsforfurtherresearchareproposed.
Keywords Spectralclustering,Spectralgraphtheory,Graphpartition
类,详细研究了各类中的代表性算法,并对算法进行了比较分
析;最后对本文进行总结,提出了几个有价值的研究方向。
1 引言
聚类分析是机器学习领域中的一个重要分支[1],是人们
认识和探索事物之间内在联系的有效手段。所谓聚类(clus-tering)就是将数据对象分组成为多个类或簇(cluster),使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。传统的聚类算法,如k-means算法、EM算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。
为了能在任意形状的样本空间上聚类,且收敛于全局最优解,学者们开始研究一类新型的聚类算法,称为谱聚类算法(SpectralClusteringAlgorithm)。该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并计算矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉[3]、VLSI设计[4]等领域,最近才开始用于机器学习中[5],并迅速成为国际上机器学习领域的研究热点。
谱聚类算法建立在图论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。但由于其涉及的理论知识较多,应用也还处于初级阶段,因此国内这方面的研究报道非常少。本文作为一篇综述性文章,旨在向读者介绍这种新型的聚类算法,使研究人员尽可能详细地总结该领域的研究现状。后续篇幅安排如下:第2部分介绍了图论方法用于聚类的基本理论;第3部分根据图划分准则,将谱聚类算法分为两
2 基本理论
2.1 图划分准则
谱聚类算法的思想来源于谱图划分理论[2]。假定将每个数据样本看作图中的顶点V,根据样本间的相似度将顶点间的边E赋权重值W,这样就得到一个基于样本相似度的无向加权图G=(V,E)。那么在图G中,就可将聚类问题转化为在图G上的图划分问题。基于图论的最优划分准则就是使划分成的两个子图内部相似度最大,子图之间的相似度最小[5]。划分准则的好坏直接影响到聚类结果的优劣。常见的划分准则有Minimumcut,Averagecut,Normalizedcut,Min-maxcut,Ratiocut,MNcut等。下面我们将分别介绍这几种准则。2.1.1 最小割集准则[6](Minimumcut)
谱图理论中,将图G划分为A,B两个子图(其中A∪B=V,A∩B= )的代价函数为:
cut(A,B)=
u∈A,v∈B
∑w(u,v)(1)
Wu和Leahy提出最小化上述剪切值来划分图G,这一划分准则被称为最小割集准则。他们用这个准则对一些图像进行分割,并产生了较好的效果,同时他们也注意到,该准则容易出现歪斜(即偏向小区域)分割。Shi和Malik提出的规范割集准则及Hagen和Kahng提出的比例割集准则均可避免这种情况的发生。
*)基金项目:国家863计划资助项目(2005AA147030)。蔡晓妍 博士生,主要研究方向为智能信息处理、网络与信息安全;戴冠中 教授,博士生导师,主要研究领域为自动控制、信息安全;杨黎斌 博士生,研究方向为网络与信息安全、嵌入式系统。
2.1.2 规范割集准则[5](Normalizedcut)
Shi和Malik在2000年根据谱图理论建立了2-way划分的规范割目标函数(Ncut):+
assoc(A,V)assoc(B,V)
其中assoc(A,V)=∑w(u,t)
Ncut(A,B)=
u∈A,t∈V
Melia指出Ncut和MNcut的差异之处仅在于所使用的
谱映射不同,并且当k=2时,MNcut与Ncut等价。多路规范割集准则在实际应用中合理有效,但其优化问题通常难以解决。
2.2 相似矩阵、度矩阵及Laplacian矩阵
由于图划分问题的本质,求图划分准则的最优解是一个NP难问题。一个很好的求解方法是考虑问题的连续放松形式,这样便可将原问题转换成求解相似矩阵或Laplacian矩阵的谱分解,因此将这类方法统称为谱聚类,可以认为谱聚类是对图划分准则的逼近[11]。
相似矩阵通常用W或A表示,有时也称为亲合矩阵(Af-finityMatrix)。该矩阵的定义为:
d(si,sj)
Wij=exp(-2
2σ
(2)
最小化Ncut函数被称为规范割集准则。该准则不仅能
够衡量类内样本间的相似程度,也能衡量类间样本间的相异程度。
Shi和Malik同时还提出了规范关联目标函数(Nassoc):
assoc(A,A)assoc(B,B)
Nassoc(A,B)=+(3)
assoc(A,V)assoc(B,V)assoc(A,A)与assoc(B,B)分别是子图A,B内所有顶点
之间的连接权值之和。这一无偏函数进一步反映了类内样本间互相连接的紧密程度。同时,可以看出Ncut函数与Nas-soc函数是相关的,它们满足关系:Ncut(A,B)=2-Nassoc(A,B)。因此,最小化Ncut函数等价于最大化Nassoc函数,但通常情况下都是通过最小化Ncut函数获取图的最优划分。2.1.3 比例割集准则[7](Ratiocut)
Hagen和Kahng提出了比例割目标函数(Rcut):Rcut=(4)
min( A , B )
其中 A , B 分别表示子图A,B中顶点的个数。最小化Rcut函数只考虑了类间相似性最小,减小了过分割的可能性,但运行速度较慢。2.1.4 平均割集准则[8](Averagecut)
平均割目标函数为:
Avcut(A,B)=(5)
A B
可以看出Avcut和Ncut函数都表示无向图G中边界损失与分割区域相关性的比值之和,因此最小化Avcut与Ncut目标函数都能产生较准确的划分。其共同缺点是倾向于欠分割且易分割出只包含几个顶点的较小子图。文献[5]通过实验发现,当把Normalizedcut和Averagecut准则分别用于同一图像的分割问题时,Normalizedcut准则能够产生更好的划分结果。2.1.5 最小最大割集准则[9](Min-maxcut)
最小最大割集准则要求最小化cut(A,B)的同时,最大化assoc(A,A)与assoc(B,B)。该准则可通过最小化下面的目标函数得以实现:
cut(A,B)cut(A,B)
Mcut=+(6)
assoc(A,A)assoc(B,B)我们将这个目标函数称为最小最大割函数,或简称为
Mcut函数。最小化该函数可避免分割出仅包含几个顶点的较小子图,因此它倾向于产生平衡割集,但实现速度较慢。Mcut与Ncut一样满足类间样本间的相似度小而类内样本间的相似度大的原则,与Ncut具有相似的行为,但当类间重叠较大时,Mcut比Ncut更加高效。2.1.6 多路规范割集准则[10](MultiwayNormalizedcut)
上述五种划分准则所使用的目标函数都是将图G划分为2个子图的2-way划分函数,Meila提出一种可以将图G同时划分为k个子图的k-way规范割目标函数:
cut(A1,V-A1)cut(A2,V-A2)
MNcut=++…+
assoc(A1,V)assoc(A2,V)cut(A,V-A)
(7)
assoc(Ak,V)
(8)
2
其中si表示每个数据样本点,d(si,sj)一般取 si-sj ,σ为事先指定的参数。
将相似矩阵的每行元素相加,即得到该顶点的度,以所有
度值为对角元素构成的对角矩阵即为度矩阵,度矩阵常用D表示。
Laplacian矩阵分为非规范Laplacian矩阵和规范Lapla-cian矩阵。非规范Laplacian矩阵表示为L=D-W,规范Laplacian矩阵有两种形式,分别是:
Lsym=D-2LD2=I-D-2WDLrw=D-1L=I-D-1W2.3 势函数、Fiedler向量及谱
1
1
1
1
2
(9)
势函数为表示某样本划分归属的指示向量(indicator
vector),其定义为:
qi10
若i∈A若i∈B
(10)
若最终势函数中某样本对应的值为1,则该样本属于集
合A,若为0则属于集合B。但实际划分求解得到的结果qi常为0到1之间的实数值,此时可用k均值聚类等方法进一步决定样本的归属。
许多谱聚类算法都将图划分问题转化为求解Laplacian矩阵的第二小特征向量问题。这里的第二小特征向量就是第二个最小特征值对应的特征向量,它代表了最佳图划分的一个解(即势函数),把这一特征向量称为Fiedler向量。与特征向量(不一定是Fiedler向量)对应的特征值称为谱。
3 谱聚类算法
根据不同的准则函数及谱映射方法,谱聚类算法发展了很多不同的具体实现方法,但是都可以归纳为下面三个主要步骤[12]:
Step1 构建表示样本集的矩阵Z;
Step2 通过计算Z的前k个特征值与特征向量,构建特征向量空间;
Step3 利用k-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。
上述步骤是谱聚类算法的一个框架,在具体实现过程中,不同的算法在数据集矩阵Z的表示上存在着不同。例如根据2-waycut的目标函数,Z=W;根据随机游动关系,则Z=D-1W等。划分准则一般分为2-way和k-way,本文根据所使用的划分准则,将算法分为迭代谱和多路谱两类,并分别讨论了各类中典型的谱聚类算法。
·
3.1 迭代谱聚类算法3.1.1 PF算法[13]
Perona和Freeman提出用相似矩阵W的第一个特征向x1进行聚类(本文中第一个特征向量指的是相应矩阵中最大特征值λ。他们指出对于块对角相似矩1所对应的特征向量)阵,特征向量x1中非零元素对应的点属于同一类,零元素对应的点属于另外一类。PF算法作为最简单的谱聚类算法引起了学术界的广泛关注,在理论研究和应用方面都有很多论文发表。
3.1.2 SM算法[5]
SM算法由美国学者Shi和Malik在2000年提出。他们指出在约束xTWe=xTDe=0条件下,
minNcut(A,B)=min
xTDx
T
Weiss提出了一种将SLH算法和SM算法相结合的新型谱聚类算法[4]。该算法将SLH算法中的原始相似矩阵W用规范相似矩阵N代替。实验表明,此算法能够更加快速地产生正确的聚类结果。3.1.4 KVV算法[15]
KVV算法与SM算法十分相似,不同之处仅在于SM算法是寻找使Ncut(A,B)值最小的划分点,而KVV算法则是寻找使Rcut(A,B)值最小的划分点。KVV算法减少了过分割的可能性,但算法的运行速度相对较慢。3.1.5 Mcut算法[16]
Ding根据谱图理论,将(6)式重新写为:
TTx(D-W)xy(D-W)y
Mcut=+TT
xWxyWy
对于2-way划分,令q为划分指示向量,则:
ai∈A
-bi∈B最小化式(15)可得qiminMcut(A,B)=min
q
q
(15)
(11)
将x松弛到连续域[-1,1],求解minNcut(A,B)的问题
就可以转化为下式:
argmin
xT(D-W)x
T
TxDxxD1=0
(12)
(16)
根据Rayleigh商原理,式(12)的优化问题等于求解下列
等式的第二小特征值问题:
(D-W)x=λDx(13)与第二小特征值对应的特征向量(即Fiedler向量)就包含了图的划分信息。SM算法描述如下:
Step1 通过样本集建立无向加权图G,根据图G构造矩阵W和D;
Step2 计算式(13)第二小特征值及对应的Fiedler向量;
Step3 根据启发式规则在Fiedler向量中寻找划分点i,使在该点上得到的Ncut(A,B)值最小。将Fiedler向量中大于等于该值的点归为一类,小于该值的点归为另一类。
定义规范相似矩阵为:
N=D
-2
JN(A,B)
minJN(A,B)
1-JNq
TJN(A,B)≡JN(q)=(17)
qTDq
在约束xTe=0条件下,将x松弛到连续域[-1,1],根据Rayleigh商原理,(17)式的优化问题等于求解下式的第二小特征值问题:
(D-W)xx(18)
1+λ
因此,将图G划分为两个子图的Mcut算法可以简单描述如下:
Step1 计算(18)式的Fiedler向量。
Step2 在Fiedler向量中,寻找使Mcut值最小的划分点。
Step3 用基于连接的聚类算法进行优化。
Kannan将该算法与SM算法、KVV算法进行了比较,发现Mcut算法能够产生更加平衡的划分结果,尤其当类间重叠较大时,效果更为明显。3.2 多路谱聚类算法
大部分谱聚类算法都是利用2-way划分准则迭代地对样本数据进行聚类。但是近几年研究发现,若使用更多的特征向量并且直接计算k路分割将会得到更好的聚类效果[17,18]。3.2.1 NJW算法[19]
Ng,Jordan等人选取拉氏矩阵Lsym的前k个最大特征值对应的特征向量,使其在Rk空间中构成与原数据一一对应的表述,然后在Rk空间中进行聚类。NJW算法描述如下:Step1 计算矩阵Lsym的前k个最大特征值所对应的特征向量x1,…,xk(必要时需作正交化处理),构造矩阵X=[x1,…,xk]∈Rn×k;
Step2 将矩阵X的行向量转变为单位向量,得到矩阵
Xij
Y,即Yij=
X2ij
j
WD
2
即 N(i,j)=
W(i,j)
(14)
D(i,i)(j,j)
根据正规化定理[4],可以得出矩阵W的Fiedler向量等
于矩阵N的次大与最大特征向量之间的分量方式比值。因此,SM算法与PF算法的不同之处在于:①SM算法用的是规范相似矩阵,而PF算法仅用相似矩阵;②SM算法用的是前两个特征向量,而PF算法只用了第一个特征向量。
Shi和Malik同时还提出将minAvcut的离散形式松弛为连续形式进行聚类。但实验表明,SM算法得出的聚类效果要明显好于用PF算法及最小化Avcut标准得到的聚类效果。3.1.3 SLH算法[14]
SLH重定位算法将相似矩阵W和数字k作为输入,并通过下面的步骤输出一个新的矩阵Q:
Step1 求矩阵W的前k个特征向量x1,…,xk,构造矩阵X=[x1,…,xk]∈Rn×k;
Step2 将矩阵X的行向量规范化为单位长度并构造新矩阵Q=XXT;
Step3 根据Q中的元素聚类相应的点。理想情况下,Q(i,j)=1表示i,j两点属于同一类,Q(i,j)=0表示i,j两点属于不同类。一般情况下,属于同一类的点对应的Q(i,j)值均接近1,属于不同类的点对应的Q(i,j)值接近0。
Step3 将矩阵Y的每一行看作是Rk空间中的一个点,对其使用k均值算法或任意其它经典算法,得到k个聚类;
Step4 将数据点yi划分到聚类j中,当且仅当Y的第i行被划分到聚类j中。
选取矩阵Lsym的前k个最大特征值所对应特征向量的原因在于:对于存在k个理想的彼此分离簇的有限数据集,可以
证明矩阵Lsym的前k个最大特征值为1,第k+1个特征值则严格小于1,二者之间的差距取决于这k个聚类的分布情况[19]。当聚类内部分布得越密,各聚类间分布得越开时,第k+1个特征值就越小,此时,以Y矩阵中的每行作为k维空间中的一个点所形成的k个聚类,它们将彼此正交地分布于k维空间中的单位球上,并且在单位球上形成的这k个聚类对应着原空间中所有点形成的k个聚类。3.2.2 MS算法[20]
Meila将相似性解释为Markov链中的随机游动,分析了这种随机游动的概率转移矩阵P=D-1W的特征向量,并根
据随机游动对MNcut进行了概率解释。在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类算法。算法步骤与NJW算法相似,但该算法是用随机游动矩阵P的前k个特征向量构造矩阵X,并直接将矩阵X中的各行看成Rk空间中的各点进行聚类。MS算法在实际应用中取得了一定的效果,但当度矩阵D中各对角线元素差别较大时,聚类效果较差[19]。
以上对典型的谱聚类算法进行了概述,表1为这些算法的一个简单比较。
表1 典型谱聚类算法的比较
算法PF算法SM算法SLH算法Mcut算法NJW算法MS算法
目标函数cut(A,B)Ncut(A,B)
———Mcut(A,B)
———MNcut
所用方程Wx=λx(D-W)x=λDx
Wx=λxλ
(D-W)x=x
1+λ
D选取的特征向量最大特征向量Fiedler向量前k个特征向量Fiedler向量前k个特征向量前k个特征向量
特点
易产生仅包含几个顶点的较小簇当类间重叠较大时易出现歪斜分割
速度较慢能够产生更加平衡的划分结果,但后置处理需要花费大量时间
需要进行正交初始化当度矩阵D中各对角线元素差别较大时,聚类效果较差
WD
-x=λx
D-1Wx=λx
4 当前的几个热点研究问题
尽管谱聚类相对于其它聚类方法具有许多优势,并在实
践中也取得了很好的效果,但它仍有许多亟需研究和解决的问题,尤其在下述几个方面:
1)如何构造相似矩阵W:谱聚类算法中相似矩阵W的构造依赖于相似函数Wij的构造。本文介绍的算法所使用的相似函数均由式(8)表示,由于尺度参数σ是人为选取的,使得该函数带有一定的局限性。文献[19]通过反复运行NJW算法来自动确定σ的大小,消除了人为因素,却增加了运算时间。当前,绝大部分文献中相似矩阵的构造都依赖于领域知识,而没有给出通用的规则,系统地研究谱聚类中相似矩阵的构造问题将是未来研究的一个热点。
2)如何处理特征向量:在应用谱方法进行聚类问题的研究中,用多少个特征向量进行聚类,如何选取、计算及使用这些特征向量等问题均没有得到很好的理论解释,这些都是未来急需解决的问题。
3)如何自动确定聚类数目:聚类数目的多少直接影响聚类的质量。已有的自动确定聚类数目的谱聚类算法有:基于
[21]
Rcut的谱聚类算法,非线性降维(NLDR,nonlineardimen-sionalityreduction)算法[22]和基于距离的启发式方法[23]。但用这些算法在一些公共数据集上得出的聚类数和相应的聚类结果都不能令人满意[23]。所以,如何自动地确定聚类数目是一个关键的问题,是未来研究的方向。
4)如何选取Laplacian矩阵:谱聚类算法所使用的Lapla-cian矩阵有三种形式(见本文2.2节),但这三种形式的Laplacian矩阵所应用的具体环境还没有得到彻底解决。文献[23]提出应首先分析度矩阵D中各对角线元素dii,若各dii大小大致相同,则用这三种形式的Laplacian矩阵得出的聚类结果基本相同;反之,聚类结果也大相径庭。如何根据具体环境选择合适的Laplacian矩阵,我们还需要进行大量的理论研究和实验工作。
5)如何运用到大规模学习问题中:由于谱聚类算法涉及求解特征值和特征向量问题,计算复杂度较大,不利于进行大规模的计算和扩展,因此,研究高效、可扩展、适宜大规模学习问题的谱聚类算法是我们未来的研究方向。
结束语 谱聚类算法是聚类分析中一个崭新的分支,由于这种算法不用对数据的全局结构作假设,并且具有识别非凸分布聚类的能力,非常适合于许多实际问题,因此在短短的几年时间内,引起了国际学术界的广泛关注。谱聚类算法的研究将极大丰富聚类算法的研究内容,给聚类问题的求解提供了新的思路,具有巨大的科研价值和应用潜力。希望通过本文介绍,使读者对该领域有一个初步的认识,并能将此方法应用到科学和工程领域中的各种聚类问题中去。
参考文献
[1][2][3]
JainA,MurtyM,FlynnP.Dataclustering:AReview[J].ACMComputingSurveys,1999,31(3):264-323
FiedlerM.Algebraicconnectivityofgraphs.Czech,Math.J.,1973,23:298-305
MalikJ,BelongieS,LeungT,etal.Contourandtextureanaly-sisforimagesegmentation.InPerceptualOrganizationforArti-ficialVisionSystems.Kluwer,2000[4][5]
WeissY.Segmentationusingeigenvectors:Aunifiedview∥In-ternationalConferenceonComputerVision.1999
ShiJ,MalikJ.Normalizedcutsandimagesegmentation.IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(8):888-905[6]
WuZ,LeahyR.Anoptimalgraphtheoreticapproachtodataclustering:theoryanditsapplicationtoimagesegmentation[J].IEEETransonPAMI,1993,15(11):1101-1113[7]
HagenL,KahngAB.Newspectralmethodsforratiocutparti-tioningandclustering.IEEETrans.Computer-AidedDesign,1992,11(9):1074-1085[8]
SarkarS,SoundararajanP.Supervisedlearningoflargepercep-
·
tualorganization:Graphspectralpartitioningandlearningau-tomata.IEEETransactiononPatternAnalysisandMachineIn-telligence,2000,22(5):504-525[9]
DingC,HeX,ZhaH,etal.SpectralMin-MaxcutforGraphPartitioningandDataClustering[C]∥Proc.oftheIEEEIntlConf.onDataMining.2001:107-114
[10]MeilaM,XuL.Multiwaycutsandspectralclustering.U.
WashingtonTechReport.2003
[11]ZhouD,BousquetO,LalTN,etal.Scholkppf:Learningwith
LocalandGlobalConsistency.AdvancesinNeuralInformationProcessingSystems∥Thrun,S.L.SaulandB.Scholkopf,eds.MITPress,Cambridge,MA,USA,2004,16:321-328
[12]VermaD,MeilaM.Acomparisonofspectralclusteringalgo-rithms.Technicalreport,2003.UWCSETechnicalreport03-05-01
[13]PeronaP,FreemanWT.Afactorizationapproachtogrouping
∥H.BurkardtandB.Neumann,eds.Proc.ECCV.1998:655-670[14]ScottGL,Longuet-HigginsHC.Featuregroupingbyrelocal-izationofeigenvectorsoftheproximitymatrix∥Proc.BritishMachineVisionConference.1990:103-108
[15]KannanR,VempalaS,VettaA.Onclusterings-good,badand
spectral.InFOCS,2000:367-377
[16]DingC,HeXF,ZhaHY,etal.Amin-maxcutalgorithmfor
graphpartitioninganddataclustering[A]∥The2001IEEEIn-ternationalConferenceonDatamining.SanJose,USA,2001[17]AlpertC,KahnhA,YaoS.Spectralpartitioning:Themoreeig-envectors,thebetter.DiscreteAppliedMath.,1999,90:3-26[18]MalikJ,BelongieS,LeungT,etal.Contourandtextureanaly-sisforimagesegmentation.InPerceptualOrganizationforArti-ficialVisionSystems.Kluwer,2000
[19]NgAY,JordanMI,WeissY.Onspectralclustering:Analysis
andanalgorithm∥T.G.Dietterich,S.Becker,andGhahramani,eds.AdvancesinNeuralInformationProcessingSystems,Cam-bridge,MA,MITPress,2002,14:849-856
[20]MeilaM,ShiJ.Learningsegmentationbyrandomwalks.In
NIPS,2000:873-879
[21]ChanPK,SchlagDF,ZienJ.Spectralk-wayratio-cutpartitio-ningandclustering[J].IEEETranonComputerAidedDesignofIntegratedCircuitsandSystems,1994,13(9):1088-1096[22]LuxburgU.ATutorialonSpectralClustering.Technicalre-port.2006
[23]BrandM,KunH.AUnifyingTheoremforSpectralEmbedding
andClustering[C]∥Proceedingofthe9thInternationalConfer-enceonArtificialIntelligenceandStatistics.KeyWest,Florida,2003
[24]DhillonS,GuanY,KulisB.Aunifiedviewofkernelk-means,
spectralclusteringandgraphcuts.UniversityofTexasatAus-tinUTCSTechnicalReportTR-04-25.2004
[25]ZhangT,AndoR.Analysisofspectralkerneldesignbasedsemi-supervisedlearning∥Y.Weiss,B.ScholkopfandJ.Platt,eds.Advancesinneuralinformationprocessingsystems18.Cam-bridge,MA:MITPress,2006
[26]DavidS,LuxburgU,PalD.Asoberlookonclusteringstability
∥G.LugosiandH.Simon,eds.Proceedingsofthe19thAnnualConferenceonLearningTheory(COLT).Berlin,Springer,2006:5-9
[27]BieTD,CristianiniN.FastSDPrelaxationsofgraphcutclus-tering,transduction,andothercombinatorialproblems.JMRL,2006(7):1409-1436
[28]LangK.Fixingtwoweaknessesofthespectralmethod∥WeissY,
ScholkopfB,PlattJ,eds.AdvancesinNeuralInformationProcess-ingSystems,Cambridge,MA:MITPress,2006,18:715-722[43]KleinM,NoyNF.AComponent-BasedFrameworkforOntol-ogyEvolution[C]∥WorkshoponOntologiesandDistributedSystemsatIJCAI-03.Aeapulco,Mexico,2003
[44]DouDejiang,McDermottD,QiPeishen.OntologyTranslation
ontheSemanticWeb[J]∥ProceedingsInt'lConf.onOntolo-gies,
DatabasesandApplicationsof
Semantics(ODBA-SE2003).LNCS2888,2003:952-969
[45]AIFB.UniversityofKarlscruhe.KAONDemoPage[EB/OL].http://kaon.semanticweb.org/.(AccessedonOct.6,2006)
[46]http://www.daml.org/language/.(AccessedonMar.20,
2004)
[47]DingYing.OntologyManagementSystem[EB/OL].http://
sw-portal.deri.at/papers/deliverables/d17 v01.pdf,2004.8.31.(AccessedonDec21,2006)
[48]HarrisonR,ChanCW.Distributedontologymanagementsys-tem[C]∥CanadianConferenceonElectricalandComputerEn-gineering.2005(5)
[49]Ontoprise.OntoStudio[EB/OL].http://ontoworld.org/wiki/
OntoStudio.(AccessedonDec.16,2006)
[50]EuzenatJ.Evaluatingontologyalignmentmethods[C]∥Dags-tuhlSeminarProceedings.SemanticInteroperabilityandInte-gration.2005
[51]MaedcheA,StaabS.DiscoveringConceptualRelationsfrom
Text[C]∥Proceedingsofthe14thEuropeanConferenceonAr-tificialIntelligence(ECAI2000).Amsterdam:IOSPress,2000:321-325
(上接第13页)
[36]DoanA,MadhavanJ,DomingosP,etal.Ontologymatching:A
machinelearningapproach[C]∥S.Staab&R.Studer,eds.
HandbookonOntologiesinInformationSystems,Springer-Ver-lag,2004:397-416
[37]SchnurrH-P,AngeleJ.DoNotUseThisgearwithaSwitching
Lever!AutomotiveIndustryExperiencewithSemanticGuides[C]
∥
4th
International
Semantic
Web
Conference
(ISWC2005).LNCS3729,2005:1029-1040
[38]魏哲雄,冯志勇.基于字典技术的本体整合系统[J].计算机应
用,2007,27(2):428-430
[39]NoyNF,MusenMA.AnAlgorithmforMergingandAligning
Ontologies:AutomationandToolSupport[C]∥ProceedingsoftheWorkshoponOntologyManagementattheSixteenthNa-tionalConferenceonArtificialIntelligence(AAAI-99).Orlan-do,1999
[40]NoyNF,MusenMA.SMART:AutomatedSupportforOn-tologyMergingandAlignment[C]∥ProceedingsoftheTwelfth
WorkshoponKnowledgeAcquisitionModelingandManage-ment.Banff,Canada,1999(7)
[41]HorridgeM,KnublauchH,etal.Apracticalguidetobuilding
OWLontologyusingtheprotégé-OWLPluginandCO-ODEtools[EB/OL].TheUniversityofManchester,2004(8)[42]NoyNF,KleinM.Ontologyevolution:Notthesameassche-maevolution[J].KnowledgeandInformationSystems,2004,6(4):428-440