编辑推荐：
胡云佳|张斌|强千遥摘要多视图聚类因能够整合来自不同视角的互补信息而备受研究关注。近年来，基于图的多视图聚类成为了一个重要的研究领域，因为它在处理非凸数据集时表现出更优异的性能。尽管已取得一定进展，基于图的多视图聚类方法仍面临三个关键挑战：（1）由于图构建和谱分析导致的高计算复杂
胡云佳|张斌|强千遥
摘要
多视图聚类因能够整合来自不同视角的互补信息而备受研究关注。近年来，基于图的多视图聚类成为了一个重要的研究领域，因为它在处理非凸数据集时表现出更优异的性能。尽管已取得一定进展，基于图的多视图聚类方法仍面临三个关键挑战：（1）由于图构建和谱分析导致的高计算复杂度；（2）对集群规模平衡的忽视，而这对资源分配和负载均衡等实际应用而言至关重要；（3）依赖单独的后处理步骤（如-均值算法）来将连续的谱嵌入离散化，这会引入偏差。为解决这些问题，我们提出了快速平衡多视图聚类（FBMVC），这是一种快速且平衡的基于图的多视图聚类框架。FBMVC采用锚点和标签传递策略，在保持性能的同时显著降低了计算成本。自适应视图加权机制可自动优化各视图的权重，以实现有效的多视图整合。该机制还能隐式确保集群分布的平衡。尤其重要的是，FBMVC在其优化框架内即可获得离散的集群标签，从而无需额外的后处理步骤。在六个基准数据集上的实验表明，FBMVC在聚类性能和计算效率方面均优于现有最先进方法。
引言
聚类是数据挖掘和机器学习领域中的基本技术（Berkhin，2006）。它通过分析数据之间的关系并将数据划分为不同类别，从而识别出数据中的内在结构。随着信息技术的进步，多视图数据在大数据时代变得极为普遍。同一个对象可以通过从不同角度收集的数据来描述（Kang等人，2020）。例如，一张图像可以通过各种特征（如HOG、SIFT、SURF、LBP等）来表征，而多媒体片段则可以同时通过可见光摄像机的视频信号和录音设备的音频信号来表示。不同的视图通常包含一致且互补的信息。多视图聚类算法通常会结合或整合多个数据视图，以显式或隐式的方式提取共享特征和独特特性，从而揭示出潜在的共识聚类结构。
近年来，基于图的多视图聚类方法受到了广泛关注。这些方法通常涉及在多个视图之间发现一个共识亲和矩阵，然后利用谱聚类或其他技术来确定最终的标签分布。Kumar等人（Kumar和Daumé，2011）利用图拉普拉斯矩阵的特征向量对样本进行聚类，随后修改其余视图的图拉普拉斯矩阵以提高跨视图一致性。Kumar等人（2011）还引入了正则化项，强制要求来自不同视图的特征向量具有高相似性，从而实现共识聚类。Zhan等人（2017）通过学习得到的全局图来获取集群指标，而无需进行图割或-均值聚类。此外，还出现了图神经网络（GNNs）和Transformer等深度学习方法。Lin等人（2024）分离信息并运用对比学习来获得更高级别的表示；Ren等人（2024）学习并动态融合特定于视图的图，以实现面向任务的聚类；Chen等人（2024）调整编码器选择并使用双重对比学习；Jiao和Li（2024）则通过在线相互学习实现了端到端的聚类。Liang等人（2023）在Transformer架构中嵌入了聚类机制，以递归更新集群中心。Zhao等人（2023）利用自注意力机制学习具有非负性和正交性约束的深度谱嵌入，将其作为集群指标矩阵。
尽管基于图的多视图聚类方法已经取得了令人满意的成果，但它们往往存在较高的时间和空间复杂度。为了解决这些问题，人们引入了基于锚点的方法。通过选择少量具有代表性的样本作为锚点来构建二分图，这些方法有效地降低了计算复杂度。Li等人（2015）整合了来自不同类型特征的二分图，为多个视图获得了新的统一表示形式。通过构建二分图来降低图构建和谱分析的计算复杂度，他们加快了整个算法的运行速度。Li等人（2020）提出了一种基于二分图的紧凑且高效的无参数多视图聚类方法。他们还设计了一种简单的锚点选择策略，该策略不依赖于初始化，且其时间复杂度与随机选择相同，从而显著提高了聚类效率。Yang等人（2022）设计了一种新的锚图正则化方法，大幅提升了聚类效率与稳定性。
此外，大多数基于图的多视图聚类方法并未考虑集群的平衡问题。然而，在现实场景中，平衡性已成为聚类分析不可或缺的要求。这一需求在资源分配优化、服务公平性保障以及分布式系统中的负载均衡等关键领域十分普遍（Guarda等人，2020；Zheng等人，2022）。例如，在无线传感器网络的部署中，如果传感器节点的分布严重偏离平衡状态，就会导致局部计算负载急剧增加、能量消耗不均，最终造成网络拓扑结构不稳定以及整体性能大幅下降（Rajpoot和Dwivedi，2020）。在分布式数据管理领域，基于查询相关性的数据聚类策略可以有效减少节点间的通信开销，而节点间的数据负载均衡则对系统稳定性至关重要。研究表明，数据分布不平衡很容易导致局部瓶颈、网络拥堵和能源浪费，进而影响整体服务质量（Su等人，2015）。
为解决这一问题，许多研究引入了硬约束或软正则化策略来增强集群的平衡性。Liu等人（2017）使用排他性套索作为平衡正则化器，并将其与最小二乘回归相结合，从而得到平衡的集群类别。Li等人（2018）隐式地将排他性套索作为正则化器，并提出了一个自平衡最小割模型。这一框架后来通过引入锚点策略被扩展到大规模数据集上（Chen等人，2019）。此外，Nie等人（2021）、Wang等人（2023）和Zhao等人（2024）也通过结合锚点策略和不同的正则化项实现了快速且平衡的聚类。由于基于图的多视图聚类通常依赖传统的谱聚类算法来确定最终的标签分布，而谱聚类所需的单独后处理步骤可能会引入偏差，从而影响最终结果的准确性（Qiang等人，2023）。
在本文中，我们提出了快速平衡多视图聚类（FBMVC），旨在同时解决上述问题，包括高时间和空间复杂度、对集群平衡性的忽视以及两阶段处理带来的偏差。为了降低时间复杂度，我们采用基于锚点的策略来构建二分图，并将集群指标矩阵（n×c）的更新转化为锚点指标矩阵（m×c，其中m?n）的更新。通过优化策略，我们的方法可以直接获得最终的聚类结果，无需任何额外步骤。此外，我们还隐式确保了集群的平衡性，且无需任何额外参数。同时，我们运用自适应视图加权来确定每个视图的权重，以实现有效的多视图数据整合。
总之，我们的主要贡献可总结如下：
- •
我们提出了一种快速的基于图的多视图聚类方法，无需额外的后处理步骤即可获得离散的聚类结果。
- •
我们的方法引入了隐式的平衡约束，无需额外的平衡参数即可得到平衡的聚类结果。
- •
我们的方法能够自主学习每个视图的权重，从而有效整合多视图信息。
- •
在六个基准数据集上的实验展示了我们方法的聚类性能与效率。
本文的其余部分结构如下。第2节介绍了本文中使用的符号和定义，并简要回顾了一些相关研究。第3节具体阐述了FBMVC模型，第4节详细说明了优化过程。第5节报告并分析了在六个真实世界数据集上的实验结果。最后，第6节对本文进行了总结。
章节要点
相关工作
在本节中，我们将介绍本文中使用的符号和定义，并回顾一些密切相关的研究工作。
动机
在处理大规模数据集时，传统的基于图的多视图聚类方法因其高时间和空间复杂度而受到限制。此外，这些传统方法也忽视了聚类结果的平衡性，往往会产生不平衡的集群，从而降低了它们的实际应用价值。为同时解决这些局限性，我们提出了FBMVC模型，该模型协同整合了三项关键创新：1）加速聚类过程
优化
对于公式（14）中的目标函数，存在两个变量U和α。直接求解这两个变量较为困难，因此我们采用交替优化策略，即固定其他变量的同时更新其中一个变量。
实验
在本节中，我们在6个数据集上将我们的方法与12种竞争方法进行了比较，以证明我们方法的优越性。所有实验均在配备2.9 GHz Intel Core i7-10700 CPU、32 GB内存及Matlab R2022b（64位）系统的Windows 10台式电脑上完成。
结论
本文提出了一种快速的基于图的多视图聚类方法FBMVC，解决了基于图的多视图聚类中的三个关键问题：高昂的计算成本、不平衡的集群分布，以及依赖后处理步骤来获得离散聚类结果的问题。该方法通过整合基于锚点的二分图、隐式平衡约束以及自适应视图加权，实现了高效且平衡的聚类结果。FBMVC降低了计算复杂度
CRediT作者贡献说明
胡云佳：写作——审稿与编辑，写作——初稿撰写，软件工具，形式化分析，数据整理。张斌：指导监督，资源提供，项目管理。强千遥：写作——审稿与编辑，方法设计，形式化分析。
利益冲突声明
作者声明，他们不存在任何可能影响本文所汇报工作的已知利益冲突或个人关系。
