基于核心集选择的共识感知稀疏子空间聚类方法

《Pattern Recognition》:Consensus-Aware Sparse Subspace Clustering via Coreset Selection

【字体: 大 中 小 】 时间:2026年01月16日 来源:Pattern Recognition 7.6

编辑推荐:

  本文针对大规模数据集中自表达模型存在的连通性差和过分割问题,提出了一种基于共识学习和选择性采样的可扩展自表达模型。通过核心集选择技术生成代表性数据子集,并利用共识优化框架融合局部解以获得全局解,从而显著提升了亲和力矩阵的连通性和聚类精度。在合成与真实数据集上的实验表明,该方法在聚类准确率和连通性方面均达到了最先进水平,为大规模子空间聚类提供了有效解决方案。

  
在高维数据分析中,子空间聚类(Subspace Clustering)作为一种重要的无监督学习方法,其核心目标是从高维数据中恢复出低维子空间结构,并将每个数据点划分到其对应的子空间簇中。这一技术在图像聚类、运动分割、异常检测和混合系统识别等领域具有广泛应用。然而,随着数据规模的不断扩大,传统的子空间聚类方法面临着严峻的 scalability(可扩展性)挑战。
当前最先进的子空间聚类方法主要依赖于自表达模型(Self-Expressive Model),该模型基于一个直观的假设:每个数据点都可以由同一子空间内的其他数据点的线性组合来表示。通过求解系数矩阵并构建亲和力矩阵(Affinity Matrix),再结合谱聚类(Spectral Clustering)技术,最终实现数据点的聚类划分。理想情况下,亲和力矩阵应呈现出清晰的块对角结构(Block-Diagonal Structure),即子空间内部具有强相似性,而子空间之间则保持弱相似性。为了诱导这种结构,研究者们通常会在系数矩阵的优化过程中引入各种正则化项,例如鼓励稀疏性的?1范数(如稀疏子空间聚类SSC)、鼓励稠密性的?2范数(如最小二乘回归LSR),或者兼顾全局结构的核范数(如低秩表示LRR)等。
尽管这些方法在中小规模数据集上表现良好,但在处理大规模数据集时却遇到了瓶颈。一个尤为突出的问题是,旨在保持子空间结构的稀疏正则化(如SSC)虽然能有效捕获局部结构,但其产生的解往往包含大量假阴性(即同一子空间内的点被错误地赋予零相似性),导致亲和力矩阵的连通性(Connectivity)较差,进而引发最终的聚类结果出现严重的过分割(Over-Segmentation)现象。反之,那些旨在改善连通性的稠密正则化方法(如LSR)又常常对异常值敏感,且可能破坏子空间保持(Subspace-Preserving)特性。此外,直接在全数据集上优化自表达模型的计算复杂度高达O(N2),这对于大规模数据而言是难以承受的。
为了应对这些挑战,近期的一些研究开始探索基于子采样的策略。例如,概率稀疏子空间聚类(S3COMP)等方法受到Dropout机制的启发,通过从数据集中均匀随机抽取多个小子集,并在这些子集上分别构建自表达模型,以期在降低计算复杂度的同时改善连通性。然而,随机采样的不确定性可能导致所选子集无法充分代表原始数据的分布,特别是在数据分布不平衡或存在异常值的情况下,子空间恢复的性能会显著下降。虽然增加采样率可以缓解这一问题,但这又会引发计算复杂度的急剧上升。
为了解决上述问题,来自岩手大学的研究团队在《Pattern Recognition》上发表了一项创新性研究,提出了一种名为“基于核心集选择的共识感知稀疏子空间聚类”的新方法。该方法的核心思想在于,通过追求跨多个小子集的全局解与局部解之间的一致性,来联合实现大规模数据集的子空间恢复和亲和力矩阵的连通性提升。研究人员的核心洞察是,这种一致性对于促进亲和力矩阵中密集连接的形成至关重要。
为了开展这项研究,作者们主要运用了几个关键技术方法。首先,他们设计了一个共识感知的自表达学习框架,将问题表述为一个共识优化问题,旨在促进源自原始大规模数据集子集的各个子问题解之间的对齐。该框架包含一个自表达项(Lse)和一个子空间保持共识项(Lsc),后者通过衡量全局系数向量与局部系数向量之间的内积来惩罚因未能满足子空间保持特性而产生的大偏差。其次,针对子集选择的可靠性问题,研究者引入了一种选择性子采样技术,该技术受核心集(Coreset)选择方案的启发,采用结合了最小最大化设施分配策略的贪心选择算法,以识别出能够有效近似原始数据集特征空间覆盖的代表性数据点。这种采样策略比均匀随机采样产生的点分布更均匀,从而提高了子集对原始数据空间支撑的近似能力。最后,为了高效求解所提出的非凸优化模型,他们开发了一种基于正交匹配追踪(Orthogonal Matching Pursuit, OMP)的交替最小化算法,该算法交替更新局部系数向量和全局系数向量,并通过对角近似来降低计算复杂度,使得整体复杂度与S3COMP等OMP-based方法渐近一致。
3.1 初步:自表达模型
该部分回顾了传统的自表达模型。给定数据矩阵X,其目标是找到一组系数,使得每个数据点都能由同一子空间内的其他点线性表示,并通过引入正则项来获得子空间保持的解。最终通过谱聚类亲和力矩阵 |C| + |C?| 得到聚类结果。
3.2 通过共识学习的可扩展自表达模型
本研究的主要创新点在于提出了可扩展的共识感知框架。不同于直接在全集X上预测系数,该方法利用多个小子集来捕获更丰富的子空间内成对关系。其优化目标函数包含了自表达损失和共识损失,后者强制要求从各个子集得到的局部解与全局解保持一致。这种设计在保持子空间结构的同时,有效改善了系数矩阵的连通性。
3.3 用于关键子集选择的核心集选择性子采样
针对随机采样的不足,本部分提出了核心集选择性子采样技术。该技术通过迭代地选择与当前子集中所有点最远的数据点(最大化最小距离),确保选出的代表点能够均匀分布并有效覆盖原始数据的特征空间。可视化对比表明,该方法在不同采样率和子集数下均能产生比随机采样更均匀的采样点,从而提升了子集对原始数据分布的代表性。
3.4 优化算法
研究者设计了交替优化算法来求解模型。当固定全局系数cj时,各个局部系数cj(t)可以并行求解,这转化为一个带有稀疏约束的优化问题,并使用改进的OMP算法求解。当固定所有局部系数时,全局系数cj的更新有闭式解,为了效率,对其中的矩阵进行了对角近似。算法在相对系数变化小于阈值或达到最大迭代次数时终止。
4.1 合成数据实验
在合成数据上的定量评估显示,随着每个子空间内数据点数量Ni从100增加到6000,该方法在聚类精度(ACC)、归一化互信息(NMI)和连通性(CONN)上均显著优于SSC-OMP、S3COMP等基线模型,尤其在数据点密度较低时优势明显。同时,其运行时间与基线方法相当。对亲和力矩阵的可视化分析进一步证实,该方法在不同采样率下均能产生更高连通性和更低子空间表示误差(SRE)的系数矩阵。
4.2 真实世界基准数据集实验
在ORL、GTSRB、MNIST10000、MNIST、EMNIST和CIFAR-10等五个真实数据集上的实验表明,该方法在绝大多数情况下取得了最优或次优的聚类性能。特别是在不平衡数据集GTSRB上,其性能提升显著,证明了选择性采样在处理不平衡数据时的优势。在MNIST、EMNIST等大规模数据集上,该方法成功运行而部分基线方法因内存不足失败,凸显了其可扩展性。运行时分析表明,尽管核心集选择引入了额外开销,但由于亲和力矩阵构建是主要计算瓶颈,总运行时间与S3COMP等方法仍具有可比性。
4.3 分析
深入的消融实验验证了共识项Lsc的关键作用,移除该项会导致所有指标显著下降。对全局系数更新中对角近似的效果评估表明,该近似在几乎不损失性能的前提下大幅降低了计算成本。将选择性采样替换为随机采样的对比实验证实,前者能带来全面的性能提升。参数敏感性分析为δ(采样率)、T(子集数)、s(稀疏度)、λ(平衡参数)的设置提供了指导。收敛性分析显示,算法在不同数据规模下均能快速稳定收敛。
综上所述,这项研究成功提出并验证了一种基于共识学习和核心集选择的可扩展子空间聚类框架。该框架通过巧妙地融合来自多个代表性子集的局部解,有效解决了传统自表达模型在大规模数据集上面临的连通性差和过分割问题。选择性采样策略增强了对原始数据分布的近似能力,尤其适用于不平衡数据集。广泛的实验证明,该方法在合成数据和真实世界基准数据集上均实现了领先的聚类精度和连通性,为大规模高维数据分析提供了强有力的工具。研究者也指出,未来的工作将着眼于探索在线学习框架,以解决当前方法仍需全局数据访问进行子集初始化所带来的内存瓶颈问题。这项工作标志着在构建高效、鲁棒的大规模子空间聚类算法方向上迈出了重要一步。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号