🤖 machine learning

Topology-Driven Clustering: Enhancing Performance with Betti Number Filtration

本文介绍了 BFTC，这是一种新颖的拓扑聚类算法，它利用从局部 Vietoris-Rips 过滤中导出的多尺度 Betti 序列来构建拓扑感知相似性结构，从而有效地对复杂、非凸且交织的数据结构进行聚类，并超越了现有的最先进方法。

原作者： Arghya Pratihar, Kushal Bose, Swagatam Das

发布于 2026-07-22

📖 1 分钟阅读☕ 轻松阅读

原作者： Arghya Pratihar, Kushal Bose, Swagatam Das

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

事物的形状

想象一下，你正试图整理一堆乱七八糟的玩具。其中有一些是红色的积木，一些是蓝色的球，还有一些是绿色的蛇。如果你仅仅观察它们在地面上的距离来分组，你可能会因为红色的积木恰好落在蓝色球旁边，就把它们归为一类。这就是许多传统计算机程序尝试对数据进行分类的方式：它们测量点之间的直线距离。但如果那些“蛇”实际上是缠绕在“球”周围的长而弯曲的环呢？仅凭距离无法告诉你这条蛇是一个单一的、连通的形状；它只能看到一堆散乱的点。

为了解决这个问题，科学家们使用了一个叫做拓扑数据分析（Toplyogical Data Analysis, TDA）的领域。可以将 TDA 想象成一种不仅将数据视为散落的点，还将其视为具有山丘、山谷和隧道的景观的方法。该领域的一个关键工具是“持续同调”（persistent homology），它就像一个相机，可以在不同的缩放级别下拍摄数据的照片。随着你不断放大（缩小视野），你可以看到哪些特征（比如甜甜圈中的洞或蛇身上的环）保持可见，而哪些只是随机噪声。另一个核心概念是“贝蒂数”（Betti number），它简单来说就是这些特征的数量：有多少个独立的岛屿？有多少个隧道？有多少个中空的泡泡？通过计算这些形状，计算机可以理解数据的真实结构，即使这些数据是扭曲的、缠绕的或非凸的（即看起来不像简单的球体或方块）。

论文的核心思想：BFTC

在这篇论文中，作者介绍了一种名为基于贝蒂数过滤的拓扑聚类（Betti Number Filtration-based Topological Clustering，简称 BFTC）的新方法。他们认为，虽然以前的方法尝试使用这些拓扑思想，但往往由于试图一次性观察整个数据集，或者只计算最简单的特征（比如仅仅计算岛屿数量），从而错失了目标。BFTC 提出了一种更聪明的方法：像侦探检查特定街区一样，局部地观察数据，并在每一个尺度上计算复杂的形状。

以下是其运作的魔力步骤：

邻里观察： 首先，算法选择一个点并观察其直接邻居（要么是最近的 $k$ 个朋友，要么是所有在一定半径范围内的点）。
缩放镜头（过滤/Filtration）： 算法不仅仅是观察这个邻域一次，而是创建了一个“过滤”。想象在你所在的邻域周围慢慢吹大一个气球。随着气球的膨胀，它会连接原本相距较远的点。在膨胀的每一个阶段，算法都会构建一个临时形状（称为 Vietoris–Rips 复形），并计算其中的洞和环。
拓扑指纹： 随着气球从小到大膨胀，洞的数量会发生变化。一个小气球可能会看到 10 个独立的岛屿。一个中等大小的气球可能会看到它们合并成 2 个岛屿和 1 个隧道。一个巨大的气球可能会看到一切都变成 1 个巨大的岛屿。这一系列数字被称为贝蒂序列（Betti sequence）。这就像是该特定邻域的独特指纹，描述了其形状如何随规模演变。
匹配指纹： 算法随后比较相邻点的贝蒂序列。如果两个点的序列相似（意味着它们的邻域随着缩放过程以相同的方式演变），那么即使它们在物理距离上不是最近的，也会被认为在“拓扑上是相似的”。
清理工作： 算法利用这些相似性来清理地图。它会移除“离群值”或不符合拓扑模式的邻居，从而创建一个更干净、更准确的数据真实结构图。
最终排序： 最后，它在这个新的、具备拓扑感知能力的地图上使用一种标准的数学技术（谱聚类）将数据分组。

他们的发现

作者在各种棘手的数据集上测试了 BFTC，包括旨在欺骗其他算法的合成数据集。这些数据集包括：

