谱聚类算法综述

计算机科学2008V ol .35№.7　

谱聚类算法综述＊)

蔡晓妍　戴冠中　杨黎斌

(西北工业大学自动化学院　西安710072)

摘　要　谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。本文首先介绍了图论方法

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

Survey on Spectral C lustering Algorithms

CA 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 ∈B

w (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 ∈V

w (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]。

相似矩阵通常用W 或A 表示,有时也称为亲合矩阵(Af -finity M atrix )。该矩阵的定义为:

W ij =exp (-d (s i ,s j )

2σ

2

)(8)

其中s i 表示每个数据样本点,d (s i ,s j )一般取 s i -s j 2

,σ为事先指定的参数。

将相似矩阵的每行元素相加,即得到该顶点的度,以所有

度值为对角元素构成的对角矩阵即为度矩阵,度矩阵常用D 表示。

Laplacian 矩阵分为非规范La placian 矩阵和规范Lapla -cian 矩阵。非规范Laplacian 矩阵表示为L =D -W ,规范Laplacian 矩阵有两种形式,分别是:

L sym =D -1

2LD -1

2=I -D -1

2WD -1

2

L rw =D -1L =I -D -1W (9)

2.3　势函数、Fiedler 向量及谱

势函数为表示某样本划分归属的指示向量(indicato r

v ecto r ),其定义为:

q i =

1若i ∈A 0

若i ∈B

(10)

若最终势函数中某样本对应的值为1,则该样本属于集

合A ,若为0则属于集合B 。但实际划分求解得到的结果q i 常为0到1之间的实数值,此时可用k 均值聚类等方法进一步决定样本的归属。

许多谱聚类算法都将图划分问题转化为求解Laplacian 矩阵的第二小特征向量问题。这里的第二小特征向量就是第二个最小特征值对应的特征向量,它代表了最佳图划分的一个解(即势函数),把这一特征向量称为Fiedler 向量。与特征向量(不一定是Fiedler 向量)对应的特征值称为谱。

3　谱聚类算法

根据不同的准则函数及谱映射方法,谱聚类算法发展了很多不同的具体实现方法,但是都可以归纳为下面三个主要步骤[12]:

Step1　构建表示样本集的矩阵Z ;

Step2　通过计算Z 的前k 个特征值与特征向量,构建特征向量空间;

Step3　利用k -means 或其它经典聚类算法对特征向量空间中的特征向量进行聚类。

上述步骤是谱聚类算法的一个框架,在具体实现过程中,不同的算法在数据集矩阵Z 的表示上存在着不同。例如根据2-w ay cut 的目标函数,Z =W ;根据随机游动关系,则Z =D -1W 等。划分准则一般分为2-w ay 和k -w ay ,本文根据所使用的划分准则,将算法分为迭代谱和多路谱两类,并分别讨论了各类中典型的谱聚类算法。

3.1　迭代谱聚类算法3.1.1　PF 算法[13]

Pero na 和F reeman 提出用相似矩阵W 的第一个特征向x 1进行聚类(本文中第一个特征向量指的是相应矩阵中最大特征值λ1所对应的特征向量)。他们指出对于块对角相似矩阵,特征向量x 1中非零元素对应的点属于同一类,零元素对应的点属于另外一类。P F 算法作为最简单的谱聚类算法引起了学术界的广泛关注,在理论研究和应用方面都有很多论文发表。

3.1.2　SM 算法[5]

SM 算法由美国学者Shi 和M alik 在2000年提出。他们指出在约束x T We =x T De =0条件下,

min N cut (A ,B )=min

x T

(D -W )x

x T D x

(11)

将x 松弛到连续域[-1,1],求解min N cut (A ,B )的问题

就可以转化为下式:

arg min

x T D 1=0

x T (D -W )x

x T

D x (12)

根据Ray leig h 商原理,式(12)的优化问题等于求解下列

等式的第二小特征值问题:

(D -W )x =λD x (13)与第二小特征值对应的特征向量(即F iedler 向量)就包含了图的划分信息。SM 算法描述如下:

Step1　通过样本集建立无向加权图G ,根据图G 构造矩阵W 和D ;

Step2　计算式(13)第二小特征值及对应的Fiedler 向量;

Step3　根据启发式规则在Fiedle r 向量中寻找划分点i ,使在该点上得到的N cut (A ,B )值最小。将Fiedler 向量中大于等于该值的点归为一类,小于该值的点归为另一类。

定义规范相似矩阵为:

N =D

-12

WD

-1

2

即　N (i ,j )=

W (i ,j )

D (i ,i )D (j ,j )

(14)

根据正规化定理[4],可以得出矩阵W 的F iedler 向量等

于矩阵N 的次大与最大特征向量之间的分量方式比值。因此,SM 算法与P F 算法的不同之处在于:①SM 算法用的是规范相似矩阵,而P F 算法仅用相似矩阵;②SM 算法用的是前两个特征向量,而PF 算法只用了第一个特征向量。

Shi 和M alik 同时还提出将minA v cut 的离散形式松弛为连续形式进行聚类。但实验表明,SM 算法得出的聚类效果要明显好于用P F 算法及最小化Av cut 标准得到的聚类效果。3.1.3　SL H 算法[14]

SL H 重定位算法将相似矩阵W 和数字k 作为输入,并通过下面的步骤输出一个新的矩阵Q :

Step1　求矩阵W 的前k 个特征向量x 1,…,x k ,构造矩阵X =[x 1,…,x k ]∈R n ×k ;

Step2　将矩阵X 的行向量规范化为单位长度并构造新矩阵Q =X X T ;

Step3　根据Q 中的元素聚类相应的点。理想情况下,Q (i ,j )=1表示i ,j 两点属于同一类,Q (i ,j )=0表示i ,j 两点属于不同类。一般情况下,属于同一类的点对应的Q (i ,j )值均接近1,属于不同类的点对应的Q (i ,j )值接近0。

W eiss 提出了一种将SL H 算法和SM 算法相结合的新型谱聚类算法[4]。该算法将SL H 算法中的原始相似矩阵W 用规范相似矩阵N 代替。实验表明,此算法能够更加快速地产生正确的聚类结果。3.1.4　KV V 算法[15]

K V V 算法与SM 算法十分相似,不同之处仅在于SM 算法是寻找使N cut (A ,B )值最小的划分点,而K VV 算法则是寻找使Rcut (A ,B )值最小的划分点。K VV 算法减少了过分割的可能性,但算法的运行速度相对较慢。3.1.5　M cut 算法[16]

Ding 根据谱图理论,将(6)式重新写为:

Mcut =x T (D -W )x x T W x +y T (D -W )y

y T

Wy

(15)

对于2-w ay 划分,令q 为划分指示向量,则:

q i =

a i ∈A

-b i ∈B (16)

最小化式(15)可得min q

Mcut (A ,B )=min

q

J N (A ,B )

1-J N (A ,B )/2 min q

J N (A ,B )

J N (A ,B )≡J N (q )=q T (D -W )q

q T Dq

(17)

在约束x T e =0条件下,将x 松弛到连续域[-1,1],根据Ray leigh 商原理,(17)式的优化问题等于求解下式的第二小特征值问题:

(D -W )x =λ

1+λ

D x (18)

因此,将图G 划分为两个子图的M cut 算法可以简单描述如下:

Step1　计算(18)式的F iedler 向量。

Step2　在Fiedler 向量中,寻找使M cut 值最小的划分点。

Step3　用基于连接的聚类算法进行优化。

K annan 将该算法与SM 算法、K V V 算法进行了比较,发现M cut 算法能够产生更加平衡的划分结果,尤其当类间重叠较大时,效果更为明显。3.2　多路谱聚类算法

大部分谱聚类算法都是利用2-w ay 划分准则迭代地对样本数据进行聚类。但是近几年研究发现,若使用更多的特征向量并且直接计算k 路分割将会得到更好的聚类效果[17,18]。3.2.1　N JW 算法[19]

N g ,Jor dan 等人选取拉氏矩阵L s y m 的前k 个最大特征值对应的特征向量,使其在R k 空间中构成与原数据一一对应的表述,然后在R k 空间中进行聚类。N JW 算法描述如下:Step1　计算矩阵L s y m 的前k 个最大特征值所对应的特征向量x 1,…,x k (必要时需作正交化处理),构造矩阵X =[x 1,…,x k ]∈R n ×k ;

Step2　将矩阵X 的行向量转变为单位向量,得到矩阵

Y ,即Y ij =

X ij

∑j

X 2ij

Step3　将矩阵Y 的每一行看作是R k 空间中的一个点,对其使用k 均值算法或任意其它经典算法,得到k 个聚类;

Step4　将数据点y i 划分到聚类j 中,当且仅当Y 的第i 行被划分到聚类j 中。

选取矩阵L sy m 的前k 个最大特征值所对应特征向量的原因在于:对于存在k 个理想的彼此分离簇的有限数据集,可以

证明矩阵L s y m 的前k 个最大特征值为1,第k +1个特征值则严格小于1,二者之间的差距取决于这k 个聚类的分布情况[19]。当聚类内部分布得越密,各聚类间分布得越开时,第k +1个特征值就越小,此时,以Y 矩阵中的每行作为k 维空间中的一个点所形成的k 个聚类,它们将彼此正交地分布于k 维空间中的单位球上,并且在单位球上形成的这k 个聚类对应着原空间中所有点形成的k 个聚类。3.2.2　M S 算法[20]

M eila 将相似性解释为M a rkov 链中的随机游动,分析了这种随机游动的概率转移矩阵P =D -1W 的特征向量,并根

据随机游动对M N cut 进行了概率解释。在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类算法。算法步骤与N JW 算法相似,但该算法是用随机游动矩阵P 的前k 个特征向量构造矩阵X ,并直接将矩阵X 中的各行看成R k 空间中的各点进行聚类。M S 算法在实际应用中取得了一定的效果,但当度矩阵D 中各对角线元素差别较大时,聚类效果较差[19]。

以上对典型的谱聚类算法进行了概述,表1为这些算法的一个简单比较。

表1　典型谱聚类算法的比较

算法目标函数所用方程选取的特征向量特点

PF 算法cut (A ,B )W x =λx 最大特征向量易产生仅包含几个顶点的较小簇S M 算法Ncut (A ,B )

(D -W )x =λD x

Fiedler 向量当类间重叠较大时易出现歪斜分割

S LH 算法———W x =λx 前k 个特征向量速度较慢M cut 算法M cut (A ,B )

(D -W )x =λ

1+λ

D x

Fiedler 向量能够产生更加平衡的划分结果,但后置处理需要花费大量时间

NJW 算法———D -12

WD

-12

x =λx

前k 个特征向量需要进行正交初始化M S 算法

M Ncut

D -1Wx =λx

前k 个特征向量

当度矩阵D 中各对角线元素差别较大时,聚类效果较差

4　当前的几个热点研究问题

尽管谱聚类相对于其它聚类方法具有许多优势,并在实

践中也取得了很好的效果,但它仍有许多亟需研究和解决的问题,尤其在下述几个方面:

1)如何构造相似矩阵W :谱聚类算法中相似矩阵W 的构造依赖于相似函数W ij 的构造。本文介绍的算法所使用的相似函数均由式(8)表示,由于尺度参数σ是人为选取的,使得该函数带有一定的局限性。文献[19]通过反复运行N JW 算法来自动确定σ的大小,消除了人为因素,却增加了运算时间。当前,绝大部分文献中相似矩阵的构造都依赖于领域知识,而没有给出通用的规则,系统地研究谱聚类中相似矩阵的构造问题将是未来研究的一个热点。

