谱聚类与图结构学习的全面综述

摘要—谱聚类是一种强大的高维数据聚类技术，利用基于图的表示来检测复杂的非线性结构和非凸聚类。构建相似度图对于确保准确有效的聚类至关重要，因此图结构学习（GSL）在应对日益增长的可扩展解决方案需求中，成为提升谱聚类性能的核心。尽管在GSL方面取得了一定的进展，但目前缺乏专门针对其在谱聚类中的作用的全面调查。为填补这一空白，本调查提供了关于谱聚类方法的全面综述，重点讨论了GSL的关键作用。我们探讨了多种图构建技术，包括成对、锚点以及基于超图的方法，涵盖固定和自适应设置。此外，我们将谱聚类方法分类为单视角和多视角框架，研究它们在单步和两步聚类过程中的应用。我们还讨论了多视角信息融合技术及其对聚类数据的影响。通过解决当前的挑战并提出未来的研究方向，本综述为推动谱聚类方法的发展提供了有价值的见解，并强调了GSL在处理大规模高维数据聚类任务中的关键作用。关键词—谱聚类，图结构学习，谱嵌入，多视角聚类

I. 引言

聚类（Clustering）是无监督学习中的一种基础技术，旨在将数据点划分为不同的组或簇，使得簇内的点彼此相似，而与其他簇中的点差异较大【1】–【3】。与监督学习不同，聚类在没有预定义标签或类别的情况下运行，而是通过识别数据中的内在模式和结构来实现目标。这使得聚类在探索性数据分析中尤为重要，在此过程中，目标是揭示隐藏的模式，而不依赖于数据结构的先验假设【4】。聚类被广泛应用于各个领域，包括市场营销【5】、社交网络分析【6】、图像分割【7】、生物信息学【8】、异常检测【9】和文档分类【10】。它简化了复杂的数据，增强了理解，且常常作为其他机器学习任务（如分类）的预处理步骤。

聚类方法可以大致分为传统方法和基于降维的聚类方法，如图1所示。传统方法包括基于划分的方法【11】、层次聚类方法【12】、基于密度的方法【13】和概率算法【14】，每种方法都采用不同的策略来对数据进行分组。基于划分的方法（如K-means）将数据划分为固定数量的簇，每个簇由一个质心表示【11】。层次方法，如凝聚型和分裂型聚类，通过合并较小的簇（凝聚型）或拆分较大的簇（分裂型）来构建聚类层次【15】【16】。基于密度的方法，如DBSCAN，通过基于高密度区域对数据点进行分组，能够识别形状各异的簇【17】。概率方法，如高斯混合模型（GMM），使用概率模型来表示数据分布和聚类【14】。

