稀疏子空间聚类算法研究

黄佳雯，王丽娟，王利伟

（1.广东工业大学计算机学院，广州510006；2.陆军工程大学电子与光学工程系，石家庄050003）

0 引言

高维数据广泛存在于图像处理、计算机视觉、模式识别、生物计算机学等领域[1]。高维数据识别算法需要具有较好的时间和空间性能。同时由于噪声的影响，处理过程中容易产生“维数灾难”，严重影响算法识别性能。研究发现，高维数据具有低维子空间结构，即数据通常分布在多个低维子空间的并集上。例如，图1 所示的两个变化的两个人脸图像位于两个低维空间上[2]。恢复数据的低维子空间潜在结构不仅有助于数据的存储和管理，而且也能降低维数灾难对于数据识别的影响，提高算法性能。子空间聚类算法可以有效恢复数据的低维子空间结构，并根据这种子空间结构将数据正确地划分到每一个子空间所隶属的数据类别[3]。

子空间聚类算法作为一种有效的高维聚类算法被众多专家学者广泛研究。现有的方法可以分为四类[4]：基于迭代的方法，基于代数的方法，基于统计的方法和基于谱聚类的方法。近年来，由于基于谱聚类的稀疏子空间聚类算法的求解简单且聚类效果好，这类型的方法很为流行。它是一种以谱图理论为基础的数据聚类方法，通过学习数据在低维子空间上的表示系数矩阵来还原数据本质，帮助数据聚类。

图1 两个人脸图像的低维子空间近似表示[2]

1 稀疏子空间聚类算法概述

图像、视频、文本和生物信息等数据广泛存在，它们普遍具有高维、稀疏和噪音的性质，在识别过程中容易产生维数灾难，影响影响识别效果。高维即是其数据维度多，有时甚至远超样本量。稀疏是指这些高维数据（维度h）映射到的低维子空间（维度d）上的表示系数矩阵呈现很强的稀疏性，其中d<

其中Zi表示第i 个子空间中数据的表示系数矩阵[5]。反之，当得到具有块对角结构的Z时，即可得到输入数据的子空间结构。稀疏子空间聚类算法就是利用不同的范数约束Z，使其尽可能具有块对角的理想结构，从而探索到数据的子空间结构。它的流程如图2所示，首先学习到表示系数矩阵Z，然后使用Z构造相似度矩阵W=(Z+ZT)/2，最后对W进行谱聚类即可得到聚类结果。

图2 稀疏子空间聚类流程图

2 稀疏子空间聚类算法研究

由于稀疏子空间聚类算法简单高效，它从提出至今得到了广泛关注。本节对它发展过程中的经典模型和这四年最新的研究方向进行了详细介绍。

2.1 经典稀疏子空间聚类模型

最经典的两种子空间聚类算法分别是基于一维稀疏的稀疏子空间聚类（SSC）[6]方法和利用二维稀疏的基于低秩表示（LRR）[7]的子空间聚类方法。其中SSC 的模型如下：

SSC 使用l1范数约束Z，同时约束Zii=0 来避免每个数据仅用它自己表示的特殊情况。这种方法求得的Z，在数据所属子空间独立的情况下呈现块对角结构，Z中块的个数揭示了输入数据子空间的个数，块的大小揭露了各个子空间的维数。LRR 使用核范数来约束Z，它的模型如下：

它通过对表示系数矩阵Z的秩逼近得到数据的子空间表示。相比于SSC 的单独考虑每个数据的稀疏表示，这种低秩约束有利于捕捉数据的全局结构。

2.2 最新的稀疏子空间聚类模型

本文对近四年的稀疏子空间聚类算法进行了梳理，其中大部分的模型可以用如下的一般形式表示：

正则项R(Z)约束Z 呈块对角结构，数据项F(E)处理噪声。表1 列出了几种典型的稀疏子空间聚类模型，可以看出这些模型的主要区别在于正则项和数据项的不同范数设计，其目的分别是改进系数矩阵块对角约束和改进抗噪性。图2 是稀疏子空间聚类算法的一般流程，近年来有些研究关注于子空间投影阶段，结合了特征选择方法改进了稀疏子空间聚类算法。还有一些方法关注于改进算法流程，将原本流程中分为两步的系数矩阵学习和谱聚类步骤合二为一。最后由于深度学习的流行，有些研究尝试将其与稀疏子空间聚类算法结合。

