谱聚类算法及其在图像分割中的应用

式(11)的是个最小特征值对应的特征向量所组成的子空间上。

2．3 算法描述

谱聚类算法由三个部分组成： 1．建立表示样本集的矩阵S。 2．计算S的k个特征值与特征向量

a．2-way：将原始样本数据映射到一维空间(k=1)；

b．k-way；将原始样本数据映射到由k个正交向量组成的k维空间S’。 3．将k维子空间S’ 的行作为样本的新的数据表示，且基于这种新的表示，将样本进行聚类。

a．2-way：在一维空间上根据目标函数最优原则划分，并且在划分好的两个子图上迭代划分；

b．k-way：利用传统的k-means或其它传统聚类算法在是维空间上进行聚类。 上述的描述是算法的一个框架，在具体的算法中，不同的算法在数据集矩阵S的表示上存在着不同，如：根据2-wayNcut的目标函数，S=D-1/2LD-1/2；根据随机游动关系，S=D-1 W 等。

3 谱聚类算法在图像分割中的应用

谱聚类方法最初是在图像分割中应用 shi和Malik[4]将像素作为顶点，根据像素的亮度和空间位置确定连接像素点问边的权值，利用2-wayNcut的谱聚类方法迭代地进行图的分割。该方法获得了满意的效果。

M.Gu,H.Zha等人[10]分析了在不规则图上进行k-way图划分的谱松散模型，并且根据该模型，提出了k-way Ncut与k-way Min-Max cut不同目标函数设置的下限值，同时分析了对应于最优解的特征空间或单个特征向量的代数结构，为将谱图理论运用到k-way图划分问题中，提供了理论基础。

Meila和shi[6]将相似性解释为Markov链中的随机游动，分析了这种随机游动的概率转移矩阵P=D-1W 的特征向量(其中：W是相似度矩阵)，并且根据随机游动对Ncut进行了概率的解释，提出了基于随机游动的新的算法。同时，在这

个解释框架下提出了多个特征相似矩阵组合下的谱聚类方法，在图像分割中也取得了很好的效果。

Zha[7]等人和Dhillon[7]研究了基于二分图G= 上的谱聚类。聚类目标是使得在最小化二分图上的不匹配顶点对间的边权重和最小，故目标函数可以用变形的Ncut表示；

将二分图的邻接矩阵W转换对称矩阵 ：

然后再根据谱图理论对二分图上划分的目标函数式(12)进行分析(与2的分析相似)。Zha等人与Dhilion发现最小化目标函数式(12)可以等同于与二分图相关联的边权重矩阵的奇异值分解。Dhillonc将其运用到文档聚类中，对CMU的Newsgroup20做了实验，取得了很好的效果。基于二分图模型，该算法同样也可以用于市场分析中交易-商品的分析，生物信息挖掘中的Gene expression profiles。

Zha等人分析了核k-means的方法，发现最小化核k-means的目标函数等同于一个由数据向量组成的Gram矩阵的迹最大化问题。同时，迹最大化问题的松散解可以通过Gram矩阵的部分特征分解获得。首次用谱松散的方法获得核k-means的目标函数的全局最优解。Dhillon[11]在此基础上，又研究了加权核k-means的目标函数，将其与Ncut目标函数建立联系，提出了一个可以单调递减Ncut值的新颖的加权核k-means算法。

Ncut是一个可行的聚类目标函数。它的求解是一个NP难问题。传统的方法是宽松的谱松散方法。Xing与Jordan则分析了对Ncut的半正定规划(SDP)模型。根据该模型，对Ncut提出了一个比谱松散更紧的下限。同时指出Ncut本身不能刻画最优的聚类，但它可以通过不同的松散方法获得合理的聚类。

图一所示为一种基于PCA加权的Ncut图像分割结果：

a.原始图像

b.子采样后训练图像

c.背景图像(1)

d.背景图像(2)

e.前景图像

f. Pepper图像细节

图一. 基于Ncut的“Pepper”图像分割结果

由于Ncut算法计算量比较大(为O(n3))，尤其在图像的数据量大时更为明显。

Uros Damnjanovic和Ebroul Izquierdo[11]提出了Acut算法，该算法是Ncut图像分割算法的一种简化处理。Acut算法只对感兴趣的区域进行处理，仅需要一步就能够提取出图像信息。通过利用两个像素之间和与其相邻像素的相关性来构造这两像素之间的相似矩阵，然后再利用Ncut算法来实现图像的分割。Acut算法图像分割结果如图二所示。

图二. Acut图像分割结果

谱聚类方法不仅用于无监督学习中[13]，也用于有约束的半监督学习中[15]。Kamvar[16]等人将PageRank的随机游动模型运用到相似度矩阵中，根据已知样本的类别修正相似度矩阵。然后根据谱聚类算法获得聚类结果。Bach与Jordan则是根据一个基于已知的划分与Ncut谱松散结果的误差，提出了新的目标函数。通过最小化新的目标函数推出新的谱聚类算法，获得聚类结果。

田铮和李小斌[17]针对谱聚类应用于图像分割时权矩阵的谱难以计算的实际问题，定义了像素点与类之间的距离, 给出一个采样数定理, 设计了一个图像的分层分割(hierarchical divisive)算法. 在利用该算法进行图像分割时, 由于既要对待分类的点进行随机抽样, 又要通过调节尺度因子来合并较小的类或拆分较大