完整文档和代码

https://gitee.com/youryouth/mc/tree/master/spectral_clustering

一、概述

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

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

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

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

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

关于凸集和非凸，如下图左非凸，图右凸

二、基础知识

无向权重图

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

假设总共个样本点，这些样本点构成的图可以用表示，其中，图中的每个点也就代表了一个样本，是边，用邻接矩阵（相似度矩阵）来表示，，由于是无向图，因此。

另外还有度的概念，这里可以类比有向图中的出度和入度的概念，不过图中的点的度

并不是和该点相连的点的数量，而是和其相连的边的权重之和，也就是邻接矩阵的每一行的值加起来，即：

而图的度矩阵（对角矩阵）可以表示如下：

另外我们定义，对于点集的一个子集，我们定义等于子集A中点的个数

构建邻接矩阵

-近邻法

首先需要设置一个阈值，比较任意两点和之间的距离与的大小，定义邻接矩阵如下：

这种方法表示如果两个样本点之间的欧氏距离的平方小于阈值，则它们之间是有边的。

因为不支持markdown语法，关于其他构建邻接矩阵方法可以参考链接，下面只贴出代码的运行结果。

运行结果