A Tutorial on Spectral Clustering
摘要
近年来，谱聚类已成为最流行的现代聚类算法之一。它实现简单，可以通过标准线性代数软件有效求解，并且通常优于传统的聚类算法（例如 k-means 算法）。乍一看，谱聚类似乎有点神秘，而且很难看出它为什么起作用以及它到底做了什么。本教程的目标是对这些问题提供一些直观的了解。我们描述了不同的图拉普拉斯算子及其基本属性，提出了最常见的谱聚类算法，并通过几种不同的方法从头开始推导这些算法。讨论了不同谱聚类算法的优点和缺点。
符号表示
| 符号 | 表示 |
|---|---|
| $x_i$ | 数据点 |
| $s_ij$ | 数据点之间的相似度 |
| $G=(V,E)$ | 相似图(本文无向) |
| $v_i$ | 相似图的顶点 |
| $W$ | 图的加权邻接矩阵是矩阵 |
| $D$ | 度矩阵（度数的对角矩阵） |
| $A$ | 给定顶点的子集 |
| $\bar{A}$ | $A$在$V$的补集 |
| $\mathbb{1}_A$ | 指示向量，1表示属于$v\in A$， |
| $S$ | 两个样本点的相似度矩阵 |
| $H$ | 指示向量组成的矩阵 |
2 Similarity graphs
我们想要找到图的一个分区，使得不同组之间的边具有非常低的权重（这意味着不同簇中的点彼此不相似）并且组内的边具有高权重（这意味着不同簇中的点）相同的簇彼此相似）。
2.1 Graph notation
顶点$v_i$的度定义为：
对于两个不一定相交的子集$A,B \in V$:
测量$A$大小的两种方法：
说明：
2.2 Different similarity graphs
The ε-neighborhood graph：
这里我们连接所有两两距离小于 ε 的点。由于所有连接点之间的距离大致相同（最多 ε），对边进行加权不会将有关数据的更多信息合并到图中。因此，ε-邻域图通常被认为是未加权图。
k-nearest neighbor graphs:
这里的目标是，如果 $v_j$ 是 $v_i$ 的 k-近邻之一，则将顶点 $v_i$ 与顶点 $v_j$ 连接起来。然而，这个定义导致有向图，因为邻域关系不是对称的。有两种方法可以使该图成为无向图。第一种方法是简单地忽略边的方向，即如果 $v_i$ 位于$ v_j $的$ k $个近邻中，或者$ v_j$ 位于 $v_i $的 $k$ 个近邻中，则用无向边将 $v_i$ 和 $v_j$ 连接起来。生成的图通常称为 $k$ 最近邻图。第二种选择是连接顶点 $v_i$ 和 $v_j$，如果 $v_i$ 位于 $v_j$ 的 $k$-近邻之中并且 $v_j$ 位于$ v_i$ 的 $k$-近邻之中。所得图称为互 $k$-近邻图。在这两种情况下，在连接适当的顶点之后，我们通过端点的相似性对边进行加权。
The fully connected graph:
在这里，我们简单地将所有具有正相似度的点连接起来，并通过 $s_{ij}$ 对所有边进行加权。由于该图应该表示局部邻域关系，因此只有当相似性函数本身对局部邻域进行建模时，这种构造才有用。这种相似性函数的一个例子是高斯相似性函数 $s(x_i, x_j) = \exp(−‖x_i − x_j‖^{2}/(2σ^{2}))$，其中参数 σ 控制邻域的宽度。该参数与 ε 邻域图中的参数 ε 起着类似的作用。
3 Graph Laplacians and their basic properties
3.1 The unnormalized graph Laplacian
非归一化图拉普拉斯矩阵定义为：
Proposition 1
Proposition 2
命题2（连通分量数与拉普拉斯矩阵的谱）设 $G$是一个具有非负权重的无向图。那么，拉普拉斯矩阵$ L$的特征值0的重数 $k$等于图中的连通分量数 $A_1, \ldots, A_k$。特征值0的特征空间由这些连通分量的指示向量 $\mathbf{1}_{A_1}, \ldots, \mathbf{1}_{A_k}$张成。
3.2 The normalized graph Laplacians
文献中有两个矩阵被称为归一化图拉普拉斯矩阵。两个矩阵彼此密切相关，定义为：
Proposition 3
Proposition 4
（连通分量数与 $L_{sym}$和$ L_{rw}$的谱）设 $G$是一个具有非负权重的无向图。那么，$L_{rw}$和$ L_{sym}$的特征值0的重数 $k$等于图中的连通分量数$ A_1, \ldots, A_k$。对于$ L_{rw}$，特征值0的特征空间由这些连通分量的指示向量 $\mathbf{1}_{A_i}$张成。对于$ L_{sym}$，特征值0的特征空间由向量 $D^{1/2} \mathbf{1}_{A_i}$张成。
4 Spectral Clustering Algorithms
不归一化谱聚类：
5 Graph cut point of view
划分图解决mincut问题：
在许多情况下，mincut 的解决方案只是将一个单独的顶点与图的其余部分分开,于是改进：
上面改进导致问题变为NP问题，而谱聚类能解决。
5.1 Approximating RatioCut for k = 2
目标是：
定义$f$向量：
可以使用非归一化图拉普拉斯算子方便地重写 RatioCut 目标函数：
有：
等式（2）中定义的向量$ f $与常数一向量 1 正交，并满足:
公式(1)可以重新成：
从离散优化问题松弛到连续优化问题：
5.2 Approximating RatioCut for arbitrary k
如果划分为$k$个，定义指示向量为：
$H$的每一列是正交的，因此$H^{‘}H=I$,并且有：
而且：
得到：
重写问题为：
这是迹最小化问题的标准形式，瑞利-里茨定理的一个版本，解决方案是通过选择 $H$ 给出的作为包含 $L$ 的前$ k$ 个特征向量作为列的矩阵。我们可以看到，矩阵$ H $实际上是第 4 节中描述的非归一化谱聚类算法中使用的矩阵 $U$。我们再次需要将实值解矩阵重新转换为离散分区。如上所述，标准方法是对 U 的行使用 k-means 算法。这导致了第 4 节中介绍的一般非归一化谱聚类算法。
5.3 Approximating Ncut
5.4 Comments on the relaxation approach
6 Random walks point of view
解释谱聚类的另一个论据是基于相似图上的随机游走。图上的随机游走是一个从一个顶点随机跳转到另一个顶点的随机过程。我们将在下面看到，谱聚类可以解释为试图找到图的分区，使得随机游走在同一簇内停留很长时间并且很少在簇之间跳跃。直观上这是有道理的，特别是与上一节的图割解释一起：具有低割的平衡分区还将具有随机游走没有太多机会在簇之间跳转的属性。
从顶点$v_i$跳跃到$v_j$的概率与边权重成正比:$p_{i,j}=w_{i,j}/d_i$，随机矩阵定义为：
Random walks and Ncut
Proposition 5 设 $G $是连通的且非二分的。假设我们从平稳分布 $π$ 中的 $X_0$ 开始运行随机游走 $(X_t)_{t\in N}$。对于不相交子集 $A, B ⊂ V$ ，表示为 $P (B|A) := P (X_1 ∈ B|X_0 ∈ A)$。然后：
