《谱聚类算法综述_蔡晓妍》由会员分享，可在线阅读，更多相关《谱聚类算法综述_蔡晓妍（5页珍藏版）》请在金锄头文库上搜索。
1、* ) 基金项目: 国家 863 计划资助项目( 2005AA147030)。蔡晓妍? 博士生, 主要研究方向为智能信息处理、 网络与信息安全; 戴冠中? 教授, 博士生导师, 主要研究领域为自动控制、 信息安全; 杨黎斌? 博士生, 研究方向为网络与信息安全、 嵌入式系统。计算机科学 2008Vol ? 35?7 ?谱聚类算法综述* )蔡晓妍? 戴冠中 ? 杨黎斌 ( 西北工业大学自动化学院? 西安 710072) ? 摘? 要? 谱聚类算法是近年来国际上机器学习领域的一个新的研究热点。谱聚类算法建立在谱图理论基础上, 与传统的聚类算法相比, 它具有能在任意形状的样本空间上聚类且收敛于全局最
2、优解的优点。本文首先介绍了图论方法 用于聚类的基本理论, 然后根据图划分准则对谱聚类算法进行分类, 着重阐述了各类中的典型算法, 并对算法进行了 比较分析, 最后进行总结并提出了几个有价值的研究方向。关键词? 谱聚类, 谱图理论, 图划分 ?Survey on Spectral Clustering AlgorithmsCAI Xiao ?yan? DAI Guan?zhong ? YANG Li ?bin(College of Automation, Northwestern Polytechnical University, Xi? an 710072, China) ?Abstract?
3、 Spectral clustering algorithms are newly developing technique in recent years. Unlike the traditional cluste? ring algorithms, these apply spectral graph theory to solve the clustering of non ?convex sphere of sample spaces, so thatthey can be converged to global optimal solution. In this paper, th
4、e clustering principle based on graph theory is first in? troduced, and then spectral clustering algorithms are categorized according to rules of graph partition, and typical algo?rithms are studied emphatically, as well as their advantages and disadvantages are presented in detail. Finally, some va
5、l? uable directions for further research are proposed.Keywords? Spectral clustering, Spectral graph theory, Graph partition ?1? 引言聚类分析是机器学习领域中的一个重要分支 1, 是人们 认识和探索事物之间内在联系的有效手段。所谓聚类( clus?tering) 就是将数据对象分组成为多个类或簇( cluster) , 使得 在同一簇中的对象之间具有较高的相似度, 而不同簇中的对象差别较大。传统的聚类算法, 如 k?means 算法、 EM 算法等 都是建立在凸球形的样
6、本空间上, 但当样本空间不为凸时, 算法会陷入局部最优。 为了能在任意形状的样本空间上聚类, 且收敛于全局最优解, 学者们开始研究一类新型的聚类算法, 称为谱聚类算法 ( Spectral Clustering Algorithm)。该算法首先根据给定的样 本数据集定义一个描述成对数据点相似度的亲合矩阵, 并计算矩阵的特征值和特征向量, 然后选择合适的特征向量聚类 不同的数据点。谱聚类算法最初用于计算机视觉 3、 VLSI 设计4等领域, 最近才开始用于机器学习中 5, 并迅速成为国际 上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问
7、题, 是一种点对聚类算法, 对数据聚类具有很好的应用前景。但由于其涉及的理论知识较多, 应用也还处于初级阶段, 因此国内这方面的研究报道非 常少。本文作为一篇综述性文章, 旨在向读者介绍这种新型的聚类算法, 使研究人员尽可能详细地总结该领域的研究现 状。后续篇幅安排如下: 第 2 部分介绍了图论方法用于聚类的基本理论; 第 3 部分根据图划分准则, 将谱聚类算法分为两类, 详细研究了各类中的代表性算法, 并对算法进行了比较分 析; 最后对本文进行总结, 提出了几个有价值的研究方向。2 ? 基本理论2. 1? 图划分准则 谱聚类算法的思想来源于谱图划分理论2。假定将每个数据样本看作图中的顶点 V
8、, 根据样本间的相似度将顶点间 的边 E 赋权重值 W, 这样就得到一个基于样本相似度的无向加权图 G= (V, E)。那么在图 G 中, 就可将聚类问题转化为 在图 G 上的图划分问题。基于图论的最优划分准则就是使 划分成的两个子图内部相似度最大, 子图之间的相似度最小 5。划分准则的好坏直接影响到聚类结果的优劣。常见的 划分准则有 Minimum cut, Average cut, Normalized cut, Min? max cut, Ratio cut, MNcut 等。下面我们将分别介绍这几种准则。 2. 1. 1? 最小割集准则6(Minimum cut) 谱图理论中, 将图
9、G 划分为 A , B 两个子图( 其中 A ? B = V , A ?B= ?)的代价函数为:cut( A, B)=? u ? A , v? Bw (u, v)( 1)Wu 和 Leahy 提出最小化上述剪切值来划分图 G, 这一 划分准则被称为最小割集准则。他们用这个准则对一些图像 进行分割, 并产生了较好的效果, 同时他们也注意到, 该准则容易出现歪斜( 即偏向小区域) 分割。Shi 和 Malik 提出的规 范割集准则及 Hagen 和 Kahng 提出的比例割集准则均可避免这种情况的发生。?14?2. 1. 2? 规范割集准则 5( Normalized cut) Shi 和 Mal
10、ik 在 2000年根据谱图理论建立了 2 ?way 划分 的规范割目标函数(Ncut) :Ncut( A, B)=cut(A , B) assoc( A, V)+cut(A , B) assoc(B, V) 其中 assoc( A, V) =? u ? A , t? Vw (u, t)(2)最小化 Ncut 函数被称为规范割集准则。该准则不仅能 够衡量类内样本间的相似程度, 也能衡量类间样本间的相异程度。 Shi 和 Malik 同时还提出了规范关联目标函数( Nassoc) :Nassoc(A , B) =assoc(A , A ) assoc(A , V)+assoc( B, B) as
11、soc( B, V )(3)assoc( A, A) 与 assoc( B, B) 分别是子图 A, B 内所有顶点 之间的连接权值之和。这一无偏函数进一步反映了类内样本 间互相连接的紧密程度。同时, 可以看出 Ncut 函数与 Nas?soc 函数是相关的, 它们满足关系: Ncut( A, B) = 2- N assoc ( A, B) 。因此, 最小化 Ncut 函数等价于最大化 Nassoc 函数,但通常情况下都是通过最小化 Ncut 函数获取图的最优划分。 2. 1. 3? 比例割集准则 7( Ratio cut) Hagen 和 Kahng 提出了比例割目标函数(Rcut) :Rc
12、ut=cut(A , B) min( | A | , | B| )(4)其中| A | , | B| 分别表示子图 A , B 中顶点的个数。最小化 Rcut 函数只考虑了类间相似性最小, 减小了过分割的可能性, 但运行速度较慢。 2. 1. 4? 平均割集准则 8( Average cut) 平均割目标函数为:Avcut(A , B) =cut( A, B) | A|+cut( A, B) | B|(5)可以看出 Avcut 和 Ncut 函数都表示无向图 G 中边界损 失与分割区域相关性的比值之和, 因此最小化 Avcut 与 Ncut目标函数都能产生较准确的划分。其共同缺点是倾向于欠分
13、割且易分割出只包含几个顶点的较小子图。文献 5 通过实验发现, 当把 Normalized cut 和 Average cut 准则分别用于同 一图像的分割问题时, Normalized cut 准则能够产生更好的划分结果。 2. 1. 5? 最小最大割集准则 9( Min?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)我们将这个目标函数称为最
14、小最大割函数, 或简称为 Mcut 函数。最小化该函数可避免分割出仅包含几个顶点的 较小子图, 因此它倾向于产生平衡割集, 但实现速度较慢。Mcut 与 Ncut 一样满足类间样本间的相似度小而类内样本间 的相似度大的原则, 与 Ncut 具有相似的行为, 但当类间重叠较大时, Mcut 比 Ncut 更加高效。 2. 1. 6? 多路规范割集准则 10(Multiway Normalized cut) 上述五种划分准则所使用的目标函数都是将图 G 划分为 2 个子图的 2 ?way 划分函数, Meila 提出一种可以将图 G 同时划分为k 个子图的k?way 规范割目标函数:MNcut =
15、cut(A1, V- A1) assoc( A1, V)+cut( A2, V- A2) assoc(A2, V)+? +cut(Ak, V- Ak) assoc(Ak, V)(7)Melia 指出 Ncut 和 MNcut 的差异之处仅在于所使用的 谱映射不同, 并且当 k= 2 时, MNcut 与 Ncut 等价。多路规范割集准则在实际应用中合理有效, 但其优化问题通常难以 解决。2. 2? 相似矩阵、 度矩阵及 Laplacian 矩阵 由于图划分问题的本质, 求图划分准则的最优解是一个NP 难问题。一个很好的求解方法是考虑问题的连续放松形 式, 这样便可将原问题转换成求解相似矩阵或
16、Laplacian 矩阵 的谱分解, 因此将这类方法统称为谱聚类, 可以认为谱聚类是对图划分准则的逼近 11。 相似矩阵通常用 W 或A 表示, 有时也称为亲合矩阵( Af?finity Matrix) 。该矩阵的定义为:Wij= exp(-d(si, sj) 2?2)( 8)其中 si表示每个数据样本点, d( si, sj)一般取| | si- sj| |2, ? 为事先指定的参数。 将相似矩阵的每行元素相加, 即得到该顶点的度, 以所有度值为对角元素构成的对角矩阵即为度矩阵, 度矩阵常用 D 表示。Laplacian 矩阵分为非规范 Laplacian 矩阵和规范 Lapla? cian 矩阵。非规范 Laplacian 矩阵表示为 L = D - W, 规范Laplacian 矩阵有两种形式, 分别是:Lsym= D-1 2LD-1 2= I- D-1 2WD-1 2Lrw= D- 1L= I- D- 1W( 9) 2. 3? 势函数、 Fiedler 向量及谱势函数为表示某样本划分归属的指示向量( indicator
