[mathjax]
1. 子空间聚类
1.1 问题描述
子空间聚类是对高维数据聚类的一种方法。现实生活中的数据，比如文本、图像，都是高维的。
高维数据有以下几个特点：
- 高维数据常包含大量的冗余信息。比如，对于一个图像的像素构成的矩阵来说，相邻的行列之间是有一定的相关性的；对文本而言，上下文之间的相关性更是显然。
- 高维数据经常是稀疏的。举这样一个例子：假设样本在空间中分布均匀，在二维空间，$l^2$ 个单位大小的“正方形”样本就可以填满 $l \times l$ 的空间，而在三维则需要 $l^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