多块投影聚类

《Engineering Applications of Artificial Intelligence》：Multi-block projection clustering

　　摘要
投影聚类通过学习从原始空间到低维表示的显式映射，为高维数据分析提供了一个有效的框架。然而，许多现有方法在整个数据集上构建邻域关系，导致高昂的计算和内存成本，从而限制了它们的可扩展性。为了解决这个问题，我们提出了多块投影聚类（MBPC），该方法首先将样本随机划分为大小大致相等的多个块，然后共同学习块级自适应邻域、块特定投影和共享投影。通过这种方式，MBPC避免了全尺度相似性计算，同时保留了局部几何结构，并将不同块的互补信息整合到一个统一的投影中。我们开发了一种高效的交替优化算法来解决所提出的模型。在基准数据集上的广泛实验表明，MBPC在聚类性能方面具有竞争力，同时在运行时间、内存消耗和样本外适用性方面也表现出良好的可扩展性。

引言
随着信息技术的快速发展，高维、大规模数据集在许多实际应用中变得越来越普遍。因此，针对这类数据的有效聚类方法吸引了学术界和工业界的广泛关注（Dol和Jawandhiya，2023；Daneshfar等人，2024；Ran等人，2024；Liu，2024）。
对于大规模数据集，k均值（McQueen，1967）和模糊c均值（FCM）（Guo等人，2023）因其简单性和计算效率而被广泛使用。为了提高它们的优化效率和聚类性能，已经开发了许多变体（Nie等人，2022b；Xue等人，2022；Nie等人，2022c）。然而，这些基于原型的方法通常更适合近似球形和分离良好的簇，并且不显式地对数据的局部邻域结构进行建模。
谱聚类（Ng等人，2001）通过构建相似性图来捕捉这种局部邻域结构。基于该图，它学习一个嵌入，以最小化相邻样本之间的相似性加权平方距离，从而有助于识别具有复杂和非凸形状的簇。然而，传统的谱聚类需要构建和存储完整的相似性矩阵，通常会导致较高的内存需求和计算成本，这大大限制了其在大规模数据上的适用性。
基于锚图的自聚类方法通过使用更小的锚集来表示原始样本，从而提高了可扩展性。基于地标的谱聚类（LSC）（Cai和Chen，2015）是一种代表性方法，它用更小的锚图矩阵代替了完整图拉普拉斯矩阵的分解。后续研究进一步改进了基于锚图的自聚类，包括改进锚点选择和锚图构建（Zhou等人，2026；Wang等人，2017），直接优化离散簇分配矩阵（Wang等人，2024；Wang等人，2023），以及解决簇大小不平衡问题（Yu等人，2024；Liu等人，2023；Nie等人，2022a）。尽管这些方法显著提高了计算效率，但它们的性能可能取决于所选锚点的质量和结果锚图的质量。此外，大多数纯基于图的方法不学习显式映射，因此需要额外的图构建来嵌入未见过的样本。
对于高维数据集，投影学习通过将原始数据通过显式投影矩阵映射到低维表示，提供了一个有效的框架，之后可以在投影空间中进行聚类（Parsons等人，2004）。学习到的映射也可以直接应用于样本外数据。代表性的投影学习方法包括保持局部性的投影（LPP）（He和Niyogi，2003）和保持邻域关系的嵌入（NPE）（He等人，2005）。LPP保留了成对邻域关系，而NPE保留了相邻样本之间的局部重构关系。
近年来，开发了各种投影聚类方法来提高表示质量和聚类性能。典型性感知学习已被引入到投影聚类中（Zhou等人，2024；Gao等人，2023），而低秩回归也被用来捕捉局部和全局结构信息（Zhu等人，2018）。特征加权（Li等人，2023）、非负矩阵分解（Chen等人，2018；Li等人，2020）、无监督判别学习（Nie等人，2023）、局部正则化（Y. Wang等人，2021）、样本加权（Hu等人，2020）、谱旋转（Wen等人，2020；Wen等人，2021）和自适应邻域学习（Nie等人，2014；Lu等人，2021）也被结合到投影聚类中。
一些研究进一步尝试通过将投影学习与可扩展的聚类机制相结合来同时处理高维性和大样本量。一个代表性的方向是将投影学习与k均值结合起来。例如，基于比率迹的无监督线性判别分析（F. Wang等人，2021）可以解释为在投影空间中共同学习低维嵌入并执行k均值聚类。由于k均值的简单性和效率，这些方法适用于高维和大规模数据。然而，与k均值类似，它们在利用局部邻域结构方面仍然受到限制。
另一个代表性的方向是将投影学习与锚图结合。无监督大图嵌入（ULGE）（Nie等人，2017）基于锚图学习显式线性投影，从而避免了构建完整的相似性图，同时产生低维表示。因此，ULGE适用于高维和大规模数据。然而，与其他基于锚图的方法一样，ULGE对锚点选择和构建的锚图质量敏感。
总体而言，尽管现有的投影聚类方法在表示学习和可扩展性方面取得了显著进展，但它们仍然存在各自的局限性。基于k均值的方法没有显式利用局部邻域结构，而基于锚图的投影方法依赖于所选锚点的质量和结果锚图的质量。此外，许多传统的保持邻域关系的投影聚类方法在整个数据集上构建邻域关系，随着样本数量的增加，成对相似性计算变得非常昂贵。
将样本划分为多个块提供了一种替代方法，通过将邻域学习限制在各个块内来降低这种计算成本。然而，从不同块独立学习的投影可能会产生不一致的表示空间，使得难以获得整个数据集的统一表示。
为了解决这些挑战，我们提出了多块投影聚类（MBPC）。对于每个块，MBPC共同学习一个块特定投影和一个二元邻域矩阵来捕捉其局部几何结构。同时，所有块共享一个投影。引入了一种局部-全局一致性机制，将块特定表示与共享表示连接起来，使每个块能够适应自己的局部结构，而不同块在共同的投影空间中对齐。
本项目的主要贡献总结如下：
（1）我们提出了一种可扩展的多块投影聚类方法，该方法将邻域构建限制在各个块内，从而避免了在整个数据集上进行成对相似性计算。
（2）我们开发了一种局部-全局一致性机制，共同学习块特定投影和共享投影，使模型能够捕捉块级局部结构，同时保持不同块之间的表示一致性。
（3）我们推导了一种高效的交替优化算法，并分析了其收敛性和计算复杂性。在基准数据集上的广泛实验表明，与代表性聚类方法相比，MBPC的有效性和可扩展性得到了证明。
本文的其余部分组织如下：第2节介绍符号和相关方法。第3节介绍所提出的MBPC模型、其优化算法以及收敛性和计算复杂性分析。第4节报告实验结果，第5节总结本文。

