【论文阅读】Anchor-based fast spectral ensemble clustering

论文地址：Anchor-based fast spectral ensemble clustering - ScienceDirect

代码地址：

---

摘要

集成聚类通过融合多个基础聚类方法，可以获得更好且更稳健的结果，因此受到广泛关注。尽管近年来已经出现了许多代表性的算法，但该领域仍然存在两个棘手的问题。首先，谱聚类能够识别任意形状的聚类，但其高时间和空间复杂度限制了其在生成基础聚类时的应用。现有的大多数算法使用 k-means 来生成基础聚类，但对于非线性可分数据集的聚类效果仍需进一步改进。其次，集成聚类算法应该生成多个基础聚类。即使应用低复杂度的算法，运行时间仍然较长，这严重影响了集成聚类算法在大规模数据集上的应用。为了解决这些问题，作者提出了一种快速的 K-最近邻近似方法，构建锚点图以近似相似度矩阵，并使用奇异值分解（SVD）代替特征值分解（EVD），从而降低了传统谱聚类的时间和空间复杂度。同时，通过一次运行谱嵌入获得多个基础聚类。最后，将这些基础聚类转换为二分图，并使用转移切割（transfer cut）得到最终的聚类结果。所提算法显著降低了集成聚类的运行时间。对大规模数据集的实验结果充分证明了提出的算法的效率和优越性。

引言

聚类将给定的一组样本划分为多个簇，以确保同一簇内的样本具有较高的相似性，而不同簇之间的样本相似性较低。作为无监督机器学习的核心部分，聚类在推荐系统[1-3]、模式识别[4,5]、图像分割[6-8]等领域具有重要作用。经过多年的发展，研究人员提出了许多聚类算法，如k-means[9-11]、层次聚类[12-14]和谱聚类[15-17]等。其中，谱聚类由于在非线性可分数据集上的良好表现，受到了广泛的关注和研究。传统的谱聚类的时间和空间复杂度很高，主要体现在相似度矩阵构建和特征值分解（EVD）上。这两个步骤的时间复杂度分别为 O(N²d) 和 O(N²k)，空间复杂度为 O(N²)，其中 N 是样本数，k 是类别数，d 是数据集的维度。高时间和空间复杂度大大限制了谱聚类在大规模数据集上的应用。

集成聚类[18,19]，或称为共识聚类，通过融合来自多个基础聚类的信息，能够获得更好且更稳健的结果。集成聚类主要由基础聚类生成和共识函数分割组成。基础聚类是指单一聚类算法的划分结果，而共识函数则融合基础聚类生成最终的聚类结果。为了提高聚类结果的鲁棒性和准确性，需要确保基础聚类之间具有显著的差异。如果多个相同的基础聚类通过共识函数得到的结果，可能与单一的基础聚类等效，这违背了集成聚类的初衷。生成基础聚类的方法有很多，包括但不限于使用不同的聚类算法、相同聚类算法的不同参数和初始化、以及通过随机抽样获得不同的数据集进行聚类。基础聚类的聚类算法、参数和初始化方式不同，可以从不同角度反映数据集的内部结构信息，并对数据分布和噪声具有不同的敏感性。同时，共识函数用于融合丰富且互补的信息。因此，集成聚类能够提高聚类结果的准确性和稳定性，缓解单一聚类算法在初始化和参数敏感性以及只能处理特定结构数据集上的问题。

