稀疏自表示子空间聚类 + 后续改进

[mathjax]

1. 子空间聚类

1.1 问题描述

子空间聚类是对高维数据聚类的一种方法。现实生活中的数据,比如文本、图像,都是高维的。

高维数据有以下几个特点:

  1. 高维数据常包含大量的冗余信息。比如,对于一个图像的像素构成的矩阵来说,相邻的行列之间是有一定的相关性的;对文本而言,上下文之间的相关性更是显然。
  2. 高维数据经常是稀疏的。举这样一个例子:假设样本在空间中分布均匀,在二维空间,$l^2$ 个单位大小的“正方形”样本就可以填满 $l \times l$ 的空间,而在三维则需要 $l^3$ 个。也就是说,随着维度的升高,同样的样本数量会使样本空间空出来的位置更多,也就是数据会更加稀疏。
  3. 高维数据带来维度灾难:数据维度高了,某些时间复杂度的算法可能就不适用了。

子空间聚类的想法是假设每个分类对应一个子空间,一个分类的所有样本都属于本类对应的子空间。转换成数学语言如下:

假设 $N$ 个 $M$ 维数据构成的数据矩阵为 $Y=(y_1,y_2,···,y_N) \in R^{M \times N}$,是来自 $n$ 个不同线性子空间的并 $S = \bigcup_{l=1}^nS_l(n\ge 1)$,子空间 $S_i$ 的维度为 $d_i, \; 0 \le d_i \le M$,对应的基矩阵为 $B_i = (b_1,b_2,···,b_{d_i})\in R^{M\times d_i}$,则子空间 $S_i$ 可表示为:

$$S_l = \lbrace y \in R^M : y = B_i\cdot c = \sum_{j=1}^{d_i}b_jc_j \rbrace \quad l = 1,2,···,n$$

其中 $c\in R^{d_i}$ 为 $y$ 在子空间中的表示系数。

因此,找“子空间”的过程就是找到数据矩阵 $Y$ 在特定基下的表示系数。

1.2 子空间聚类的方法

谱聚类方法分为四类:基于统计、基于矩阵分解、基于代数、基于谱聚类,分别的介绍可见此文,本文不多赘述。

基于谱聚类的子空间聚类,是将数据看做图中的点,通过求解数据在特定基下的表示系数,得到图的相似度矩阵,再利用谱聚类的方法得到最终聚类的过程。

而基于谱聚类的方法又分为两种,即稀疏表示子空间聚类算法和低秩表示子空间聚类算法。

这俩都有“表示”,那就先说说什么是表示。

数据的自表示,即在子空间并集中的每个点,都可以由其他的点线性表示(废话)。也就是说,对于每个数据点 $y_i \in \bigcup_{i=1}^nS_i$,都可以表示成:

$$y_i = Y \cdot c_i \ ,\quad c_{ii} = 0$$

这里的 $c_i$ 是表示系数矩阵 $C$ 的某几列做列变换得到的矩阵。$c_{ii} = 0$ 避免了数据点自己表示自己的平凡解。由于在子空间里,数据的个数往往大于他的维度,即 $N_i > d_i$,这就导致每个数据点都有无穷多的表示方式,$C$ 有无穷多解。

稀疏表示,就是让这个解稀疏,即里面 0 越多越好;低秩表示,就是让这个解低秩,即 rank 越小越好。

2. Sparse Subspace Clustering

再写一遍自表示的方程:

$$y_i = Y \cdot c_i \ ,\quad c_{ii} = 0$$

稀疏子空间聚类(Sparse Subspace Clustering,SSC [1])的关键思想就在于,在这所有的解中,必然存在一个最稀疏的解 $\mathcal{C}$,“whose nonzero entries correspond to data points from the same subspace as $y_i$.”

换句话说,表示矩阵 $C$ 的每一个分量代表一个数据被所有数据表示的过程,稀疏解使得每个数据只由和他在同一个子空间的点表示。因此只有在其同一子空间点对应的位置上,才可能是非零分量。我就管这个叫“子空间内自表示”

