高维空间中的稀疏表示聚类方法

"Sparse Subspace Clustering - Ehsan Elhamifar & René Vidal - Center for Imaging Science, Johns Hopkins University" 本文介绍了一种基于稀疏表示（SR）的聚类方法，该方法针对高维空间中嵌入的多个低维线性或仿射子空间的数据进行聚类。在稀疏子空间聚类（SparseSubspaceClustering）中，关键思想是每个数据点在由所有其他数据点构成的字典中都有一个稀疏表示。通常情况下，找到这样的稀疏表示是一个NP难问题。然而，作者们提出，在温和的假设下，可以通过使用L1优化来“精确”地获取这种稀疏表示。 文章指出，通过利用这种稀疏表示构建相似性矩阵，然后应用谱聚类算法，可以对数据进行分割。这种方法能够处理噪声、异常值以及缺失数据。在多运动视频分割问题上应用了他们的子空间聚类算法，实验结果表明，其性能显著优于现有的先进方法。 1. 引言 子空间聚类是一个具有广泛应用的重要问题，特别是在图像处理领域，如图像表示和压缩。在高维数据集（如视频序列）中，数据往往可以分解成多个低维度的子空间，这些子空间可能对应于不同的对象、动作或者场景。稀疏表示方法能够捕获数据的主要特征，从而帮助区分不同的子空间。 2. 稀疏表示理论 稀疏表示的核心在于找到一个最简洁的方式来表达数据，即使用尽可能少的基元素来表示数据点。在子空间聚类的上下文中，这意味着每个数据点都可以通过其他数据点的线性组合（即字典元素）近似表示，且这个组合尽可能稀疏，即大部分系数为零。 3. L1优化与精确稀疏表示 L1范数优化被用来寻找最稀疏的解，因为它倾向于产生稀疏解，即具有大量零元素的向量。作者证明，在一定的条件下，使用L1优化可以精确地得到数据点的稀疏表示。 4. 相似性矩阵与谱聚类 构建相似性矩阵是通过计算每个数据点与其他数据点之间的稀疏表示的内积来完成的。这种矩阵反映了数据点之间的关系强度。谱聚类算法随后应用于这个矩阵，寻找数据的自然分组，它能有效处理非凸和不规则形状的子空间。 5. 应用与实验 在167个视频序列上的实验展示了该方法的优越性，特别是在处理复杂背景、运动变化和遮挡情况时。与传统方法相比，提出的算法在识别和分离不同动作方面表现出更高的准确性和鲁棒性。 总结来说，"Sparse Subspace Clustering"提供了一种创新的聚类策略，它利用稀疏表示和L1优化解决了高维数据中的子空间聚类挑战，适用于处理噪声、异常值和缺失数据，并在实际应用中表现出色。