A tutorial on spectral clustering文献翻译

前言
Abstract
1. Introduction
2. 相似图
- 2.1 基础图符号
- 2.2 不同的相似图
3. 图拉普拉斯矩阵以及它们的特性
- 3.1 非正则化拉普拉斯图矩阵
- 3.2 正则化图拉普拉矩阵
4. 谱聚类算法
- 非正则化谱聚类
- 正则化聚类
5. 从图割视角来看待谱聚类
8. 谱聚类实施上的指导性细节

前言

谱聚类是一类很前沿的聚类算法，它的特点是具有极强的可解释性。这篇文章不仅从根源上深入浅出介绍了谱聚类与其算法，同时使用图割理论，随机游走理论(用Markov状态转移矩阵作为工具)以及矩阵扰动理论从不同角度剖析了谱聚类的直观意义以及我们如何使用谱聚类。在看整篇论文的过程中，我不断被这些直观简洁的解释所吸引，并为此文作者的迷人思想所折服.这就是促使我翻译这篇文章的原因。

因为时间所限，我暂时翻译了第1-5章节，这些章节主要介绍了谱聚类与如何做谱聚类，并为谱聚类给出了一个与图割问题的线性规划松弛解的等价性证明，以及第8章节，主要是关于如何使用谱聚类，如何选择超参数与正确的拉普拉斯图矩阵的问题.我会在未来翻译第6章节，一个关于谱聚类问题的随机游走理论与马尔科夫链的平稳状态分布解以及第7章节，用矩阵扰动理论解释谱聚类.第9章节是一些扩展性内容与文献推荐，此处暂时不翻译。

以下是翻译部分

Abstract

最近几年，谱聚类成为了最热门的聚类算法。它可以用现成的线性函数库来简单地实现，其聚类效果也往往比k-means方法要好.谱聚类方法初看起来有一些令人迷惑，因为仅仅从算法实现的过程中我们并不能理解它为什么会work。作者写这个介绍是为了对这些问题给一些直观的解释。我们将从图Laplacian矩阵出发，研究它们的一些基本特性，并给出传统的谱聚类算法。然后我们会从不同的角度来解释谱聚类算法.最后我们会讨论如何选取谱聚类的超参数，并分析谱聚类的强项与不足之处。

1. Introduction

这篇文章是对谱聚类的一个单独介绍，我们将从不同角度分析谱聚类为什么work。阅读这篇文章，你除了基本线性代数知识，并不需要其它数学背景，当然对于里面的一些理论我们会不加证明地给出结论。我们将在开始两节里介绍这篇文章所需要的数学理论，如第二节介绍相似图理论，第三节介绍图Laplacian矩阵。我们在第四节提出谱聚类算法，并在接下来三节介绍为什么谱聚类是work的：第五节用图割法来解释，第六节用随机游走来解释，第七节用矩阵扰动理论来分析。在第8节，我们将研究一些在实际实施谱聚类的问题。第九节我们将进行一些扩展并介绍与谱聚类相关的文献。

2. 相似图

给出一个数据集$(x_1,x_2,...,x_n)$，对于任意成对数据集点$(x_i,x_j)$，我们给定相似度$s_{i,j}\geq0$。聚类的直观目标是将数据集聚为不同的几类，满足在同一类内的数据集点要尽可能相似，同时不同类的数据集点要尽量不相似。如果除了对相似度的度量，我们并没有对成对数据集点的额外信息，那么一个表示数据的好方法是相似图$G=(V,E)$。在相似图中，每一个顶点代表一个数据点$x_i$，两个顶点$x_i,x_j$之间有边连接当且仅当$s_{i,j}\geq0$或者$s_{i,j}$大于给定的阈值，我们定义边的权重$w_{i,j}=s_{i,j}$，该聚类问题可以用相似图来进行刻画：我们想要找一个图的分割，这个分割满足在不同类之间的边的权重非常低，也就是说不同类之间点非常不相似；同时在同一类之间的边权重非常高，也就是说分到同一类的点非常相似。为了建立这种直观，我们先介绍一些基础图符号，并简单介绍我们所研究的图的基本特性。

2.1 基础图符号

用$G=(V,E)$来表示一个无向图，它的顶点集合为$V=\{v_1,...,v_n\}$。我们假设图$G$是赋权的，即对任意两个顶点$v_i,v_j$都存在一个非负权重$w_{i,j}\geq0$。图的加权邻接矩阵可以表示为$W=(w_{i,j})_{i,j=1,...,n}$，其中，$w_{i,j}=0$意味着顶点$v_i$和$v_j$之间没有任何边连接。显然，因为$G$是无向图，因此$W$是对称矩阵。对于顶点集合$V$，我们定义它的度（degree）为$d_i=\sum_{j=1}^{n}w_{i,j}$,同时定义度矩阵$D=\text{diag}(d_1,...,d_n)$。给定顶点子集$A\subset V$，我们记它的补集为$\bar{A}=V\backslash A$。此外，我们定义顶点子集$A$的指标向量为 $1_{A}=(f_1,...,f_n)'\in \mathbb{R}^{n},f_i=1 \text{ iff}\ v_i\in A,\text{ or }\ f_i=0$ 为方便起见，我们用$i\in A$来表示$v_i\in A$。此时对于任意两个集合$A,B$(这两个集合并非是不相交的)，我们可以定义$A,B$之间的距离为 $W(A,B)=\sum_{i\in A,j\in B}w_{i,j}$

同时我们给出两个对$V$的子集$A;A\subset V$的大小进行度量的方法：

记$\vert A \vert$为$A$中顶点的个数
记$\text{vol}(A)$为$A$的度，即$\text{vol}(A)=\sum_{i\in A}d_i$

我们可以对这两种度量方法进行直观理解：$\vert A \vert$通过$A$中顶点个数的多少度量了集合$A$的大小，同时$\text{vol}(A)$通过计算$A$的度对集合大小进行了度量.

此外，我们给出与$A$相关的两个重要概念：

子集$A\subset V$称为连通图，如果$A$中任意两个顶点都可以被一条路径所连接，同时路径里的所有点都在$A$中。
子集$A\subset V$被称为$V$的一个连通分支（这里应该理解为$A,\bar{A}$构成了$V$的连通二部图），如果$A$是连通的，而且$A,\bar{A}$之间没有连通路径。
非空子集$A_1,...,A_k$形成了一个图的割，如果它们满足$A_i\cap A_j=\emptyset$，且$A_1\cup...\cup A_k=V$。

2.2 不同的相似图

如果我们有一个数据集$X=(x_1,\ldots,x_n)$，且对该数据集的任意两个点，我们都给定一个相似度$s_{i,j}$或是距离$d_{i,j}$，那么我们可以用以下三种方法将其转换为上文所描述的图，并通过谱聚类进行聚类挖掘。但是要注意，我们的目的都是为数据点之间的局部相邻关系进行建模，也就是描述点与周围临近点的关系。