连锁环面（Linked Tori）： 两个像链条一样相互锁定的甜甜圈（环面）。
扭曲形状： 混合了螺旋、圆圈和球体的形状数据。
现实世界数据： 如“动物园”（分类动物）、“大肠杆菌”（细菌）和 “MNIST”（手写数字）等数据集。

结果非常令人鼓舞。在模拟实验中，BFTC 始终优于其他先进的方法，包括旧的拓扑方法如 ToMATo、TPCC 和 TKM。例如，在“连锁环面”数据集（两个纠缠在一起的甜甜圈）中，BFTC 取得了近乎完美的得分（ARI 为 1.00 且 NMI 为 1.00），而其他方法在分离这两个相互锁定的形状时表现挣扎。即使研究人员在数据中加入了噪声（随机静电），BFTC 依然保持稳健，这表明它能很好地处理杂乱的现实世界信息。

论文还探讨了不同设置如何影响结果。他们发现，使用余弦相似度（比较贝蒂序列的方向而非仅仅是大小）比标准的距离度量效果更好。他们还发现，“邻域”的大小至关重要：如果邻域太小，会错过全局图景；如果太大，则会连接无关的形状。然而，通过调整这些设置，BFTC 成功识别出了其他算法错过的复杂结构。

它目前还做不到什么

需要注意的是，论文并未声称该方法是解决所有问题的万能药。作者明确指出，他们的方法依赖于计算贝蒂数，如果你尝试在海量数据集中计算极高维度的洞（如 4D 或 5D 的洞），计算成本可能会变得非常高昂。他们建议，对于极高维度，最好坚持使用较低的维度（如 0、1 或 2 维），这样数学处理才是可控的。

此外，虽然论文在数学上证明了该算法是稳定的（即数据的微小变化不会导致结果崩溃），但这些是基于假设的理论证明。论文中展示的实际“胜利”是基于特定数据集的模拟和实验，而非对宇宙中所有可能数据的普遍保证。作者建议，未来的工作可以侧重于如何让该方法在超大规模数据集上运行得更快，以及如何探索无需人工干预即可自动选择最佳设置的方法。

简而言之，BFTC 表明，通过监听数据通过其不断演变的洞和环所展现出的“形状”，我们可以比仅仅测量点与点之间的距离更好地对复杂的、纠缠的信息进行分类。

技术摘要：基于贝蒂数过滤的拓扑聚类 (BFTC)

1. 问题陈述

传统的聚类算法（如 k-Means、DBSCAN、谱聚类）严重依赖于基于欧几里得距离或核函数的相似性度量。虽然这些方法在许多应用中非常有效，但它们在处理具有复杂几何结构的数据集（如非凸形状、多尺度或交织流形）时往往表现不佳。它们经常无法捕捉到内在的拓扑特征，如环（loops）、空腔（voids）和高维连通性。

现有的拓扑数据分析（TDA）方法试图弥补这一差距，但也面临着特定的局限性：

ToMATo：依赖于 0 维同调（连通分量）和密度景观，限制了其整合高维拓扑信息的能力。
TPCC：使用单纯复形和 Hodge 拉普拉斯算子，但在区分拓扑特征在不同过滤尺度下涌现的区域方面可能存在困难。
拓扑 k-Means (TKM)：将持久图嵌入到再生核希尔伯特空间（RKHS）中，但侧重于全局拓扑摘要，而非局部、多尺度的拓扑。

本研究解决的核心挑战是：需要一种能够同时捕捉局部几何邻近性和高维拓扑结构，并在多尺度方式下运行的聚类算法，且不完全依赖于全局持久性摘要或固定的拓扑尺度。

2. 方法论：BFTC 算法

所提出的方法——基于贝蒂数过滤的拓扑聚类 (BFTC)，通过以下步骤构建了一个具备拓扑感知能力的相似性结构：

A. 邻域图构建

算法首先为数据集 $X$ 构建一个局部邻域图。它支持两种变体：

k-NN BFTC：使用 k-最近邻图以确保统一的基数和受控的稀疏性。
$\epsilon$ -BFTC：使用基于固定几何半径的 $\epsilon$ -邻域图，与度量阈值构造自然对齐。

B. 局部 Vietoris-Rips 过滤与贝蒂序列

对于每个数据点 $x_i$ ，算法在其局部邻域 $N(x_i) \cup \{x_i\}$ 上构建一系列嵌套的 Vietoris-Rips (VR) 复形。

