谱聚类

Spectral Clustering

谱聚类是一种基于图论和线性代数的聚类方法，利用数据点之间的相似性来进行聚类。对比 k-means 算法，谱聚类对数据分布的适应性更强，能够有效地处理非凸形状的数据集，同时聚类的计算量也小很多。

定义

对于图 $G=(V,E)$，其中 $V=v_1,v_2,\cdots ,v_n$ 为点的集合，$E=\{w_{ij}\}$ 为边的集合，$w_{ij}$ 为边的权重

在谱聚类中，相似度矩阵的构建方法直接影响最终聚类效果，常见的三种策略如下：

• 全连接法
• ε-近邻法
• k-近邻法

一般采用全连接法，即所有点对计算相似度，这个时候图 $G$ 的邻接矩阵 $\mathbf{W}$ 与相似度矩阵 $\mathbf{S}$ 相同。

$$w_{ij}=s_{ij}=\exp (-\frac{{\Vert x_i-x_j\Vert }_2^2}{2{\sigma }^2})$$$$\mathbf{W}=\mathbf{S}=\left(\begin{array}{ccc}{w}_{11}& \cdots & w_{1n}\\ ⋮& & ⋮\\ w_{n1}& \cdots & w_{nn}\end{array}\right)$$

对于图中的每一个点 $v_i$，定义它的度 $d_i$ 为和它相连的所有边的权重之和：

$$d_i=\sum _{j=1}^n{w}_{ij}$$

可以得到一个 $n\times n$ 的度矩阵 $\mathbf{D}$，它是一个对角矩阵，对应第 $i$ 行的第 $i$ 个点的度数：

$$\mathbf{D}=\left(\begin{array}{ccc}{d}_1& \dots & \dots \\ ⋮& d_2& \dots \\ ⋮& ⋮& d_n\end{array}\right)$$

假设聚类的目标为 $K$ 个，对图进行分割：

$$\text{Cut}(V)=\text{Cut}(A_1,A_2,\cdots ,A_K)=\frac{1}{2}\sum _{k=1}^K\mathbf{W}(A_K,\overline{A_K})$$

我们的目标就是求解：$\underset{A_K}{min}\text{Cut}(V)$

但这种容易出现问题：选择一个权重最小的边缘点进行分割就可以最小化目标，但我们希望的是 $A_1,A_2,\cdots ,A_K$ 都相对来说比较“大”。

两个常用的解决方法为：

• RatioCut

$$\text{RatioCut}(V)=\frac{1}{2}\sum _{k=1}^K\frac{\mathbf{W}(A_k,\overline{A_k})}{\left|A_k\right|}$$

$\left|A_k\right|$表示 $A$ 中包含顶点的数目

• NCut

$$\text{NCut}(V)=\frac{1}{2}\sum _{k=1}^K\frac{\mathbf{W}(A_k,\overline{A_k})}{\sum _{i\in A_k}{d}_i}$$

RatioCut 直接用子集元素个数来衡量集合大小，而 NCut 则用了子集内所有元素的度来衡量大小。

拉普拉斯矩阵

拉普拉斯矩阵 (Laplacian Matrix) ，也称为基尔霍夫矩阵，是图的一种矩阵表示形式，对于图 $G$ 其定义为：

$$\mathbf{L}=\mathbf{D}-\mathbf{W}$$

其标准化形式为：

$$\mathbf{L}={\mathbf{D}}^{-\frac{1}{2}}(\mathbf{D}-\mathbf{W}){\mathbf{D}}^{-\frac{1}{2}}$$

对于任意的向量 $f$，有：

$$f^{\mathrm{\top }}Lf=\frac{1}{2}\sum _{i,j}^n{w}_{ij}{(f_i-f_j)}^2$$

RatioCut 求解

引入 $A_1,A_2,\cdots ,A_K$ 的指示向量 $h_j\in \{h_1,h_2,\cdots ,h_K\}$，$v_i$ 表示其中的第 $n$ 个样本，定义：

