1. 谱聚类概述

谱聚类是从图论中演化出来的算法，后来在聚类中得到了广泛的应用。它的主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来。距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的。

2. 相似矩阵

基本思想是，距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，不过这仅仅是定性，我们需要定量的权重值。一般来说，我们可以通过样本点距离度量的相似矩阵谱聚类 - 图2来获得邻接矩阵谱聚类 - 图3。
第三种定义邻接矩阵谱聚类 - 图4的方法是全连接法，相比前两种方法，第三种方法所有的点之间的权重值都大于0，因此称之为全连接法。可以选择不同的核函数来定义边权重，常用的有多项式核函数，高斯核函数和Sigmoid核函数。最常用的是高斯核函数RBF，此时相似矩阵和邻接矩阵相同：
谱聚类 - 图5

3. 拉普拉斯矩阵

　单独把拉普拉斯矩阵(Graph Laplacians)拿出来介绍是因为后面的算法和这个矩阵的性质息息相关。它的定义很简单，拉普拉斯矩阵谱聚类 - 图6。拉普拉斯矩陣的半正定、对称的性质在算法当中是非常重要的，可以说谱聚类算法就是围绕着拉普拉丝矩阵的EVD
image.png

4. 无向图切图

image.png

5. 切图聚类

1.RatiaCut

image.png
image.png

2.Ncut

image.png

image.png

6. 算法流程

image.png