谱聚类

引言

谱聚类（spectual clustering)是一类非常使用的聚类方法。因为算法基于谱图的理论基础上，因此成为谱聚类。与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点，因此应用广泛，同时是目前研究和应用最广泛的聚类算法。

谱聚类算法

谱聚类思想

谱聚类的本质思想就是将数据当做空间中的点，这些点之间可以用边连接，形成无向图。

其中，距离较远的点之间的权重较低，距离较近的点之间的权重较高，

对图进行切图，让不同的子图之间的权重和尽可能的低，子图内的权重尽可能的高，进而达到聚类的目的。

基础知识

无向权重图

我们用$G = (V, E)$来表示无向权重图。其中$V = (v_1, v_2 ,..,v_n)$ 表示点，$E$表示边，边连接两个点，我们定义边的值为权重$w_{ij}$,因为是无向图，因此$w_{ij} = w_{ji}$,

对于有边连接的点，有$w_{ij} > 0$
对于没有边连接的点，有$w_{ij} = 0$

对于点$v_i$,我们定义它的度为与它相连接的所有的边的权重的和，即：

$$d_{i} = \sum_{j=1}^n w_{ij}$$

因此对于无向图，我们可以定义相应的度矩阵：

$$D = \begin{pmatrix} d_1 & & & \\ & d_2& & \\ & & ...& \\ & & & d_n \end{pmatrix}$$

对于度矩阵，只有主对角线上有值。值表示每一个点的度。

邻接矩阵

邻接矩阵$W$,其中$w_{ij}$为$v_i$与$v_j$之间的权重

那么我们如何定义权重呢？一般场景下，我们利用两点之间的距离来构建邻接矩阵。

一般有三种方法：$\epsilon$近邻法，k近邻法，全连接法

$\epsilon$近邻法