（1）正则项改进

l0范数可以约束得到数据本质子空间，但对于l0范数的求解是一个NP 难问题。使用正交匹配追踪（OMP）方法可以对其求解，但当数据量大的时候，这种方法效率很低。Li 等人[8]提出一种学习型OMP 方法（LOMP）来加速求解。它通过对OMP 方法得到的l0稀疏表示的学习得到单个隐藏神经网络（SHNN），再将学习到的SHNN 用于新的数据稀疏表示矩阵学习上，从而提高效率。Hashemi 等人[9]在l0范数约束的基础上引入正交最小二乘法的变体来加速求解，同时更有效地找到高维数据的底层子空间。

表1 几种典型的子空间聚类模型

SSC 使用l1范数来松弛l0最小化问题，这种方法的效率低，且在高噪声下可能失效。Dong 等[10]使用一种p（0

LRR 使用核范数来约束Z，这种方法拥有封闭解，解法简单，但需要很强的子空间独立假设且对数据质量有要求。Lu 等人[11]提出了一种k 块对角约束，直接约束表示系数矩阵呈现块对角结构，这种方法相对于LRR 无需那么强的子空间独立假设。

对于Z的约束也可使用多种范数结合的方式。Wang 等人[12]将LRR 和稀疏表示结合起来，提出了一种低秩子空间稀疏表示框架，这种方法结合了两种方法的优点，对于全局信息和局部子空间信息都有考虑。Sui 等人[13]将低秩和稀疏约束分别施加在两个级联自表达式上，它首先利用全局信息使得样本低秩，然后学习该低阶表示的稀疏表示来捕获领域结构，最后对该稀疏表示进行谱聚类得到最终聚类结果。

（2）抗噪性改进

现实中的数据往往存在噪声、异常值和缺失项，因此很多学者分别从理论和实践上对算法的抗噪性进行了研究。Wang 等人[14]对LASSO-SSC 算法处理带有噪声或损坏数据的情况进行了理论分析，分析证明当噪声的大小不超过由半径与子空间不相干之间的几何间隙确定的阈值时，该算法恢复的子空间簇是正确的。Peng 等人[15]提出一种名为子空间内投影优势（IPD）的理论，证明了l1、l2、l∞和基于核范数的投影空间共享的IPD 的性质，即小值系数（平凡系数）总是对应于误差的投影。然后利用该理论设计了一种从线性投影空间中消除误差的影响的方法。Li 等人[16]引入了柯西损失函数惩罚噪声项，从而提升算法抗噪性。Fang 等人[17]引入一种转换核范数和融合策略扩展了原始的潜在低秩表示（LLRR）算法，增强了算法鲁棒性。

（3）子空间投影改进

传统的子空间聚类算法是在输入空间使用自表示方法学习到数据的表示系数矩阵，但这种方法不能有效处理非线性流形聚类。一种有效的方式就是将输入空间投影到低维空间再进行学习。Peng 等人[18]将特征选择与子空间聚类集成到一起，从而可以恢复具有最相关特征的子空间。Zhu 等人[19]在特征选择基础上还将传统子空间聚类数据表示和聚类两个步骤合一了，从而提升了算法效果。Song 等人[20]提出了一种基于结构化稀疏PCA 的字典学习的方法，使用结构信息以及数据稀疏性来学习降维字典和系数矩阵，再从学习到的字典系数向量的内积构造相似度矩阵。Tang 等人[21]提出一种基于鲁棒子空间学习的低秩表示算法（RSLLRR），在子空间投影学习表示系数矩阵时，使用了线性投影和非线性投影将数据映射到低维空间中。

（4）过程改进