$\epsilon-\text{neighborhood}$图

我们连接图中所有满足$d_{i,j}<\epsilon$的点（注意一般来说距离$d_{i,j}$越小意味着相似度$s_{i,j}$越大）。因为此时所有连接的点的距离都被$\epsilon$所严格限制，因此对连接的边进行赋权并没有增加很多额外的信息。因此，$\epsilon-\text{neighborhood}$图一般是无向无权图.
\[\text{k-nearest neighbor graphs}\]
这里就用的是$k$近邻分类的策略了，即如果$v_j$是$v_i$的$k$个近邻点之一，那么我们连接$v_i\rightarrow v_j$。但是这个定义会导致一个有向图，因为$k$-近邻关系并没有对称性。有两种方式让这个图变为无向图：（1）只要$v_i,v_j$中存在一个方向的近邻关系，就把两个点用无向边(或者说双向边)连接起来，这种图称为$k-$近邻图；（2）如果$v_i,v_j$彼此都是对方的k-近邻点，我们再用无向边把它们连接起来，否则不进行连接，这种图被称为是双向$k-$-近邻图。在这两种连接方式下，对于连接的顶点仍然用相似度$s_{i,j}$对边进行赋权.
全连接图

我们直接用正相似度把所有的点彼此连接，并用$s_{i,j}$来给所有的边赋权。注意到图应该表现局部的相邻关系，因此这里的相似度也要表现这种关系。我们一般用高斯相似度函数$s(x_i,x_j)=\exp(\frac{-\Vert x_i-x_j \Vert_{2}^2}{2\sigma^2})$，这里超参数$\sigma$用于控制相邻关系的幅度（后面会讲到增大超参数$\sigma$在某种程度上可以视作增大图中的$\epsilon-\text{neighborhood}$中的$\epsilon$)。

这三种图都被谱聚类所广泛使用，到底用哪个比较好仍然是一个没有定论的问题，但是我们会在第8节予以一些经验性的指导。

3. 图拉普拉斯矩阵以及它们的特性

谱聚类所用的主要手段是图拉普拉斯矩阵，对这些矩阵有一个专门的理论进行研究，这个理论叫谱图理论。这一节中，我们定义不同的图拉普拉斯矩阵，并对这些矩阵展开研究。但是需要注意的一点是，在文献里仍然没有一个对什么样的矩阵可以被称为图拉普拉斯矩阵问题的共识，而每一个文献作者都宣称他做的矩阵是图拉普拉斯矩阵，因此在阅读这方面的文献的时候需要非常小心。

接下来我们都假设$G$是一个无向的加权图，加权矩阵为对称阵$W$，满足$w_{i,j}=w_{j,i};w_{i,j}\geq0$。同时，我们用到矩阵特征向量时，一般不假设特征向量是正则化的。因此，对于相同元素个数的常数向量$(1,1,1,...,1)$和$(a,a,a,...,a);a\neq0$，在作为特征向量的时候，我们认为它们是等价的。此外，特征值总是会按照升序排列，即当我们谈论到开始的$k$个特征值的时候，我们一般会指从小到大排列的$k$个最小的特征值.

3.1 非正则化拉普拉斯图矩阵

我们定义非正则化的拉普拉斯矩阵为

$L=D-W$ 如上文定义，$D=\text{diag}(d_1,...,d_n)$.我们给出下列与谱聚类理论分析有关的命题并证明.

命题1

矩阵$L$满足以下特性：
1. 对于任意向量$f\in \mathbb{R}^{n}$，我们有$f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{i,j} \cdot (f_i-f_j)^2$
  
  证明：利用$d_i=\sum_{j=1}^nw_{i,j}$的关系，我们有：
  \[f'Lf=f'Df-f'Wf=\sum_{i=1}^nd_if_i^2-\sum_{i,j=1}^nf_iw_{i,j}f_j= \\ \frac{1}{2}(\sum_{i=1}^nf_i^2d_i-2\sum_{i,j}^nf_if_jw_{i,j}+\sum_{j=1}^nf_j^2d_j)\]
代入$D=\text{diag}(d_1,...,d_n)$，我们就得$f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{i,j} \cdot (f_i-f_j)^2$。

$L$是对称半正定的

这是显然的，半正定是因为$L$是一个对角占优矩阵，或者直接从命题1也可以得到。
$L$的最小特征值是0，存在$1_{V}$的特征向量。

显然。
利用对称半正定的性质不难得到，$L$有非负实值的特征值$0=\lambda_1\leq \lambda_2\leq \lambda_n$。

我们利用这些特性来展开谱聚类分析,并用以上命题得到如下非常重要的结论：

命题2

假设$G$是一个无向图，边权矩阵$W$为正，那么特征根$0$的幂次$k$等于这个图里面的连通分支$A_1,..,A_k$的个数.同时特征值$0$的特征空间由连通分支的指标向量$(1_{A_1},1_{A_2},...,1_{A_k})$所扩张而成。

这个命题是一个基本命题，它展示了一个理想情况，即如果通过数据所构建的图$G$真的可以分为很多互不连通的子图的话，那么这个聚类应该怎么展示出来。我们从$k=1$开始证明：

证明：

假设$k=1$，同时注意到对于特征值$0$，我们有$0=f'Lf=\sum_{i,j=1}^{n}w_{i,j} \cdot (f_i-f_j)^2$，因此在$w_{i,j}>0$的地方$f_i=f_j$。如果$k=1$的话，说明特征值$0$的特征向量只有一个$1_{V}$，那么对于任意的$(x_i,x_j)$，满足$w_{i,j}>0$，因此该图有且只有1个连通分支。反之如果有1个连通分支的话，那就意味着$w_{i,j}>0$，也就是$k=1$。充要性得证。

假设$G$有$k$个连通分支，不失一般性，我们假设顶点都由它们所属的连通分支$A_1...,A_k$按顺序排列而成，也就是说此时的边权矩阵W是分块的，可以刻画为$\text{diag}(W_1,...,W_k)$，那么对应的拉普拉斯矩阵$L$也是分块的，相应的为$L=\text{diag}(L_1,...,L_k)$，此时每一个分块$L_i$都是一个图拉普拉斯矩阵，具有命题1的特性，因此每一个$L_i$都有且仅有1个特征根为0，同时特征向量为$1_{A_i}$，从而得到此时L起码有$k$个$0$特征根。同时因为$L$是分块对角的，那么$L$最多只有$k$个特征根为0，充分性得证。

假设$L$有$k$个特征根为0的话，依据$0=f'Lf=\sum_{i,j=1}^nw_{i,j} \cdot (f_i-f_j)^2$这个写法，特征向量只可能是$(0,1,0,0,...,1,0,...)$这种，我们可以把特征向量重排列，依据上面的证明方法仍然可以得到我们想要的结论。

3.2 正则化图拉普拉矩阵

在文献中，正则化拉普拉斯图矩阵一般指两个矩阵:$L_{sym}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2}; L_{rw}=D^{-1}L=I-D^{-1}W$，这两个矩阵彼此的关系非常紧密。第一个矩阵用$L_{sym}$来表示是因为这是一个对称矩阵，而第二个用$L_{rw}$来表示是因为它与随机游走（random walk）理论息息相关。我们用命题3来刻画$L_{rw},L_{sym}$的特性：