$$w_{ij} =\left\{\begin{matrix} 0, \ S_{ij}>\epsilon \\ \epsilon,\ S_{ij}\leq \epsilon \end{matrix}\right.$$

其中$S_{ij} =||x_i - x_j ||^2$

$k$近邻法

取每个样本最近的k个点作为近邻，只有和样本距离最近的k个点间的$w_{ij} > 0$。一般为了对称性，采用下面的公式处理

第一种：

$$w_{ji} = w_{ij} =\left\{\begin{matrix} 0, \ x_i \notin KNN(x_j) \ and \ x_j \notin KNN(x_j) \\ exp(-\frac{||x_i - x_j||^2}{2\sigma^2}), \ x_i \in KNN(x_j) \ or \ x_j \in KNN(x_j) \end{matrix}\right.$$

第二种：

$$w_{ji} = w_{ij} =\left\{\begin{matrix} 0, \ x_i \notin KNN(x_j) \ or \ x_j \notin KNN(x_j) \\ exp(-\frac{||x_i - x_j||^2}{2\sigma^2}), \ x_i \in KNN(x_j) \ and \ x_j \in KNN(x_j) \end{matrix}\right.$$

全连接法

当然用的最多的还是全连接法，这个最简单：

$$w_{ji} = S_{ij} = exp(-\frac{||x_i - x_j||^2_2}{2\sigma^2})$$

相似矩阵

相似矩阵就是上面的S矩阵，其中：

$$S_{ij} = exp(-\frac{||x_i - x_j||^2_2}{2\sigma^2})$$

拉普拉斯矩阵

$$L = D - W$$

矩阵$L$就是laplace矩阵。laplace矩阵有几个优良性质：

1） 矩阵$L$是对称矩阵

2） 矩阵$L$的特征值都是实数

3） 对于任意向量$f$，都有

$$f^TLf = \frac{1}{2} \sum_{i=1,j =1}^N w_{ij}(f_i - f_j)^2$$

证明如下：

$$f^TLf = f^TDf - f^TWf = \sum_{i=1}^N d_if_i^2 - \sum_{i=1,j=1}^{N} w_{ij}f_if_j =\frac{1}{2}(\sum_{i=1}^N d_if_i^2 - 2\sum_{i=1,j=1}^{N} w_{ij}f_if_j + \sum_{i=1}^N d_jf_j^2)= \frac{1}{2} \sum_{i=1,j =1}^N w_{ij}(f_i - f_j)^2$$

4） 矩阵$L$是半正定矩阵

无向图切图

将G切分成相互没有连接的k个子图，每个子图的点的集合$A_1,A_2,...,A_k$,满足$A_i \bigcap A_j = \phi$ 且 $A_1 \bigcup A_2 \bigcup ... \bigcup A_k = V$

对于任意两个子图，其切图的权重为：

$$W(A,B) = \sum_{i \in A, j \in B} w_{ij}$$

定义$cut(A_1,A_2,...,A_k) = \frac{1}{2}\sum_{i=1}^k W(A_i, \overline A_i)$

切图的目的就是使子图内的点的权重的和尽可能的高，子图间的点的权重和尽可能的低。

因此可以通过最小化$cut(A_1,A_2,...,A_k)$实现，但是单纯最小化$cut(A_1,A_2,...,A_k)$是有问题的，会导致切图得到不理想的结果，如将某一个点切为一个图，剩余的点切为一个图等等，因此需要对切图进行一定的约束。

切图

有了点之间的度量，那么我们还剩下一个问题，就是按照什么规则将点划分到不同的区域，既然谱聚类是基于图算法，那么我们就利用切图的算法，将点划分到不同的子类中。

RatioCut

Ratio切图不仅要最小化$cut(A_1,A_2,...,A_k)$，还要最大化每个子图中点的个数，因此可以用下面的公式来表示：

$$RationCut(A_1,A_2,...,A_k) = \frac{1}{2} \sum_{i=1}^k \frac{ W(A_i, \overline A_i)}{|A_i|}$$

其中${|A_i|}$是A中的点的个数

那么我们该如何解析这个函数呢？我们引入指示变量$h_j = (h_1,...,h_k), j=1,2,...,k$,$h_j$是一个n维向量，定义$h_{ji}$:

$$h_{ji} =\left\{\begin{matrix} 0, \ v_{i}\notin A_j \\ \frac{1}{\sqrt{|A_j|}},\ v_i \in A_j \end{matrix}\right.$$ $$h_i^TLh_i = \frac{1}{2} \sum_{m=1}\sum_{n=1} w_{mn}(h_{im} -h_{in})^2 = \frac{1}{2} (\sum_{m \in A_i, n \notin A_i} w_{mn}(\frac{1}{\sqrt{|A_i|}} - 0)^2$$ $$+ \sum_{m \notin A_i, n \in A_i} w_{mn}(\frac{1}{|A_j|}))$$ $$=\frac{1}{2}(\sum_{m \in A_i, n \notin A_i} w_{mn}\frac{1}{|A_i|}) + \sum_{m \notin A_i, n \in A_i} w_{mn}\frac{1}{|A_i|}))$$ $$=\frac{1}{2}(cut(A_i,\overline A_i)\frac{1}{|A_i|} + cut(\overline A_i,A_i)\frac{1}{|A_i|}) = \frac{cut(A_i,\overline A_i)}{|A_i|}$$

因此有：

$$RationCut(A_1,A_2,...,A_k) = \sum_{i=1}^k h_i^TLh_i = \sum_{i=1}^k (H^TLH)_{ii} = tr(H^TLH)$$

因此问题转化为：

$$argmin_H \ tr(H^TLH) , \ s.t. H^TH = I$$

这是一个NP-hard问题，我们可以近似来解决这个问题。可以对$H^TLH$做特征值分解，找到k个最小的特征值，这些特征值对应的特征向量组成的n*k维矩阵就是H（类似于PCA的过程）。

由于上面的方式损失了少量的信息，导致对应的H不能完全只是个样本的归属，一次你得到n*k矩阵后需要对每一行进行一个常规的聚类，如k-means。

NCut切图

$$NCut(A_1,A_2,...,A_k) = \frac{1}{2} \sum_{i=1}^k \frac{ W(A_i, \overline A_i)}{vol(A_i)}$$

也就是将RatioCut的分母用$vol(A_i)$代替。

$$vol(A_i) = \sum_{i \ in A_i} d_i$$

即用权重和来代替点的个数，因为点多，权重不一定大。

这里我们引入指示向量

$$h_{ji} =\left\{\begin{matrix} 0, \ v_{i}\notin A_j \\ \frac{1}{\sqrt{vol(A_j)}},\ v_i \in A_j \end{matrix}\right.$$

同理有：

$$h_i^TLh_i = ... = \frac{cut(A_i,\overline A_i)}{vol(A_i)} = Ncut(A_i, \overline A_i)$$

优化的目标依旧是$tr(H^TLH)$，问题转化为：

$$argmin_H \ tr(H^TLH) , \ s.t. H^TDH = I$$

因为：

$$h_i^TDh_i = \sum_{j=1}^{n} h_{ij}^2d_j = \frac{1}{vol(A_i)} \sum_{v_k \ in A_i} w_{v_j} = \frac{1}{vol(A_i)} vol(A_i) = 1$$

令$H= D^{-\frac{1}{2}}F$，因此目标为：

$$argmin_H \ tr(F^TD^{-\frac{1}{2}}LD^{\frac{1}{2}}F) , \ s.t. F^TF = I$$

也就是求$D^{-\frac{1}{2}}LD^{\frac{1}{2}}$的前k个最小特征值及其对应的特征向量并标准化，得到矩阵F，对F做k-means即可。

一般来说：

$$D^{-\frac{1}{2}}LD^{\frac{1}{2}}$$相当于$$\frac{L_{ij}}{\sqrt{d_i*d_j}}$$

谱聚类流程

输入

• 样本集$D=(x_1,x_2,..,x_n)$
• 降维后的维度k
• 聚类后的簇数m

算法

• 利用全连接RBF核生成相似矩阵S
• 根据相似矩阵构建邻接矩阵W和度矩阵D
• $$L = D - W$$
• 标准化$D^{-\frac{1}{2}}LD^{\frac{1}{2}}$
• 计算$D^{-\frac{1}{2}}LD^{\frac{1}{2}}$的最小k个特征值及其特征向量f
• 将f按行标准化，得到n*k的矩阵F
• 将F中的每一行作为K维的样本，利用k-means聚类为m
• 得到m个簇划分

谱聚类优缺点

优点

• 对稀疏数据很有效
• 算法流程进行了降维，因此对高维数据效果较好

缺点

• 若降维幅度不够，则运行速度和效果会较差
• 聚类效果依赖于相似矩阵，相似矩阵不同，效果不同