算法简介

算法步骤

划分准则(最小割集准则 规范割集准则 比例割集准则 平均割集准则 最小最大割集准则 多路规范割集准则)

典型的算法(二路谱聚类算法 多路谱聚类算法)

算法的新进展

面临的问题(如何构造相似度矩阵 如何自动确定聚类数目 如何选择特征向量 如何解决模糊聚类的问题 如何提高谱聚类的运行速度)

算法简介

谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。

该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量 ， 然后选择合适 的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉 、VLS I 设计等领域， 最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。

谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。

算法步骤

谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。

虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤：

1) 构建表示对象集的相似度矩阵W；

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提出了比例割集准则。

平均割集准则

在计算机视觉中，图像原始像素条理有序地分组可以通过寻找场景结构图(Scene Structure Graph)中松散耦合的结点来完成，于是原始像素的聚合问题就转化为场景结构图的分割。Sarkar和Soundararajan[62]提出了一种最小化两两分割之间相似度的计算方法并把它命名为平均割集准则。

最小最大割集准则

Mini cut准则容易出现分割出只包含几个顶点的较小子图的歪斜分割现象，Ratio cut和Normalized cut等在一定程度上可以避免这种现象，但是当类间重叠严重时歪斜分割现象仍旧会发生。Chris Ding等人提出的基于Min-max cut的图划分方法充分体现了“子图内部相似度最大，子图之间的相似度最小”原则，能够产生比较平衡划分。

上述五种划分都是不断地将图划分为2个子图的反复迭代运算过程，当划分函数的最小值满足一定的条件时迭代过程便会终止，相应的函数可以称为2-way划分函数。

多路规范割集准则

Meilă和Xu[64]认为可以同时把图划分为k个子图并于2004年提出了一种k-way规范割目标函数，而且对于参数k的选取问题也作了分析说明。

我们可以发现当k=2时，MNcut与Ncut两者是等价的。

典型的算法

根据谱聚类算法所使用的划分准则，可以把算法分为二路谱聚类算法和多路谱聚类算法，前者使用2-way划分准则而后者使用k-way划分准则。

二路谱聚类算法

PF算法。Perona和Freeman提出用相似度矩阵W最大特征值所对应的特征向量进行聚类指出对于块对角相似矩阵，特征向量中非零值对应的点属于同一类，零值对应的点属于另外一类。

SM算法。Meliă指出Ncut和MNcut的差异之处仅在于所使用的谱映射不同。多路规范割集准则在实际应用中合理有效，但其优化问题通常难以解决。Shi和Malik认为第二小特征值对应的特征向量，即Fiedler向量包含了图的划分信息，根据启发式规则在此向量中寻找划分点i使在该点上得到的Ncut(A,B)值最小，最后把向量中的值与Ncut准则函数的最小值进行比较，大于等于该值的点划分为一类，小于该值的点则划分到另外一类。

SLH算法。SLH重定位算法计算相似度矩阵W的前k个特征向量，参数k需要事先指定。

KVV算法。根据启发式规则在Fiedler向量中寻找划分点i使在该点上得到的Rcut(A,B)值最小的划分点，与SM算法相似；不同之处仅在于SM算法是寻找使Ncut(A,B)值最小的划分点。虽然在实际问题中KVV算法存在运行速度相对较慢的缺陷，但是算法减少了过分割的可能性。

Mcut算法。Ding根据谱图理论将最小最大割集准则函数的最优化问题转化为下式的第二小特征值的求解。

多路谱聚类算法

NJW算法。Ng，Jordan等人选取拉普拉斯矩阵的前k个最大特征值对应的特征向量构造新的向量空间R，在这个新的空间内建起与原始数据的对应关系，然后进行聚类。

田铮和李小斌等人利用矩阵的扰动理论逐步分析了理想情形、分块情形和一般情形下权矩阵的谱和特征向量与聚类之间的关系[69]：顶点集合V的类内离散程度充分小而类间离散程度充分大时，V 中所有顶点可以划分成的数目与相似度矩阵W特征值中大于1的特征值的数目相等。同时特征值的大小可以在一定程度上反映每一类所包含顶点的个数。相似度矩阵W的前k个单位正交特征向量组成的矩阵X 的行向量之间的夹角可以用来计算两个顶点是否属于同一类，如果属于同一类，那么这对应的行向量接近于相互平行；反之对应的行向量接近于相互正交。理想情况中，V中两个顶点属于同一类时，相应的行向量相互平行；属于不同的类，相应的行向量相互正交。

MS算法[70]。Meilă把基于马尔可夫链随机游动过程的概率转移矩阵运用到相似度矩阵的构造中，研究了这种随机游动的概率转移矩阵的特征值和特征向量，在随机游动的框架下了对Ncut进行了概率解释。该算法是用随机游动矩阵P的前k个非零特征值对应的特征向量构造矩阵，然后将矩阵中的行看成R空间中的点进行聚类，步骤与NJW算法相似。MS算法在实际的图像分割中取得了良好的效果，但是度矩阵D中对角线元素值之间存在较大的差别时就会导致较差的聚类效果。

