一、概述

对于下图所示的数据进行聚类，可以采用GMM或者K-Means的方法：

                                     数据

然而对于下图所示的数据，单纯的GMM和K-Means就无效了，可以通过核方法对数据进行转换，然后再进行聚类：

                                          数据    

如果直接对上图所示的数据进行聚类的话可以考虑采用谱聚类（spectral clustering）的方法。

总结来说，聚类算法可以分为两种思路：

①Compactness，这类有 K-means，GMM 等，但是这类算法只能处理凸集，为了处理非凸的样本集，必须引⼊核技巧。

②Connectivity，这类以谱聚类为代表。

二、基础知识

1. 无向权重图

谱聚类的方法基于带权重的无向图，图的每个节点是一个样本点，图的边有权重，权重代表两个样本点的相似度。

2. 邻接矩阵

上述方法是不用先建立图而直接获得邻接矩阵，在编程实现时能够更加简便，构建的邻接矩阵也就表明了哪些样本点之间有边连接。也可以采用先建立图然后再在图上有边的数据点上保留权重获得邻接矩阵的方法。

• 全连接法

在实际应用时选择全连接法建立邻接矩阵是最普遍的，在选择相似度度量时径向基核函数是最普遍的。

3. 拉普拉斯矩阵

①对称性。

②由于其对称性，则它的所有特征值都是实数。

③对于任意向量 ，有：

这一性质利用拉普拉斯矩阵的性质很容易可以得到：

每个子图就相当于聚类的一个类，找到子图内点的权重之和最高，子图间的点的权重之和最低的切图就相当于找到了最佳的聚类。实现这一点的一个很自然的想法是最小化 。然而这种方法存在问题，也就是最小化的 对应的切图不一定就是符合要求的最优的切图，如下图：

                                  举例

接下介绍谱聚类使用的切图方法。

三、谱聚类之切图聚类

四、总结

1. 算法流程

2. 优缺点

谱聚类的优点有：

①谱聚类只需要数据之间的相似度矩阵，因此对于处理稀疏数据的聚类很有效。这点传统聚类算法比如K-Means很难做到。

②由于使用了降维，因此在处理高维数据聚类时的复杂度比传统聚类算法好。

谱聚类的缺点有：

①如果最终聚类的维度非常高，则由于降维的幅度不够，谱聚类的运行速度和最后的聚类效果均不好。

②聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同。

参考资料

ref:谱聚类（spectral clustering）原理总结