这时可能会有人要问了,稀疏解 $\Leftrightarrow$ 子空间内自表示,这是为什么呢?

我是这样理解的:最稀疏的解即最大线性无关的一组向量,且其生成空间 $\supset$ 子空间并集。因此这个解对应了子空间并的一组基。设这组基为 $\lbrace b_i \rbrace_{i=1}^{m}$。那么对于每一个子空间,必然能在 $\lbrace b_i \rbrace_{i=1}^{m}$ 中找到几个 $\lbrace b_j \rbrace$,作为自己的基。于是,表示向量 $c_i$ 在 $\lbrace b_j \rbrace$ 对应位置上非零、其余位置为零的,就表示他们是用 $\lbrace b_j \rbrace$ 这组基表示的,于是他们就属于同一个子空间。

那么,现在只需要求稀疏解。稀疏,自然想到 0 范数:

$$\mathcal{C} = min\|C\|_0\quad s.t. \; Y = YC, \; diag(C) = 0$$

0 范数是向量里非零元素的个数,但是 NP 难,所以松弛成 1 范数:

$$\mathcal{C} = min\|C\|_1\quad s.t. \; Y = YC, \; diag(C) = 0$$

解了这个优化问题,得到了表示矩阵 $C$,分出了子空间结构,接下来就是构建相似度矩阵,再进行谱聚类。于是现在就缺相似度矩阵 $W$ 了。我们观察一下表示矩阵 $C$,其实已经非常完美:同一类对应位置非零,不同类对应位置为零,可以很好地表示相似度。但是,SSC 中是这样定义的:

$$W = |C| + |C|^T,\qquad which \ means \ w_{ij} = w_{ji} = c_{ij} + c_{ji} $$

这是因为,尽管子空间的所有点都用同一组基 $\lbrace b_j \rbrace$ 表示,但是并非所有点都要用到所有的基,因此对于统一子空间内两个数据点 $y_i,y_j \in S_l$,可能 $y_i$ 的表示用到了 $y_j$,$y_j$ 的表示并没有用到 $y_i$,这就使得有可能 $c_{ij} \ne c_{ji}$。作者就这样巧妙地解决了。

这里还有一个可选的步骤:在计算 $W$ 前,可以先 normalize $C$:$c_i \gets \dfrac{c_i}{\|c_i\|_\infty}$

有了 $W$,后面就是谱聚类,得到最终结果。

当然,上面讲的是理想情况,在实际问题中,输入数据通常会包含异常值 $e$ 和噪声 $z$, 即:

$$y_i = y_i^0 + e_i^0 + z_i^0$$

我们假设异常值是很少的,所以 $|e_i^0| \le k$;我们还假设噪声是零均值高斯噪声,所以 $\|z_i^0\|_2 \le \zeta$

因此我们的优化问题就变为:

$$min \|C\|_1 + \lambda_e\|E\|_1 + \frac{\lambda_z}{2}\|Z\|_F^2$$ $$s.t. \quad Y = YC + E + Z,\quad diag(C) = 0$$

其中 1 范数使得 $C$ 和 $E$ 每一列稀疏,$F$ 范数使得 $Z$ 每一列元素都比较小。从正则化理论的角度理解, $C$ 和 $E$ 的先验分布是拉普拉斯分布,$Z$ 的先验分布是高斯分布。

关于这个优化问题的解,作者用的是 ADMM。详见我的这篇文章

以上是稀疏自表示子空间聚类的最原始想法,下面是我导师的一个改进版:

3. Structured Sparse Subspace Clustering: A Unified Optimization Framework

SSC 有什么缺点呢?我朴素地感觉,它是将算法分成了没太大关系的两步,没办法用神经网络迭代循环优化。最好能让这两步产生关系。

