谱聚类算法——精选推荐

转载⾃：

1、问题描述

　　谱聚类(Spectral Clustering, SC)是⼀种基于图论的聚类⽅法——将带权⽆向图划分为两个或两个以上的最优⼦图(sub-Graph)，使⼦图内部尽量相似，⽽⼦图间距离尽量距离较远，以达到常见的聚类的⽬的。　　对于图的相关定义如下：

对于⽆向图G = (V,E)，V表⽰顶点集合，即样本集合，即⼀个顶点为⼀个样本；E表⽰边集合。设样本数为n，即顶点数为n。

权重矩阵：W，为n*n的矩阵，其值wi,j为各边的权值，表⽰顶点 i，j（样本）之间的相似性。对于任意wi,j = wj,i ，wi,i=0，即对⾓线上元素为0。

通常情况下，相似性⼩于某⼀阈值的两个顶点不相连，否则连接两顶点的边的权值为两个样本的相似性度量函数的值。

定义n*n的矩阵：D，其第 i ⾏，第 i 列的元素（对⾓线上）元素为W第 i ⾏所有元素的和，即 i 顶点与其他所有顶点的相似性之和。将图G分割为⼦图G1,G2，所要断开的边的权重之和为损失函数：

如下图给出⼀个六个样本所对应的图：此例中对应的损失函数为 w1,5 + w3,4 = 0.3。

　　谱聚类的⽬的就是找到⼀个较好的划分准则，将整个样本空间形成的图分成为各个⼦图(sub-Graph)，⼀个⼦图即为⼀个类别。根据分割⼦图的准则，可以将其分为不同的谱聚类（Minimum Cut、Ratio Cut and Normalized Cut等）。　　讲具体算法之前，回顾⼀些线性代数有关的结论，不清楚的可以查阅相关资料：

Ax = λx ，则λ为A的特征值，x为对应λ的特征向量。

对于实对称矩阵A，其特征向量正交。即当i ≠ j时， = 0（<,>表⽰内积）。对于正定矩阵，其所有特征值都⼤于0；对于半正定矩阵，其所有特征值都⼤于等于0

2、问题转化

　　⾸先看看这个损失函数，对其进⾏如下变换：1、定义qi如下：

当顶点 i 属于⼦图G1中时，qi = c1。顶点 i 属于⼦图G2中时，qi = c2。2、Cut(G1,G2)变形：

当且仅当i，j属于不同⼦图时，(qi - qj)2/(c1 - c2)2 = 1，否则(qi - qj)2/(c1 - c2)2 = 0。常数1/2：由每个 i 遍历⼀遍 j ，这样，被剪断的边的权值被计⼊了两次，所以除以2。3、Cut(G1,G2)分⼦变形：

4、拉普拉斯矩阵 L = D - W，满⾜：

5、问题转化：

由第3步，等式⾸尾可知：因此，总结上述推导，有下式：

因为wi,j ≥ 0，所以qTLq对于任意的q ≠ 0，都有 qTLq ≥ 0，所以L为半正定的矩阵，其L为实对称矩阵。有如下三条性质：1. L所有特征值 ≥ 0 ，且特征值对应的特征向量正交。

2. L有⼀个等于0的特征值，其对应的特征向量为[1,1,...,1]T，此值的具体意义，后⽂介绍。3. 所有⾮零的特征向量与[1,1,...,1]T的内积为0，即正交。

第⼀点在⽂章开头结论中以提及，不做详述，对于第2点，我们来好好看看这个L。对于⽂章最初的样本集，有如下矩阵，下图分别对应于W,D,L矩阵。

对于向量λ0=[1,1,1,1,1,1]T总能使得，L*λ0 = 0 = 0*λ0，所以0总是L的特征值，且0特征值对应的特征向量为[1,1,...,1]T。第2点理解了，第3点也⾃然可以理解了。

　　因此，最终将最⼩化损失函数Cut(G1,G2)问题转化为最⼩化多项式qTLq，只不过对应于不同的准则，其限制条件有所不同，可以利⽤的性质求解，接下来将逐⼀介绍。

3、划分准则

　　⾸先，来看看型如 qTLq 的多项式的优化问题。在此之前，先看看（具体见维基百科），此处只列出部分性质：对于Rayleigh quotient定义如下：

对于⼀个给定的M，R(M,x)的最⼩值为λmin（为M的最⼩特征值），当且仅当x = vmin（为对应的特征向量）时，同样的，R(M,x) ≤λmax，且R(M,vmax) = λmax。

