谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样
本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个
描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量,然后选择合适的特
征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域,最近才开
始用于机器学习中,并迅速成为国际上机器学习领域的研究热点。
论中的谱图理论基础上,其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算
法,对数据聚类具有很好的应用前景。
谱聚类算法将数据集中的每个对象看作是图的顶点V,将顶点间的相似度量化作为相应
顶点连接边 E 的权值,这样就得到一个基于相似度的无向加权图G(V, E ),于是聚类问题就可
以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大,子
虽然根据不同的准则函数及谱映射方法,谱聚类算法有着不同的
1) 构建表示对象
具体实现方法,但是这些实现方法都可以归纳为下面三个主要步骤:
2) 通过计算相似度矩阵或拉普拉斯矩阵的前 k 个特征值与特征向
3) 利用 K-means 或其它经典聚类算法对特征向量空间中的特
上面的步骤只是谱聚类算法的一个总体框架,由于划分准则、相似度
矩阵计算方法等因素的差别,具体的算法实现同样会有所差别,但其本质依然是图划分问题
的连续放松形式。
谱聚类算法将聚类问题就可以转化为图的划分问题之后,基于图论的划分准则的优劣直
接影响到聚类结果的好坏。常见的划分准则有 Mini cut,Average cut,Normalized cut,Min-max
cut,Ratio cut,MNcut 等。
在对图像分割中产生了较好的效果,但是该准则容易产生分割出只包含几个顶点的较小
子图的歪斜分割现象。
在 2000 年 Shi 和 Malik 根据谱图理论建立了 2-way 划分的规范割目标函数,此方法通过
计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之
和来衡量划分的优劣。
对于超大规模集成电路设计中的电路层次设计和分支划分问题,最大流最小割算法能够
发现其中的类结构(clustering structure),但是在实际中该算法通常会产生规模非常不一致
的电路分支;Kemighan-Lin 算法采用固定参数的方式可以得到规模具有一定可比性的分支划
分,由于电路中的分支倾向于自然结合的形成,所以通过预先设定分支规模进行划分的方法
存在明显的局限。针对以上的现象 Wei 和 Cheng 提出了比例割集准则。
平均割集准则
在计算机视觉中,图像原始像素条理有序地分组可以通过寻找场景结构图
Structure Graph)中松散耦合的结点来完成,于是原始像素的聚合问题就转化为场景结构图的
分割。Sarkar 和 Soundararajan[62]提出了一种最小化两两分割之间相似度的计算方法并把它
命名为平均割集准则。
Mini cut 准则容易出现分割出只包含几个顶点的较小子图的歪斜分割现象,Ratio cut 和
Normalized cut 等在一定程度上可以避免这种现象,但是当类间重叠严重时歪斜分割现象仍