原理

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

基础

度矩阵

对于任意一个点，它的度为所有与它相连的边的权重之和$d_i=\sum w_{ij}$

由此我们可以得到一个度矩阵D，度矩阵为一个对角矩阵且只在主对角线上有值，值为每个点的度，对于一个n个点的图，度矩阵为n*n

建立邻接矩阵

对于给定的数据点构建邻接矩阵的基本思想是，距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高，构建邻接矩阵的方法有三类

$\epsilon -临近法$

用欧氏距离度量任意两点的距离，即$s_{ij}=||x_i-x_j||_2^2$，定义邻接矩阵$W_{ij}=0(s_{ij}>\epsilon),\epsilon(s_{ij}\leq\epsilon)$，由于信息很少，距离远近度量很不精确，很少使用该方法

$K-邻近法$

利用KNN算法遍历所有的样本点，取每个样本最近的k个点作为近邻，只有和样本距离最近的k个点之间的$w_{ij}>0$，但这样会导致重构之后的邻接矩阵非对称，我们可以用两种方式：一种为只要一个点在另一个点的近邻中，则保留，另一种为两个点必须互为K近邻中才保留。

KNN算法

K Nearest Neighbors，找K个最近的邻居，KNN 的原理就是当预测一个新的值 x 的时候，根据它距离最近的 K 个点是什么类别来判断 x 属于哪个类别。

$全连接法$

所有的点之间的权重值都大于0，可用不同的核函数来定义边权重。

拉普拉斯矩阵

拉普拉斯矩阵L=度矩阵D-邻接矩阵M

1. 拉普拉斯矩阵为对称矩阵
2. 对于任意向量f，有$f^TLf=\frac{1}{2}\sum_{i,j=1}^{n} w_{ij}(f_i-f_j)^2$
3. 拉普拉斯矩阵为半正定，且对应的n个实数特征值都大于等于0

无向图切图

对于任意两个子图点的集合，定义A，B的切图权重为$W_{AB}=\sum_{i\in A,j\in B} w_{ij}$

对于k个子图点的集合，定义切图为$cut(A_1,A_2,…,A_k)=\frac{1}{2}\sum_i^kW(A_i,\overline{A_i})$

谱聚类使用的切图方式一般有两种：RatioCut切图和Ncut切图，通常情况下，Ncut优于RatioCut，因此，我们在下面只介绍Ncut切图

类内连接相似度

assoc