命题3：
1. 任取$f\in \mathbb{R}^{n}$，我们有$f'L_{sym}f=\frac{1}{2}\sum_{i,j=1}^nw_{i,j}(\frac{f_i}{\sqrt{d_i}}-\frac{f_j}{\sqrt{d_j}})^2$。
  
  第一个命题用命题1的证明思路是显然的
2. 如果$\lambda,\mu$为$L_{rw}$的特征根和特征向量，那么$\lambda,w=D^{1/2}\mu$也是$L_{sym}$的特征根和特征向量，即$D^{-1}Lu=\lambda u,D^{-1/2}LD^{-1/2}D^{1/2}u=D^{-1/2}Lu=D^{1/2}\lambda u=\lambda w$。
3. $\lambda$是$L_{rw}$的特征值，特征向量为$u$当且仅当$\lambda,u$满足广义特征方程$Lu=\lambda Du$。
4. $0$是 $L_{rw}$ 的特征值，同时 $1_{V}$为 $L_{rw}$ 的特征向量。0为 $L_{sym}$ 的特征值，同时 $D^{1/2}$ $1_{V}$ 为 $L_{sym}$ 的特征向量。
  
  这是显然的，从(3),(1) 可得
5. $L_{sym}$和$L_{rw}$为正实数半正定矩阵，有n个非负实特征根 $0=\lambda_1\leq...\leq\lambda_n$。
  
  非负是显然的，实特征根由对称实矩阵特征根都是实数这个定理得到。

从上面的这些结论我们可以推出针对正则化矩阵的第4个命题：

命题4

令$G$为有非负权值的无向图，那么特征根中$0$的幂次$k$等价于图中的连通分支$A_1,...,A_k$的数目。对于正则拉普拉斯图矩阵$L_{rw}$而言，0的特征空间由$1_{A_{i}}$的这样一组指标向量扩展而成。同时对于$L_{sym}$而言，0的特征空间由 $D^{1/2}\ 1_{A_{i}}$而扩展而成。

与命题2可以相似证明。

这个命题说明什么呢？它说明，如果$G$是有明确子空间边界的，那么我们可以求特征根和特征向量把它们划分开，基于此我们衍生出基本谱聚类算法.

4. 谱聚类算法

非正则化谱聚类

输入:相似度矩阵$S\in \mathbb{R}^{n\times n}$以及要分为的类数k：

通过上述的几个方法构建相似图模型，$W$为相应的邻接矩阵(注意此时$w_{i,j}=0$才代表$v_i,v_j$之间没有边相连接，而$w_{i,j}$越大代表连接越紧密)。
计算非正则化拉普拉斯矩阵$L$。
计算前$k$个特征向量。
把前$k$个特征向量排成k列得到$U\in \mathbb{R}^{n\times k}$。
令$U=(y_1,...,y_n)^T$,其中$y_i\in \mathbb{R}^k$为$U$的第$i$行。
对$n$个数据向量$(y_1,...,y_n)$做k-means聚类，得到标签集$(C_1,...,C_k)$。
输出聚类结果$A_1,...,A_k$，满足$A_i=\{j \vert y_j\in C_i\}$。

注意第6步，以及$y_i$的定义，这在后面非常重要.这个方法看起来很难理解，但是后面将会从三个角度来进行解释。

正则化聚类

输入：相似度矩阵$S\in R^{n*n}$，聚类个数k

构建相似图模型，计算正则化拉普拉斯图矩阵$L_{rw}$。
利用$Lu=\lambda Du$公式计算前k个广义特征向量与特征值。
采用非正则化聚类$(4-7)$所述的步骤进行聚类。

这个算法用正则化拉普拉斯矩阵$L_{rw}$来进行，因此称为正则化谱聚类。对于$L_{sym}$也可以用类似步骤进行，但是它需要进行正则化过程，这一步区别于其它两步，而我们会在第7节找到原因。以下是利用$L_{sym}$进行聚类的过程：

输入：相似度矩阵$S\in R^{n*n}$，聚类个数k

构建相似图模型，计算正则化对称拉普拉斯图矩阵$L_{sym}$。
计算$L_{sym}$的前k个特征向量$(u_1,...,u_k)$，构成$U。$
取$y_i$为U的第i行，同时$y_i=\text{norm}(y_i)$，即对每个$y_i$做正则化操作。
采用非正则化聚类$(4-7)$所述的步骤进行聚类。

以上三种算法，除了各自使用了不同的拉普拉斯图矩阵以外，各自看起来都非常相似。这三个算法的核心技巧都是把数据点$x_i$映射到特征向量空间$y_i$，而从实践效果来看，这种映射是非常有用的。我们将在下一个章节中对其进行解释，简单而言这种变换加强了数据之间的聚类特性，而在经过这种变换后，k-means算法能够简单有效地进行分类。

在我们进入谱聚类的理论解释部分之前，我们想用一个非常简单的例子来展示谱聚类的作用。这个例子将在文章中多次使用，因为它很好地绘出了类别之间的数量关系。这个数据集是一个含有200个数据点的数据集，它们由4个高斯分布混合而成。在处理这个数据集的过程中，我们选择相似度函数为$s(x_i,x_j)=\exp(- \frac{\Vert x_i-x_j\Vert_{2}^2}{2\sigma ^2}),\sigma=1$。

计算好相似图之后，我们考虑全连接图矩阵以及$10-\text{nearest neighbor}$图矩阵，这两个图矩阵依据2.2中的定义构建.我们接下来会展示未正则化拉普拉斯图矩阵$L$与正则化拉普拉斯图矩阵$L_{rw}$的前面几个特征值和特征向量，并对它们进行分析.

1524449771309

这张图可以进行如下解读：

左上角的直方图是我们所取样本的值以及出现的频率.

第一行是以$k-\text{nearest neighbor}$构建的正则化Laplace矩阵$L_{rw}$的前10个特征值的分布图以及相应的特征向量。我们可以看到前4个特征值都是0，说明整个图可以被划分为4个连通分支$A_1,...,A_4$，对应每个连通分支的特征向量都可以写成$\alpha_i*1_{A_i}$的形式，而第5个特征向量就不一样了。