现有的大多数集成聚类算法[20–22]使用k-means算法生成基础聚类。尽管其时间复杂度较低，但由于k-means的局限性，这些算法在非线性可分数据集上的性能仍需要进一步改进。近年来，一些集成聚类算法[23–25]利用谱聚类生成基础聚类并取得了良好的效果，但其高复杂度限制了它们在大规模数据集上的应用。为了降低传统谱聚类的复杂度，一种广泛研究的策略是样本抽样[26,27]。Yan等人[26]首先运行k-means选择𝑝个代表点，然后对代表点进行谱聚类，最后将数据集中的样本划分为与最近代表点所属的簇相同的聚类。Shinnou和Sasaki[27]提出了一种新的抽样方法，运行k-means获取𝑝个代表点，然后去除靠近代表点的样本（预先定义距离阈值），并对剩余样本构建数据集进行谱聚类。尽管该策略显著提高了谱聚类的速度，但在抽样过程中会丢失大量的局部结构信息，导致聚类性能较差。另一种常用的策略是子矩阵近似。Chen等人[28]随机选择𝑝个样本作为锚点，构建一个大小为𝑁×𝑝的矩阵来近似相似度矩阵，然后通过执行特征值分解（EVD）获得特征向量。为了提高随机选择的稳定性，Cai和Chen[29]通过运行k-means获得𝑝个聚类中心，使用聚类中心作为锚点构建子矩阵，并最终通过奇异值分解（SVD）计算特征向量。此外，Huang等人[30]综合了上述两种算法，首先随机选择𝑝′（𝑝′>𝑝）个样本，然后在𝑝′个样本上运行k-means获得𝑝个聚类，并使用聚类中心作为锚点。然而，该算法在随机选择和k-means之间做了折衷，并没有消除随机性的影响。同时，在实际应用中，为了获得更好、更稳定的聚类结果，锚点的数量通常较大，因此时间复杂度仍然较高。集成聚类领域的另一个问题是需要生成多个不同的基础聚类。即使使用k-means等低复杂度算法，对于大规模数据集，运行时间仍然较长，严重限制了集成聚类处理大规模数据集的能力。尽管上述提到的U-SENC[30]可以处理大规模数据集，但它仍然需要多次运行谱聚类来获取基础聚类，聚类过程需要进一步加速。

为了解决集成聚类中的这些问题，本文提出了一种基于谱聚类的快速集成聚类算法，称为基于锚点的快速谱集成聚类（FSEC）。采用一种快速且稳定的锚点选择方法，并提出了一种快速的K-最近邻近似方法。为了减少谱聚类的时间和空间复杂度，构建了一个锚点图来近似相似度矩阵，并使用SVD替代EVD。更重要的是，该算法可以通过运行一次谱嵌入获得多个基础聚类，从而避免了多次运行谱聚类，显著减少了算法的运行时间。

总之，本文的主要贡献总结如下：

• 提出了一种快速的K-最近邻近似方法，显著减少了相似度矩阵构建的时间复杂度，从𝑁𝑝𝑑减少到𝑁𝐾𝑑，其中𝐾≪𝑝。
• 与其他基于谱聚类的集成聚类算法不同，所提算法通过运行一次谱嵌入即可获得多个基础聚类。
• 本文应用多种加速技术进行谱集成聚类，并提出了一种新的基于锚点的快速谱集成聚类算法。该算法的时间复杂度为 O(Npk)，空间复杂度为 O(Np)，非常适合处理大规模数据集。
• 在多个大规模数据集上进行了广泛实验，实验结果充分证明了所提算法在较短运行时间内获得了更好的聚类结果。

相关工作

2.1. 谱聚类

谱聚类算法来源于图论。它将数据集中的样本视为图中的顶点，并将样本之间的距离作为图中的权重。切割图时，最大化子图内的权重和，同时最小化子图之间的权重和，从而达到聚类的目的。对于具有𝑁个样本的数据集，谱聚类首先计算一个𝑁 × 𝑁的相似度矩阵，矩阵中的元素表示对应样本对之间的相似性。然后，对拉普拉斯矩阵进行特征值分解（EVD），以获取对应最小的𝑘个特征值的特征向量，实际上是对𝑁个样本的低维谱嵌入。最后，使用诸如k-means之类的离散化算法得到聚类结果。传统谱聚类的时间复杂度和空间复杂度分别为𝒪(𝑁²𝑘)和𝒪(𝑁²)。尽管在处理非线性可分数据集时具有明显优势，但高复杂度严重限制了谱聚类在大规模数据集和集成聚类中的应用。

