Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation
TL;DR 精炼摘要
本文提出了一种新颖的半监督子空间聚类方法,通过将初始监督信息表示为成对约束矩阵,构建具有判别力的亲和矩阵。该方法将亲和矩阵和成对约束矩阵堆叠成三维张量,并施加全局低秩约束,从而增强聚类效果。通过结合局部几何结构,提升了亲和矩阵的学习精度,在多个基准数据集上表现优越。
摘要
In this letter, we propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. By representing the limited amount of supervisory information as a pairwise constraint matrix, we observe that the ideal affinity matrix for clustering shares the same low-rank structure as the ideal pairwise constraint matrix. Thus, we stack the two matrices into a 3-D tensor, where a global low-rank constraint is imposed to promote the affinity matrix construction and augment the initial pairwise constraints synchronously. Besides, we use the local geometry structure of input samples to complement the global low-rank prior to achieve better affinity matrix learning. The proposed model is formulated as a Laplacian graph regularized convex low-rank tensor representation problem, which is further solved with an alternative iterative algorithm. In addition, we propose to refine the affinity matrix with the augmented pairwise constraints. Comprehensive experimental results on eight commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods. The code is publicly available at this https URL.
论文精读
中文精读
1. 论文基本信息
1.1. 标题
Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation (基于张量低秩表示的半监督子空间聚类)
1.2. 作者
- Yuheng Jia (东南大学计算机科学与工程学院)
- Guanxing Lu (东南大学吴健雄学院)
- Hui Liu (明爱专上学院计算机信息科学学院,通讯作者)
- Junhui Hou (香港城市大学计算机科学系,IEEE 高级会员)
1.3. 发表期刊/会议
- 期刊: IEEE Signal Processing Letters (SPL)
- 发布时间: 2022-05-21 (Published)
1.4. 摘要
本文提出了一种新颖的半监督子空间聚类方法。该方法能够同时增强初始监督信息并构建具有判别力的亲和矩阵 (Affinity Matrix)。通过将有限的监督信息表示为成对约束矩阵 (Pairwise Constraint Matrix),作者观察到理想的聚类亲和矩阵与理想的成对约束矩阵共享相同的低秩结构。因此,作者将这两个矩阵堆叠成一个三维张量,并施加全局低秩约束,以同步促进亲和矩阵的构建和初始成对约束的增强。此外,利用输入样本的局部几何结构来补充全局低秩先验,以实现更好的亲和矩阵学习。该模型被公式化为拉普拉斯图正则化的凸低秩张量表示问题,并通过交替迭代算法求解。最后,作者提出利用增强后的成对约束来进一步细化亲和矩阵。
1.5. 原文链接
-
发布状态: 已正式发表 (IEEE Signal Processing Letters, Vol 29)
2. 整体概括
2.1. 研究背景与动机
高维数据处理的挑战: 高维数据(如人脸图像、DNA 微阵列数据)通常可以被近似为一组低维线性子空间的并集。子空间聚类 (Subspace Clustering) 的目标是在子空间成员未知的情况下,将这些数据样本划分到各自的子空间中。目前最先进的方法通常基于自表达性 (Self-Expressiveness),即用样本自身的线性组合来表示高维数据,从而学习一个亲和矩阵。
现有半监督方法的局限性: 在实际应用中,通常可以获得少量的监督信息(如部分标签或成对约束)。现有的半监督子空间聚类方法通常以局部或逐元素(element-wise)的方式利用这些信息:
-
硬约束 (Hard Constraints): 强制具有“必须连接 (Must-link)”约束的样本具有相同的表示。
-
亲和度调整: 直接增加或减少具有约束关系的样本间的亲和度值。
核心 Gap: 现有的方法虽然利用了监督信息,但主要从局部视角出发,忽略了成对约束矩阵本身的全局结构。作者认为,这种处理方式在一定程度上未充分利用监督信息。
2.2. 核心贡献
-
全局张量低秩先验: 提出了一种全新的视角,即理想的亲和矩阵和理想的成对约束矩阵共享相同的低秩结构。通过将它们堆叠成 3D 张量并施加张量低秩约束,实现了两者的相互促进和增强。
-
联合优化框架: 提出了一个凸优化模型,集成了全局张量低秩表示、局部几何结构(图正则化)以及稀疏噪声建模,并通过交替方向乘子法 (ADMM) 高效求解。
-
亲和矩阵细化策略: 提出了一种后处理策略,利用在优化过程中增强后的成对约束矩阵来进一步修正亲和矩阵,显著提升聚类性能。
-
卓越的性能: 在 8 个基准数据集上的实验表明,该方法在准确率和归一化互信息 (NMI) 指标上均显著优于现有的最先进半监督方法。
下图(原文 Fig. 1)展示了该方法的整体流程:它并未孤立地处理亲和矩阵和约束矩阵,而是利用它们共同的低秩特性进行联合学习。
该图像是示意图,展示了提出的方法如何通过利用配对约束矩阵和亲和矩阵的全局低秩结构,来同时学习亲和度并增强配对约束。图中包括初始亲和矩阵、初始配对约束矩阵、构建的张量及其增强过程,直至最终的改进亲和矩阵。
3. 预备知识与相关工作
3.1. 基础概念
为了理解本文,初学者需要掌握以下核心概念:
- 子空间聚类 (Subspace Clustering): 假设数据点分布在多个低维子空间的并集上,目标是将数据点分组,使得每组数据属于同一个子空间。
- 自表达性 (Self-Expressiveness): 这是一个核心假设,即一个数据点可以由属于同一子空间的其他数据点的线性组合来表示。数学上表示为 ,其中 是数据矩阵, 是表示系数矩阵(也即亲和矩阵的基础), 是误差。
- 低秩表示 (Low-Rank Representation, LRR): 假设数据是从多个子空间采样的,那么理想的表示矩阵 应当是全局低秩的。LRR 通过最小化 (核范数)来求解 。
- 成对约束 (Pairwise Constraints):
- Must-link (): 两个样本属于同一类。
- Cannot-link (): 两个样本属于不同类。
- 张量 (Tensor): 矩阵的高维推广。本文主要涉及 3 阶张量(即数据立方体)。
3.2. 前人工作与差异化分析
- LRR (Low-Rank Representation) [4]:
- 方法: 寻找最低秩的表示矩阵 使得 。
- 局限: 是一种无监督方法,无法利用先验知识。
- SSLRR (Semi-Supervised LRR) [7] & CLRR (Constrained LRR) [5]:
- 方法: 这些方法将监督信息作为约束条件加入到 LRR 的优化问题中。例如,如果样本 和 必须连接,则强制 较大;如果不连接,则强制 为 0 或较小。
- 差异: 本文作者指出,这些方法是逐元素 (element-wise) 地施加约束,只改变了矩阵中的局部数值,而没有利用“约束矩阵本身应该是低秩的”这一全局结构信息。
本文的创新点: 本文不再将约束视为 的附属补丁,而是将约束矩阵 视为一个与 平等的实体。通过构建张量 和 ,利用张量低秩范数同时约束两者,使得监督信息能在全局范围内传播。
4. 方法论
4.1. 方法原理
本文的核心直觉是:
-
理想亲和矩阵 是低秩的(块对角结构)。
-
理想成对约束矩阵 也是低秩的(如果我们要表示所有样本间的关系,它也是一个块对角矩阵)。
-
结构一致性: 和 应该具有极其相似的低秩结构。
因此,将它们堆叠成一个张量 ,该张量也应当是低秩的。
4.2. 核心方法详解 (逐层深入)
4.2.1. 模型构建:从矩阵到张量
首先,我们需要定义两个核心矩阵:
-
亲和矩阵 : 用于表示样本间的相似度。
-
成对约束矩阵 : 用于编码监督信息。
作者引入一个张量 ,并通过以下方式构建:
-
-
为了利用全局低秩先验,作者首先提出了初步的优化目标(原文 Eq. 3):
符号解释:
- : 张量核范数 (Tensor Nuclear Norm)。这是为了鼓励张量 是低秩的,从而迫使 和 共享结构信息。本文采用基于 t-SVD 的定义 [14]。
- : 范数,用于处理样本特定的稀疏噪声(Sample-specific corruption)。
- : 分别是已知的 Must-link 和 Cannot-link 集合。
- : 一个标量,用于控制 的数值尺度,使其与 相近(通常设为 LRR 学习到的亲和矩阵的最大元素值)。注意这里约束了 在已知位置的值为 或
-s。
4.2.2. 引入局部几何结构:图正则化
除了全局低秩,局部几何结构对聚类也很重要。如果两个样本在特征空间中接近,它们应该具有相似的成对关系(即 的列应该相似)。为此,作者引入了 Laplacian 正则化项。
最终的优化模型如下(原文 Eq. 4):
新增符号解释:
- : 平衡参数,控制局部正则化的权重。
- : 拉普拉斯正则化项。
- : 拉普拉斯矩阵。其中 是基于原始数据构建的 近邻 (NN) 图, 是度矩阵 ()。这一项的作用是平滑 ,使得相似的样本拥有相似的约束模式。
4.2.3. 优化算法 (ADMM)
由于目标函数包含多个变量和约束,作者使用了 ADMM (Alternating Direction Method of Multipliers) 算法进行求解。算法通过引入拉格朗日乘子,将问题分解为多个子问题交替求解:
-
更新 : 这是一个张量奇异值阈值 (t-SVD) 问题。
-
更新 : 涉及矩阵求逆和乘法。
-
更新 : 结合了来自张量的约束和拉普拉斯正则项,通常涉及求解线性系统(Sylvester 方程的形式)。
-
更新 : 这是一个标准的 范数最小化问题,有闭式解。
该算法的整体复杂度在一次迭代中主要由矩阵乘法和求逆主导,为 。
4.2.4. 亲和矩阵细化 (Affinity Matrix Refinement)
在通过 ADMM 求解得到 和 后,作者并没有直接使用 进行聚类,而是利用增强后的 对 进行进一步的“修理”。
细化公式如下(原文 Eq. 5):
公式逻辑深度解析:
这里首先假设 每一列已归一化到 [0, 1],且 也被归一化()。
-
情况 1 (): 此时 倾向于认为 和 是同类(Must-link)。公式 实际上是一个“概率或”逻辑(类似于 )。如果 很大(接近1),即使 原本很小,结果也会接近 1。这增强了亲和度。
-
情况 2 (): 此时 倾向于认为 和 是异类(Cannot-link)。公式 会因为 而使得 变小。这抑制了亲和度。
最后,对修正后的亲和矩阵 应用标准的谱聚类算法得到最终结果。
5. 实验设置
5.1. 数据集
实验使用了 8 个常用的基准数据集,涵盖了人脸、物体、手写数字、语音字母和视频等多种类型。
-
人脸数据: ORL, YaleB
-
物体/图像数据: COIL20, MNIST (手写数字)
-
其他数据: Isolet (语音), Alphabet, BF0502, Notting-Hill (视频人脸聚类)
监督信息的生成方式:从数据集中随机抽取一定比例(如 5% 到 30%)的标签,然后根据这些标签推断出成对约束(Must-link 和 Cannot-link)。
5.2. 评估指标
实验采用两个标准指标。由于原文未给出具体公式,此处根据通用标准补充定义。
5.2.1. 聚类准确率 (Clustering Accuracy, ACC)
- 概念定义: 衡量聚类结果与真实标签的一致性。由于聚类标签是无监督生成的,它与真实标签之间可能存在排列置换,因此需要找到最佳的一一映射。
- 数学公式:
- 符号解释:
- : 样本总数。
- : 第 个样本的真实标签 (Ground Truth)。
- : 第 个样本的聚类预测标签。
- : 将聚类标签映射到真实标签的最佳置换函数(通常使用 Kuhn-Munkres 算法求解)。
- : 指示函数,当 时为 1,否则为 0。
5.2.2. 归一化互信息 (Normalized Mutual Information, NMI)
- 概念定义: 基于信息论的指标,衡量聚类结果与真实标签分布之间的相似度,并对结果进行了归一化,使得范围在
[0, 1]之间。 - 数学公式:
- 符号解释:
- : 真实标签集合。
- : 聚类结果集合。
I(Y; C): 和 之间的互信息 (Mutual Information)。H(Y), H(C): 分别是 和 的熵 (Entropy)。
5.3. 对比基线
实验对比了 LRR(无监督基线)以及 6 种最先进的半监督子空间聚类方法:
-
DPLRR [8], SSLRR [7], SC-LRR [9], CLRR [5]: 基于 LRR 的半监督变体。
-
CP-SSC [20]: 基于 SSC (Sparse Subspace Clustering) 的方法。
-
L-RPCA [19]: 另一种低秩相关方法。
6. 实验结果与分析
6.1. 核心结果分析
实验结果表明,所提出的方法在绝大多数数据集和监督比例下都取得了最优性能。
以下是原文 [Table I] 的结果,展示了在 30% 初始标签下的准确率 (Accuracy) 和 NMI 对比:
| Metric | Method | ORL | YaleB | COIL20 | Isolet | MNIST | Alphabet | BF0502 | Notting-Hill | Average |
|---|---|---|---|---|---|---|---|---|---|---|
| Accuracy | LRR | 0.7405 | 0.6974 | 0.6706 | 0.6699 | 0.5399 | 0.4631 | 0.4717 | 0.5756 | 0.6036 |
| DPLRR | 0.8292 | 0.6894 | 0.8978 | 0.8540 | 0.7442 | 0.7309 | 0.5516 | 0.9928 | 0.7862 | |
| SSLRR | 0.7600 | 0.7089 | 0.7159 | 0.7848 | 0.6538 | 0.5294 | 0.6100 | 0.7383 | 0.6876 | |
| L-RPCA | 0.6568 | 0.3619 | 0.8470 | 0.6225 | 0.5662 | 0.5776 | 0.4674 | 0.3899 | 0.5612 | |
| CP-SSC | 0.7408 | 0.6922 | 0.8494 | 0.7375 | 0.5361 | 0.5679 | 0.4733 | 0.5592 | 0.6445 | |
| SC-LRR | 0.7535 | 0.9416 | 0.8696 | 0.8339 | 0.8377 | 0.6974 | 0.7259 | 0.9982 | 0.8322 | |
| CLRR | 0.8160 | 0.7853 | 0.8217 | 0.8787 | 0.7030 | 0.6837 | 0.7964 | 0.9308 | 0.8020 | |
| Proposed Method | 0.8965 | 0.9742 | 0.9761 | 0.9344 | 0.8747 | 0.8355 | 0.8697 | 0.9934 | 0.9193 | |
| NMI | LRR | 0.8611 | 0.7309 | 0.7742 | 0.7677 | 0.4949 | 0.5748 | 0.3675 | 0.3689 | 0.6175 |
| DPLRR | 0.8861 | 0.7205 | 0.9258 | 0.8853 | 0.7400 | 0.7477 | 0.5388 | 0.9748 | 0.8024 | |
| SSLRR | 0.8746 | 0.7409 | 0.7986 | 0.8337 | 0.6373 | 0.6070 | 0.4810 | 0.5949 | 0.6960 | |
| L-RPCA | 0.8038 | 0.3914 | 0.9271 | 0.7834 | 0.5805 | 0.6590 | 0.4329 | 0.2294 | 0.6009 | |
| CP-SSC | 0.8705 | 0.7224 | 0.9583 | 0.8127 | 0.5516 | 0.6459 | 0.4453 | 0.4733 | 0.6850 | |
| SC-LRR | 0.8924 | 0.9197 | 0.9048 | 0.8362 | 0.7803 | 0.7316 | 0.7068 | 0.9931 | 0.8456 | |
| CLRR | 0.9028 | 0.7895 | 0.8568 | 0.8892 | 0.6727 | 0.7091 | 0.6970 | 0.8293 | 0.7933 | |
| Proposed Method | 0.9337 | 0.9548 | 0.9716 | 0.9218 | 0.7825 | 0.8107 | 0.7693 | 0.9771 | 0.8902 |
分析:
-
显著提升: 提出的方法在平均准确率上达到了 0.9193,远超第二名 SC-LRR 的 0.8322。在 YaleB 数据集上,NMI 从 SC-LRR 的 0.9197 提升到了 0.9548。
-
鲁棒性: 相比其他方法在不同数据集上表现波动较大(例如 L-RPCA 在 YaleB 上仅 0.3619 准确率),本文方法在所有数据集上都表现极其稳定且优秀。
下图(原文 Fig. 2)展示了随着初始监督标签比例的增加,各方法准确率的变化曲线。可以看出红色曲线(本文方法)始终位于最上方。
该图像是多组数据集的分类准确率对比图,其中包含了多种方法在不同标记百分比下的表现。图中展示了提出的方法在 ORL、YaleB、COIL20、Isolet、MNIST、Alphabet、BF0502 和 Notting-Hill 数据集上的准确率变化,红色曲线代表提出的方法,显示了其在各个数据集上优于其他比较方法的效果。
6.2. 亲和矩阵可视化
为了直观验证方法的有效性,作者可视化了在 MNIST 数据集上学习到的亲和矩阵。 下图(原文 Fig. 4)展示了不同方法生成的亲和矩阵对比。
-
LRR: 较为模糊。
-
Proposed Method: 展示了极其清晰的块对角结构(Block Diagonal Structure),这意味着类内连接紧密,类间干扰极小,这直接解释了其优越的聚类性能。
该图像是一个图表,展示了不同方法在 MNIST 数据集上学习的亲和矩阵的可视化比较。图中包含了八种方法的结果,包括所提出的方法、LRR、DPLRR、SSLRA、L-RPCA 等,亲和矩阵已归一化到 [0,1]。
6.3. 消融实验 (Ablation Study)
作者通过逐步添加组件来验证每个模块的贡献。以下是原文 [Table II] 的部分结果(平均准确率):
| Percentage | Method | Average Accuracy |
|---|---|---|
| 10% | SSLRR (Baseline) | 0.5808 |
| CLRR (Baseline) | 0.6301 | |
| Eq. (3) (Only Tensor Low-Rank) | 0.6824 | |
| Eq. (4) (+ Laplacian Reg) | 0.7740 | |
| Eq. (5) (+ Post-Refinement) | 0.8036 |
分析:
- Eq (3) vs Baselines: 仅使用全局张量低秩约束(Eq. 3)就已经超过了 SSLRR 和 CLRR,证明了全局结构建模优于逐元素约束。
- Eq (4) vs Eq (3): 加入图正则化显著提升了性能,说明局部几何结构是很好的补充。
- Eq (5) vs Eq (4): 最后的亲和矩阵细化步骤进一步提升了结果,证明了增强后的成对约束矩阵 的价值。
6.4. 运行时间与收敛性
-
收敛速度: 如图 6(原文 Fig. 6)所示,算法在 130 次迭代内收敛,速度较快。
-
运行时间: 如图 7(原文 Fig. 7)所示,虽然比纯无监督的 LRR 稍慢,但比 SSLRR 快很多,且性能提升巨大,因此计算成本是可以接受的。
该图像是多个迭代过程中收敛标准的对比图,展示了不同方法在八个数据集上的表现,包括 ORL、YaleB、COIL20 和 Isolet 等。每个子图显示了迭代次数与收敛标准之间的关系,清晰比较了各方法的收敛速度和效果。
该图像是一个柱状图,展示了不同方法在八个数据集上的运行时间比较。图中包括了所提方法、DPLRR、L-RPCA、SSL RR等多种方法,运行时间以秒为单位,显示了各方法在各数据集上的性能差异。
7. 总结与思考
7.1. 结论总结
本文提出了一种基于张量低秩表示的半监督子空间聚类框架。其核心思想是打破传统方法将“亲和学习”与“约束利用”割裂的局面,通过张量堆叠的方式,利用两者共享的低秩结构进行联合优化。实验结果强有力地证明了这种全局结构对齐 (Global Structure Alignment) 策略相比于传统的局部约束施加 (Local Constraint Imposition) 策略具有显著优势。
7.2. 局限性与未来工作
- 局限性:
- 目前的方法虽然对噪声有一定的鲁棒性(通过误差项 ),但主要处理的是样本特征的噪声。对于监督信息本身的噪声(即给定的 Must-link/Cannot-link 可能是错的),目前的模型可能还不够鲁棒。
- 未来工作:
- 结合深度学习: 作者计划将此框架融入端到端的神经网络中,例如利用增强后的成对约束作为 Loss 函数来指导网络训练。
- 处理噪声约束: 改进模型以处理带有噪声的成对约束。
7.3. 个人启发与批判
- 启发: 这篇论文提供了一个非常优雅的视角——“结构即信息”。当我们有两个相关的任务(亲和度学习和约束传播)时,与其设计复杂的交互规则,不如寻找它们共有的数学结构(如低秩),并在该结构层面进行统一建模。这种“高维升维(形成张量)再约束”的思路可以迁移到多视图学习 (Multi-view Learning) 或多模态融合中。
- 批判:
- 超参数敏感性: 虽然文中分析了参数 和 ,但在实际应用中,如何自动确定 (约束强度)以及张量核范数的权重可能仍然是一个这就需要调参的痛点。
- 计算复杂度: 的复杂度主要来源于矩阵求逆和 SVD,这限制了该方法在大规模数据集(如百万级数据)上的直接应用。虽然这也是基于谱聚类方法的通病,但如果要扩展应用,必须考虑近似算法或基于 Landmark 的方法。
相似论文推荐
基于向量语义检索推荐的相关论文。