摘要

在许多实际问题中，我们处理的是高维数据集，如图像、视频、文本和网页文档、DNA微阵列数据等。通常情况下，这些高维数据点接近于几个低维结构，这些结构对应于数据所属的多个类别或分类。本文提出并研究了一种称为稀疏子空间聚类（Sparse Subspace Clustering, SSC）的算法，用于对位于低维子空间联合中的数据点进行聚类。其核心思想是，在无限多种可能的数据点表示方法中，稀疏表示意味着从同一子空间中选择少数几个点。这激发了解决一个稀疏优化问题，该问题的解可以在谱聚类框架中用于推断数据点到子空间的聚类情况。由于一般情况下求解稀疏优化问题是NP难问题，我们考虑了一个凸松弛方案，并证明了在子空间排列和数据分布满足适当条件的情况下，所提出的最小化程序能够成功恢复所需的稀疏表示。所提出的算法可以高效求解，并且能够处理靠近子空间交界的 数据点。相对于现有技术，该算法的另一个重要优势在于它可以直接通过将数据模型纳入稀疏优化程序来处理数据中的干扰因素，如噪声、稀疏异常值和缺失值。我们通过合成数据实验以及两个实际问题——运动分割和人脸聚类——验证了所提算法的有效性。