一些算法通过子矩阵近似来避免计算𝑁 × 𝑁的相似度矩阵。Chen等人[28]随机选择𝑝个样本作为锚点，构建一个𝑁 × 𝑝的矩阵，图构建的时间复杂度为𝒪(𝑁𝑝𝑑)。虽然随机选择锚点的速度更快，但算法对所选锚点的质量依赖性很大，聚类效果不稳定（见图1(a)）。为了增强算法的稳定性，Cai和Chen[29]通过k-means得到𝑝个锚点。该方法旨在消除与锚点选择相关的随机性（如图1(b)所示）。然而，k-means的时间复杂度为𝒪(𝑁𝑝𝑑𝑡)，而图构建的时间复杂度为𝒪(𝑁𝑝𝑑)，对于大规模数据集来说不可接受。为了加速k-means，Huang等人[30]首先随机选择𝑝′个样本，然后对𝑝′个样本运行k-means得到𝑝个锚点，并通过K近邻近似方法构建子矩阵。在这个算法中，k-means的时间复杂度为𝒪(𝑝²𝑑𝑡)，图构建的时间复杂度为𝒪(𝑁𝑝^½𝑑)，但仍需要随机选择样本，并未消除随机性。如图1(c)所示（根据原文中的实验设置，首先随机选择80个样本并运行k-means），可以看到所选的锚点并不具有代表性，为了获得更好的聚类结果，通常会将𝑝设置得更大，但𝒪(𝑝²𝑑𝑡)仍然不可忽视。

2.2. 锚图

对于具有𝑁个样本的数据集，传统基于图的聚类算法需要计算𝑁²对样本的相似性，即计算并存储𝑁 × 𝑁的相似度矩阵，当处理大规模数据集时，这是不现实的。为了解决上述问题，Liu等人[31]利用锚图替代相似度矩阵，从而减少计算资源和存储空间的需求。锚图通过以下公式构建：

𝑾 = 𝑩 \𝜦^{-1} 𝑩^⊤

其中，𝑩 ∈ 𝑅^{𝑁×𝑝}，𝑏𝑖𝑗表示第𝑖个样本与第𝑗个锚点之间的相似度，𝜦是一个对角矩阵，其中𝛬𝑗𝑗 = ∑𝑖 𝑏𝑖𝑗。

2.3. 集成聚类

集成聚类通过结合多个基础聚类来获得更好且更稳定的聚类结果，因此受到了更多的关注。经过多年的发展，出现了大量的算法。根据共识函数，现有的算法主要分为三类：基于共现的算法、基于图的算法和基于中位数划分的算法。

基于共现的算法需要计算数据集的共现矩阵，即计算所有基础聚类中属于同一聚类的样本对的数量。可以将共现矩阵视为相似度矩阵，其中元素值越大，表示相应的样本对的相似度越高。通过使用一些基于相似度的聚类算法，可以得到最终的聚类结果。Fred 和 Jain [32] 利用证据积累的思想，通过在共现矩阵上使用层次聚合方法来获得聚类结果。Liu 等人 [21] 证明了加权 k-means 和谱聚类的等价性，并将其应用于共现矩阵，提出了谱集成聚类。

基于图的算法首先根据基础聚类的信息构建图，然后将图划分为一定数量的无连接子图，作为聚类结果。Strehl 和 Ghosh [33] 提出了三种基于图的集成聚类算法，CSPA、HGPA 和 MCLA，分别使用相似度度量、超图划分和元聚类的思想。Fern 和 Brodley [34] 从给定的基础聚类中构建了一个二分图，其中顶点表示样本和聚类，然后使用谱图划分或多级图划分来获得聚类结果。

与上述两种方法不同，基于中位数划分的方法将集成聚类问题转化为一个约束优化问题来求解。Li 和 Ding [35] 计算了来自基础聚类的相似度矩阵的加权和。然后，他们使用 Frobenius 范数作为目标函数来逼近指标矩阵，并获得聚类结果，而不需要其他聚类算法。

2.4. 快速集成聚类算法

经过多年的发展，研究人员提出了各种快速集成聚类算法。

在集成聚类领域，常用的加速策略是引入锚点。Liu 等人 [21] 使用加权 k-means 代替谱聚类来减少算法复杂度，但它仍然使用 k-means 生成基础聚类，因此聚类效果并不理想。Huang 等人 [30] 提出了混合代表选择策略，并使用转移切割加速相似度矩阵的划分。然而，混合策略仍未消除随机性的影响。Yang 等人 [36] 在锚点上执行谱聚类，然后将样本划分到最近的锚点聚类中。本文主要致力于降低空间复杂度，并直接对锚点进行聚类，但忽略了局部结构信息。基于 [30,37]，进一步通过重用锚点图和引入轻量级 k-means 加速了聚类过程。Liang 等人 [38] 首先利用低秩约束和锚点来获得鲁棒的相似度矩阵，然后使用谱聚类来获取聚类结果。然而，它直接对锚点进行聚类，忽略了数据集的局部结构信息，聚类效果较差。

