动态且一致的双随机相似性学习方法，用于多视图和多阶聚类

《Pattern Recognition》：Dynamic and Consistent Doubly Stochastic similarity learning for multi-view and multi-order clustering

多视图多阶聚类方法存在输入信息不可靠和图融合效果不佳的问题。本文提出动态一致双随机相似性学习（DCDS）方法，通过动态图过滤机制筛选有效视图并构建三维张量，结合低秩约束学习一致相似性；采用双随机图学习策略，将相似性融合与对称性约束统一优化，直接生成块对角图结构，避免人工对称化导致的相似性偏移。实验表明该方法在YaleA、MSRC、HW2数据集上聚类效果优于现有基线方法，且无需后处理步骤。

　　

Nian Wang|Zhigao Cui|Yanzhao Su|Aihua Li|Yuanliang Xue|Wenqi Ren

火箭动力工程学院，中国陕西省西安市，710025

摘要

当前基于多视图图的方法由于输入信息不可靠和多视图融合效果不佳，往往会产生次优的结果。为了克服这些限制，我们提出了动态一致的双随机（DCDS）相似性学习方法，用于多视图和多阶聚类。为了提高输入的可靠性，DCDS动态选择有信息的图并将其聚合成一个三维张量，从而在选定的维度上学习出一致的相似性。在图融合方面，我们引入了一种高效的双随机图学习策略，将相似性整合和对称性强制执行合并为一步，明确揭示聚类结构而无需后处理。DCDS在一个统一的优化框架内制定这些组件，以协同实现最佳的聚类性能。我们提出了一种基于增广拉格朗日乘数（ALM）的方法，并通过一个关键的等价变换来解决具有双随机约束的子问题。广泛的实验表明，DCDS学习的图具有更好的结构清晰度，性能优于现有方法，并在YaleA、MSRC和HW2数据集上获得了真实的聚类结果。代码将在https://github.com/NianWang-HJJGCDX/DCDS.git发布。

引言

由于信息技术的发展，多视图数据在我们的生活中变得越来越普遍。例如，新闻可以由不同的机构报道，如BBC、路透社或卫报。面部图像可以通过许多手工制作的特征提取器来表示，包括SIFT、GIST、LBP和HOG等。数据来源的多样性提高了后续任务的可靠性，从而催生了一个名为多视图聚类的新研究领域。多视图聚类的关键是从多视图数据中挖掘出一致性和可靠的信息[1]。在各种方法中，基于多视图图的聚类（MGC）是一个突出的研究前沿，因为图学习在捕捉复杂数据结构方面表现出优越的性能。

对于MGC来说，一个关键挑战是从融合图中得出聚类指标。虽然一些方法（例如[2]、[3]）依赖于谱分解后进行k-means离散化，但由于初始质心的敏感性，它们的性能会受到固有的不稳定影响。为了解决这个问题，一些最近的工作，如AWP [4]和CSRF [5]，采用了谱旋转作为离散化方法，虽然得到了更稳定的结果，但由于多阶段优化，可能会引入不匹配的问题。为了解决这些后处理限制，结构化图学习最近成为MGC的一个前沿领域。结构化图方法通过在图融合过程中施加秩约束来学习块对角亲和矩阵，从而直接从图的连通性中得出聚类指标。代表性的工作包括CDMGC [6]、CGDD [7]、MCGC [8]、MVGL [9]和GMC [10]。然而，这些模型对图的局部邻域非常敏感，因为它们倾向于学习一个结构化的图，然后聚类指标完全由连通性驱动。

对于结构化图方法，理想图的亲和矩阵应该是一个对角矩阵，块的数量严格等于聚类的数量（见图1(f)），其中主对角线内的连接称为“必须链接”，它们提供了精确的数据结构；而主对角线外的连接称为“不能链接”，它们是不同聚类之间的错误亲和。通常，通过图表示学习数据的相关性需要边的稀疏性，这可以抑制异常样本的影响并提高计算效率。然而，由于数据分布的差异，构建具有特定邻居范围的图可能会缺少一些必须链接，以保持必要的连通性（如图1(a)所示）[11]。为了解决这个问题，多阶图学习成为一个重要的研究分支，通过引入高阶图构建来增强连通性，通过不断连接任意两个节点的常见第二跳邻居[12]、[13]。如图1(a)–(e)所示，随着图阶数的增加，增强的连通性有效地促进了图的对角结构。然而，这带来了一个重大挑战，即如何处理不可靠的图输入和连接关系，因为随着图阶数的增加，不能链接的同时放大。

最近，基于锚点的聚类方法通过选择少量代表性点来构建样本-锚点图，从而实现了快速聚类[14]、[15]。然而，这些方法通常会导致聚类精度不佳，因为信息丢失，而且它们的性能对锚点数量非常敏感，导致参数调整过程繁琐[16]。无锚点方法面临的共同挑战是相似性融合和图对称性的解耦，导致类似的波动。具体来说，假设图的相似性矩阵为，由于优化对称性约束的挑战，现有方法通常首先施加非负性约束（$W0$）和总和为一的约束（$1^{}TW$），以在图融合过程中获得概率亲和性。随后，通过对称性操作$W\frac{W}{T}$人为地强制对称性。这种亲和性估计和对称性施加之间的分离无法确保严格的概率亲和性——样本的度数不是1——这反过来引入了相似性的偏移，并模糊了图的对角结构[17]。因此，尽管融合图可以直接通过其连通性生成聚类指标，但在图融合过程中的多阶段设计会损害图的质量，通常导致聚类性能不佳[18]。

