一、算法步骤
谱聚类算法将数据集中的每个对象看作是图的顶点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>上的谱聚类，发现最小化目标函数可以等同于与二分图相关联的边权重矩阵的奇异值分解。
接受自己的失败面，是一种成熟，更是一种睿智;