第二行是以$k-\text{nearest neighbor}$构建的未正则化Laplace矩阵$L$的前10个特征值的分布图，以及相应的特征向量.我们可以看到前4个特征值都是0，说明整个图可以被划分为4个连通分支$A_1,...,A_4$，对应每个连通分支的特征向量都可以写成$\alpha_i*1_{A_i}$的形式，而第5个特征向量就不一样了。同时，这里我们发现未正则化的矩阵第5个特征值其实也近似为0，这是未正则化的特性，而正则化矩阵对应的则是分的非常清楚。

第三行是以全连接图所构建的正则化Laplace矩阵$L_{rw}$的前10个特征值的分布图，以及相应的特征向量。注意因为全连接所以只有1个连通分支，因此只有第一个特征向量是$\alpha1_{V}$的，而其它特征向量都不满足这一条件。但是我们也可以看到，模型在第4个特征值与第5个特征值上产生了悬崖式落差，这也预示了可以分为4类.

第四行是以全连接图所构建的未正则化Laplace矩阵$L$的前10个特征值的分布图，以及相应的特征向量。它与第三行相似，但是我们注意到这个时候第5个特征值也很小，与第4个特征值的落差很低。如果我们设置特征值的阈值为0.15的话，我们可能会错误分为5类。两个对比可以看出正则化$L_{rw}$的作用。

5. 从图割视角来看待谱聚类

回顾我们谱聚类的目的，谱聚类是为了把数据点聚为不同的集合，使得依据相似度度量的集合内尽量相似，集合间尽量不相似.对于给定的数据集与相似度图，我们可以把这个问题用图论语言进行阐述：

我们想要找到一个图的割，这个割将图分为了若干子图，并且满足子图之间的连接权重非常低，同时每一个子图内的连接权重非常高.

我们将阐述谱聚类算法与子图分割算法的联系，这里我们采用的工具是研究最小割问题.

给定一个有权值矩阵W的相似图，一个最简单最直接的构建图割的策略是解一个最小割问题.我们记$W(A,B)=\sum_{i\in A,j\in B}w_{i,j}$，同时延续上文的记号记$\bar{A}$为$A$的补集.给定分割的子集数k，最小割方法即选取子图划分$A_1,...,A_k$，从而最小化函数:

$\text{cut}(A_1,...,A_k)=\frac{1}{2}\sum_{i=1}^kW(A_i,\bar{A_i})$ 这里我们用系数$\frac{1}{2}$以保持标记的一致性，并保证每条边只计算一次.对于$k=2$,这个图割算法是非常容易求解的（解一个最大流问题），但是在实际使用中，基于上文公式，这个损失函数一般不会给出一个令人满意的分割.导致这个问题的原因在于，在实际过程中这个最小割的解往往会把整个数据集分为一团和一个非常非常非常孤立的孤立点，这显然不是我们想要的聚类结果.一个改进的方案是我们对划分加以约束，使得$A_1,...,A_k$都相对来说比较”大”.基于这个目的的两个常用的损失函数是$\text{RatioCut}$和$\text{NCut}$.它们的定义是这样的：

$\text{RatioCut}(A_1,...,A_k)=\sum_{i=1}^k\frac{\text{cut}(A_i,\bar{A_i})}{\ \vert A_i\ \vert }\\ \text{NCut}(A_1,...,A_k)=\sum_{i=1}^k\frac{\text{cut}(A_i,\bar{A_i})}{\text{vol}(A_i)},\text{vol}(A_i)=\sum_{x_i\in A_i}d_i$ 也就是说，$\text{RatioCut}$直接用子集元素个数来衡量集合大小，而$\text{NCut}$则用了子集内所有元素的度来衡量大小. 这两个目标函数都是为了类别能够尽量平衡.但是加权图割算法就是一个$NP-hard$问题了，而我们下面会证明整个谱聚类的过程就是为了解决这个问题，以及松弛的$\text{RatioCut}$算法诱导出了非正则化谱聚类.

5.1 对于$k=2$的近似$\text{RatioCut}$算法推导

我们先研究$\text{RatioCut}$，并设定$k=2$来进行初步分析.我们的目的是解决优化问题

$\min_{A\subset V}\text{RatioCut}(A,\bar{A})$ 我们用组合优化的方式来写这个问题.给定一个子集$A\subset V$，我们如下定义一个向量$f=(f_1,...,f_n)'\in \mathbb{R}^{n}$：

$f_i=\begin{cases} \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{cases}$ 此时对于未正则化拉普拉斯矩阵L,我们有

$f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{i,j} \cdot (f_i-f_j)^2\\ \text{注意到}f_i\text{的特性}，\text{在同一类的}f_i,f_j\text{互相抵消得}\\ =\text{cut}(A,\bar{A})(\frac{\ \vert \bar{A}\ \vert }{\ \vert A\ \vert }+\frac{\ \vert A\ \vert }{\ \vert \bar{A}\ \vert }+2)\\ = \vert V \vert \text{RatioCut}(A,\bar{A})$ 同时对$f_i$我们有:

$\sum_{i=1}^nf_i=\sum_{i\in A}\sqrt{\ \vert \bar{A}\ \vert / \ \vert A\ \vert }+\sum_{i\in \bar{A}}-\sqrt{\ \vert A\ \vert /\ \vert \bar{A}\ \vert }=0\\ \vert \vert f \vert \vert ^2=n$ 因此，原优化问题可以写成：

$\min_{A\subset V}f'Lf\\ s.t.\ f\perp 1_{V},\ \vert f\ \vert =\sqrt{n}$ 因为此时向量$f$仍然是个二值向量，因此它仍然是个$NP$难问题.而它的松弛解正好是一个线性规划.我们不加证明地给出一个结论，即这个问题的解向量$f$恰好是L的第二个最小特征值对应的特征向量(其实这个结论是很显然的，但是证明起来就费劲一些).得到了$k=2$的解向量$f\in \mathbb{R}^{n}$之后，我们可以把其映射到一个坐标轴上，这样就形成了数据点$x_i$与坐标轴$R$上的点$f_i$的一个1-1对应，我们对坐标轴上的点进行$k-means$聚类为$C,\bar{C}$，然后对原数据点按照:

\[\begin{cases} v_i\in A&\text{if } f_i \in C,\\ -v_i\in\bar{A}& \text{if } f_i \in\bar{C}. \end{cases}\]

这就是未正则化的谱聚类在k=2的时候的聚类算法（考虑到此时第一列都是1）

5.2 对于任意聚类数k的$\text{RatioCut}$

对于k聚类数的松弛线性规划我们可以写成这样的形式.给出集合V的一个分割$A_1,...,A_k$，我们定义k个指标向量$h_j=(h_{1,j},...,h_{n,j})''$:

$h_{i,j}=\begin{cases} 1/\sqrt{\ \vert A_j\ \vert }&\text{if } v_i\in A_j,\\ 0&\text{otherwise}. \end{cases}$ 此时我们有：