2)如何处理特征向量:在应用谱方法进行聚类问题的研究中,用多少个特征向量进行聚类,如何选取、计算及使用这些特征向量等问题均没有得到很好的理论解释,这些都是未来急需解决的问题。

3)如何自动确定聚类数目:聚类数目的多少直接影响聚类的质量。已有的自动确定聚类数目的谱聚类算法有:基于

Rcut 的谱聚类算法[21]

,非线性降维(N LD R ,nonlinea r dimen -sio na lity reduc tion )算法[22]和基于距离的启发式方法[23]。但用这些算法在一些公共数据集上得出的聚类数和相应的聚类结果都不能令人满意[23]。所以,如何自动地确定聚类数目是一个关键的问题,是未来研究的方向。

4)如何选取L aplacian 矩阵:谱聚类算法所使用的La pla -cian 矩阵有三种形式(见本文2.2节),但这三种形式的Laplacian 矩阵所应用的具体环境还没有得到彻底解决。文献[23]提出应首先分析度矩阵D 中各对角线元素d ii ,若各d ii 大小大致相同,则用这三种形式的Laplacian 矩阵得出的聚类结果基本相同;反之,聚类结果也大相径庭。如何根据具体环境选择合适的L aplacian 矩阵,我们还需要进行大量的理论研究和实验工作。

