1 算法概况
谱聚类（spectral clustering）：一种基于图的聚类算法
前置知识：图论基础概念、图论基础#3.1 理解拉普拉斯矩阵
核心思想：将数据转化为图的形式，距离近的数据间对应的边权重高，距离远的数据间对应的边权重低。之后通过切图的方式，使得不同子图间的边权值和尽可能低，子图内部的边权值和尽可能高，从而达到聚类的目的
2 算法细节
2.1 数据转图
核心思想：把每个样本看作一个节点，然后构建任意两点$(x_i,x_j)$间权重边$w_{ij}$
方法1：$\epsilon-$邻近法 $$\begin{equation} w_{ij} = \left\{ \begin{array}{rl} 0 & \mbox{if } ||x_i-x_j||_2^2 < \epsilon, \\ \epsilon & \mbox{if } ||x_i-x_j||_2^2 \geq \epsilon. \end{array} \right. \end{equation}$$
- 其中$\epsilon$为预设的距离阈值。此方法较为粗糙，实际应用中不常见
方法2：K邻近法 $$\begin{equation} w_{ij}=w_{ji} = \left\{ \begin{array}{rl} 0 & \mbox{if } x_i \notin KNN(x_j) \mbox{ and } x_j \notin KNN(x_i), \\ exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2}) & \mbox{if } x_i \in KNN(x_j) \mbox{ or } x_j \in KNN(x_i), \\ \end{array} \right. \end{equation}$$
- 此公式中的$and$和$or$互换后，是K邻近法的另一种形式
方法3： 全连接法 $$w_{ij}=w_{ji} =exp(-\frac{||x_i-x_j||_2^2}{2\sigma^2})$$
- 此方法会在任意两点间都构建权重边
- 权重的计算可选择不同的核函数，本文使用最常见的高斯核函数RBF
2.2 切图聚类
切图：将无向图$G$切分成$k$个无关联的子图${A_1,A_2,...,A_k}$
定义切图成本函数：$W(A_1,A_k)=\Sigma_{i\in A_1,j\in A_k}w_{ij}$
整体的切图成本：$cut(A_1,...,A_k)=\frac{1}{2}\Sigma_{i=1}^kW(A_i,\overline{A_i})$
- 其中集合$\overline{A_i}$表示集合$A$的补集，而切图的原则是切图成本最低
2.2.1 RatioCut切图
仅考虑最低切图成本，往往导致模型倾向于切割边缘的低权重节点。因此RatioCut将子图的节点数融入成本函数中（追求子图节点数量尽可能的多）： $$Rdtiocut(A_1,...,A_k)=\frac{1}{2}\Sigma_{i=1}^k\frac{W(A_i,\overline{A_i})}{|A_i|}$$ 为了化简成本函数，引入指示向量$h_j$，其中$j=1,...,k,h_j\in R^n$： $$\begin{equation} h_{ij} = \left\{ \begin{array}{rl} 0 & \mbox{if } v_i \notin A_j \\ \frac{1}{\sqrt{|A_j|}}) & \mbox{if } v_i \in A_j \\ \end{array} \right. \end{equation}$$ 假设无向图$G$对应的拉普拉斯矩阵为$L$，则根据$L$的性质可知： $$h_i^TLh_i=\frac{1}{2}\Sigma_m\Sigma_nw_{mn}(h_{im}-h_{in})^2=\frac{W(A_i,\overline{A_i})}{2|A_i|}$$ 最终RatioCut成本函数形式可化简如下： $$RadioCut(A_1,...,A_k)=\Sigma_{i=1}^kh_i^TLh_i=\Sigma_{i=1}^k(H^TLH)_{ii}=tr(H^TLH)$$ 其中$H\in R^{n\times k}$，是由$n$个指示向量按列拼接而成的矩阵。对$H$添加标准化约束后，最终的切图优化目标为： $$argmin_H \ tr(H^TLH)\ \ s.t.\ H^TH=I$$ 转化为标准瑞利熵问题后，借助拉格朗日乘子法对上式进行化简求解。
注：本小节的推导过程有省略，更多细节和补充信息可查阅文章最后的参考文献
$H$的求解：迹是特征值的和，所以追求矩阵迹的最小化，就是追求特征值的最小。通过矩阵$L$找到最小的$k$个特征值对应的特征向量，这些向量构成了一个$n\times k$的矩阵，即$H$的最优解。同时为了保证$H$的标准化约束成立，还需要对$H$进行标准化： $$h^{\ast}_{ij}=\frac{h_{ij}}{(\Sigma_{t=1}^k h^2_{it})^{\frac{1}{2}}}$$ 此过程相当于降维，保留了用于描述切图最小成本的信息。最终还需要针对矩阵$H$的每一行进行一次传统的聚类过程（抽取与切图相关的信息），比如K-means聚类
2.2.2 Ncut切图
将RatioCut切图成本函数的分母$|A_i|$换为$vol(A_i)=\Sigma_{j\in A}d_j$，即转化为Ncut切图。其中$d_j$表示节点$j$对应的度。由于考虑了结点权重，所以一般来说Ncut切图优于RatioCut切图
Ncut切图的成本函数： $$\frac{1}{2}\Sigma_{i=1}^k\frac{W(A_i,\overline{A_i})}{vol(A_i)}$$
Ncut切图的指示向量定义： $$\begin{equation} h_{ij} = \left\{ \begin{array}{rl} 0 & \mbox{if } v_i \notin A_j \\ \frac{1}{\sqrt{vol(A_j)}}) & \mbox{if } v_i \in A_j \\ \end{array} \right. \end{equation}$$ Ncut切图的最终优化目标： $$argmin_H \ tr(H^TLH)\ \ s.t.\ H^TDH=I$$ 其中$D$表示度矩阵，为方便套用RatioCut切图求解矩阵$H$的思路，上式可转换如下： $$argmin_H \ tr(F^TD^{-\frac{1}{2}}LD^{-\frac{1}{2}}F)\ \ s.t.\ F^TF=I$$ 最后的步骤和RatioCut切图一致，对矩阵$D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$进行标准化和一般聚类过程
注：矩阵$D^{-\frac{1}{2}}LD^{-\frac{1}{2}}$也被称为对称型标准化拉普拉斯矩阵
2.3 完整流程
- 通过关联结点（确立边）进行数据转图，得到相似矩阵$S$
- 计算得出矩阵$S$的邻接矩阵$W$、度矩阵$D$和拉普拉斯矩阵$L$
- （可选）如果是Ncut切图，会对拉普拉斯矩阵进行标准化
- 求解拉普拉斯矩阵，得到最小的$k$个特征值对应特征向量
- 特征向量组成矩阵$H$，以每一行作为样本进行传统聚类
3 算法分析
算法优点：
- 谱聚类只需要数据之间的相似度矩阵，加强了对局部”连通性“的考虑
- 先借助特征向量对原始数据进行表示（Laplacian Eigenmap降维），再借助K-Means算法进行聚类，能更好地捕捉到数据间的主要矛盾
- 降维的计算（特征分解）过程具备高效的方法，因此谱聚类在处理高维数据/稀疏数据聚类时，整体的计算复杂度显著低于传统聚类算法
算法缺点：
- 当降维时保留的维度过高时，谱聚类的运行速度和最终聚类效果均会受到影响
- 聚类结果依赖于相似矩阵，相似矩阵的构建方式不同，最终的聚类结果可能存在差异