谱聚类
除了K-means和GMM，谱聚类算得上是当今聚类算法的一大流派了。该流派中的算法主要区别于矩阵（也就是“谱”）的构造，本文只讲述谱聚类这一类算法的基本原理，不对各种变体一一展开。
1. 算法流程
- 将数据集中的$N$个样本看作是空间上的一个个点， 假设点与点之间我们有了一个相似度值，我们将空间中的相似的点链接起来并赋予对应的权重（一般为相似度值）。由此，我们将数据集构造成了一个Graph（无向图），Graph的邻接矩阵可直接表示为顶点之间的相似度矩阵$W$。那么如何获得点与点之间的相似度值呢？通俗的一种方法就是使用欧式距离衡量，当然这还要取决于你数据集样本特征的特点。
- 将邻接矩阵$W$按行求和，得到每一个顶点的度数，把它们作为对角矩阵$D \in \mathbb{R}^{N\times N}$的对角线上的值。然后，令$L=D-W$，$L$称为laplacian矩阵。
- 对矩阵$L$求解其前K个小的特征值 \(\{ \lambda \}_{i=1}^k\) 以及对应的特征向量 \({\{ v \}}_{i=1}^k\)。
- 将这k个特征向量组成矩阵$S\in \mathbb{R}^{N\times k}$，矩阵的每一行表示对应顶点在k维空间中的向量表示。最后使用K-means算法进行聚类得到k个类别的聚类结果。
2. 优缺点
在上面的算法流程中，很容易发现谱聚类的一个特点：以顶点之间的相似度矩阵作为算法的启动资源。这其实就是谱聚类优缺点的来源：
** 优点 **
- 能够处理离散、稀疏的数据，只要我们能够定义出顶点之间的相似度矩阵；
- 由于进行了降维处理，谱聚类更容易抓到问题的主要矛盾，不被噪声影响，因此算法更加鲁棒。
** 缺点 **
- 聚类效果依赖于相似矩阵，不同的相似矩阵得到的最终聚类效果可能很不同；
- 由于降维时需要进行特征值和特征向量的求解，因此可能影响算法的运行速度。
3. 原理与公式推导
现在，你是不是觉得谱聚类并没有如同名字一样的神秘了，你觉得他实际上就是对数据做了一些变换，最终还是要在背后偷偷地调用k-means。然而，就如同k-means一样，简单易懂的算法背后常常蕴涵着非常复杂的计算推导，谱聚类也不例外，例如，为什么谱聚类降维时要刚好降到k维呢（k等于要聚类的类别个数）？那么，我们就从分割问题说起吧（一大堆公式即将袭来）。
3.1 分割 Segmentation
在图像处理(Image Processing）领域中有一类图像分割（Image Segmentation）问题，即让相似的像素组成一个区域。例如，我们一般希望一张照片里面的人（前景）和背景被分割到不同的区域中。在图像处理领域里已经有许多自动或半自动的算法来解决这个问题，并且有不少方法和聚类算法密切相连。比如我们在谈Vector Quantization的时候就曾经用K-means来把颜色相似的像素聚类到一起，不过那还不是真正的Segmentation，因为如果仅仅是考虑颜色相似的话，图片上位置离得很远的像素也有可能被聚到同一类中，我们通常并不会把这样一些“游离”的像素构成的东西称为一个“区域”，但这个问题其实也很好解决：只要在聚类用的feature中加入位置信息（例如，原来是使用 R、G、B 三个值来表示一个像素，现在加入 x、y 两个新的值）即可。
与此类似的，在图论中有一个经常被研究的问题就是Graph Cut。简单地说，Graph Cut就是把一个 Graph的一些边切断，让他被打散成一些独立联通的子图（sub-Graph），而这些被切断的边的权值的总和就被称为Cut值。如果用一张图片中的所有像素来组成一个Graph，并把（比如，颜色和位置上）相似的节点连接起来，边上的权值表示相似程度，那么把图片分割为几个区域的问题实际上等价于把Graph分割为几个子图的问题，并且我们要求分割所得的Cut值最小，亦即：那些被切断的边的权值之和最小。直观上我们可以知道，权重比较大的边没有被切断，表示比较相似的点被保留在了同一个子图中，而彼此之间联系不大的点则被分割开来。我们可以认为这样一种分割方式是比较好的。
实际上，抛开图像分割的问题不谈，在Graph Cut相关的一系列问题中，Minimum cut（最小割）本身就是一个被广泛研究的问题，并且有成熟的算法来求解。只是单纯的最小割在这里通常并不是特别适用，很多时候只是简单地把和其他像素联系最弱的那一个像素给分割出去了，相反，我们通常更希望分割出来的区域（的大小）要相对均匀一些，而不是一些很大的区块和一些几乎是孤立的点。为此，又有许多替代的算法提出来，如 Ratio Cut、Normalized Cut等。
3.2 最小割
（一大波公式真的要来了）我们将$W$记作Graph的邻接矩阵，其中$w_{ij}$是节点$i$到节点$j$的权值，若权值为零，则表示两个节点之间不相连。假设A和B是Graph的节点集合中的两个子集（A和B没有交集），则A和B之间的cut值为:
\[\text{cut}(A, B) = \sum_{i\in A, j\in B} w_{ij}\]首先，如果将Graph只分割为两个部分的话（即$B=\bar{A}$, $\bar{A}$表示A的补集），那么最小割问题就是要最小化$\text{cut}(A, \bar{A})$。但是由于这样经常会出现孤立节点被分割出来的情况，因此我们可以使用RatioCut：
\[\text{RatioCut}(A, \bar{A}) = \frac{\text{cut}(A, \bar{A})}{\vert A\vert} + \frac{\text{cut}(A, \bar{A})}{\vert\bar{A}\vert}\]或者NormalizedCut：
\[\text{NCut}(A, \bar{A}) = \frac{\text{cut}(A, \bar{A})}{\text{vol}(A)} + \frac{\text{cut}(A, \bar{A})}{\text{vol}(\bar{A})}\]其中$\vert A\vert$表示A中的节点数目，而$\text{vol}(A)=\sum_{i\in A}w_{ij}$。两者都可以算作A集合“大小”的一种度量，通过在分母上放置这样的项，就可以有效地防止孤立点的情况出现，达到相对平均一些的分割。
RatioCut实际上是一个典型的离散问题，它的最小化解是一个NP难问题。因此，我们需要对它进行变形： 定义一个$N$维向量$f$:
\[f_i = \left\{\begin{array}{ll}\sqrt{\vert\bar{A}\vert/\vert A\vert} &\text{if } v_i \in A \\-\sqrt{\vert A\vert/\vert\bar{A}\vert} & \text{if } v_i \in \bar{A}\end{array}\right\}.\]令$\mathbf{1}$向量为各元素都为1的向量，则\(f^{T}\mathbf{1} = \sum f_i = \vert A\vert*\sqrt{\vert\bar{A}\vert/\vert A\vert}-\vert\bar{A}\vert*\sqrt{\vert A\vert/\vert\bar{A}\vert}= 0\)。同样的，我们很容易推出： \({\| f\|}_2 = \sum f_i^2 = \vert A\vert*\vert\bar{A}\vert/\vert A\vert + \vert\bar{A}\vert*\vert A\vert/\vert \bar{A}\vert = N\)
回到此前算法流程中提到的拉普拉斯矩阵$L=D-W$(Graph Laplacia)，其具有一个性质，即对于任意的向量$f$，以下等式都成立：
\[f^{T}Lf = \frac{1}{2}\sum_{i,j}^N w_{ij}(f_i-f_j)^2\]这个公式也被称作信号的平滑处理（smoothness of signal），然而这个等式的证明网上基本都没有，所以我自己推了一下：
\[\begin{aligned} f^{T}Lf=&f^{T}Df-f^{T}Wf\\ =&\sum_{i=1}^N d_i f_i^2 - \sum_{i,j}^N w_{ij}f_i f_j\\ =&\frac{1}{2}\left(\sum_{i=1}^N d_i f_i^2 - 2\sum_{i,j}^N w_{ij}f_i f_j + \sum_{j=1}^N d_j f_j^2\right)\\=&\frac{1}{2}\left(\sum_{i=1}^N \sum_{j=1}^N w_{ij} f_i^2 - 2\sum_{i,j}^N w_{ij}f_i f_j + \sum_{j=1}^N \sum_{i=1}^N w_{ij} f_j^2\right)\\ =&\frac{1}{2}\sum_{i,j}^N w_{ij}(f_i-f_j)^2\end{aligned}\]题外话，这个公式侧面也反应出了拉普拉斯矩阵确实是一个半正定矩阵。回到我们的主题，我们将刚才定义的$f$向量带入这个公式可以得到：
\[\begin{aligned} f^{T}Lf &= \frac{1}{2}\sum_{i,j=1}^N w_{ij}(f_i-f_j)^2 \\ &= \frac{1}{2}\sum_{i\in A, j\in\bar{A}} w_{ij}\left(\sqrt{\frac{\vert \bar{A}\vert }{\vert A\vert }}+\sqrt{\frac{\vert A\vert }{\vert \bar{A}\vert }}\right)^2 + \sum_{i\in \bar{A}, j\in A} w_{ij}\left(-\sqrt{\frac{\vert \bar{A}\vert }{\vert A\vert }}-\sqrt{\frac{\vert A\vert }{\vert \bar{A}\vert }}\right)^2\\&=\text{cut}(A,\bar{A})\left(\frac{\vert \bar{A}\vert }{\vert A\vert }+\frac{\vert A\vert }{\vert \bar{A}\vert }+2\right)\\&=\text{cut}(A,\bar{A})\left(\frac{\vert A\vert +\vert \bar{A}\vert }{\vert A\vert } +\frac{\vert A\vert +\vert \bar{A}\vert }{\vert \bar{A}\vert }\right)\\&=\vert N\vert \cdot\text{RatioCut}(A,\bar{A})\end{aligned}\]由于\(\vert N\vert =\vert A\vert +\vert \bar{A}\vert\)是一个常量，因此最小化RatioCut就等价于最小化$f^TLf$，当然，别忘了上面公式的推导是建立在附加条件$f \bot \mathbf{1}$ 以及 $|f|_2 = N$上的。
现在我们可以比较好的求解RatioCut了，因为有一个叫做 Rayleigh quotient的东西：
\[R(A, x) = \frac{x^TAx}{x^Tx}\]它的最大值和最小值分别等于矩阵A的最大的那个特征值和最小的那个特征值，并且极值在x 等于对应的特征向量时取到。由于$f^Tf = \sqrt{n}$ 是常数，因此最小化$f^TLf$ 实际上也就等价于最小化$R(L, f)$ ，不过由于L的最小的特征值为零，并且对应的特征向量正好为 $1$(我们这里仅考虑Graph是联通的情况，\(L\mathbf{1}=\lambda \mathbf{1}\)，当\(\lambda=0\)时等式成立)，不满足\(f \bot \mathbf{1}\) 的条件，因此我们取第二个小的特征值，以及对应的特征向量$v$。
到这一步，我们看起来好像是很容易地解决了前面那个NP难问题，实际上是我们耍了一个把戏：之前的问题之所以NP难是因为向量$f$的元素只能取两个值: \(\sqrt{\vert \bar{A}\vert /\vert A\vert }\) 和 \(-\sqrt{\vert A\vert /\vert \bar{A}\vert }\) 中的一个，是一个离散的问题。而我们求的的特征向量$v$其中的元素可以是任意实数，就是说我们将原来的问题限制放宽了。那如何得到原来的解呢？一个最简单的办法就是看$v$的每个元素是大于零还是小于零，将他们分别对应到离散情况的 \(\sqrt{\vert \bar{A}\vert /\vert A\vert }\) 和 \(-\sqrt{\vert A\vert /\vert \bar{A}\vert }\) ，不过我们也可以采取稍微复杂一点的办法，用k=2的K-means来将$v$的元素聚为两类。
到此为止，已经有Spectral Clustering的影子了：求特征值，再对特征向量进行K-means聚类。实际上，从两类的问题推广到k 类的问题（数学推导我就不再详细写了，我们就得到了和之前的Spectral Clustering 一模一样的步骤：求特征值并取前k个最小的，将对应的特征向量排列起来，再按行进行 K-means 聚类。分毫不差！
参考文章：
【1】漫谈Clustering (4): Spectral Clustering 【2】A Tutorial on Spectral Clustering