多视图聚类也面临着处理大规模数据集困难的问题。Kang 等人 [39] 在每个视图上学习小规模的图，然后将它们融合成一个线性时间复杂度的单一图。然而，它多次使用 k-means 查找锚点，且在大规模数据集上的运行时间仍然较长。Sun 等人 [40] 将锚点学习和图构建结合成统一的优化框架，以提高所选锚点的质量，时间复杂度仅为线性。此外，Zhao 等人 [41] 专注于不完全多视图聚类问题，使用视图间二分图来指导视图内二分图的自我完成。Yin 和 Sun [42] 通过重构不完整的视图来发现潜在表示。Huang 等人 [43] 使用混合代表选择策略和转移切割方法加速了每个单一视图的谱聚类过程。更重要的是，算法提出了一种多阶段混合策略来提高聚类的准确性。

虽然上述算法有效地加速了集成聚类过程，但该领域仍有许多问题需要解决。首先，锚点选择方法需要进一步改进。现有的方法可以分为 k-means 选择、随机选择和混合代表选择。在这些方法中，k-means 选择产生的锚点质量较高，但会产生显著的时间成本。另一方面，随机选择和混合选择策略具有较低的时间复杂度，但引入的随机性通常会导致锚点质量较差，从而影响聚类性能。其次，构建相似度矩阵的时间复杂度较高。大多数方法计算所有样本与其𝐾个最近锚点之间的距离，但未能高效利用锚点的特性，导致了大量的时间成本。第三，生成基础聚类的过程较为繁琐。为了增强基础聚类之间的多样性并改善聚类效果，现有的算法通常需要多次运行谱聚类并调整不同的参数。即使是改进后的谱聚类，在大规模数据集上的运行时间依然不可接受。

为了解决这些问题，作者提出并实现了一系列加速方法。对于锚点选择问题，引入了一种基于平衡 k-means 的层次 k-means 方法，能够在较短的时间内高效地识别高质量的锚点。为了改进相似度矩阵的构建，开发了一种 K-最近邻快速近似方法，该方法充分利用了锚点的特性，显著加快了处理速度。对于基础聚类的生成，算法采用一次谱嵌入运算，随后进行多次 k-means 运算，从而生成多样化的基础聚类。这种方法不仅简化了生成过程，还显著降低了时间复杂度。

模型

 FSEC 的整体框架（见图 2）。

3.1 构建锚点图

3.1.1 锚点选择

对于包含 N 个样本的数据集，传统的谱聚类需要构建 N×N 的相似度矩阵来挖掘数据集的内部结构。图的构建时间复杂度高达 O(N2d)，空间复杂度为 O(N2)，对于大规模数据集来说是不可行的。为了扩展谱聚类在大规模数据集上的应用，常用的策略是基于锚点的子矩阵近似，这主要包括两个步骤：锚点选择和子矩阵构建。在这种策略中，锚点的质量对聚类结果具有至关重要的影响。随机选择锚点速度较快，但无法保证锚点的质量，导致聚类效果较差。基于 k-means 的选择策略在给定数据集上运行 k-means 算法，并使用聚类中心作为锚点。高质量的锚点能够改善聚类效果，但 k-means 的时间复杂度为 O(Npdt)，这在一定程度上增加了谱聚类的时间开销和计算负担。混合代表选择策略在随机选择和 k-means 之间进行平衡，首先随机选择 p′（p′>p）个样本，然后在 p′个样本上运行 k-means 算法生成 p 个聚类，并将聚类中心作为锚点。其时间复杂度为 O(p′2dt)。尽管混合代表选择策略减少了 k-means 策略的时间复杂度，但它并未完全消除随机性的影响，因此无法保证得到最具代表性的高质量锚点。

与上述方法不同，作者参考了平衡 k-means 基层次 k-means 算法（BKHK）[44]，该算法能够快速获得给定数据集的高质量锚点。如图 3 所示，BKHK 借鉴了平衡二叉树结构，并采用分治思想加速 k-means 算法。在 BKHK 中，每次迭代将当前样本分成两个子集，每个子集的样本数量相同，直到子集的数量等于数据集中的聚类数为止，迭代停止。其时间复杂度为 O(Nlog⁡(p)dt)。利用 BKHK 将数据集划分为 p 个聚类，并计算聚类中心作为锚点。图 1(d) 显示了 BKHK 在玩具数据集上的锚点选择效果。

