通过直接求解成对约束问题的快速半监督图聚类

《Pattern Recognition》:Fast semi-supervised graph clustering by directly solving pairwise constrained problem

【字体: 大 中 小 】 时间:2026年09月26日 来源:Pattern Recognition 9.1

编辑推荐:

   - 通过块坐标下降法直接优化原始的离散约束图聚类问题。 - 每个"不可连接"对都在一个二行离散子问题中被穷举优化。 - 一种新颖的二行增量策略大大加速了联合优化。 - "必须连接"分量在锚图中被合并,以减少问题规模。 - FSCDPC实现了近乎完全满足约束条件的优越聚类效果。

  

- 通过块坐标下降法直接优化原始的离散约束图聚类问题。
- 每个"不可连接"对都在一个二行离散子问题中被穷举优化。
- 一种新颖的二行增量策略大大加速了联合优化。
- "必须连接"分量在锚图中被合并,以减少问题规模。
- FSCDPC实现了近乎完全满足约束条件的优越聚类效果。

**引言**

聚类旨在根据数据的内在结构特性将其划分为不同的组,将相似性高的数据归为同一簇,将相似性低的数据归为不同簇。过去几十年中,各种经典聚类算法被不断开发[1]、[2]、[3]、[4]。然而,监督标签或先验知识的缺乏可能损害这些方法的可靠性和可解释性,限制了其实际适用性。因此,半监督聚类吸引了越来越多的研究关注[5]。

半监督聚类通过引入有限的先验信息实现了显著的性能提升,这些信息通常以标签信息或成对约束的形式提供。前者为给定样本提供明确的真实标签,后者仅指示一对样本是否属于同一类别(必须连接,ML)或不同类别(不可连接,CL)。在实际应用中,成对约束往往比完整的标签信息更容易获取,特别是在获取真实标签具有挑战性的领域中。这主要是由于它们避免了硬性类别分配,从而降低了获取成本[6]。最近的研究在各种学习任务中探索了有限监督的使用。成对监督已被整合到自适应对称非负矩阵分解中,用于多视图相似性学习和信息融合[7]。在社区检测和特征选择方面也做出了相关努力,利用有限标签或成对关系来增强结构判别能力和识别更具信息量的表示[8]、[9]。

成对约束也被广泛整合到k-means变体[10]、[11]、基于密度的方法[12]、[13]和约束图聚类[14]、[15]中。其中,约束图聚类作为一种特别有效的方法脱颖而出,因为它在考虑边的结构的情况下将图顶点划分为簇,特别适合于具有非凸分布的数据[16]。然而,找到一个满足一组CL约束的聚类分配是NP完全问题,并且可以理论上转化为经典的图K-着色问题[17]、[18]。为了应对这一挑战,一个直观的想法是将成对约束引入相似性图中,然后进行谱嵌入过程。尽管如此,这种方法仍然面临有效满足成对约束并确保计算效率的困难。

成对约束在相似性图上的应用主要涉及根据给定的约束关系调整相似性值。例如,Kamvar等人[19]最初提出了一种修改相似性图的方法,将ML约束下的相似性值设为1,CL约束下设为0。Kulis[20]引入了一种基于核的半监督图聚类算法,其中成对约束被编码到约束矩阵中并整合到相似性矩阵中,从而生成受限的相似性表示。此外,Lu等人[21]将成对约束与半监督k近邻(k-NN)图框架中的标签传播技术相结合,实现了从受约束样本到未约束样本的成对关联传播,以优化相似性矩阵。类似地,Chen等人[22]提出了"近亲或远亲"的概念,建议ML对的邻居应表现出更大的相似性,而CL对的邻居应表现出更大的差异性,随后根据某些函数规则修改相似性值。所有这些方法最终都在修改后的图上应用谱聚类。然而,仅靠此类图修改方法无法确保约束信息得到令人满意的执行,特别是由于CL约束的非传递性,这往往导致谱分析过程中低维嵌入时的高约束违反率。为了缓解这一局限性,Wang等人[23]放弃了直接的图修改,而是将约束重新表述为一个带有自适应阈值的新约束优化问题,从而实现了更灵活的约束满足。最近,Jia等人[24]设计了一种联合优化的成对约束传播(PCP)模型,同时学习传播矩阵和亲和矩阵。Nie等人[25]通过引入基于Laplacian秩约束的不可连接图正则化项来改善CL约束的满足。Chen等人[26]在特征空间和标签空间中整合了双相似性矩阵,以全面探索全局和局部图结构。Zhang等人[27]开发了一个统一框架,将簇比例信息与成对约束相结合,通过缩放指示矩阵获得近似解。