SSSC(Structured Sparse Subspace Clustering,[2])就找到了两部分的关系,从而可以循环迭代。具体地说,SSSC 找到了 $C$ 和 $Q$ 的关系。$C$ 代表稀疏自表示得到的子空间划分结果;$Q$ 代表最后聚类的结果,其元素 $q_{ij}$ 表示点 $i$ 属于 $j$ 类;$Q$ 的第 $i$ 列 $q_i$ 是由 01 组成的向量,1 的位置表示点 $i$ 处于的类别。

SSC 是先划分子空间,再谱聚类。按理说划分完子空间,就也算是聚完了,但划分的子空间个数不一定就是想要的聚类类数,所以 SSC 中又进行了谱聚类。那能不能让划分好的子空间直接就是聚类结果呢?SSSC 中,量化了两结果的差距,让他们差距最小,由此连接了两步。

在 SSC 中,划定好子空间的分布后,如果两点 $i,j$ 属于同一个子空间,将满足 $c_{ij} \ne 0$ ;谱聚类结束后,如果两点 $i,j$ 属于同一个子空间,将满足 $q_i = q_j$。在 SSSC 中,我们就以子空间划分为基准,数一数谱聚类后变了多少:

$$\|\Theta\odot C\|_0 = \sum_{i,j:q_i\ne q_j}I_{\lbrace|C_{ij}|\ne 0\rbrace}$$ $$where \quad \Theta_{ij} = \frac{1}{2}|q_i – q_j|^2$$

这个式子字母都比较奇怪,我一点点解释:

$\odot$ 是求两个矩阵的 Hadamard product。比如,两个同型矩阵 $A\ B$ 的 Hadamard product $C$,其计算方式是对于每一个元素,$c_{ij} = a_{ij} \times b_{ij}$。

$\Theta_{ij} = 0$ 表示谱聚类结束后 $i,j$ 属于同一个子空间,$\Theta_{ij} = 1$ 则不属于。

$\|\Theta\odot C\|_0$ 表示 $c_{ij}$ 非零、$\Theta_{ij}$ 也非零的所有位置 $(i,j)$ 的数量。其中$c_{ij}$ 非零表示在划分子空间后,点对 $(i,j)$ 属于一个子空间;$\Theta_{ij}$ 非零表示谱聚类后,点对 $(i,j)$ 不属于一类。这就是在统计,有多少个点对,在划分子空间后属于一个子空间,而谱聚类后却不属于一类。这就量化了两结果的差距。这就是 SSSC 的精髓。

可惜 0 范数 NP 难没法算,只得松弛成 1 范数,管这个 “disagreement between W and Q” 叫做 “subspace structured norm of W with respect to (w.r.t.) Q”,写成 $\|C\|_Q$:

$$\|C\|_Q \doteq \sum_{i,j}\|c_{ij}|(\frac{1}{2}|q_i – q_j|^2) = |\Theta\odot C\|_1$$

接下来的优化问题照旧,只是用 $Q$ 范数代替 SSC 中的 1 范数:

$$min \|C\|_Q + \lambda_e\|E\|_l$$ $$s.t. \quad Y = YC + E,\quad diag(C) = 0$$

在这个优化问题中,给定 $Q$,可以用 ADMM 解得 $C,E$;给定 $C,E$,可以用谱聚类得到 $Q$。这样就实现了两个环节,同一个优化问题。

然而这个问题的结果非常依赖开始时 $Q$ 的选择。为了解决,在优化问题中加了一项 $C$ 的 1 范数:

$$\|C\|_{1,Q} = \|C\|_1 + \alpha\|\Theta\odot C\|_1 =\sum_{i,j}|c_{ij}|(1+\frac{\alpha}{2}|q_i – q_j|^2)$$

最终的优化问题:

$$min \|C\|_{1,Q} + \lambda_e\|E\|_l$$ $$s.t. \quad Y = YC + E,\quad diag(C) = 0,\quad Q^TQ = I$$

该优化问题依然是 ADMM 求解。

