谱聚类算法实现

谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法。

将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。

"带权无向图"这个词太学术了，我们换一种叫法，即：相似度矩阵。

假设我们有一个相似度矩阵，矩阵中存的是所有对象的两两相似度。

 

那么这个矩阵应该有如下性质：

1. 矩阵为N * N，N为对象总数
2. 矩阵对角线的值为0，自己和自己相似个毛啊
3. 矩阵为对称矩阵，及相似度是无向的

我们将该矩阵记为：W。

 

谱聚类的任务就是根据这个相似度矩阵，将这一大堆对象，分成不同的小堆，小堆内部的对象彼此都很像，小堆之间则不像。

 

谱聚类本身也提供了好几种不同的分割(cut)方法，每种方法对应一种优化目标。

本文只介绍其中比较常见，也是比较实用，而且实现起来也比较经济的一种：Nomarlized cut.

 

说白了，就是你最应该掌握和使用的一种，好了，进入正题。

 

当你得到一个相似度矩阵W后，即可通过以下几个步骤，来得到对应的图分割方案：

1. 计算对角矩阵D[N*N]。，公式如下：  

 

 

 

 

   D矩阵为对角矩阵，对角线上的值为W矩阵中对应行或列的和。

 

2. 计算拉普拉斯矩阵(Laplacian) L：

3.  归一化L矩阵

4. 计算归一化后L矩阵的K个最小特征值及对应的特征向量

    将K个特征向量竖着并排放在一起，形成一个N*K的特征矩阵，记为Q。

 

5. 对特征矩阵Q做kmeans聚类，得到一个N维向量C。

    分别对应相似度矩阵W中每一行所代表的对象的所属类别，这也就是最终的聚类结果。

 

此外：

关于第3步中，对拉普拉斯矩阵归一化时，归一化公式进行变换得到：

 

 

            令：

 

 

则在第4步中，我们可以将求L的K个最小特征值及其对应的特征向量的问题，转化为求矩阵E的K个最大的特征值及其对应的特征向量。

        ---可以证明：L的K个最小特征值对应的特征向量，分别对应于E的K个最大的特征值对应的特征向量。

            且矩阵L的最小特征值为0，对应于矩阵E最大的特征值为1.矩阵L的第K小特征值等于1-矩阵E的第K大特征值

 

之所以要这么做，是因为在数值计算中，求矩阵的最大特征值，往往要比求最小特征值更方便和高效。

 

OK，至此，谱聚类就完成了，关于谱聚类的其他问题，诸如公式的推导，以及谱聚类的物理意义等，可参考博文：谱聚类算法。

 

谱聚类的实现很简单，按照上述5个步骤按部就班即可，在matlab中只需寥寥数行：

 

function C = SpectralClustering(W, k)
    [n,m] = size(W)  
    s = sum(W);
    D = full(sparse(1:n, 1:n, s));
    E = D^(-1/2)*W*D^(-1/2);
    [Q, V] = eigs(E, k);
    C = kmeans(Q, k);
end

 

在整个实现过程中，比较麻烦的就是E矩阵特征值的求解。

在自己实现时，可以调用已有的线性代数的包来完成这一步。