尽管上述方法在成对约束引导的聚类方面取得了进展并实现了更好的聚类性能,但许多现有方法通过图修改、正则化、约束惩罚项或松弛的谱表示间接地整合成对监督。这存在耗时的缺点,并且产生了难以满足的模糊约束关系。此外,这些方法通常采用松弛和后处理策略来求解指示矩阵,这在一定程度上偏离了真正的离散解。Chen等人[28]提出了一种高效的离散优化方案来精确分配CL约束。然而,转换目标函数中两个变量的交替优化策略可能导致收敛到次优性能。此外,当涉及大量约束时,方法的计算效率可能会受到影响。

最近,提出了一些快速的半监督聚类方法,包括种子引导的图聚类[29]、基于锚点的多视图半监督学习[30]、快速证据聚类[31]和基于二部图的线性时间聚类[32]。然而,许多现有的快速方法依赖于显式标签,而专注于成对约束的研究仍然相对稀缺。Zeng等人[33]通过利用保持邻域的图采样降低了时间和空间复杂度,但仍存在额外的采样和优化成本。因此,提高成对约束图聚类的效率仍然是一个重要的研究主题。

为了克服约束聚类中的这些挑战,我们提出了一种名为快速半监督图聚类通过直接求解成对约束问题的方法(FSCDPC)。不同于修改相似性图或松弛离散指示矩阵,FSCDPC直接优化原始的离散成对约束图聚类问题。本工作的主要贡献如下:

(1) 通过块坐标下降法直接优化原始的离散约束图聚类。
(2) 每个不可连接对都在一个二行离散子问题中被穷举优化。
(3) 一种新颖的二行增量策略大大加速了联合优化。
(4) 必须连接分量在锚图中被合并,以减少问题规模。
(5) FSCDPC实现了近乎完全满足约束条件的优越聚类效果。

本文其余部分组织如下。第2节介绍符号和预备知识。第3节提出了合并ML约束的方法,详细介绍了在指示矩阵中优化CL约束的块坐标下降法。随后,我们推导出加速过程。第4节展示了实验结果。最后,第5节总结了本文。

**符号说明**

本节提供了论文中使用的符号的统一概述。粗体大写字母表示矩阵,小写字母表示向量或标量值。给定一个矩阵 ??∈?^??×??,???? 和 ???? 分别是 ?? 的第 ?? 行和第 ?? 列。?????? 是 ?? 的 (??,??)-元素。?????? 和 ???? 分别是 ???? 和 ?? 的转置。???1 表示 ?? 的逆矩阵。‖?‖2? 表示 ??-范数的平方。对于指示矩阵 ??∈?^??×??,每行恰好包含一个

**图的简化**

作为一种图聚类方法,一旦ML子集内的样本被视为超链接点,将它们的边与原始数据图中相对于其他样本的边合并是自然的,而不是修改原始数据特征。为进一步降低计算复杂度,我们首先在锚图 ?? 中实现此合并。在这里,我们采用一种简单的方法。????? 与 ???? 之间的边权定义为对应ML中所有样本与 ???? 之间边权的平均值

**实验**

为了实证评估FSCDPC的性能,在合成数据集和真实数据集上进行了广泛的实验。所有实验均在MATLAB 2018b中实现,并在一台配备Intel i7-10700 CPU@2.9 GHz和16 GB RAM的PC上执行。

**结论**

在本研究中,我们提出了一种新颖的方法来直接求解原始约束图聚类问题。首先,在锚图中,该方法通过利用ML约束的传递闭包,有效地合并了连接样本与锚点的边,从而构建了一个由超链接点组成的基于锚点的相似性图。此外,原始CL集合也得到了简化。然后,提出了一种块坐标下降法来直接分配CL对。该方法

**CRediT作者贡献声明**

朱建勇:写作 – 审阅与编辑、方法论、资金获取、概念化。陈昆:写作 – 原始草稿、软件、方法论、数据整理、概念化。丁琼:验证、方法论、调查。蔡英杰:验证、软件、形式分析。杨辉:资源、资金获取。聂飞平:监督、方法论、资金获取。

**利益冲突声明**

作者声明他们没有已知的可能影响本文所报告工作的竞争性经济利益或个人关系。

**致谢**

本工作得到了中国国家自然科学基金(项目编号62363010)、江西省自然科学基金重点项目(20252BAC250019)和江西省双千计划(编号SSQ2023018)的支持。

朱建勇,2014年获中南大学博士学位。现为华东交通大学电气与自动化工程学院教授,中国南昌。主要研究方向包括数据分析、随机分布控制和预测控制。

朱建勇 | 陈昆 | 丁琼 | 蔡英杰 | 杨辉 | 聂飞平
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

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

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号