稀疏子空间聚类 SSC（Sparse Subspace Clustering）

在高维数据中，数据点往往并不是随机分布的，而是分布在多个低维子空间中。例如，人脸图片的集合可能分布在不同的子空间中，每个子空间对应不同的人；高光谱数据中的像素分布可以划分为不同的子空间，每个子空间对应不同的材料或地物。稀疏子空间聚类的目标是要将高维数据划分到多个低维子空间中，同时保持子空间的稀疏性。

1. 稀疏子空间

在线性代数中，子空间是由一组 线性无关基向量 张成的空间，所有向量都可以表示为这些基向量的线性组合。子空间的维度由基向量的数量决定，且每个子空间是一个闭合的线性子集。

由此推断，高维数据分布在多个低维子空间中，每个子空间由一组基向量定义。假设数据 $X$ 来自于 $K$ 个不同的子空间 { S 1 , S 2 , … , S K } \{S_1, S_2, \dots, S_K\} {S1​,S2​,…,SK​}，每个子空间是低维的。如果数据点 $x_i$ 属于子空间 $S_k$​，那么 $x_i$ 可以用子空间 $S_k$ 内的其他点的线性组合表示，而与其他子空间无关： $$x_i=\sum _j{c}_{ij}{x}_j,\text{其中 }{x}_j\in S_k。$$ 数据点 $x_i$ 只需要与自己子空间内的点关联，而不需要依赖其他子空间的点。

对于任意一个数据点 $x_i$，其表示 $c_i=[c_{i1},c_{i2},\dots ,c_{iN}]$ 应该是稀疏的，只有少数非零项对应于 $x_i$​ 所属的子空间内的点。利用数据的自表达和稀疏性，自动捕获子空间结构。

2. SSC 的数学建模

SSC 通过优化以下目标函数，计算稀疏表示矩阵 $C$：$$\underset{C}{\min }\Vert C{\Vert }_1+\frac{\lambda }{2}\Vert X-XC{\Vert }_F^2,\text{subject to }\text{diag}(C)=0.$$ 符号解释：

• $X\in {\mathbb{R}}^{d\times N}$：数据矩阵，$N$ 个 $d$-维数据点。
• $C\in {\mathbb{R}}^{N\times N}$：稀疏表示矩阵，表示每个数据点 $x_i$ 是如何由其他点 $x_j$​ 表示的。
• $\Vert C{\Vert }_1$：对稀疏性的约束，鼓励 $C$ 的大部分元素为零。
• $\Vert X-XC{\Vert }_F^2$​：重建误差，要求数据点 $X$ 用 $XC$ 精确重建。
• $\lambda$：控制稀疏性与重建误差的权衡。
• $\text{diag}(C)=0$：对角元素为零，防止点 $x_i$ 自我表示。

该优化问题是凸的，常用交替方向乘子法（ADMM）求解，得到稀疏表示矩阵 $C$。

3. 相似性矩阵的构建

稀疏表示矩阵 $C$ 计算完成后，用它构造一个对称的相似性矩阵 $S$： $$S=|C|+|C{|}^T.$$ $S_{ij}$ 表示数据点 $x_i$ 和 $x_j$ 的相似程度，值越大说明它们可能属于同一子空间。

4. 子空间划分（谱聚类）

在相似性矩阵 $S$ 的基础上，通过谱聚类将数据点划分到不同的子空间中。最终结果是数据点被划分到 $K$ 个子空间，每个子空间对应一个簇。

谱聚类基于图划分的思想，将聚类问题转化为图分割问题。它将数据点视为图中的节点，用边权重表示节点之间的相似性（用相似性矩阵 $S$ 表示）。依据相似性矩阵 $S$ 划分图中的节点，使得簇内紧密（簇内节点之间的边权重尽可能大）和簇间松散（簇间节点之间的边权重尽可能小）。划分过程通过最小化某种切割代价（如标准化切割），找到最优划分。

具体实现步骤：

1. 构造拉普拉斯矩阵：
   图的拉普拉斯矩阵 $L$ 用来表示图的结构：$$L=D-S,$$ 其中，$S$ 是相似性矩阵（图的邻接矩阵），$D$ 是度矩阵（对角矩阵），其对角元素为每个节点的度数：$D_{ii}={\sum }_j{S}_{ij}$。
   然后，归一化拉普拉斯矩阵（常用）：$$L_{\text{norm}}=D^{-1/2}L{D}^{-1/2}.$$

2. 特征值分解：
   计算拉普拉斯矩阵 $L$ 的前 $K$ 个最小特征值对应的特征向量，构成特征矩阵 $U$： $$U=[u_1,u_2,\dots ,u_K].$$

3. 特征向量聚类：
   将特征矩阵 $U$ 的行视为数据点，在欧几里得空间中应用 K-Means 对这些行进行聚类。

特征向量可以看作是一种数据点的 嵌入表示 ，它们捕获了图中全局的结构信息。