1. 什么是谱聚类
谱聚类算法是一种聚类算法，算法思想是首先将样本特征降维，然后对降维后的样本采用其他聚类算法进行聚类。
2. 如何求解
由于谱聚类算法有几种版本，这里讲解最常用的版本。已知有$N$个样本，每个样本都有一个$M$维向量$x_i$，则可以对这些样本计算出一个相似矩阵$W$，计算方式如下：
其中$\sigma$是一个超参数，用来调整顶点之间的相似度大小。计算出矩阵$W$，接着可以计算矩阵$D$，矩阵$D$是一个对角矩阵，且有：
接着可以使用矩阵$W$和矩阵$D$，计算拉普拉斯矩阵$L$：
为什么要求$L$？首先$L$是半正定的，$L$所有的特征值均大于等于0，其次$L$存在一个特征值等于0，再者$L$满足以下性质：
为什么满足这个性质，大家可以自己动笔算算，将$L=D-W$代入化简即可得到上式。现在我们将矩阵$W$看作是一个图的邻接矩阵，即将$W_{i,j}$看作是顶点$i$和顶点$j$的边权，现在我们想要将顶点划分为$K$类，可以看作是将$W$代表的图划分为$K$个子图，且这$K$个子图之间的边权和尽量小。可以表示为：
其中$A_k$表示第$k$类集合的顶点，$\hat{A_k}$表示除第$k$类集合外的其他顶点，$cut$表示求第第$k$类集合顶点和其他集合顶点的切割，即边权和。但是求这个式子的最小值有个问题就是容易将1个顶点归为1个集合，我们希望一个集合内部的顶点数尽量多，所以可以改进目标函数为：
这表明，一个集合内部顶点数越多，则分母越大，所以目标函数值也会少，算是一种对顶点数大的奖励。现在我们对每一类集合构造一个向量$h_k$：
可以看到不同集合向量间是正交的，因为每个点只会在一个集合中，即如果向量$h_{k,i}\ne 0$，则其他向量$h_{j,i}=0$。而且还有这样一条性质：
然后还有下面一条重要的性质：
所以现在问题等价于求：
设$H=D^{-\frac{1}{2}}F$，则问题可以转换成：
其中，$D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$是标准化的拉普拉斯矩阵。现在我们需要求$F$中的每一列$f$，如果$f$是矩阵$D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$的特征向量，那么有：
$\lambda$是特征值。很容易证明当$f$是特征值最小的向量时，其对应的特征值是上式的最小值解，当$f$是特征值最大的向量时，其对应的特征值是上式的最大值解。现在我们要求最小解，所以可以利用贪心算法的思路，将特征值最小的特征向量作为矩阵$F$的第一列，特征值第二小的特征向量作为矩阵$F$的第二列，特征值第$k$小的特征向量作为矩阵$F$的第$k$列。照着这个思路求出来的矩阵$F$恰好又可以满足$F^TF=I$这个约束。假设我们求出了最标准最正确的解，现在看$H$矩阵的每一行，每一行代表样本属于哪一类，所以只有一个元素不为0，其他都等于0，对应到矩阵$F$也是一样的。如果直接使用矩阵$F$的每一行的向量代表样本，则聚类是容易的，因为每个样本的向量只有一个元素有值，将有值的归为一类即可。我们可以先对矩阵$F$的每一行标准化为只有一个元素为1，然后使用其他聚类算法对这些样本进行聚类。需要注意的是，上面矩阵$F$每一行只有一个元素有值，是在标准解的条件下才会成立的，我们使用特征向量作为解，特征向量组成的矩阵在每一行可能并不止一个元素不为0，所以这种方法只是一个近似解。现在总结一下谱聚类的算法步骤：
(1) 构造相似矩阵$W$。
(2) 根据$W$,求出矩阵$D$。
(3) 根据$W$和$D$，求出拉普拉斯矩阵$L$。
(4) 标准化拉普拉斯矩阵$D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$。
(5) 对标准化拉普拉斯矩阵求出特征值前$k$小的特征向量组成矩阵$F$。
(6) 对矩阵$F$的每一行进行标准化。
(7) 矩阵$F$的每一行对应一个样本的向量，使用其他聚类算法使用这些向量进行聚类。