符号说明
在本文中，小写斜体字母表示标量，粗体小写字母表示向量，粗体大写字母表示矩阵。对于矩阵??，????和??:,??分别表示其第??行和第??列。符号tr?(??)和????分别表示??的迹和转置。Diag?(??)表示对角矩阵，其对角线上的元素为????。此外，??表示适当大小的单位矩阵，??表示全一向量。

动机
虽然投影聚类通过从原始空间到低维表示的学习对于高维数据非常有效，但许多现有方法仍然需要在整个数据集上构建邻域图。在穷举邻域搜索下，构建这样的图需要???(??2)次成对相似性评估，并且在存储密集相似性矩阵时还可能消耗???(??2)的内存。这种计算瓶颈限制了...

实验
实验在七个基准数据集上进行，包括四个面部图像数据集（YaleB（Georghiades等人，2001）、AR（Martinez和Kak，2001）、PIE（Sim等人，2001）和PIE11k），一个3D对象识别数据集（NORB（LeCun等人，2004）以及两个大规模图像数据集（cifar100和TinyImageNet）。对于这两个大规模图像数据集，即cifar100（Krizhevsky，2009）和TinyImageNet，提取了2048维的深度特征。

结论
在本文中，我们提出了一种多块投影聚类方法MBPC，用于高维数据的可扩展聚类。通过在各个块内进行自适应邻域学习并将块特定表示与共享投影空间对齐，MBPC在保持局部几何结构的同时避免了全尺度邻域图的构建。广泛的实验表明，MBPC在聚类性能方面具有竞争力，并且在运行时间...