5)如何运用到大规模学习问题中:由于谱聚类算法涉及求解特征值和特征向量问题,计算复杂度较大,不利于进行大规模的计算和扩展,因此,研究高效、可扩展、适宜大规模学习问题的谱聚类算法是我们未来的研究方向。

结束语　谱聚类算法是聚类分析中一个崭新的分支,由于这种算法不用对数据的全局结构作假设,并且具有识别非凸分布聚类的能力,非常适合于许多实际问题,因此在短短的几年时间内,引起了国际学术界的广泛关注。谱聚类算法的研究将极大丰富聚类算法的研究内容,给聚类问题的求解提供了新的思路,具有巨大的科研价值和应用潜力。希望通过本文介绍,使读者对该领域有一个初步的认识,并能将此方法应用到科学和工程领域中的各种聚类问题中去。

参考文献

[1]Jain A ,M u rty M ,Flynn P .Data clus tering :A Review [J ].ACM C om puting S urvey s ,1999,31(3):2-323

[2]Fiedler M .Algeb raic conn ectivity of graphs .Czech ,M ath .J .,1973,23:298-305

[3]

M alik J ,Belongie S ,Leung T ,et al .Contour and texture analy -sis for image segm en tation .In Percep tual Organization for Arti -ficial Vision Sy stem s .Klu wer ,2000[4]Weiss Y .Segm entation u s ing eigenvectors :A unified view ∥In -ternational Conference on C om puter Vision .1999