算法的新进展

Zha和Dhillon等人研究了基于二分图G=<X, Y, W>上的谱聚类，发现最小化目标函数可以等同于与二分图相关联的边权重矩阵的奇异值分解。

Meila和Shi将相似性解释为Markov链中的随机游动，分析了这种随机游动的概率转移矩阵P=DW的特征向量(W为相似度矩阵)，并且利用随机游动对Ncut进行了概率的解释，提出了基于随机游动的新的算法。同时，在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类方法，在图像分割中取得了很不错的效果。

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

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

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

王玲，薄列峰，焦李成认为在聚类搜索过程中充分利用先验信息会显著提高聚类算法的性能，并分析了在聚类过程中仅利用成对限制信息存在的不足，提出利用数据集本身固有空间一致性先验信息的具体方法。在经典的谱聚类算法中同时引入两类先验信息的基础上提出一种密度敏感的半监督谱聚类算法，两类先验信息在指导聚类搜索的过程中能够起到相辅相成的作用，使得算法相对于仅利用成对限制信息的聚类算法在聚类性能上有了显著的提高。

王娜，李霞提出了一种基于监督信息特性的主动学习策略，找出同一类中距离相对较远的数据对象对和不同类中距离相对较近的数据对象对组成监督信息并将其引入谱聚类算法，构建新颖的主动半监督谱聚类算法，结果优于采用随机选取监督信息的谱聚类性能。

面临的问题

尽管谱聚类具有坚实的理论基础，相对于其它聚类方法具有许多优势，在实践中的应用领域在不断扩展，取得了不错的效果[38]，但是它仍然需要改进，尤其在下述几个方面：

如何构造相似度矩阵

如何创建相似度矩阵W，使其更加真实地反映数据点之间的近似关系，使得相近点之间的相似度更高，相异点之间的相似度更低，是谱聚类算法必须要解决的一个问题。高斯相似函数是经典谱聚类算法中计算两点间相似度的常用方法，虽然该函数使原始的谱聚类算法取得了一些成功，但尺度参数σ的选取问题使该函数具有明显的局限性。NJW算法[7]通过预先指定几个尺度参数σ的值，分别执行谱聚类，最后选取使聚类结果最好的σ作为参数，这种做法消除了尺度参数σ选取的人为因素，却增加了运算时间。

近年来，为了避免参数的选择问题，有学者提出在计算相似度时不使用高斯核函数。如Gong 等人[41]借鉴Wang Fei和Zhang Changshui[42]在半监督中使用的方法，将每个点的k 近邻对该点进行线性近似表示时所占的权重作为两点间的相似度。通过求n 个二次规划问题，就可以求得相似度矩阵W，降低了谱聚类算法对参数的敏感性，使算法更稳定。

如何自动确定聚类数目

由相似度矩阵得到拉普拉斯矩阵后，接下来要确定所需特征向量的数目，它与最终的聚类数目相等。虽然该数目可以由人工确定，但是准确地给出对聚类效率和最终的聚类质量有直接影响的数目值是个非常困难的问题。因此，如何自动确定聚类数目成为谱聚类需要解决的关键问题之一。

如何选择特征向量

大多情况下的谱聚类算法直接选择前k 个最大特征值对应的特征向量用于新向量空间的构造。2008 年Xiang等人[44]提出了“向量相关度”的概念，在使用该定义对向量的相关度进行衡量的基础上选出相关度最高的k 个特征向量用于新向量空间的构造。实验结果表明运用此方法选取拥有较高相关度和较多信息量的特征向量可以得到更加令人满意的聚类效果。

如何解决模糊聚类的问题

尽管在文档聚类中，谱聚类取得了很好的效果。但是在文档聚类中，单个词可能属于多个类，单个文档可能是多主题的文档。这就需要我们用模糊聚类的方法解决。如何确定基于模糊聚类与谱方法的联合：如何建立模糊标准的图划分的目标函数等都是谱聚类算法在模糊聚类中所面临的问题。如何运用到大规模学习问题中：由于谱聚类算法需要求解特征值和特征向量，所以计算复杂度相对较大，针对目前强烈的大规模数据处理要求研究高效、可扩展、适宜大规模学习问题的谱聚类算法。

如何提高谱聚类的运行速度

在谱聚类算法的聚类过程中需要求解矩阵的特征值与特征向量，求解非稀疏矩阵特征向量的复杂度O(n)，所以处理大规模数据集的时候，计算中形成的矩阵空间非常大，求解过程不但会非常耗时，而且所需要的内存空间也非常大，面临着内存溢出的危险，对计算机内存容量的要求变得较高。因此，如何提高算法的运行速度，降低运行所需的内存空间，减少算法运行的时间和空间代价是谱聚类算法在不断扩展应用领域的过程中所面临的另一关键问题。