尽管传统方法对于低维且结构良好的数据集有效，但当应用于高维或复杂数据时，往往面临局限性。在高维空间中，点与点之间的距离度量变得困难，通常会导致聚类性能不佳。此外，传统方法常常无法捕捉非凸形状和复杂的数据结构。为了应对这些局限性，基于降维的聚类方法应运而生，通过减少特征或维度的数量，使得在较低维度空间中进行聚类，同时保留必要的结构信息。基于降维的聚类方法包括非负矩阵分解（NMF）【18】、谱聚类【19】【20】、核聚类【21】和深度聚类【22】。NMF是一种有效的降维技术，用于将数据矩阵分解为两个低维的非负矩阵【18】。然而，当处理更加复杂或非线性的数据结构时，可能面临一定的挑战。核聚类（包括核K-means和核主成分分析（PCA）等方法）通过应用核函数来处理数据中的非线性关系【21】。谱聚类利用图论，将数据点表示为图中的节点，节点之间的相似度则通过边来表示，并采用如Ratio-cut【23】和Normalized-cut【24】等方法。深度聚类将深度学习与聚类结合，通过神经网络学习低维表示【22】。尽管深度聚类对于大规模、高维数据非常强大，但它需要大量的计算资源，并且需要细致的超参数调优。在降维技术中，谱聚类因其能够通过图结构方法识别非凸簇并捕捉非线性结构，而在处理复杂数据时表现尤为突出。谱聚类通过将数据点表示为图中的节点，并使用基于图的嵌入方法，根据数据点之间的连通性和关系来划分数据。这种灵活性使得谱聚类能够应用于各种领域中的问题，特别是在结合有效的图构建技术时。谱聚类尤其适用于高维数据，在这种情况下，谱嵌入通过降低维度同时保留必要的结构信息，从而缓解了“维度灾难”问题，并使得非线性模式的聚类变得可靠。对于大规模数据集，基于锚点图的谱聚类通过使用一部分代表性点（或称为锚点）来高效近似数据点之间的关系，从而提供了一种可扩展的解决方案，既节省了计算资源，又保证了聚类质量。因此，谱聚类具有很强的灵活性和可扩展性，能够适应高维和大规模数据的应用，是进行复杂聚类任务的强大工具【21】【25】。谱聚类成功的关键因素之一是相似度图的构建，图结构是整个过程的基础。这个图表示了数据点之间的关系，节点对应数据点，边表示它们之间的成对相似度。图的质量显著影响谱嵌入和聚类结果，因为它直接决定了数据底层结构的捕捉精度【25】。在谱聚类中，常用的图类型包括成对图【26】、锚点图【27】【28】和超图【29】【30】。不同类型的图在数据的性质不同的情况下提供了各自的优势。这些图可以是固定的，即结构在整个聚类过程中保持不变，也可以是自适应的，即在聚类过程中动态学习并更新图的结构。尽管在谱聚类，尤其是在图像分割【31】、文本分类【32】和工业设计【33】等领域取得了进展，但仍缺乏一篇全面的综述，专门探讨图结构学习（GSL）在谱聚类中的作用。为填补这一空白，本调查提供了关于谱聚类的广泛综述，特别强调了图结构在提升聚类准确性方面的关键作用。虽然先前的综述【34】提供了关于谱聚类的概述，重点讨论了图切割、拉普拉斯矩阵和聚类过程，但我们的综述深入探讨了更为具体且至关重要的GSL方面。先前的综述侧重于谱聚类的数学基础和应用，但没有广泛探讨图的构建方式及其对聚类性能的影响。相较之下，我们的综述突出了图构建技术的作用，包括成对、锚点和超图方法，并探讨了固定和自适应形式下的应用。此外，我们将谱聚类方法分类为单视角和多视角方法，分析它们在单步和两步框架中的应用。这些框架的区别在于聚类是否作为独立步骤，在谱嵌入之后进行，还是与谱嵌入一起联合优化。我们还对多视角谱聚类中的信息融合技术进行了更深入的探讨，这一领域在先前的综述中没有涉及，提供了关于如何通过整合来自多个来源的数据来增强聚类性能的新见解。这对于处理复杂、异构和高维数据尤为重要，是推动多视角谱聚类发展的重要贡献。

本综述的贡献如下：

• 我们首次提供了关于谱聚类的最全面且详细的综述，特别强调了GSL，突出了其在提升聚类准确性方面的重要性。
• 我们对各种图构建技术进行了全面回顾，包括成对、锚点和超图，并探讨了它们在固定和自适应形式下的应用。此外，我们将谱聚类方法分为单视角和多视角方法，分析了这些方法中不同图构建技术的应用，以及它们在单步和两步聚类框架中的应用。
• 我们讨论了多视角谱聚类中的信息融合技术，提供了关于如何通过整合来自多个来源的数据来提升聚类性能的新见解。这对于处理复杂、异构和高维数据具有特别重要的意义，是推动多视角谱聚类研究的重要贡献。
• 我们分析了谱聚类和图学习领域的最新研究进展、出现的挑战以及未来可能的研究方向。这包括确定有前景的研究领域，并推动更先进算法的发展，促进该领域的成长与演化。 本文的结构如下：第二节我们提供了谱聚类的详细背景。第三节介绍了谱聚类的主要阶段，包括图结构学习、谱嵌入和分割阶段。第四节提供了基于单视角和多视角方法、图结构类型以及单步和两步框架的谱聚类方法的综合分类，并探讨了每一类别中的不同谱聚类方法。第五节讨论了未来的研究方向，最后，第六节给出了结论。