$H'H=I\\ h_k'Lh_k=\sum_{i,j}w_{i,j}(h_{i,k}-h_{j,k})^2=\sum_{i\in A,j\in\bar{A}}w_{i,j}/\ \vert A_k\ \vert +\sum_{j\in A,i\in\bar{A}}w_{i,j}/\ \vert A_k\ \vert \\ =2*\text{cut}(A_k,\bar{A_k})/\ \vert A_k\ \vert$ (注意此时按照原文的定理应该是$2\times \text{cut}(A_{k},\bar{A_k})$)，因为此时权重都没有$1/2$在，因此我认为应该给一个修正是

$1/\sqrt{\ \vert A_j\ \vert }\rightarrow1/\sqrt{2 \vert A_j\ \vert }$ 同时此时有$h_{i}'Lh_{i}=(H'LH)_{ii}$，原来的

$\min_{A_{1},...,A_{k}\subset V}\text{RatioCut}(A_{1},...,A_{k})$ 可以写成是：

$\min_{A_1,...,A_k}Tr(H'LH),s.t. H'H=I$ 和$k=2$的情况一致，我们可以得出此时松弛线性规划的解是$H=(u_1,...,u_k)$，代表了$L$的前$k$个最小的特征根。注意到这个时候我们利用k-means的工具将松弛线性规划映射到了非松弛的线性规划，这个映射一般是有效的，但是这里的理论支持就弱了一些.

以上就是$\text{RatioCut}$方法的松弛线性规划解法，以及整个方法与谱聚类算法的联系。因此谱聚类算法可以视作是解一个图割算法的松弛线性规划，并将松弛解映射到约束条件上来的过程.

近似$\text{NCut}$

上面描述了对于$\text{RatioCut}$的分析，接下来我们来分析$\text{NCut}$的松弛线性规划.还是从$k=2$开始，我们来定义指标向量$f:$

$f_i=\begin{cases} \sqrt{\text{vol}(\bar{A})/ \text{vol}(A)}&\text{if }v_i\in A,\\ -\sqrt{\text{vol}(A)/\text{vol}(\bar{A})}& \text{if }v_i\in \bar{A}. \end{cases}$ 有几个显然的结论是这样的：

\[(Df)'1_{V}=\sum_{v_i\in A}d_i*\sqrt{\frac{\text{vol}(\bar{A})}{\text{vol}(A)}}-\sum_{v_i\in\bar{A}}d_i*\sqrt{\text{vol}(A)/\text{vol}(\bar{A})}=0\] \[f'Df=\sum_{i=1}^nd_if_i^2=\sum_{v_i\in A}d_i*\frac{\text{vol}(\bar{A})}{vol{A}}+\sum_{v_i\in\bar{A}}d_i*\frac{\text{vol}(A)}{\text{vol}(\bar{A})}=\text{vol}(V)\] \[f'Lf=\sum_{w_{i,j}}(f_i-f_j)^2=\sum_{i\in A,j\in \bar{A}}w_{i,j}(\sqrt{\text{vol}(\bar{A})/ \text{vol}(A)}+\sqrt{\text{vol}(A)/\text{vol}(\bar{A})})^2\]

又有$\sum_{i\in A,j\in \bar{A}}w_{i,j}=\text{cut}(A,\bar{A})$，因此代入$\text{NCut}(A_1,...,A_k)$有

\[\text{NCut}(A_1,...,A_k)=\text{cut}(A,\bar{A})*\frac{(\text{vol}(\bar{A})+\text{vol}(A))^2}{\text{vol}(A)\text{vol}(\bar{A})}=\text{vol}(V)*\text{NCut}(A,\bar{A})\]

因此我们可以把问题写成一个最小割的形式： $\min_Af'Lf,s.tDf\perp 1_{V},f'Df=\text{vol}(V)$ 同时f由上定义.它的松弛线性规划的写法与$\text{RatioCut}$一样可以写成

$\min_{f\in \mathbb{R}^{n}}f'Lf,s.tDf\perp 1_{V},f'Df=\text{vol}(V)$ 为了把这个松弛线性规划与拉普拉斯图矩阵相联系，我们令$g=D^{1/2}f$,则原松弛线性规划可以写成

$\min_{g\in \mathbb{R}^{n}}g'D^{-1/2}LD^{-1/2}g,s.t.g\perp D^{1/2}1_{V},\ \vert g\ \vert ^2=\text{vol}(V)$ 此时$D^{-1/2}LD^{-1/2}=L_{sym}$,而同时$D^{1/2}\ 1_{V}$是$L_{sym}$的0特征值的特征根，因此根据我们在$\text{RatioCut}$中所提到的定理，我们可以得出它的松弛解为$L_{sym}$的第2个特征向量。而利用$L_{rw},L_{sym}$之间的关系我们可以得出此时$f$为$L_{rw}$的第2个最小特征值所对应的特征向量。对于$K>2$的结论，我们可以定义一系列指标向量$h_j=(h_{1,j},...,h_{n,j})'$，其定义为

$h_{i,j}=\begin{cases} 1/\sqrt{\text{vol}(A_j)}&\text{if} v_i\in A_j,\\ 0&\text{otherwise}. \end{cases}\\ i=1,...,n;j=1,...,k$ 与$\text{RatioCut}$类似，我们有$H'H=I,h_i'Dh_i=1,h_i'Lh_i=\text{cut}(A_i,\bar{A_i})/\text{vol}(A_i)$.因此我们可以把$\text{NCut}$问题重写为：

$\min_{A_1,...,A_k}Tr(H'LH),s.t. H'DH=I$ 记$T=D^{1/2}H$,它的松弛线性规划为:

$\min_{T\in R^{n*k}}Tr(T'D^{-1/2}LD^{-1/2}T),s.t. T'T=I$ 显然它的解$T$是$L_{sym}$的前k个最小的特征根$T=(t_1,...,t_k)$，同时由$T=D^{1/2}H,t_i=D^{1/2}h_i$，我们得到$H$为$L_{sym}$的前k个最小特征向量，即满足$Lu=\lambda D u$的前k个最小特征值对应的广义特征向量。

对松弛方法的一些评论

以上分析中，我们把谱聚类过程与求解图的k个最小割问题的松弛线性规划所联系了起来，这些结论告诉我们所求解的约束/无约束的拉普拉斯图矩阵的特征向量就是k最小割问题的松弛线性规划解。而k-means算法在这里扮演的角色，就是把这个松弛线性规划解映射到原问题的解上。但是这种做法的最坏情况界可能是无穷，作者给出了这个最坏情况界的证明：

1524486923878

显然这个聚类问题的最优解是切$Vk,V_{k+1},V_{3k},V_{3k+1}$这两组边，即解为2.但是这个实例用谱聚类来做可能是把$v_{k+p},v_{3k+p},p=1,...,k$的边全部切断，此时解为k，让k趋向于无穷我们就可以得到它的最坏情况界是无穷。

但是，我们并没有能够解决这种图割问题的完美工具。当然对于我们刚刚提到的这些问题的松弛解不止一种，很可能有其它的松弛方法能得到更好的结果，而谱聚类方法迷人之处并不在于它总能得到非常好的结果，而是谱聚类方法可以转换为解一个非常简单的标准线性代数问题的过程。

8. 谱聚类实施上的指导性细节

在这一节我们会简要讨论一些谱聚类实现上的细节问题。谱聚类的过程中我们需要选择一些超参数，我们会讨论这些超参数选择的整体影响。

8.1 建立相似图

相似图的构建能对谱聚类产生很大的影响，但是如何构建相似图选择超参数并不这么显然，而相应的理论也还没有完善。

8.1.1 关于相似函数

构建相似图的关键是为数据集点选择相应的相似函数.因为我们等下需要构建的是能够体现相邻关系的邻接图，我们需要保证由我们的相似函数所诱导出的局部相邻关系是有意义的，即我们用相似函数所刻画的”非常相似”这一特征也要在我们的数据空间中得到体现.比如说如果我们想为文本数据构建相似度矩阵，我们也要确保相似函数所度量出非常相似的两个文本实际上也是一类文本.而全局的相似信息并没有那么重要，比如相似度$0.01,0.001$之间其实没什么差别.

如果我们的数据点都可以表示为欧式空间$\mathbb{R}^d$中的点，那么一个比较具有可解释性的相似函数是$s(x_i,x_j)=\exp(\frac{-\Vert x_i-x_j \Vert _{2}^2}{2\sigma^2})$,当然我们仍然要对$\sigma$进行选取。一个准则是相似函数必须基于数据所来源的空间，而并没有一个适用于所有数据的准则。

8.1.2 选哪种相似图

给定了相似函数之后，我们需要对相似图进行选择.在2.2部分我们已经介绍了3个典型的相似图，比如k-近邻图，或者是$\epsilon-$近邻图。我们仍然用来自于不同分布混合的数据来解释不同的图的特性，如图所示：

1524489181209

这里我们使用来自于$R^2$空间的3个分布，如左上角的图所示。我们会发现这3类数据可以用2个弧形和一个高斯分布来描述，位于中间的弧形数据比上面的弧形数据更加稠密。

在$\epsilon$邻接图中，我们可以看到选择一个$\epsilon$是很难的。当$\epsilon=0.3$的时候，中间的弧形区域彼此紧密连接，而高斯区域则并没有那么紧密。当我们的数据集是由不同尺寸不同疏密的集合所构建的时候，这种问题尤为严重。

对于k-近邻图，它可以连接不同尺寸的点，但是我们同时注意到这里把高斯分布和中间的弧形分布的点给连起来了（虽然只有2条边）。因此k-近邻图能够很好地区分彼此相隔比较远的高密度区域，但是它对于疏密不一的相邻区域内的点会进行彼此连接。

对于双向k-近邻图，我们看到它在我们这个数据集里面对于密度不一的两个图表现的非常不错，它区分了中间的弧形与下面的正态分布。但是它的缺点是非常容易把数据集划分为多个密度很大的区域，区域之间彼此不连接，也就是它比较倾向于分更多类。

这里我们没有给全连接图的例子。一般全连接图就是用高斯相似函数$s(x_i,x_j)=\exp(\frac{-\Vert x_i-x_j \Vert _{2}^2}{2\sigma^2})$所诱导出的全连接图。这里参数$\sigma$扮演了与$\epsilon-$邻接图一样的角色：局部相邻区域的点之间用比较高的权重来进行互相连接，而相隔很远的点权重非常接近于0。但是它所得到的相似矩阵并不是一个稀疏矩阵。

作为经验性的指导，我们建议先用k-近邻图试一试，因为它使用起来很方便，需要选取的超参数空间比较小，得出来的权重矩阵是个稀疏矩阵，同时对参数的选取比较鲁棒。

8.1.3 构建相似图的参数

相似图一旦确定，那么我们就要寻找对应的超参数，但是并没有理论对如何寻找超参数进行引导。总之，如果我们期望谱聚类算法将数据集分为k类，而事实上整个数据集有多于k个连通分支，那么谱聚类会直接给出连通分支作为聚类结果（这是显然的）。我们总应该先对图进行分析，以确保相似图是全连通的，或者说只有非常少的连通分支，或者有非常少的孤立点。

对于随机图的连通性研究已经有很多理论，但是它们都是建立在$n\rightarrow\infty$的基础上的。比如对于$n$个来自$\mathbb{R}^d$空间服从某种分布的i.i.d数据，那么如果我们选择$k=log(n)$，那么我们一般能确保这些数据可以被划分为一个连通分支。同样的结论可以在$\epsilon-$邻接图中适用，一般我们选取$\epsilon=(\frac{log(n)}{n})^d$来保证来自同一分布数据的连通性。然而这些理论对于在有限样本集上选聚类个数k没有任何用。

我们来给出一些经验法则。当我们使用$k-$近邻图的时候，连通参数的选择需要满足使得我们最后计算的图是连通的，或者图的连通分支说比我们想要找到的类的个数k要小。对于中小规模的图我们可以采用穷取法一点一点试，但是对于很大的图，一个初步的尝试应该是先选择$k=log(n)$，然后再在附近逐步试验。

对于双向$k-$近邻图，并没有什么经验性的想法。正如我们上文的实验结果，双向$k-$近邻图比起k-近邻图的优势在于它不会把不同密度的点也连接起来，因此趋向于更多分类。如果我们有很多彼此接近的高密度区域，采用双向$k-$近邻图是个很好的手段，但是在那些并没有很显然的聚类关系的情况下，只要距离彼此比较远谱聚类就会把它们聚为两类，这会导致连通分支的数目往往多于聚类个数。总之，双向k-邻近图在处理特定的数据时很有优势，但是这个特定情况往往难以满足，因此对于超参数k选取的经验性指导也有所欠缺。

对于$\epsilon$邻接图，我们建议选择$\epsilon$满足我们得到的相似图是”安全”连通的。找到满足整个图是连通图的最小$\epsilon$是很简单的：我们只需要对全连接图用最小生成树算法来得到一个生成树，然后选取生成树里最长的边值就可以了。但是这个算法有一个问题在于，如果我们的数据集中含有很多的离群点，那么会导致$\epsilon$非常大.同时如果我们的数据集有很多类数据，而这些聚类彼此都非常远，那么此时$\epsilon$的选取也非常大。在以上两个非常可能发生的情形下，$\epsilon$的选取都会很大，使得数据集的尺度发生改变。

最后，如果我们直接用相似函数所生成的全连接图的话，比如我们用高斯相似函数生成全连接图，我们需要对参数$\sigma$进行选取，使得这个全连接图有k-近邻图与$\epsilon-$邻接图所具有的特性。我们需要保证对于大部分的数据点，它们与邻居点的相似度应该”不是太小也不是太大”。对于高斯相似函数，我们常常用以下几个经验性准则：

选取$\sigma$应该满足数据点的平均相似距离所对应的连接点应该是这个点的第k个最近邻点，k的选取与上文相似，满足$k~log(n)+1$.
我们也可以用先用最小生成树算法来选取$\epsilon$，再选择$\sigma=\epsilon$。

注意经验准则仅仅是经验准则，一切都要以所拿到数据的分布为主。

总之，实验结果表示谱聚类对于相似图的改变以及对于超参数的选取比较敏感，但是现在并没有一个非常有效的经验策略来解决这些问题，而我们上面所提出的这些经验性理论没有一个是基于理论的，而基于理论给出超参数选取的一些建议是很有意义的研究方向。

8.2 计算特征向量

在实现谱聚类的过程中，我们需要计算一个很大的Laplace矩阵的前k个特征向量。如果我们用$k-$近邻图或者是$\epsilon$邻接图，那么L矩阵是一个稀疏矩阵。我们已经有了一些有效的方法来计算特征根，而这些算法的收敛速率取决于特征差$\gamma_k= \vert \lambda_k-\lambda_{k+1} \vert$，其中更大的特征差意味着前k个特征值更快收敛.

但是当我们遇到一个特征根要比前一个大很多倍的时候可能会导致一些问题.比如在k个连通分支的理想情况下，特征根0有k次幂，此时特征空间由k个特征向量所张成.但是在实际计算的过程中，这些数值解并不一定收敛到这些特征向量，相反，这些特征向量可能会收敛到一组特征空间的正交基.但是它并不会影响什么.注意到由$1_{A_i}$所张成的特征空间的向量总是可以写成$u=\sum_{i=1}^{k}a_{i}\ 1_{A_i}$，因此在聚类方面就算它是其它向量的线性组合也没有关系.因此所返回的特征向量仍然编码了聚类信息，所以它们可以被k-means来重构类别。

8.3 类别的数目

选择聚类的个数k对于所有的聚类算法而言都是非常重要的问题，已经有很多讨论了.基于分布模型的聚类问题已经有了非常自洽的聚类个数选取理论，这些理论大都是基于数据集的log似然，然后可以用频率学派或者是贝叶斯理论来进一步解释.但是如果我们对于模型并没有什么假设的话，我们可以用很多方式来选取聚类个数.这些方法有ad-hoc测度，比如集合内的相似度与集合间相似度的比值，信息论，间隙统计以及稳定性方法等.这些方法当然也可以直接用于谱聚类，但是正如我们上面所分析的那样，特征根间距方法是专门为谱聚类设计的有效分类方法，而特征根方法可以在3种不同的图拉普拉斯矩阵中使用.这里一个很简单的实现方法就是选择聚类个数k以满足$\lambda_1,...,\lambda_k$是非常小的，同时$\lambda_{k+1}$是相对来说比较大的.这个方法有很多理由，矩阵扰动理论是一个很好的解释，即在有且仅有k个连通分支的理想情况下特征根0的幂次为k，而此时$\lambda_{k+1}>0$.其它的解释可以由谱图解释给出，此时图的许多几何变体可以在图拉普拉斯矩阵的第一特征值的帮助下表达或限制.其实，我们的割的尺寸与一开始的几个特征值的大小息息相关.

通过我们给出的聚类样例，我们来阐述分层特征值的影响.此时我们考虑4组正态分布数据的混合，并逐渐增大每一组分布的方差：

1524557780076

第一行表现出了3组样本的分布情况，我们考虑k=10的k-最近邻图，计算不同样本上的正则化拉普拉斯矩阵$L_{rw}$，并把它们的前10个特征根绘制出来.图中可以看出，对于第一组数据，前4个特征值是0，而$\lambda_{5}-\lambda_{4}$是很大的，因此它显示我们有4个聚类.从第二张图我们也可以看出，对于比较明显的聚类，分层特征值方法是有效的.但是对于高度混合的数据集，这个方法逐渐失效.比如对于第三列数据，如果我们按照特征值来分类的话，可能按照图会分为7类，但是事实上是4类.但是同样地，这种混合的很多的数据集会让很多聚类算法都无从下手，除非我们事先对分布有一个先验.面对这种数据集，就算我们用肉眼看也无能为力.以上实例告诉我们，特征根法对于选取聚类个数具有很大的帮助，一般只要对能看出来的聚类个数，特征根法都可以做出很好的建议.

最后我们需要注意的是，对于聚类个数的选取与对于邻接图超参数的选取是彼此影响的.如果我们对邻接图的连接参数选取很小，那么图很可能会被分为$k_0$个连通分支，而通过特征根方法很显然我们也只能选取$k_0$个连通分支.然而一旦邻接图被确定，我们就不清楚聚类个数与连接参数到底是如何相互影响的.对于聚类个数以及对于超参数的选取都是非常困难的问题，而我们暂时还不知道它们互相影响的机理.

8.4 K-means方法

注意到我们所提出的3个聚类算法都是用k-means算法来作为最后一部分，目的是把特征向量这个松弛解编码到非松弛解上.但是注意到并没有一个定理表明这里一定要用k-means算法.其实从我们对于谱聚类的解释也可以看出，如果我们的数据集确实有很强的聚类表征，那么k-means步骤是非常简单的.比如在理想情况下，对于彼此分离的类，$L,L_{rw}$的特征向量都是相应的常数，此时所有属于一类的数据点$x_i$都被编码到一个相同的点$y_i$，因此可以很容易地通过k-means算法来区分类别.

尽管在谱聚类的最后一步中选聚类算法有些武断，但是$y_i$之间的欧氏距离确实是有意义的.我们已经看到$y_i$直接的欧氏距离与图中的”交流距离”或者相似度具有高度的相关性，同时在Nadler(2006)作者同样指出$y_i$之间的欧氏距离与一个更具有泛化性的扩散距离息息相关.而其它谱聚类的使用者也表明$R^d$空间的欧氏距离是有意义的.

在k-means算法之外，也有一些人在使用其它的方式从松弛解映射到聚类的离散表示.比如Lang采用了超平面法.而Bach与Jordan提出了一个更先进的对于特征向量的加工方法，他们研究了由k个特征向量所张成的子空间，并尽可能地采用多个常数向量来模拟这个子空间.这个做法仍然相当于在$R^k$空间中最小化欧氏距离，同样也可以通过加权$k-means$方法解决.

8.5 我们应该用哪一个图拉普拉斯矩阵呢

上文中我们提出了3个拉普拉斯矩阵，那么到底哪一个矩阵应该使用呢？在讨论这个问题之前，我们应该看一看相似图中每一个数据点的度$d_i$的分布.如果这个相似图是很常规的，大部分顶点都有相同的度，那么所有的拉普拉斯图矩阵彼此都很相似，用于聚类效果都很好.但是如果度的值广泛分布，那么选用不同的拉普拉斯图矩阵结果就非常不同.我认为总体来说，有非常多的理由认为选择正则化的拉普拉斯矩阵比选择非正则化的拉普拉斯矩阵要好，同时在正则化拉普拉斯矩阵中，选择$L_{rw}$比选择$L_{sym}$要好.

8.5.1 不同算法满足的聚类目的

第一个采用正则化谱聚类的论点来源于图割视角.为了简化问题我们不妨假设$k=2$.总之，我们需要完成两个聚类目标：

我们想要找一个分割，这个分割满足不同集合中的数据点彼此不相似，也就是说我们想要让类间的相似度最小
我们想让在同一类的点尽量相似，也就是说我们想要让类内相似度尽可能大

所有的$\text{RatioCut}$以及$\text{NCut}$都能达到第一个任务，但是对于第二个任务而言，不同的算法表现都不一样.注意到$W(A,A)=\text{vol}(A)-\text{cut}(A,\bar{A})$，如果$\text{vol}(A)$很大，同时$\text{cut}(A,\bar{A})$很小的话，类内相似度就会很大，这正是$\text{NCut}$所能达到的目的。同时我们也可以考虑另外一个叫做$\text{MinMaxCut}$的损失函数：

\[\text{MinMax}\text{Cut}(A_1,...A_k)=\sum_{i=1}^k\frac{\text{cut}(A_i,\bar{A_i})}{W(A_i,A_i)}\]

对比$\text{NCut}$，这里把每一项的分母换了一下。事实上，$\text{NCut}$与$\text{MinMaxCut}$往往都会最小化$\text{cut}(A,\bar{A})$，因此分母项并不重要。同时，最小化$\text{MinMaxCut}$问题的松弛算法与最小化$\text{NCut}$的松弛算法的解一模一样，即用$L_{rw}$的特征向量做的谱聚类算法，因此正则化谱聚类可以同时实现以上两个目标. 同时考虑$\text{RatioCut}$的情形，我们的目的是最大化$\vert A \vert , \vert \bar{A} \vert$ 从而代替$\text{vol}(A)$,$\text{vol}(\bar{A})$ .但是$\vert A \vert , \vert \bar{A} \vert$与类内相似度没有必然的联系，因为类内相似度与边有关，但是和A中顶点的个数无关.比如说如果集合A有很多顶点，但是顶点之间的边权重很低，那么最小化$\text{RatioCut}$并不能达到第二个目的，而$\text{RatioCut}$的松弛解是未正则化的谱聚类.

因此我们的脑海里要有第一个观念，就是正则化的谱聚类能够达成上面的2种目的，而未正则化的谱聚类则只能达到第一种聚类目的。

8.5.2 一致性问题

关于正则化谱聚类的另外一个完全不同的论点来自于两个算法的统计分析。我们假设数据集$(x_1,...,x_n)$是取自某个分布P的来自数据空间$X$的i.i.d样本.一个最基本的问题是一致性问题：假设我采样越来越多的点，谱聚类的结果能够收敛到对数据空间$X$的一个有效的分割吗？

对于正则化谱聚类算法，能够证明这个命题是成立的。从数学角度有人已经证明了当$n\rightarrow\infty$的时候，矩阵$L_{sym}$收敛到数据空间$X$的一个连续函数$C(X)$所对应空间的一个算子$U$，很自然地此时$L_{sym}$的特征值和特征向量同样收敛到U的特征值和特征向量。

可以证明由X诱导的算子U的特征根可以被解释为谱聚类的随机游走理论。也就是说，如果我们考虑在数据空间X上的扩散过程，那么由U的特征向量所得出的划分是稳定的，在不同的聚类之间不会频繁地游走.这些关于正则化谱聚类的一致性陈述都是在非常弱的条件下成立的，这些条件在现实世界的数据集上往往都能满足.对于这些内容的证明所需要的知识已经超出了本文的讨论范围，有兴趣的读者可以看von Luxburg的相关文章。

与正则化谱聚类清晰的收敛断言相反，对于未正则化谱聚类的情形并没有一个令人满意的理论。我们现在只能证明未正则化的谱聚类很可能不能收敛，或者说会收敛到一个由数据空间的某个单点所构成的集合上，这个结论是非常弱的.从数学角度，即使我们可以证明矩阵$L/n$可以收敛到$C(X)$上的一个有界算子$T$，这个有界算子T的谱性质也是非常糟糕的.我们可以构建一些实例，表明这个问题不仅会出现在样本量极大的情形下，对于样本点很少的情形仍然可能导致非常不好的结果.不过我们可以给出这些问题不发生的一个条件，即我们必须保证矩阵L的特征值以及相应的特征向量比图中的最小度还要小.这意味着如果我们要用前k个特征向量来聚类的话，那么我们需要满足对$i=1,...,k,\lambda_{i}<<\min_{j=1,...,n}d_j$.这个限制条件的数学解释是大于$\min d_{j}$的特征值对应的特征向量近似于一个狄利克雷函数，也就是说除了几个单点以外基本都是0.如果我们用这些特征向量来聚类，那么它们会把一个特征向量非0的单点分出来，这显然不是我们想要的结果.具体的证明请自己查阅文献。

我们可以继续通过上面提出的例子来阐述这个现象.我们考虑未正则化拉普拉斯矩阵的前k个特征值与特征向量，同时为高斯相似度函数选择不同的$\sigma$参数，如图所示：

1524570337393

在$\min d_j$之下的特征值用红色菱形标注，其它用蓝色*标注.对于$\sigma=1$的情形，前4个特征值都在$\min d_j$下方，当我们增大$\sigma$的时候，情况发生了变化.当$\sigma=2$我们可以看到只有前3个特征根在$\min d_j$下方，而第4，5个特征向量则出现了如狄利克雷函数一样的峰值.在$\sigma=5$的情形下，相应满足条件的特征根只有2个，而特征向量同样出现了狄利克雷函数一样的问题.这些特征向量当然是不适合做聚类的.当$n\rightarrow\infty$的时候，特征向量会收敛到狄利克雷函数，以上这些就阐明了为什么未正则化谱聚类在小数据集与大数据集上都可能出现相应的问题。

这些问题在未正则化拉普拉斯图矩阵$L$上很常见，但是在正则化$L_{rw},L_{sym}$上就得到了有效解决，因此从统计学观点我们应避免使用未正则化拉普拉斯矩阵。

8.5.3 选哪个正则化拉普拉斯图矩阵呢

对比$L_{rw},L_{sym}$的不同之处以及谱聚类算法，3个对谱聚类的数学解释都倾向于采用$L_{rw}$，原因是$L_{rw}$的特征向量就是聚类的指标向量 $1_{A_{i}}$，而$L_{sym}$的特征向量前要乘$D^{1/2}$，这可能会带来一些意外.因为使用$L_{sym}$并不会减少计算负担，因此我们推荐使用$L_{rw}$。