文档介绍：Spectral Clustering algorithm谱聚类算法
组长:
小组成员:

聚类( clustering) 就是将数据对象分组成为多个类或簇(cluster) , 使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。传统的聚类算法, 如k-means算法、EM 算法等都是建立在凸球形的样本空间上, 但当样本空间不为凸时, 算法会陷入局部最优。
为了能在任意形状的样本空间上聚类, 且收敛于全局最优解, 学者们开始研究一类新型的聚类算法, 称为谱聚类算法(Spectral Clustering Algorithm) 。
算法概念:
该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵, 并计算矩阵的特征值和特征向量, 然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLSI 设计等领域, 最近才开始用于机器学习中, 并迅速成为国际上机器学习领域的研究热点。
谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题, 是一种点对聚类算法,对数据聚类具有很好的应用前景。
图划分准则:
谱聚类算法的思想来源于谱图划分理论。假定将每个数据样本看作图中的顶点V, 根据样本间的相似度将顶点间的边E赋权重值W, 这样就得到一个基于样本相似度的无向加权图G= (V, E) 。那么在图G 中, 就可将聚类问题转化为在图G 上的图划分问题。基于图论的最优划分准则就是使划分成的两个子图内部相似度最大, 子图之间的相似度最小。划分准则的好坏直接影响到聚类结果的优劣。常见的划分准则有Minimum cut, Average cut, Normalized cut, Min2 max cut, Ratio cut, MNcut 等。下面我们将分别介绍这几种准则。
基本理论:
谱图理论中, 将图G 划分为A , B 两个子图的代价函数为:

通过最小化上述剪切值来划分图G, 这一划分准则被称为最小割集准则。他们用这个准则对一些图像进行分割, 并产生了较好的效果, 同时他们也注意到, 该准则容易出现歪斜( 即偏向小区域) 分割。规范割集准则及比例割集准则均可避免这种情况的发生。
最小割集准则:(Minimum cut)

1
2
3
4
5
6

A
B
cut(A,B) =
Shi 和Malik 在2000 年建立了规范割集目标函数(Ncut) :
Vol(A)、 Vol(B)分别是子图A, B 内所有顶点之间的连接权值之和。
最小化Ncut 函数被称为规范割集准则。该准则不仅能够衡量类内样本间的相似程度, 也能衡量类间样本间的相异
程度。通常情况下都是通过最小化Ncut 函数获取图的最优划分。
规范割集准则:(Normalized cut)
Hagen 和Kahng 提出了比例割目标函数(Rcut) :
其中| A| , | B| 分别表示子图A, B 中顶点的个数。最小化
Rcut 函数只考虑了类间相似性最小, 减小了过分割的可能
性, 但运行速度较慢。
比例割集准则:(Ratio cut)
平均割目标函数为:
可以看出Avcut 和Ncut 函数都表示无向图G 中边界损失与分割区域相关性的比值之和, 因此最小化Avcut 与Ncut目标函数都能产生较准确的划分。其共同缺点是倾向于欠分割且易分割出只包含几个顶点的较小子图。文献通过实验发现, 当把Normalized cut 和Average cut 准则分别用于同一图像的分割问题时, Normalized cut 准则能够产生更好的划分结果。
平均割集准则: (Average cut)
最小最大割集准则要求最小化cut( A, B) 的同时, 最大化vol( A) 与vol( B) 。该准则可通过最小化下面的目标函数得以实现:
我们将这个目标函数称为最小最大割函数, 或简称为Mcut 函数。最小化该函数可避免分割出仅包含几个顶点的较小子图, 因此它倾向于产生平衡割集, 但实现速度较慢。Mcut 与Ncut 一样满足类间样本间的相似度小而类内样本间的相似度大的原则, 与Ncut 具有相似的行为, 但当类间重叠较大时,Mcut 比Ncut 更加高效。
最小最大割集准则: ( Minmax cut)
上述五种划分准则所使用的目标函数都是将图G 划分为2 个子图的划分函数, Meila 提出一种可以将图G同时划分为k 个子图的规范割目标函数:
其中:
Melia 指出Ncut 和MNcut 的差异之处仅在于所使用的
谱映射不同, 并且