谱聚类

对于一组模式{x1, x2, …, xn}，谱聚类：

基于无向加权图G=(V,E)，其中每个顶点vi对应一个xi，顶点vi和vj间的边有权值wij≥0

聚类问题就是要求G的连通子图

顶点vi的度为 di=wij求和

相应的，定义邻接矩阵W和度矩阵D(对角阵)

邻接矩阵W可根据模式间的相似度s(xi, xj)获得

无向图G=(V,E)的拉普拉斯矩阵(Laplacianmatrix) L=D-W

拉普拉斯矩阵有以下特性

–对任意n维向量f，有 f(T)Lf=1/2*[对其求和：wij*(fi-fj)平方]

L为半正定矩阵

L存在0特征值，且对应的特征向量所有元素均为1

理想情况下，若G能被分为若干个互不联通的连通子图，则可获得“完美”的聚类结果。

在上述情况下，L的0特征值个数即为类别数，且对于第k个0特征值，对应的特征向量e满足

1） ei=1，if xi属于Cluster i

2） ei=0，otherwise

尽管完美的聚类往往难以实现，我们仍可认为：

若L的某些特征向量对应的特征值较小，则该特征

向量给出了对聚类有用的信息

算法流程：

定义相似性度量s并计算相似性矩阵，设定聚类的类别数k

根据相似性矩阵S计算邻接矩阵W

计算拉普拉斯矩阵L

计算L的k个最小特征值对应的特征向量e1,…, ek

基于所求得的特征向量，定义一个k维空间，模式xi在该空间中表示为[e1i,…, eki]

利用任意现有的聚类算法，如k-means，在新空间中进行聚类。

谱聚类的本质实际就是先将模式隐射到一个新的空间，再以传统方式聚类

使用谱聚类须首先回答的一些问题：

给定相似度矩阵S，怎样获得邻接矩阵W？

若s(xi, xj)小于某一阈值，令wij= s(xi, xj)，否则为0

当xi, xj互为对方的k近邻时，令wij= s(xi, xj)

直接令wij= s(xi, xj)，这时G成为一个全连通图

如何确定类别数目？

将所有特征值由小到大排序，若第k个特征值与第k+1个特征值差别较大，则取k为类别数

对于L，要计算对应k个最小特征值的特征向量，并不需要做完全的特征值分解，可以用一些经典的迭代法，比如Krylovsubspace方法