频谱聚类|拉普拉斯矩阵

频谱聚类的概念

频谱聚类的本质是利用样本间的相似度，降维后使用聚类算法进行节点聚类。
其中用到的拉普拉斯矩阵的特征值被成为“谱”。

拉普拉斯矩阵

① 样本相似度矩阵S：
我们有n个样本，利用某种相似度度量方法可以获得两两样本之间的相似度。如使用高斯相似度：
$$S_{i,j}=exp(-\frac{||x_i-x_j|{|}_2^2}{2{\sigma }^2})$$
得到样本的相似度矩阵，记为S。
② 邻接矩阵A：
对每个样本点，取其k近邻作为其邻居节点，构造邻接矩阵A。
即如果i是j的k近邻且j是i的k近邻，则$A_{i,j}=S_{i,j}$，否则$A_{i,j}=0$
③ 度矩阵D：
D是一个对角阵，对角元是每个节点的度，其余元素为0.
④ 非标准化的拉普拉斯矩阵：
L=D-A
⑤ 标准化后的拉普拉斯矩阵：
$L_{sym}=D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}$
此处$L_{sym}$有一条重要的性质：拉普拉斯矩阵的0特征值重数k等于其对应的图中的连通分量的个数。

频谱聚类的步骤

输入：样本集D=(𝑥1,𝑥2,…,𝑥𝑛)，降维后的维度m, 聚类方法，聚类后的维度y
输出： 簇划分𝐶(𝑐1,𝑐2,…𝑐y).
　
①~⑤：同上，求出标准化后的拉普拉斯矩阵∈$R_{n\ast n}$
⑥ 求出$L_{sym}$的特征值，取最小的m个特征值，求其对应的特征向量，组成一个n*m的矩阵，即降维后的特征矩阵，每行对应一个样本点。
⑦ 对该矩阵进行标准化
⑧ 对标准化后的特征向量矩阵进行聚类（如k-means）