过滤尺度由一系列阈值序列 $\epsilon_1, \epsilon_2, \dots, \epsilon_L$ 定义。
对于每个尺度，形成 VR 复形 $VR(x_i, \epsilon_l)$ 。
贝蒂数：算法计算最高至用户指定最大维度 $M$ 的贝蒂数 $\beta_m$ （其中 $M$ 反映了内在的拓扑复杂度，而不一定是环境特征维度）。
贝蒂序列：对于每个维度 $m \in [0, M]$ ，跨过滤尺度的贝蒂数序列构成一个贝蒂序列 $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$ 。这些序列作为局部邻域的多尺度拓扑签名。

C. 拓扑感知相似性与图精炼

算法通过比较相邻点的贝蒂序列来量化它们之间的拓扑相似性。

相似性度量：针对每个维度 $m$ ，计算相邻点 $x_i$ 和 $x_j$ 贝蒂序列之间的余弦相似度：
$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$
异常值移除：应用一组阈值 $\alpha_0, \dots, \alpha_M$ 。只有当对于所有维度 $m$ ，均满足 $(d_{ij})_m \geq \alpha_m$ 时，邻居 $x_j$ 才会保留在精炼后的邻域 $N'(x_i)$ 中。这一步消除了拓扑不相似的邻居和异常值，从而得到一个更稀疏、信息量更丰富的图。

D. 谱聚类

利用高斯核从精炼后的图中构建对称加权邻接矩阵 $A'$ 。计算拉普拉斯矩阵 $L' = D' - A'$ ，并应用谱聚类（通过对最小的 $p$ 个特征值的特征向量进行 k-Means 聚类）以获得最终的聚类结果。

3. 主要贡献

本文概述了三个主要贡献：

新颖算法 (BFTC)：一种高效的聚类算法，它在局部邻域上构建 Vietoris-Rips 复形，并评估高达指定维度的贝蒂数。它利用贝蒂序列来衡量拓扑相似性，超越了简单的连通性（ $\beta_0$ ）以捕捉高维特征。
复杂结构的有效性：该方法通过利用底层的拓扑特性，专门设计用于处理具有复杂、交织形状和结构的数据集。
理论分析：论文提供了关于 BFTC 收敛性和稳定性的广泛理论基础。研究表明，在合理的几何和谱分离条件下，该算法在结构上是稳定的；输入数据的微小扰动不会改变最终的聚类结果（仅限于标签置换）。

4. 实验结果

作者在合成数据集和真实世界数据集上，将 BFTC（包括 k-NN 和 $\epsilon$ 变体）与最先进的基准方法（k-Means、Spectral、DBSCAN、ToMATo、TPCC、TKM 等）进行了评估。

合成数据集：在具有非凸和交织结构的数据集（如 Linked Tori, 3MC, Smile1, Torus Sphere Line）上，BFTC 一致取得了优异的调整兰德指数 (ARI) 和归一化互信息 (NMI) 分数。例如，在带有噪声 ( $\rho=0.3$ ) 的 Linked Tori 数据集上，k-NN BFTC 实现了 0.49 的 ARI 和 0.56 的 NMI，显著优于 DBSCAN (0.01 ARI) 和 ToMATo (0.17 ARI) 等竞争对手。
真实世界数据集：实验表明，在 UCI 数据集（Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL）上，BFTC 几乎超越了所有竞争者。
鲁棒性：该方法对高斯噪声扰动表现出了稳定性。
消融研究：
- 邻域构建：k-NN 和 $\epsilon$ -邻域均被证明是有效的，尽管对于高度交织的流形，k-NN 提供了更平滑的谱行为。
- 距离度量：研究发现，贝蒂序列之间的余弦相似度在捕捉拓扑关系方面明显比欧几里得距离更有效。
- 核函数：在邻接矩阵中引入高斯核相比于未加权图提高了性能。

5. 意义与主张

论文声称，BFTC 通过将多尺度拓扑信息直接整合进聚类过程，代表了一项重大进展。与以往依赖全局持久性摘要或固定尺度的算法不同，BFTC 通过贝蒂序列捕捉了局部多尺度拓扑。

作者断言，这种方法使得算法能够：

区分流形中拓扑特征在不同过滤尺度下涌现的区域。
同时捕捉几何邻近性和高维拓扑结构（环、空腔）。
为具有复杂、非凸和交织结构的数据集提供稳健的解决方案，而传统的基于欧几里得的方法在这些场景下会失效。

理论分析进一步支持了实验结果，声称 BFTC 不仅在计算上是有限的，而且在结构上是稳定的，这确保了聚类流水线对于输入数据的微小扰动具有局部不变性。研究结论指出，探索针对具有复杂重叠结构的大规模数据集的拓扑方面，仍是未来研究的一个充满前景的方向。