用于多视图聚类的张量化纯非线性锚图学习方法

《Pattern Recognition》：Tensorized pure nonlinear anchor graph learning for multi-view clustering

　　王飞|卢贵富
安徽工业大学计算机科学与信息学院，芜湖，241000，安徽，中国

**摘要**
基于锚点的构建方法已成为多视图聚类的核心技术，因为它具有计算效率高且能很好地扩展到大规模数据的特点。然而，现有方法通常依赖于原始特征空间中的线性建模，这限制了它们捕捉潜在非线性关系的能力，尤其是在多视图数据特有的复杂非线性分布情况下。此外，锚图经常受到噪声的干扰，导致难以区分纯结构和冗余部分，从而影响聚类性能。为了解决这些问题，本文提出了一种创新方法，称为张量化纯非线性锚图学习用于多视图聚类（Tensorized Pure Nonlinear Anchor Graph Learning for Multi-View Clustering，简称TPNAGL）。具体而言，TPNAGL在核化特征空间中动态构建非线性锚点，以更好地描述样本与锚点之间的非线性关系。然后，为了提高锚图的鲁棒性，每个图被明确划分为纯结构部分和噪声部分，从而可以直接分离出有信息的结构和冗余或受损的连接。最后，将所有视图的净化锚图堆叠成一个张量，并对其施加张量核范数约束，以揭示高阶的跨视图相关性。值得注意的是，动态构建非线性锚点对直接应用表示定理来形成核格拉姆矩阵提出了挑战。即使用于模型优化，基于表示定理的方法通常也会导致O(n3)的时间复杂度，阻碍了对大规模数据的处理。因此，本文开发了一种高效且计算复杂度低的优化策略。广泛的实验表明，所提出的算法在效率和性能方面都表现出显著的优势。代码可在以下链接获取：https://github.com/wangfii/TPNAGL

**引言**
在现实世界中，数据通常来自多种模态或视角（如图像、文本、音频和视频），形成具有多视图特征的复杂数据结构[1]。多视图聚类（MVC）旨在利用不同视图之间的互补信息来增强对底层数据分布的建模，已成为无监督学习中的一个重要研究课题。由于其在多模态数据分析、跨媒体检索和生物信息学等任务中的广泛应用，MVC[2]、[3]近年来受到了越来越多的关注和研究。

随着数据规模的持续增长，基于所有成对样本关系的传统图构建方法会产生大量的计算和内存开销，通常具有O(n2)的计算复杂度，这严重限制了它们在大规模聚类任务中的适用性。为了提高效率和可扩展性，基于锚点的图构建方法被广泛采用。这些方法选择m个代表性锚点，并仅学习n个样本与锚点之间的连接，将复杂度从O(n2)降低到O(nm)，其中m?n。这种策略显著降低了计算成本，同时产生了稀疏且高效的图结构，非常适合大规模聚类场景。例如，Kang等人[4]对原始数据集进行k-means采样，并使用固定锚点进行聚类。Yu等人[5]提出了一种使用共享锚点和自适应视图加权的方法，以高效地进行大规模多视图聚类。Li等人[6]提出了一种高效且可扩展的锚图聚类方法，无需调整超参数，并在统一框架内进行聚类。Wang等人[7]提出了一种无参数的多视图子空间聚类方法，通过联合优化锚点选择和子空间图构建实现了高效且稳健的聚类性能。

尽管基于锚图的方法[8]、[9]在大规模场景中表现出很强的实用性，但大多数现有方法仍然在原始特征空间中进行建模，并假设样本可以表示为锚点的线性组合。然而，这种建模无法捕捉现实世界数据中常见的非线性流形结构，导致表示能力有限以及生成的锚图中的连接性失真。此外，由于缺乏结构约束，学习到的锚图经常包含冗余边或噪声扰动，导致图结构不纯，从而影响可区分性和聚类稳定性。因此，提高锚图的非线性表达能力和结构纯度仍然是基于锚点的图构建中的双重挑战。