利⽤拉格朗⽇乘数法，可以求解多项式的 （极值点）问题（具体过程参考：Formulation using Lagrange multipliers）：

对于多项式 ，s.t. 求解极值。

加⼊拉格朗⽇乘数后，求导可得Mx = λx ，即x为M的特征向量时，R(M,x)取得极值，带⼊上式可得极值为R(M,x) = λ，即对应的特征值。

我们第⼆节最后的式⼦再强调⼀遍，以便后⽂阅读，此式记为公式(1)：

3.1、MINIMUM CUT ⽅法

　　Minimum Cut 的⽬标函数即为公式(1)，对于c1，c2取任何数都不影响分类结果（当然不能相等，因为⽆法区分相等的东西，c1为样本属于G1的标签，同理c2为样本属于G2的标签，标签相等时，就⽆法区分），但是会影响求解过程：c1，c2 影响瑞丽熵求的求解条件是否满⾜，即

。为了⽅便求解，我们选择如下，

　　当c1 = - c2 = 1时，即q为：　　此时最⼩化公式(1)的求解变为：

限制条件中，第⼀条，可以由向量q元素取值只能是1或-1；第⼆条，上⽂已提及，e为元素全为1的向量，e为L的最⼩特征向量，L的所有特征向量正交。

　　此问题求解⽅法在第3节和3.1之间已经提及，其最优分类⽅案q为L的最⼩特征值对应的特征向量，L的最⼩特征值0（即为⽬标函数最⼩值），对应的特征向量即为e。可以解释：可以找到⼀个使⽬标函数为0（所剪切边权重之和为0）的⽅案，为：所有样本属于G1类（因为q此时对应的值全为1，对应i∈G1），0个样本属于G2类。这是始终存在的但毫⽆意义的分类。因此，将其排出（即第⼆限制条件的作⽤）。　　综上，求解上述问题，只需求解L的第⼆⼩的特征值对应的特征向量，对特征向量进⾏聚类。此时问题的转变：将离散的问题的求解转为连续问题的求解（此处将问题松弛化了，使得NP-hard问题变为了P问题），最后再进⾏离散化。

连续问题：求解多项式qTLq的最⼩值 =》 求L的特征值及其特征向量。

离散化：最初的qi为：1属于G1，-1属于G2。最后求得的q并⾮为最初定义的 qi 中的离散值，值的⼤⼩只作为⼀种指⽰。可以很容易的找到⼀个合理的阈值，分割最终的q，即 qi > 0 属于G1，qi < 0 属于G2。　　问题：这样的⽬标函数忽略的孤⽴点的存在，如下图：

wh,c < wb,d + wc,g 时，聚类结果为H为⼀类，其他所有点为⼀类。若对应于 0.3 < 0.2 + 0.2，将导致图中Smallest cut的结果，这样的分类显然是不合理的，我们更希望的是Best cut的结果。为了避免这样的想象，使得类别数量相对均衡，引⼊了Ratio Cut ⽅法。

3.2、RATIO CUT ⽅法

　　先看看Ratio Cut 的⽬标函数 公式(2)：

其中n1为属于G1中的顶点数，n2同理。对应上图分析，若为图中Smallest cut，则RCut(G1,G2) = 0.3/1 + 0.3/7 = 0.34，为图中Best cut，则RCut(G1,G2) = (0.2+0.2)/4 + (0.2+0.2)/4 = 0.2，显然避免了这种情况，不仅考虑了剪断边的权值，还考虑了各类别中样本数量的均衡。　　此时要转化为瑞丽问题，将qi定义如下：

带⼊公式(2)为（别忘了n1+n2=n，n为常数）：

此时⼜问题以转化为瑞丽熵可求解的问题：

限制条件qTq：

接下来的⼯作于3.1相同。

3.3、NORMALIZED CUT ⽅法

　　上述⽅法都没有考虑⼦图内部的权重系数。Normalized Cut加⼊了对⼦图内部的权重。⽬标函数如下公式(3)：

其中d1为G1内所有边权重之和加上Cut(G1,G2)，d2为G2内所有边权重之和加上Cut(G1,G2)，d = d1 + d2 - Cut(G1,G2)。如下图所⽰：(d1=asso(A,A)+cut(A,B)，d2=asso(B,B)+cut(A,B))

为了转化问题，将qi定义如下：带⼊公式(3)为:

问题转化为（其实这是⼀个Generalization Rayleigh quotient模型）：

其中限制条件为：