[5]

Shi J ,M alik J .No rm aliz ed cuts and image segmen tation .IE EE T ran sactions on Pattern Analysis and M achine Intelligence ,2000,22(8):888-905[6]

W u Z ,Leahy R .An optimal g raph theoretic approach to data clustering :theory and its application to image segmentation [J ].IEEE T ran s on PAM I ,1993,15(11):1101-1113[7]

Hagen L ,Kahn g A B .New s pectral methods for ratio cut parti -tioning and clustering .IEEE T ran s .Compu ter -Aided Des ign ,1992,11(9):1074-1085[8]

Sarkar S ,S ou ndararajan P .Supervised learning of large percep -

tomata.IEEE Transaction on Pattern Analysis and M achine In-

telligence,2000,22(5):504-525

[9]Ding C,He X,Zha H,et al.Spectral M in-M ax cut for Graph

Partitioning and Data Clu sterin g[C]∥Proc.of the IEE E Intl

Conf.on Data M ining.2001:107-114

[10]M eila M,Xu L.M ultiw ay cuts and s pectral clu sterin g.U.

W ashington Tech Report.2003

[11]Zhou D,Bous qu et O,Lal T N,et al.S cholk ppf:Learning w ith

Local and Global C onsistency.Advances in Neural Inform ation

Processing Sys tems∥T hrun,S.L.Saul and B.Scholkopf,eds.

M IT Press,Camb ridge,M A,US A,2004,16:321-328

[12]Verma D,M eila M.A comparison of spectral clu stering algo-

rithm s.Technical report,2003.UW CS E Tech nical report03-

05-01

[13]Perona P,F reem an W T.A factorization app roach to grouping

∥H.Burkardt and B.Neu mann,eds.P roc.ECCV.1998:655-670 [14]S cott G L,Longuet-H iggins H C.Featu re grouping by relocal-

ization of eigenvectors of th e p roximity matrix∥P roc.British

M achine Vision Conference.1990:103-108

[15]Kannan R,Vempala S,Vetta A.On clusterings-good,bad and

spectral.In FOCS,2000:367-377

[16]Ding C,He X F,Zha H Y,et al.A min-max cu t algorithm for

g raph partitioning and data clus tering[A]∥T he2001IEEE In-

ternational Conference on Data mining.S an Jos e,US A,2001 [17]A lper t C,Kah nh A,Yao S.S pectral partitioning:The m ore eig-

envecto rs,the better.Discrete Applied M ath.,1999,90:3-26 [18]M alik J,Belongie S,Leung T,et al.Contour and texture analy-

sis for image segmentation.In Perceptu al Organization for Arti-

ficial Vision System s.Kluw er,2000

[19]Ng A Y,Jordan M I,W eis s Y.On spectral clu stering:Analy sis

and an algorithm∥T.G.Dietterich,S.Becker,and Ghahramani,

eds.Advan ces in Neural Information Proces sing Sys tems,Cam-

bridge,M A,M IT Press,2002,14:849-856

[20]M eila M,S hi J.Learning segmentation by random w alks.In

NIPS,2000:873-879

[21]Chan P K,Schlag D F,Zien J.S pectral k-w ay ratio-cut partitio-

ning and clustering[J].IEE E Tran on Compu ter Aided Des ign

of Integ rated Circuits and Sys tems,1994,13(9):1088-1096 [22]Luxb urg U.A Tutorial on Spectral Clu stering.Technical re-

port.2006

[23]Brand M,Kun H.A Unifying T heorem for S pectral Embedding

and C lustering[C]∥P roceeding of the9th International C onfer-

ence on Artificial Intelligen ce and S tatistics.Key West,Florida,

2003