一般稀疏子空间聚类算法表示系数矩阵学习与聚类过程是两个步骤，其忽略了表示和聚类过程存在彼此依赖的关系，因此不能保证最佳的效果。Li 等人[22]提出了一个结构化稀疏子空间聚类框架，将系数矩阵的学习和聚类过程结合起来。该框架使用由相似度矩阵求出的拉普拉斯矩阵构造连续实值分割矩阵，并在下一次迭代中用其对表示矩阵进行加权，从而使用聚类相关信息帮助矫正表示系数矩阵中的误差。但这种方法仅考虑表示系数矩阵的结构化稀疏属性，Chen 等人[23]在此基础上定义了组内分组效应的概念，以将同一子空间中的数据分组在一起。Yin 等人[24]提出了一种学习自适应低秩图表示系数矩阵的子空间聚类方法，在统一框架下学习亲和度矩阵和表示系数。Wu 等人[25]也是一种学习自适应图表示稀疏矩阵的子空间聚类方法，但其学习数据的表示系数矩阵时使用的是最小二乘回归法。

（5）结合深度学习

深度学习近年来广受关注，很多研究者尝试将稀疏子空间聚类与其结合。Peng 等人[26]率先提出了基于深度学习架构的具有先验的子空间聚类算法，将输入数据逐步转换为非线性潜在空间，并同时学习了局部和全局子空间结构。Pan 等人[27]在深度自动编码器和解码器之间引入一个自表达层，以模仿传统子空间聚类中的“自表达”属性，该层可通过标准的反向传播过程来学习所有数据点之间的成对亲和力。Zhu 等人[28]使用前馈神经网络将样本映射到非线性空间，并在网络的顶层执行子空间聚类，以迭代地学习映射功能和聚类。Zhou 等人[29]引入了对抗学习来监督学习样本表示和子空间聚类。其中，生成器产生子空间估计和样本聚类。鉴别器通过检查来自估计子空间的重采样数据是否具有一致的子空间属性来评估当前的聚类性能，并监督生成器以逐步改善子空间聚类。Zhang 等人[30]提出神经协作子空间聚类。他们将子空间聚类公式化为分类问题，从而从计算中删除谱聚类步骤。神经模型由分类和亲和力学习两个模块组成，在训练和迭代过程中，后者学到的亲和力矩阵来监督前者计算出的亲和力矩阵，同时前者可以用来提升后者的自表示能力，从而协作优化来构建更好的亲和力矩阵。

3 算法应用

由于稀疏子空间聚类算法简单高效，近年来在机器学习领域很受关注，并在人脸识别、运动分割、生物信息学等方面取得了成功的应用。

不同表情或光线变换条件下的同一个人脸图像可以看作来自一个子空间的数据，不同条件下的不同人脸图像数据可以看作多个子空间的并。子空间聚类算法可以对人脸图像特征进行聚类，同一个人的图像被聚到一个子空间，从而达到人脸识别的目的。常用的人脸识别数据集有Yale B 人脸数据集[31]、PIE 人脸数据库[32]和ORL 数据库[33]等。

运动分割也是稀疏子空间聚类算法的常见应用。运动分割是根据视频中不同的运动轨迹识别出不同的物体，主要目的是从固定背景中识别出作为前景的运动物体。利用子空间聚类算法来进行运动分割，可以将做刚性运动的物体的特征点进行聚类，聚类的结果即为前景中的各个运动物体。如图3 所示的Hopkins155 运动分割数据集[34]是常用的运动分割数据集，该数据集包含了视频序列以及在帧中提取和跟踪的特征，共计有155 个序列。

对生物学和医学信息进行信息挖掘也是稀疏子空间聚类算法的一个新兴应用。例如，单细胞RNA 测序可用来分析细胞异质性并从一堆细胞中鉴定出细胞的亚型。利用子空间聚类算法，可以将同一类型的细胞聚到一个子空间中，从而达到鉴定细胞类型的目的[35]。

图3 一些具有Hopkins155数据集特征的样本

4 结语

稀疏子空间聚类算法是有效处理高维数据的聚类算法之一，它凭借着简单高效的优势被广泛运用在机器学习的各个领域，引起了学术界的广泛关注。对稀疏子空间聚类算法的研究将极大丰富高维数据处理方法，给高维数据的处理方法提供新的思路。本文详细介绍了稀疏子空间聚类算法的原理，经典模型及近年的研究方向，并对算法的应用和常用的公共数据集进行了介绍，可望使读者对稀疏子空间聚类形成基本认识，由此将该方法应用到各种实际问题上。