22 谱聚类——Spectral Clustering

22.1 背景介绍

我们在一般的聚类过程中，普遍理性而言会有两种思想：

1. 将聚集在一起的点进行聚类（离得近的为同一类数据），例如可以线性分类的一组数据。
2. 将具有联通性的一堆点进行聚类，如环形等线性不可分的数据。（这种其实在一定情况下也可以通过Kernel+K-Mean实现——进行非线性转换）

所以我们可以将聚类方法分成两大类：

1. compactness: K-means, GMM
2. connectivity: Spectral Clustering

22.2 模型介绍

Spectral Clustering实际上可以表示为一个带权重的无向图。

先给这张图做一个定义：

1. 基本数据表示为：
   G = { V , E } , V = { 1 , 2 , … , N } , W = [ w i j ] , 1 ≤ i , j ≤ N G = {\lbrace V, E \rbrace}, \quad V = {\lbrace 1, 2, \dots, N \rbrace}, \quad W = [w_{ij}], 1 \leq i, j \leq N G={V,E},V={1,2,…,N},W=[wij​],1≤i,j≤N

2. 其中$W$也被称为Simlarity Matrix或Affinity Matrix，$w_{ij}$​表示为：
   w i j = { K ( x i , x j ) = exp ⁡ { − ∥ x i − x j ∥ 2 2 2 σ 2 } ( i , j ) ∈ E 0 o t h e r w i s e w_{ij} = \begin{cases} K(x_i, x_j) = \exp{\lbrace - \frac{{\lVert x_i - x_j \rVert}_2^2}{2 \sigma^2} \rbrace} & (i, j) \in E \\ 0 & otherwise \end{cases} wij​={K(xi​,xj​)=exp{−2σ2∥xi​−xj​∥22​​}0​(i,j)∈Eotherwise​
   代表了节点之间的相似度

3. 再做一个定义，用于表示一个符号：若$A\subset V,B\subset V,A\cap B=\varnothing$，则表示集合之间的相似度为
   $$W(A,B)=\sum _{i\in A,j\in B}{w}_{ij}$$

22.3 模型导出

接下来具体导出该模型的公式：

1. 我们可以认为每个节点用于表示一个数据，而边表示数据之间的关联，而现在的目标是将数据分成$K$类，且每一组数据之间的相似度最低，所以我们自然要删除一些边，将图变成由$K$个连通图组成。

2. 为了数学化表示，我们定义一个函数$Cut(V)$用于表示集合$V$​删除边的权值之和：
   $$Cut(V)=Cut(A_1,A_2,\dots ,A_K)=\sum _{k=1}^{K}W(A_k,\overline{A_k})$$

3. 但如果通过$Cut(V)$用于表示目标函数，未免有失偏颇。因为我们切开的每一类中的节点数都是不同的，对于他们的相似度，我们应该做一个加权平均。

4. 一般来说我们会通过节点数求均值：${\sum }_{k=1}^K\frac{W(A_k,\overline{A_k})}{|A_k|}$。但本模型是通过边表示相似度，所以我们应当用类中度数加权，将新的函数定义为$Ncut(V)$：
   $$\{\begin{array}{l}Ncut(V)={\sum }_{k=1}^K\frac{W(A_k,\overline{A_k})}{{\sum }_{i\in A_k}degree(i)}\\ degree(i)={\sum }_{j=1}^N{w}_{ij}\end{array}$$

5. 所以我们最后的目标就是这样一个带优化问题：
   { A k ˉ } k = 1 K = a r g min ⁡ { A k ˉ } k = 1 K N c u t ( V ) {\lbrace {\bar{A_k}} \rbrace}_{k=1}^K = arg\min_{{\lbrace {\bar{A_k}} \rbrace}_{k=1}^K} Ncut(V) {Ak​ˉ​}k=1K​=arg{Ak​ˉ​}k=1K​min​Ncut(V)

由于这样的数学表示有些过于繁杂，我们自然会想通过矩阵将其表示，首先引入一个指示向量替代目标问题：

1. 假定有指示向量（indicator vector），定义为：
   { Y = ( y 1   y 2   …   y N ) N × K T y i ∈ { 0 , 1 } K ∑ j = 1 K y i j = 1 \begin{cases} Y = {(y_1 \ y_2 \ \dots \ y_N)}_{N \times K}^T \\ y_i \in {\lbrace 0, 1 \rbrace}^K \\ \sum_{j=1}^K y_{ij} = 1 \end{cases} ⎩ ⎨ ⎧​Y=(y1​ y2​ … yN​)N×KT​yi​∈{0,1}K∑j=1K​yij​=1​
   所以大致可以表现为$y_i={(0\dots 1\dots 0)}^T$，用于表示第$i$个样本属于第$j$个类别

2. 那么我们就可以将带优化问题表示为：
   $$\bar{Y}=arg\underset{Y}{\min }Ncut(V)$$

22.4 模型的矩阵形式

继目标问题之后，我们也要将优化问题化为矩阵形式：首先化简$Ncut(V)$函数，下文中将$degree(i)$简化为$d_i$：

$$\begin{array}{rl}Ncut(V)& =\sum _{k=1}^K\frac{W(A_k,\overline{A_k})}{{\sum }_{i\in A_k}{d}_i}=\left(\begin{array}{ccc}\frac{W(A_1,\overline{A_1})}{{\sum }_{i\in A_1}{d}_i}& & \\ & \dots & \\ & & \frac{W(A_K,\overline{A_K})}{{\sum }_{i\in A_K}{d}_i}\end{array}\right)\\ & =tr\left[\underset{O_{K\times K}}{\underbrace{\left(\begin{array}{ccc}W(A_1,\overline{A_1})& & \\ & \dots & \\ & & W(A_K,\overline{A_K})\end{array}\right)}}\underset{P_{K\times K}}{\underbrace{{\left(\begin{array}{ccc}{\sum }_{i\in A_1}{d}_i& & \\ & \dots & \\ & & {\sum }_{i\in A_K}{d}_i\end{array}\right)}^{-1}}}\right]\\ & =tr(O\cdot P^{-1})\end{array}$$

我们将$Ncut(V)$函数拆分成了两部分，我们现在已知$W,Y$，我们需要通过已知条件构造出$O,P$。为了构造出$P$：

1. 我们先来了解一下$Y$​的性质：
   $$\begin{array}{rl}{Y}^{T}Y& =(y_1{y}_2\dots y_N)\left(\begin{array}{c}{y}_1^T\\ y_2^T\\ \dots \\ y_N^T\end{array}\right)=\sum _{i=1}^N\underset{=diag(0,\dots ,1,\dots ,0)}{\underbrace{y_i{y}_i^T}}\\ & =\underset{N={\sum }_{i=1}^K{N}_i}{\underbrace{\left(\begin{array}{ccc}{N}_1& & \\ & \dots & \\ & & N_K\end{array}\right)}}=\left(\begin{array}{ccc}{\sum }_{i\in A_1}1& & \\ & \dots & \\ & & {\sum }_{i\in A_K}1\end{array}\right)\end{array}$$

2. 我们发现，倘如能把矩阵中的$1$换成$d_i$，结果就是$P$了，所以：
   $$\{\begin{array}{l}P=\left(\begin{array}{ccc}{\sum }_{i\in A_1}{d}_i& & \\ & \dots & \\ & & {\sum }_{i\in A_K}{d}_i\end{array}\right)=Y^{T}DY\\ D=\left(\begin{array}{ccc}{d}_1& & \\ & \dots & \\ & & d_N\end{array}\right)=diag(\underset{{({\sum }_{j=1}^N{w}_{1j}\dots {\sum }_{j=1}^N{w}_{Nj})}^T}{\underbrace{W\cdot 1_N}})\end{array}$$

为了构造出$O$：

1. 我们先对$O$进行一些数学变换，根据$W(A_k,\overline{A_k})=W(A_k,V)-W(A_k,A_k)$可得：
   $$\begin{array}{rl}O& =\left(\begin{array}{ccc}W(A_1,\overline{A_1})& & \\ & \dots & \\ & & W(A_K,\overline{A_K})\end{array}\right)\\ & =\left(\begin{array}{ccc}{\sum }_{i\in A_1}{d}_i& & \\ & \dots & \\ & & {\sum }_{i\in A_K}{d}_i\end{array}\right)-\left(\begin{array}{ccc}W(A_1,A_1)& & \\ & \dots & \\ & & W(A_K,A_K)\end{array}\right)\end{array}$$

2. 为了表示$O$，我们发现$left=Y^{T}DY$，这个已经求出来了。为了表示$right$，我们模仿着看一下$Y^{T}WY$是什么（我们知道$y_i{y}_j^T$的矩阵只有在$(i,j)$的位置上为$1$，其他地方都是$0$）：
   $$\begin{array}{rl}{Y}^{T}WY& =\sum _{i=1}^N\sum _{j=1}^N{y}_i{w}_{ij}{y}_j^T=\sum _{i=1}^N\sum _{j=1}^N{y}_i{y}_j^T{w}_{ij}\\ & =\left(\begin{array}{ccc}{\sum }_{i\in A_1}{\sum }_{j\in A_1}{w}_{ij}& \dots & {\sum }_{i\in A_1}{\sum }_{j\in A_K}{w}_{ij}\\ \dots & \dots & \\ {\sum }_{i\in A_K}{\sum }_{j\in A_1}{w}_{ij}& & {\sum }_{i\in A_K}{\sum }_{j\in A_K}{w}_{ij}\end{array}\right)\end{array}$$

3. 我们发现其实$Y^{T}WY\ne right$，但如果我们假设$O^{{}^{\prime }}=Y^{T}DY-Y^{T}WY$，我们会发现其实用$O^{{}^{\prime }}$替代$O$进行计算也没有问题，因为我们只需要求trace，$O^{{}^{\prime }}$的对角线与$O$​相同即可。用数学语言表示为：
   $$tr(O\cdot P^{-1})=tr(O^{{}^{\prime }}\cdot P^{-1})$$

根据以上证明，我们可以将问题简化为：
$$\bar{Y}=arg\underset{Y}{\min }tr(Y^T(D-W)Y\cdot {(Y^{T}DY)}^{-1})$$