$$h_{ij}=\{\begin{array}{ll}0& v_i\notin A_j\\ \frac{1}{\sqrt{\left|A_j\right|}}& v_i\in A_j\end{array}$$

所有 $h_j$ 组成矩阵 $\mathbf{H}=[h_1,h_2,\cdots ,h_K]\in {\mathbb{R}}^{n\times K}$

有：

$${\mathbf{H}}^{\mathrm{\top }}\mathbf{H}={\mathbf{I}}_K$$

对于 $h_j$：

$$\begin{array}{rl}{h}_j^{\mathrm{\top }}\mathbf{L}{h}_j& =\frac{1}{2}\sum _{m=1}^n\sum _{n=1}^n{w}_{mn}(h_{mj}-h_{nj}{)}^2\\ & =\frac{1}{2}(\sum _{m\in A_j,n\notin A_j}{w}_{mn}(\frac{1}{\sqrt{\left|A_j\right|}}-0{)}^2+\sum _{m\notin A_j,n\in A_j}{w}_{mn}(0-\frac{1}{\sqrt{\left|A_j\right|}}{)}^2)\\ & =\frac{\text{Cut}(A_k,\overline{A_k})}{\left|A_j\right|}\end{array}$$

例子

顶点集 $A_j=\{v_1,v_2\}$，$\left|A_j\right|=2$

边权重 $w_{13}=w_{23}=1$，其余为 $0$

计算：

$$\text{Cut}(A_j,\overline{A_j})=w_{13}+w_{23}=2$$$$h_j=[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0]$$

有：

$$\text{RatioCut}(A_1,A_2,\cdots ,A_K)=\sum _{j=1}^K{h}_j^{\mathrm{\top }}\mathbf{L}{h}_j=\mathrm{Tr}({\mathbf{H}}^{\mathrm{\top }}\mathbf{L}\mathbf{H})$$

矩阵的迹

矩阵的迹表示的是特征值的和

$$\mathrm{Tr}(\mathbf{A})=\sum _{i=1}^n{a}_{ii}=a_{11}+a_{22}+\cdots +a_{nn}$$

则我们的优化目标为：

$$\underset{\mathbf{H}}{\text{argmin}}\mathrm{Tr}\left({\mathbf{H}}^{\mathrm{\top }}\mathbf{L}\mathbf{H}\right)\text{ s.t. }{\mathbf{H}}^{\mathrm{\top }}\mathbf{H}={\mathbf{I}}_K$$

这是一个NP-hard问题

argmin

argmin 函数用于找到使某个函数取得最小值的自变量（参数）

如对于函数 $f(x)=x^2-4x+4$，$\text{argmin}(x)=2$

参考论文A short theory of the Rayleigh-Ritz method 引入瑞利商极小化

我们的目标等价于找到 $L$ 的前 $K$ 个最小瑞利商，即最小特征值对应的特征向量：

$$\mathrm{Tr}({\mathbf{H}}^{\mathrm{\top }}\mathbf{L}\mathbf{H})=\sum _{j=1}^K{h}_j^{\mathrm{\top }}\mathbf{L}{h}_j=\sum _{j=1}^{K}R(\mathbf{L},h_j)$$

选择 $\mathbf{L}$ 的前 K 个最小特征值对应的特征向量组成 $\mathbf{H}$：

$$\mathbf{H}=[u_1,u_2,\cdots ,u_K]$$

其中 $\mathbf{L}{u}_j={\lambda }_j{u}_j$，且 ${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_K$

最后，对 $\mathbf{H}$ 的行向量进行k-means聚类，得到最终划分。

NCut 求解

类似的，有：

$$h_{ij}=\{\begin{array}{ll}0& v_i\notin A_j\\ \frac{1}{\sqrt{\sum _{i\in A_k}{d}_i}}& v_i\in A_j\end{array}$$

有：

$${\mathbf{H}}^{\mathrm{\top }}\mathbf{D}\mathbf{H}={\mathbf{I}}_K$$

对于 $h_j$：

$$\begin{array}{rl}{h}_j^{\mathrm{\top }}\mathbf{L}{h}_j& =\frac{1}{2}\sum _{m=1}^n\sum _{n=1}^n{w}_{mn}(h_{mj}-h_{nj}{)}^2\\ & =\frac{\text{Cut}(A_k,\overline{A_k})}{\sum _{i\in A_k}{d}_i}\end{array}$$

优化目标为：

$$\underset{\mathbf{H}}{\text{argmin}}\mathrm{Tr}\left({\mathbf{H}}^{\mathrm{\top }}\mathbf{L}\mathbf{H}\right)\text{ s.t. }{\mathbf{H}}^{\mathrm{\top }}\mathbf{D}\mathbf{H}={\mathbf{I}}_K$$

令：

$$\mathbf{U}={\mathbf{D}}^{\frac{1}{2}}\mathbf{H}$$

则原问题转换为：

$$\underset{\mathbf{U}}{\text{argmin}}\mathrm{Tr}\left({\mathbf{U}}^{\mathrm{\top }}{\mathbf{D}}^{-\frac{1}{2}}\mathbf{L}{\mathbf{D}}^{-\frac{1}{2}}\mathbf{U}\right)\text{ s.t. }{\mathbf{U}}^{\mathrm{\top }}\mathbf{U}={\mathbf{I}}_K$$

求出 ${\mathbf{D}}^{-\frac{1}{2}}\mathbf{L}{\mathbf{D}}^{-\frac{1}{2}}$ 的最小的前 K 个特征值对应的特征向量，标准化后组成特征矩阵 $\mathbf{U}$，进行一次k-means聚类即可。