此处的求解，仍然是将⽬标函数加上第⼀个限制条件与拉格朗⽇乘数后求导，不同的限制条件中多了⼀个D矩阵，求导后与之前的结果（Mx= λx）稍有不同。step1：

step2：

step3：

step4：

　　此时，求解归⼀化的拉普拉斯矩阵(Normalized Laplacian，对⾓线元素全为1) L’ = D-1/2 L D-1/2 的特征值及其对应的特征向量即可。 因为 L 和 L’ 的特征值是相同的，特征向量的关系为 q’ = D1/2q，所以可以求L’的特征值对应的特征向量，最后在乘以D-1/2即可求得q。(以上提及的特征向量皆为第⼆⼩特征值对应的特征向量)

4、总结

　　以上提及皆为聚类为两类的情况，当使⽤谱聚类进⾏K聚类是，即可选取除特征值为0以外的，前K⼩的特征值对应的特征向量(⼤⼩为n*1），组成⼀个特征矩阵（以特征向量为列组成的⼤⼩为n*k的矩阵）。矩阵中，⾏向量即为该⾏对应样本的特征空间表⽰。 最后利⽤k-means等其它聚类算法进⾏聚类。

　　按照划分准则的不同，可以将谱聚类分为两种：Unnormalized Spectral Clustering & Normalized Spectral Clustering，区别在于Laplacian矩阵是否是规范化，Ratio Cut & Minimum Cut 皆为 Unnormalized。

1、Unnormalized Spectral Clustering算法

　　算法输⼊：样本相似矩阵S和要聚类的类别数K。

根据矩阵S建⽴权重矩阵W、三⾓矩阵D；建⽴Laplacian矩阵L；

求矩阵L的（除0外）前K⼩个特征值及其对应的特征向量；

以这K组特征向量组成新的矩阵，其⾏数为样本数，列数为K，这⾥就是做了降维操作，从N维降到K维；使⽤k-means等其它聚类算法进⾏聚类，得到K个Cluster。

2、Normalized Spectral Clustering算法

　　算法输⼊：样本相似矩阵S和要聚类的类别数K。

根据矩阵S建⽴权重矩阵W、三⾓矩阵D；建⽴Laplacian矩阵L以及L’ = D-1/2 L D-1/2 ；

求矩阵L’的（除0外）前K⼩个特征值及其对应的特征向量；利⽤q’ = D1/2q求得对应的K个q；（q不是L的特征向量）

以这K组特征向量组成新的矩阵，其⾏数为样本数N，列数为K；使⽤k-means等其它聚类算法进⾏聚类，得到K个Cluster。

Spectral Clustering的各个阶段为：

选择合适的相似性函数计算相似度矩阵来建⽴权重矩阵W；如：

计算矩阵的特征值及其特征向量，⽐如可以⽤Lanczos迭代算法；

如何选择K，可以采⽤启发式⽅法，⽐如，发现第1到m的特征值都挺⼩的，到了m+1突然变成较⼤的数，那么就可以选择K=m；使⽤k-means算法聚类，当然它不是唯⼀选择；

Normalized Spectral Clustering在让Cluster间相似度最⼩⽽Cluster内部相似度最⼤⽅⾯表现要更好，所以⾸选这类⽅法。

Spectral Clustering的性能：

⽐传统k-means要好，Spectral Clustering 是在⽤特征向量的元素来表⽰原来的数据，并在这种“更好的表⽰形式”上进⾏ K-means，这种“更好的表⽰形式”是⽤ Laplacian Eigenmap 进⾏降维的后的结果 。

计算复杂度⽐ k-means 要⼩。这个在⾼维数据上表现尤为明显。例如⽂本数据，通常排列起来是维度⾮常⾼（⽐如，⼏千或者⼏万）的稀疏矩阵，对稀疏矩阵求特征值和特征向量有很⾼效的办法，得到的结果是⼀些 k 维的向量（通常 k 不会很⼤），在这些低维的数据上做 k-means 运算量⾮常⼩。但是对于原始数据直接做 k-means的话，虽然最初的数据是稀疏矩阵，但是 k-means 中有⼀个求Centroid 的运算，就是求⼀个平均值：许多稀疏的向量的平均值求出来并不⼀定还是稀疏向量，事实上，在⽂本数据⾥，很多情况下求出来的 Centroid 向量是⾮常稠密，这时再计算向量之间的距离的时候，运算量就变得⾮常⼤，直接导致普通的 k-means 巨慢⽆⽐，⽽ Spectral Clustering 等⼯序更多的算法则迅速得多的结果。