[24]Dhillon S,Guan Y,Kulis B.A unified view of kern el k-mean s,

spectral clus tering and graph cuts.University of Texas at Au s-

tin UTCS Technical Report T R-04-25.2004

[25]Zhang T,Ando R.Analysis of spectralkerneldesign based semi-

su pervised learning∥Y.Weiss,B.Scholkopf and J.Platt,eds.

Advances in neural information p rocessing systems18.Cam-

bridge,M A:M IT Press,2006

[26]David S,Luxbu rg U,Pal D.A sober look on clustering stability

∥G.Lugosi and H.Sim on,ed s.Proceedings of the19th Annual

C onference on Learning T heory(COLT).Berlin,S pringer,

2006:5-9

[27]Bie T D,C ristianini N.Fast SD Prelaxations of graph cu t clu s-

tering,tran sduction,and other combinatorial prob lem s.JM RL,

2006(7):1409-1436

[28]Lang K.Fixing tw o w eaknesses of the spectral method∥W eiss Y,

Scholkopf B,Platt J,eds.Advances in Neural Information Process-

ing Systems,Cambridge,MA:M IT Press,2006,18:715-722

(上接第13页)

[36]Doan A,M adhavan J,Domin gos P,et al.Ontology matching:A

machine learning app roach[C]∥S.Staab&R.S tuder,eds.

Handbook on On tologies in Information Sy stems,S pringer-Ver-

lag,2004:397-416

[37]Sch nurr H-P,Angele J.Do Not Use T his gear with a S witching

Lever!Automotive In dustry Ex perience w ith S emantic Guides

[C]∥4th International Semantic W eb Conference

(IS WC2005).LNCS3729,2005:1029-1040

[38]魏哲雄,冯志勇.基于字典技术的本体整合系统[J].计算机应

用,2007,27(2):428-430

[39]Noy N F,M us en M A.An Algo rithm for M ergin g and Aligning

Ontologies:Au tomation and Tool S upport[C]∥Proceedings of

the W orkshop on Ontology M anagement at the Sixteenth Na-

tional Conference on A rtificial Intelligen ce(AAAI-99).Orlan-

do,1999

[40]N oy N F,M u sen M A.SM A RT:Automated Sup port for On-

tology M ergin g and Alignment[C]∥Proceedings of the Tw elfth

W orks hop on Know ledge Acquisition M odeling an d M anage-

ment.Banff,Canada,1999(7)

[41]Horridge M,Knublauch H,et al.A p ractical guide to b uilding

OW L on tology using the protégé-OW L Plugin and CO-ODE

tools[EB/O L].T he University of M anchester,2004(8) [42]N oy N F,Klein M.On tology evolu tion:Not the sam e as sch e-

ma evolu tion[J].Know ledge and Information S ystem s,2004,6

(4):428-440[43]Klein M,Noy N F.A C om ponen t-Based Framewo rk for Ontol-

ogy Evolution[C]∥Works hop on On tologies and Distribu ted

Sy stems at IJCAI-03.Aeapu lco,M exico,2003

[44]Dou Dejiang,M cDermott D,Qi Peishen.Ontology Translation

on the Semantic W eb[J]∥Proceedings Int'l C on f.on Ontolo-

gies,Datab ases and Applications of Seman tics(ODBA-

SE2003).LNCS2888,2003:952-969

[45]AIFB.University of Karlscru he.KAON Demo Page[EB/OL].

h ttp://kaon.semanticw eb.org/.(Accessed on Oct.6,2006)

[46]h ttp://w w w.daml.org/language/.(Accessed on M ar.20,

2004)

[47]Ding Yin g.Ontology M anagement Sys tem[E B/OL].http://

sw-po rtal.deri.at/papers/deliverables/d17v01.pdf,2004.8.

31.(Acces sed on Dec21,2006)

[48]H arrison R,C han C W.Dis trib uted ontology management sy s-

tem[C]∥Canadian Conference on Electrical and Compu ter E n-

gineering.2005(5)

[49]Ontoprise.OntoS tu dio[EB/OL].http://ontow orld.org/wiki/

OntoStudio.(Accessed on Dec.16,2006)

[50]Euz enat J.Evaluating on tology alignment methods[C]∥Dag s-

tuhl S emin ar Proceedings.Semantic In teroperability and In te-

gration.2005

[51]M aedche A,S taab S.Discoverin g C on cep tual Relations from

T ex t[C]∥Proceeding s of the14th European Conference on Ar-

tificial In telligence(EC AI2000).Am sterdam:IOS Pres s,

2000:321-325