3.1.2 图构建

在获得锚点后，谱聚类计算所有样本与其 K-最近锚点之间的相似度，以构建相似度矩阵。具体来说，谱聚类首先计算 N 个样本与 p 个锚点之间的距离，得到 N×p的子矩阵，然后保留每一行的最大 K 个元素，并将其余元素置为 0，以稀疏化相似度矩阵。其时间复杂度和空间复杂度分别为 O(Npd)，需要进一步优化。

充分利用锚点的特性，提出了一种 K-最近邻快速近似方法来加速相似度矩阵的构建。锚点是数据集不同区域中样本的代表性点，锚点之间的距离与锚点区域内的样本与其余锚点之间的距离非常相似。基于这一点，可以使用样本所属锚点的邻近锚点来减少其 K-最近邻的选择范围。

在高效近似过程中，最关键的步骤是存储每个锚点的 K-最近锚点。具体来说，对于锚点 aj，首先计算它与其他锚点的距离，然后按升序排序这些距离，最后选择距离最小的 K′个锚点作为 K-最近锚点。获得所有锚点的 K-最近锚点后，可以执行快速近似方法来获取样本的 K-最近锚点。对于样本 xi，可以按照图 4 的步骤获取它的 K-最近锚点：

• 在运行 BKHK 方法时，找到样本 xi 所属于的锚点 aj。
• 选择锚点 aj 的最近的 K′ (K′>K) 个锚点作为候选锚点，这里将 K′=10K以增加快速近似方法的鲁棒性。
• 计算并排序样本 xi与其候选锚点之间的距离。
• 使用最近的 K个锚点作为样本 xi的 K-最近锚点。

在提出的方法中，计算锚点之间的距离并排序的时间复杂度为 O(p2d+p2log⁡(p))，计算样本与邻近锚点之间的距离并排序的时间复杂度为 O(NKd+NKlog⁡(K))。

接下来，需要构建样本与其 K-最近锚点之间的相似度矩阵。大多数传统算法使用基于核的方法，例如高斯核，但它引入了额外的参数 σ，且需要调整参数值以获得更好的聚类结果。作者使用[45]中的方法来避免调参过程。样本 xi与其 K-最近锚点之间的相似度可以通过求解以下优化问题得到：

3.2. 生成基础聚类

3.2.1. SVD

谱聚类的一般形式为

其中，F是指示矩阵，L=D−W是拉普拉斯矩阵，D是对角矩阵，其对角元素为dii=∑jwij。

根据公式(1)和(3)，可以证明W是双重随机的。由于W的行和为1，因此D=I，问题(4)可以转化为

上述问题的解是W对应的最大k个特征值的特征向量，但特征值分解（EVD）的时间复杂度过高。因此，改为使用更快速的SVD方法。根据公式(1)，可以得到

其中，U是左奇异向量，V是右奇异向量，Σ是奇异值。可以证明，当Σ对角线上的值按降序排列时，U中的前k列向量等同于W的最大特征值对应的特征向量，即F。可以将F的行向量视为样本，然后运行k-means算法来获得聚类结果。

3.2.2. k-means

一些谱集成聚类算法通过多次运行谱聚类并设置不同类别来获得基础聚类，例如U-SENC，以增加基础聚类的多样性。它多次选择锚点以构建多个相似性矩阵。然后，它运行快速近似谱聚类算法以获得多个基础聚类，显著增加了U-SENC的时间复杂度。然而，具有不同类别数的基础聚类完全满足集成聚类对基础聚类多样性的要求，而且无需多次选择锚点来增加多样性。因此，只选择锚点，构建相似性矩阵，并执行SVD一次。为了减少时间复杂度，执行SVD时不需要求解所有特征值，只需满足第四节中基础聚类的最大类别数，因此U的大小可以表示为RN×min⁡(50,N)。在获得左奇异向量矩阵U后，选择左侧的ci列向量（ci在设定范围内随机选择），运行k-means算法，并使用聚类结果作为基础聚类πi。此过程重复多次，得到基础聚类集