4. Self-Supervised Convolutional Subspace Clustering Network.

SSConvSCN(Self-Supervised Convolutional Subspace Clustering Network,[3])融合了特征提取网络、稀疏自表示模块和谱聚类三个部分:

其实就是先特征提取,再在特征空间进行子空间聚类。这样一来,子空间聚类的结果可以用来监督特征学习,特征又能让聚类结果更好(有深度聚类内味儿了)。

左上是特征提取模块,通过和左下一起,作为一个自编码器,来进行预训练,loss 就是让编解码后与原数据最接近:

$$L_0 = \frac{1}{2N}\sum_{j=1}^{N}|x_j – \hat x_j|^2 = \frac{1}{2N}|X-\hat{X}|^2_F$$

中下是稀疏自表示模块,这里要优化的问题和 SSC 是一样的:

$$L_1 + L_2 = \lambda\|C\|_L + \frac{1}{2}|Z-ZC|^2_F \quad s.t. \; diag(C) = 0$$

其中的 $Z$ 代表特征空间中的数据表示,对应 SSC 中的 $Y$。$Z-ZC$ 表示 error。

右边是自监督模块,可以 feedback 稀疏表示,这里和 SSSC 是一样的:

$$L_3 = \|C\|_Q \quad s.t. \; Q^TQ = I$$

中上是一个全连接分类器,把特征空间里的数据分类,并用谱聚类结果进行监督学习:

$$L_4 = \frac{1}{N}\sum_{j=1}^N(ln(1+e^{-\widetilde y_i^Tq_j}) + \tau|y_j – \mu_{\pi(y_j)}|^2_2)$$

分成两项:第一项是交叉熵,让两个标签尽量接近,$\widetilde y_j$ 是 $y_j$ 过一个 softmax;后一项是 center loss,让每一类之内的差异最小,让学到的 feature 更接近每一类的中心。由于聚类标签和分类器标签的序号不一定是一个,所以要全排列,找到最匹配的标签序号,其中 $\pi(y_j)$ 是聚类标签全排列后最匹配的结果。

于是,最终整个模型待优化的目标函数为:

$$L = L_0 + \gamma_1L_1 + \gamma_2L_2+ \gamma_3L_3+ \gamma_4L_4$$

整个模型的优化过程是这样:

先用自编码器预训练,此时目标 $min\lbrace L_0\rbrace$;然后加入稀疏自表示模块,此时优化目标是 $min\lbrace L_0+L_1 + L_2\rbrace$;然后开始谱聚类,再用谱聚类的结果监督分类器 & 优化自表示,优化目标是 $min\lbrace L_0+L_1+L_2 + L_3 + L_4\rbrace$,几个循环下来,fintune 就完成了。

5. 总结

基于谱聚类的子空间聚类,自表示过程:

$$y_i = Y \cdot c_i \ ,\quad c_{ii} = 0$$

优化问题:

$$min \|C\|_{\mathcal{{K}}} + \lambda_e\|E\|_1 + \frac{\lambda_z}{2}\|Z\|_F^2$$ $$s.t. \quad Y = YC + E + Z,\quad diag(C) = 0$$

不同的方法其实只是 $\mathcal{k}$ 范数不同:稀疏表示中,SSC 用的 1 范数,SSSC 自己定义了 $Q$ 范数;低秩表示中,用的是核范数。

6. Reference

[1] Elhamifar, Ehsan, and Vidal, Rene. “Sparse Subspace Clustering: Algorithm, Theory, and Applications.” IEEE Transactions on Pattern Analysis & Machine Intelligence 35.11:2765-2781.

[2] Li, Chunguang, Rene Vidal. “Structured Sparse Subspace Clustering: A Unified Optimization Framework.” CVPR 2015

[3] Zhang Junjian, Li Chunguang, et al. “Self-Supervised Convolutional Subspace Clustering Network.” CVPR 2019

Leave a Comment

电子邮件地址不会被公开。