基于半定规划思想的连续松弛鲁棒多视图聚类方法，用于大规模数据处理

《Knowledge-Based Systems》：Semidefinite Program-inspired Continuous Relaxation Robust Multi-view Clustering for Large-scale Data

　　李明浩|徐慧英|王子颖|林鹤川|张晓雷|朱新忠
中国浙江省金华市321004，浙江师范大学计算机科学与技术学院

摘要
在现代社会，随着信息的多样化和海量化，大量未经标记的大规模多视图数据集应运而生。多视图聚类算法具有处理这类数据集的潜力。然而，现有研究中的多视图聚类方法在鲁棒性和可扩展性方面考虑不足。为解决这些问题，我们提出了一种新的基于半定规划的连续松弛鲁棒大规模数据多视图聚类方法（SPRMC-LS），其复杂度与样本数量呈线性关系。该方法将锚点策略融入核函数中，以获得针对不同视图的相似度矩阵。通过一种无需迭代的基于半定规划的连续松弛方法，使得指示矩阵能够识别异常值。最后，利用简单的二元分类函数整合各视图的结果。在多个数据集上的实验表明，我们的SPRMC-LS方法具有更优异的性能。

引言
随着大数据时代的到来，未处理数据的量达到了前所未有的水平，且这些数据大多具有复杂多样的特征描述。一方面，描述方式和来源的多样性催生了多视图数据的概念[1]。一个传统的中国寓言“盲人摸象”[2]很好地诠释了多视图数据的概念。另一方面，日益庞大和复杂的数据要求算法具备更低的空间时间复杂度以及更高的鲁棒性。

近年来，多视图聚类算法[3][4][5]成为聚类领域的研究热点。该算法旨在充分利用异构且互补的多视图数据，通过整合不同视图的信息来获得一致的聚类结果。与传统单一聚类方法相比，多视图聚类在诸多领域具有更广阔的应用前景。根据不同的信息融合策略，现有的多视图聚类方法大致可分为四类：非负矩阵分解法[6][7][8]、子空间聚类法[9][10][11][12]、协同训练法[13][14]以及基于图的方法[15][16][17]。具体而言，基于非负矩阵分解的方法通过矩阵分解从原始多视图数据中学习低维的共识表示，但由于需直接对原始数据观测值进行分解，因此在处理大规模数据时效率较低。基于子空间的聚类方法假设视图源自潜在子空间，并试图探索子空间表示；而基于协同训练的方法则通过交替训练策略结合多个结果，以最大化各视图之间的协同效应。基于图的方法的目标则是构建统一的图矩阵，以研究不同视图之间的关联。

尽管多视图聚类取得了显著成果，但高计算成本以及异常值问题仍然是其面临的两个不可避免的问题，尤其是在处理大规模数据时。为减轻计算负担，基于锚点图的策略因其高效性和实用性而受到广泛关注[18][19][20]。然而，现有的基于锚点的多视图聚类方法往往忽视了对大规模数据的鲁棒性。此外，大多数当前的多视图聚类方法依赖于多次迭代优化，这可能需要额外的时间才能得到理论上的近似解。在关于异常值聚类的研究中[21]表明，基于半定规划的聚类算法在没有异常值时具有强一致性，而且只要异常值的增长速度慢于节点数的增长速度，就能对任意异常值保持鲁棒性。尽管已经存在许多基于半定规划的聚类算法[21][22][23][24]，但其中很少有专注于大规模多视图聚类问题的。

鉴于此，本文提出了一种新的无需迭代的多视图聚类方法——基于半定规划的连续松弛鲁棒大规模数据多视图聚类方法（SPRMC-LS）。我们将锚点策略、核函数方法以及半定规划整合到一个统一的框架中。具体而言，我们将锚点策略融入用于大规模数据的核函数中；在对数据进行投影后，再应用基于半定规划的松弛方法得到指示矩阵，这种方法在处理高维数据时能获得更好的效果。通过定义由指示矩阵构成的辅助矩阵，可以直接识别异常值。最后，采用简单的二元分类函数整合各视图的数据，进一步提升其对大规模数据的适应性。为便于理解，SPRMC-LS的详细流程如图1所示。我们的贡献可总结如下：
1. 我们提出了一种新的鲁棒多视图聚类方法（SPRMC-LS）。与现有大规模多视图聚类方法中基于启发式的异常值去除方法不同，我们的SPRMC-LS通过将基于半定规划的连续松弛方法融入基于锚点的多视图聚类框架，实现了对任意异常值的鲁棒性处理。异常值可被识别为从半定规划结构中得到的辅助矩阵中的零行。
2. 与大多数依赖迭代优化的现有大规模多视图聚类方法不同，我们通过凸松弛得到了封闭形式的解，从而使SPRMC-LS无需迭代且效率极高。这一封闭形式解源于一种新的优化公式，它将离散的聚类问题转化为凸优化问题，从而避免了迭代近似的需要。
3. 我们的SPRMC-LS在时间和内存复杂度方面都与实例数量呈线性关系，这相较于现有的基于半定规划的聚类方法是一个根本性的改进。而且，在实现这种线性复杂度的同时并未牺牲鲁棒性，而现有的高效多视图聚类方法往往忽视了理论上的鲁棒性。

相关工作
本节简要介绍大规模多视图聚类及基于半定规划的多视图聚类领域的相关研究工作。我们在表1中总结了本文中使用的关键符号。

模型构建
对于第v个视图中的观测值{x1(v),x2(v),?,xn(v)}，我们定义第i个和第j个数据点之间的相关性为以下高斯核矩阵：
Kij(v)=exp(?∥xi(v)?xj(v)∥2/2θ2)，其中θ为缩放参数。接着，我们用m个（m???n）锚点{a1(v),a2(v),?,am(v)}替换所有的数据点，即Dij(v)=exp(?∥xi(v)?aj(v)∥2/2θ2)，这些锚点是通过随机抽样生成的。这样，由于是在D∈Rn×m上运算而非K∈Rn×n，因此可以降低计算复杂度。

实验部分
在本节中，我们通过对不同规模的数据集进行充分实验，证明了SPRMC-LS方法的优越性。所有数据集均可从公共网站获取。

结论
本文提出了一种新的无需迭代的多视图聚类方法SPRMC-LS，该方法兼具高效率与强鲁棒性。SPRMC-LS的主要创新点有三：（1）它是一种新型的大规模多视图聚类方法，通过将经过验证的基于半定规划的连续松弛方法融入基于锚点的多视图聚类框架，有效解决了异常值问题；（2）它通过封闭形式的无需迭代解实现了线性的时间和内存复杂度，这一突破显著优于现有的相关方法。

CRediT作者贡献说明
李明浩：撰写——初稿、可视化、验证、软件、方法论、研究、数据整理。徐慧英：验证、监督、研究。王子颖：资源、方法论、研究、数据整理、概念设计。林鹤川：撰写——审阅与编辑、资源、数据整理、概念设计。张晓雷：撰写——审阅与编辑、验证、概念设计。朱新忠：验证、监督、研究。

利益冲突声明
作者声明没有已知的财务利益或可能影响本文所述工作的个人关系。

致谢
本研究得到了国家自然科学基金（62376252）、浙江省自然科学基金重点项目（LZ22F030003）以及浙江省领雁计划（2024C02G1123882）的支持。