为了提高图建模对非线性结构的适应性，最近的研究中广泛引入了核方法[10]、[11]。通过将数据映射到再生核希尔伯特空间，这些方法能够在高维空间中对非线性关系进行线性建模。最近，Li等人[12]首次尝试将核方法引入锚图构建框架，通过将锚点嵌入核空间来有效建模样本与锚点之间的非线性关系。然而，这种方法依赖于固定的预定义锚点集，使得聚类性能对初始锚图的质量非常敏感，从而限制了模型捕捉复杂数据结构和泛化到不同场景的能力。此外，学习到的锚图通常包含噪声连接，缺乏对底层纯净结构的明确分离，进一步削弱了图表示的区分能力。

有一系列研究试图通过将锚图结构分解为多个组成部分来净化它[13]。代表性的工作包括Li等人[14]和Liu等人[15]，他们将锚图分解为一致和不一致的部分，以提取多个视图之间的共享潜在结构。虽然这些方法可以被视为图净化的形式，但它们主要是出于多视图对齐的动机，而不是显式的噪声建模。此外，它们没有在核空间中同时学习锚点表示和图分解，这限制了它们有效处理复杂非线性结构和结构噪声的能力。

值得注意的是，像ASR-ETR[16]这样的方法本质上是从子空间重构的角度制定的，其中学习锚点系数用于数据表示。相比之下，我们的方法是从图学习的角度出发的：我们直接在核化特征空间中学习样本-锚图，明确分离图结构和图噪声，并使用张量建模来捕捉跨视图图相关性，而不是系数一致性。因此，所提出的方法更自然地归类为基于图的多视图聚类框架，而不是子空间重构模型。

为了解决上述问题，我们提出了张量化纯非线性锚图学习用于多视图聚类（TPNAGL），这是一种基于图学习的多视图聚类框架。具体来说，TPNAGL不是通过锚点系数重建样本，而是在核化特征空间中直接学习样本-锚图，使模型能够更有效地捕捉复杂的非线性关系。为了提高鲁棒性，每个学习到的锚图都被明确划分为纯净的结构部分和残余噪声部分，从而在图级别直接实现图净化。此外，将所有视图的净化锚图堆叠成一个张量，以建模跨视图图相关性并强制图一致性。因此，所提出的方法与张量化子空间重构方法有根本不同，因为它关注非线性图学习、图净化和多视图图一致性，而不是系数重构。此外，基于表示定理的优化[17]通常具有O(n3)的时间复杂度，这限制了其对大规模数据的处理能力。为此，我们开发了一种高效且计算复杂度低的优化策略。

**本文的主要贡献如下：**
- TPNAGL首次探索了在核化特征空间中动态选择代表性非线性锚点来建模非线性样本-锚点关系，增强了锚图对复杂结构的表达能力。
- 引入了一种结构分解策略，将每个锚图明确划分为纯净的结构部分和噪声部分，提高了学习到的图的鲁棒性和区分能力。
- 将所有视图的净化锚图堆叠成一个张量，并应用张量核范数正则化来捕捉高阶的跨视图相关性。
- 开发了一种计算复杂度低的高效优化策略，避免了基于表示定理的方法的三次方时间成本，使所提出的模型能够扩展到大规模数据集。

**相关工作与预备知识**
在本节中，我们介绍了与本研究最相关的研究工作以及一些基本定义。表1总结了本文中使用的主要符号。

**提出的方法**
考虑到现有方法的局限性，我们在本节逐步介绍了我们提出的算法。

**算法**
在本节中，我们设计了一种高效的优化策略，并分析了其时间复杂度。

**实验**
所有评估TPNAGL模型的实验都是在配备Windows 11操作系统、32 GB RAM和R7-4800H处理器的Lenovo系统上实施的，以确保基准测试的一致性。

**结论**
在本文中，我们提出了一种新的张量化纯非线性锚图学习（TPNAGL）方法用于多视图聚类。通过在核化特征空间中动态构建非线性锚点，TPNAGL有效捕捉了多视图数据中固有的复杂非线性关系。在每个锚图中明确分离纯结构信息和噪声，提高了鲁棒性并减轻了受损连接对聚类性能的影响。

**作者贡献声明**
王飞：撰写——原始草稿、可视化、软件、概念化。
卢贵富：撰写——审阅与编辑、验证、资金获取、形式分析。

**利益冲突声明**
作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

**致谢**
作者衷心感谢匿名审稿人和编辑的宝贵反馈，这些反馈显著改进了本文。本研究得到了中国国家自然科学基金和安徽省高校自然科学研究项目的资助，资助编号分别为61976005和2022AH050970。