3.3. 二分图划分

3.3.1. 二分图构建

获得多个基础聚类后，通过引入二分图进行共识函数划分，得到最终的聚类结果。
基础聚类πi包含ci个聚类，那么m个基础聚类中的所有聚类集合为

使用样本X和聚类Y作为顶点来构建二分图，即G={X,Y,B~}, ，其中B是相似性矩阵，衡量X和Y之间的相似性。

3.3.2. 共识函数划分
在执行共识函数划分之前，B~需要转化为完整的相似性矩阵，即

它衡量N+C个样本之间的相似性。
根据谱聚类，通过求解以下特征问题来划分图E[46]：

其中，拉普拉斯矩阵。使用EVD求解问题(12)的时间复杂度为O((N+C)3)，对于大数据集来说是不可行的。

为了减少共识划分的时间复杂度，参考[47]使用转移切割。具体来说，利用二分图的特殊结构，求解问题(12)中的N+C个样本的特征问题，简化为求解C个样本的特征问题。新的简化图为G~={Y,E~}，其中Y是锚点集合，，是对角矩阵。
G~的特征问题可以表示为

[47]证明了问题(12)和问题(13)的等价性，并给出了f和u之间的关系：

求解问题(13)的时间复杂度为O(C3)。获得u后，可以使用公式(14)计算f，从而避免直接求解问题(12)。在此，选择对应于最小k个特征值的特征向量，形成大小为(N+C)×k(的新矩阵。前N行向量对应数据集中的N个样本，可以在这些样本的前N行向量上使用k-means算法得到最终的聚类结果。

实验

聚类结果的比较见表3到表5，运行时间的比较见表6，其中 N/A 表示由于内存不足，相关算法无法运行。在本节中，运行时间包括基聚类生成和共识函数划分。

通过比较，得出以下结论：

• FSEC 在大多数大规模数据集上取得了最好的聚类结果，特别是在 Covertype 和 MNIST 数据集上，ACC 相比次优结果提高了 18% 和 5%。

• 与基于 k-means 的集成聚类算法相比，FSEC 使用谱聚类生成基聚类，同时引入了 K 最近邻近似、锚点图等方法，显著降低了算法的时间复杂度。大规模数据集上运行时间的比较也有力地证明了 FSEC 的高效性。

• 在比较的算法中，U-SENC、LSEC 和 LiteWSEC 是适用于大规模数据集的快速集成聚类算法，与其他算法不同，它们的基聚类是通过谱聚类生成的。它们在实验数据集上实现了最优或次优的聚类结果，表明基于谱聚类的集成聚类算法在处理非线性可分数据集时更具优势。

• 与 LSEC 和 LiteWSEC 相比，FSEC 在相似或更短的运行时间内能够获得更好的聚类结果，证明提出的加速策略在谱集成聚类算法中是有效的。在某些数据集上，FSEC 的运行时间为次优。一个原因是 LSEC 和 LiteWSEC 在聚类时使用了更快的 lite-k-means，最大迭代次数设置为 10，而作者的算法使用 k-means 进行聚类，最大迭代次数为 100。

为了更清楚地说明所提算法的效率，作者记录了算法每一步的具体运行时间，结果见表7。可以看出，基聚类生成占用了谱集成聚类算法大部分的运行时间，这与本文从基聚类生成开始加速算法是一致的。

此外，为了说明所提算法与比较方法之间的差异，作者多次运行了所提算法和每种比较方法，得到了两组标准化互信息（NMI）值。然后，作者进行了 t 检验分析，以评估两组结果之间的显著差异。对于 t 检验方法，原假设是两种方法得到的聚类结果没有显著差异，而备择假设是存在显著差异，意味着所提算法与比较方法之间存在差异。

实验结果见表8。这里，𝑝-value 表示假设原假设为真时，观察到给定结果的概率。假设检验结果用 ℎ 表示，表明是否可以在显著性水平 𝛼 = 0.05 下拒绝原假设：ℎ = 0 表示无法拒绝原假设，ℎ = 1 表示拒绝原假设并接受备择假设。𝑝-value 和 ℎ 明确展示了所提算法与比较方法之间的显著差异。

---

重点在于锚点图的构建与二分图的划分。。