为了同时解决上述问题，我们提出了一种新颖的多视图和多阶聚类模型，称为DCDS，它考虑了输入信息的可靠性和图融合的有效性。如图1所示，为了提高可靠性，我们的DCDS巧妙地设计了一个动态图过滤机制，从多个视图和阶数中丢弃低质量的图，然后在3D张量（仅由选定的图连接）上施加低秩张量约束，以学习一致且有用的相似性关系。对于图融合，使用经过一致性精炼的图来生成具有严格概率亲和性的双随机图，直接通过其连通性生成聚类结果。双随机图的特点是亲和矩阵$W$满足三个关键属性：$W$、$W$和$\mathrm{W1}$，其中$1$是一个所有条目都为1的向量，这直接获得了一个对称的亲和矩阵，以避免由人工对称化引起的相似性波动。

本文的主要贡献如下：

• •
  本文介绍了DCDS，这是一种先进的基于图的聚类模型，它统一了动态图过滤、一致相似性表示和双随机图学习的过程。所提出的DCDS直接通过融合图的连通性生成聚类结果，从而无需后处理。
• •
  我们巧妙地设计了优化过程。特别是，使用基于ALM的新范式来优化具有双随机约束的子问题。与基于VSNP的方法不同，我们的方法同时优化所有约束以获得最优解，这可以很容易地扩展到其他模型。
• •
  一系列实验充分证明了所提出的DCDS获得了数据结构更清晰的图，实现了最先进的聚类性能。

组织结构：第2节介绍了相关工作。第3节介绍了所提出的DCDS。第4节设计了替代优化方法。第5节通过实验验证了其有效性。第6节总结了局限性。第7节总结了本文。

我们使用花体字母表示张量，大写粗斜体表示矩阵，小写粗斜体表示向量。所有向量都以列向量形式呈现。一些通用符号在表1中说明。

部分摘录

高阶图构建

设$X$[x,x2,…,xn]T∈Rn表示数据矩阵，其中$n$是样本数量，$d$是特征维度。图$G$编码了成对关系，其中$V$和$E$是节点和边集，$S$是亲和矩阵，每个条目$s_{}$衡量节点相似性。图拉普拉斯矩阵定义为$L_{}{S}_{}=D_{S_{}}$，其中$D_{s_{}}$是度矩阵，。

高阶图通过二阶接近性捕获更深层次的关系结构[19]，其中节点相似性取决于

所提出的DCDS

从多视图和多阶图中有效提取一致且可靠的信息仍然是一个挑战性问题。为了解决这个问题，我们提出了DCDS，它将动态图过滤、一致表示和双随机图融合整合到一个统一的框架中。如图4所示，我们的DCDS框架首先通过自适应邻居（CAN）[44]进行一阶图学习。之后，多视图和多阶图矩阵Sdv∣v∈{1,2,m

优化

为了解决DCDS框架，我们开发了一种迭代优化算法，交替更新每个变量，同时保持其他变量不变。

比较方法

所使用的比较方法包括MCGC [8]、MVGL [9]、CDMGC [6]、CSRF [5]、SGF [2]、MSGL [20]、CGDD [7]、MoMvGC [21]和NTSGL [34]。其中，MSGL和MoMvGC是两种多视图和多阶聚类方法。NTSGL和ONTF是两种基于张量的聚类方法。（一阶）图是通过自适应邻居方法[46]构建的，邻居数量设置为10。所有方法的最优超参数都是根据作者建议的范围搜索的。

局限性

我们的方法依赖于参数调整，这意味着在参数设置不当的情况下，它的性能可能会较差。参数实验表明，我们的方法对超参数$\alpha$和$\beta$相对敏感，在低秩张量约束中，最优值通常在[1, 10, 100]范围内。此外，我们模型的性能改进部分归因于使用了低秩张量，这得益于数据集中的预对齐类别。

结论

在本文中，我们提出了DCDS，一个统一的多视图和多阶聚类框架，它整合了动态图过滤、一致相似性表示和双随机图学习。对于优化，我们提出了一种基于ALM的全新策略，它同时优化所有双随机约束。实验充分证明了我们的DCDS能够更好地利用多视图和多阶图中的复杂连接。

CRediT作者贡献声明

Nian Wang：撰写——原始草稿，可视化，验证，软件，资源，方法论，调查，形式分析，数据整理，概念化。Zhigao Cui：撰写——原始草稿，监督，方法论，形式分析，数据整理，概念化。Yanzhao Su：验证，资源，调查，资金获取，形式分析，概念化。Aihua Li：撰写——审阅与编辑，软件，资源，项目管理，形式分析，数据

利益冲突声明

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