🤖 machine learning

Voronoi Histograms for Adaptive Vectorization of Expected Persistence Diagrams

本文提出了一种基于 Voronoi 直方图的期望持久图向量化方法，该方法通过自适应划分计数取代了预定义的平滑变换，具有经证明的稳定性，并在分类和降维任务的真实数据集上表现出有效的性能。

原作者： Kaifeng Zhang, Kai Ming Ting

发布于 2026-07-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Kaifeng Zhang, Kai Ming Ting

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

想象一下，你是一位正在试图理解一个神秘物体形状的侦探，但你只能将其看作是在太空中漂浮着的由数千个微小尘埃颗粒组成的云团。这就是**拓扑数据分析（Topological Data Analysis, TDA）的世界。TDA 不去测量物体的长度或重量，而是询问：“这个云团中间是否有洞？它是一个环吗？是一个空心球体吗？”为了回答这个问题，数学家们使用了一种叫做持久图（Persistence Diagram）**的工具。你可以把这张图想象成一张地图，其中的每一个点都代表一个特征（比如一个环或一个空洞），这个特征随着你逐渐“放大”观察尘埃云的过程而出现。点的坐标告诉你，随着缩放比例的变化，这个特征是在何时“诞生”以及何时“消亡”的。

然而，这里有一个问题：这些地图非常凌乱。它们是由散落的点组成的，而计算机很难直接从散落的点中学习，因为它们需要整齐的数字列表（向量）才能施展其魔力。长期以来，科学家们一直尝试通过用一层柔软、模糊的过滤器（如高斯模糊）来涂抹这些点，或者在上面绘制一个平滑的景观，将这些点图转化为整齐的列表。这就像是通过拍摄一张长曝光照片来统计拥挤房间里的人数：你会得到一张平滑的照片，但你可能会忽略掉两个紧挨在一起的人。

现在，**期望持久图（Expected Persistence Diagrams, EPD）**登场了。当尘埃云过于庞大而无法一次性分析时，科学家会对它进行多次小规模采样（子采样），为每个样本制作一张地图，然后将它们全部平均起来。这个平均后的地图就是 EPD。它是形状的一个统计摘要，但它仍然是一团点的云，而不是一个整齐的数字列表。现在的关键问题是：我们如何将这团平均后的点云转化为计算机可以使用的数字列表，从而让计算机能够分辨出一个物体是“猫”还是“狗”，同时又不丢失重要的细节？

论文的核心思想：在自定义的“桶”中计数

这篇论文介绍了一种巧妙的新方法，可以将那些凌乱的、平均后的点云转化为整齐的数字列表。作者 Kaifeng Zhang 和 Kai Ming Ting 提出了一种他们称之为**维诺图直方图（Voronoi Histograms）**的方法。

他们没有像以往的方法那样用模糊的过滤器来涂抹这些点，而是决定围绕这些点构建自定义的“桶”或“箱子”，并简单地统计落在每个桶里的点的数量。想象一下，你有一个铺满散落弹珠（你的数据点）的大型地板。你不是在地上涂抹一层平滑的渐变色，而是向地上投掷一些特殊的“吸引子”弹珠（称为码本/codebook）。然后，你在地板上画线，使得地板上的每一个位置都属于距离最近的那个吸引子。这创造了一个被称为**维诺单元（Voronoi cells）**的补丁式地毯。

神奇之处在于计数过程。你观察你的数据弹珠云，然后问道：“有多少个弹珠落在吸引子 #1 的领地内？有多少个落在吸引子 #2 的领地内？”你将这些计数记录为一个数字列表。这就是你的向量！

该论文认为，对于某些类型的数据，这种“在自定义桶中计数”的方法优于旧有的“模糊平滑”方法。以下是他们的发现：

1. 它是数据依赖型的映射
不同于使用固定网格（如坐标纸）或为所有人使用固定平滑曲线的旧方法，这种方法根据数据的实际分布来构建它的“桶”。如果你的数据聚集在一个角落，桶就会缩小以适应那个角落；如果数据分布广泛，桶就会扩大。这使得该方法具有“自适应性”。这就像是一个量体裁衣的裁缝，根据你的具体身材来制作西装，而不是买一件可能太肥或太紧的“均码”西装。

2. 它具有稳定性（大部分情况下）
作者通过数学证明，如果你轻微移动数据点（比如轻晃桌子），桶中的计数不会发生剧烈变化。他们证明了该方法是“稳定的”，这意味着数据的微小误差不会导致最终的数字列表变得失控。然而，他们也发现了一个权衡：如果你使用过多的桶（使列表变得很长），该方法会变得略微不稳定。这是一种在拥有足够细节与保持系统鲁棒性之间的平衡。

3. 它非常擅长处理“粗粒度”的变化
论文在蛋白质结构和机械零件等现实世界数据集上测试了这种方法。他们发现，当两个物体之间的差异表现为形状上的巨大、明显的位移（例如一个环从地图的一侧移动到另一侧）时，这种计数方法极其准确。它能很好地捕捉质量分布的“大局”运动。

4. 但它并非万能灵药
作者非常谨慎，并未声称这是对所有情况都最好的方法。他们明确展示了，如果两个物体之间的差异仅仅是单个桶内部极其细微的抖动，这种方法可能会错过它。在这些情况下，旧有的“模糊平滑”方法可能表现得更好，因为它们能够捕捉到微小的偏移。此外，论文指出，虽然这种方法速度很快且能很好地配合简单的分类器（如随机森林），但在某些测试中，它并不总是能击败最复杂、重型的神经网络（如 PointNet）。

5. “码本”的选择至关重要
作者实验了如何选择那些“吸引子”弹珠（即码本）。他们发现，如果基于数据中最重要的特征（如最持久的环）来挑选它们，该方法的效果会更好。如果你只是随机挑选或者从一个固定的框中选取，效果尚可，但不如前者理想。

总结

这篇论文表明，对于许多形状分析问题，我们不需要将数据平滑成一片模糊的景观。相反，我们可以构建一个由数据驱动的自定义补丁地毯，然后只需统计每个补丁中的点数即可。这是一种更简单、更直接的方法，能将复杂的形状转化为计算机可以理解的数字。

作者证明了这种“维诺图直方图”方法是现有方法的强有力竞争者。它特别擅长识别形状的重大结构性变化，并且计算效率很高。然而，他们也承认这是一种“有损”的表示——这意味着桶内的某些微小细节会被丢弃。因此，虽然它是拓扑学家工具箱中的一件有力新工具，但它并不是要取代其他所有工具。它最适合用于当你想要捕捉形状的主干故事，而不至于迷失在噪声之中时。

技术摘要：用于期望持久图自适应向量化的 Voronoi 直方图

1. 问题陈述

拓扑数据分析 (TDA) 利用持久同调 (PH) 来捕捉点云的拓扑特征，并将其编码为持久图 (PD)。PD 将拓扑特征（环）表示为开半平面 $\Omega$ 中的点 $(b, d)$ ，其中 $b$ 和 $d$ 分别表示出生时间和死亡时间。然而，PD 不能直接作为标准机器学习算法的输入，因此需要进行向量化。

使用 PD 的一个显著瓶颈在于其高计算复杂度；获取一个 PD 的复杂度可能达到 $O(m^3)$ 甚至对于 1 维特征达到 $O(|X|^9)$ 。为了缓解这一问题，开发了期望持久图 (EPD)。EPD 是通过对点云的多个子采样集合的 PD 进行平均而得到的拓扑特征分布。虽然 EPD 降低了时间成本，但现有的 EPD 向量化方法（如持久图像 Persistence Images、持久轮廓 Persistence Silhouettes 和持久景观 Persistence Landscapes）依赖于预定义的连续点变换函数（例如高斯核或景观函数）和固定的离散化网格。这些方法在平滑度、带宽和网格分辨率方面引入了设计选择，可能会模糊局部质量差异或强调非最优区域的 $(birth, death)$ 平面。

本文旨在解决一种替代性的向量化需求，该方法应避免显式的平滑点变换模型，转而利用自适应的、数据依赖的分区来表示 EPD 分布。

2. 方法论：基于 Voronoi 的表示 (Vrep)

作者提出了 Vrep，一种将经验 EPD 视为拓扑特征分布，并使用基于 Voronoi 图的直方图对其进行表示的向量化方法。

核心机制

码本采样 (Codebook Sampling)： Vrep 不使用固定网格，而是构建一组随机码本 $S$ 。每个码本 $C = \{c_1, ..., c_k\}$ 由从 EPD 支持集（即拓扑特征集合）中采样的点组成。
Voronoi 分区： 对于给定的码本 $C$ ，将开半平面 $\Omega$ 分割为 Voronoi 单元 $V(c_i)$ ，其中每个单元包含比任何其他 $c_j$ 更接近 $c_i$ 的点。
直方图构建： 表示 $\Phi(\bar{\mu}, C)$ 被定义为落在每个 Voronoi 单元中的 EPD $\bar{\mu}$ 的归一化质量向量：
$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$
聚合： 为了形成最终的表示 $\hat{\Phi}(\bar{\mu})$ ，该方法将从数据集中采样的多个码本生成的直方图进行拼接。
对角线感知变体 (Vrepd)： 一个特定的变体 Vrepd 包含一个以对角线 $\partial\Omega$ （即 $b=d$ 处）为中心的 Voronoi 单元。这对于分离噪声（靠近对角线的特征）与显著的拓扑特征至关重要。

码本采样策略

论文评估了三种在码本内采样点的策略：

默认 (Default)： 从 EPD 支持集进行均匀采样。
持久性加权 (Persistence-Weighted)： 按持久性 ( $d-b$ ) 加权采样，优先考虑显著特征。
均匀 (Uniform)： 从对角线上方的固定矩形区域进行采样（与 EPD 无关）。

归一化

该方法将 EPD 归一化为单位 $l_1$ -范数 ( $\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$ )。这将 EPD 视为概率分布，确保所有 EPD 具有相同的质量，从而允许直接使用 Wasserstein 距离进行稳定性分析和差异度量，避免了使用最优部分传输 (Optimal Partial Transport) 度量。

3. 理论贡献

论文确立了 Vrep 在特定条件下的稳定性及表示能力方面的理论保证：

稳定性界限： 作者证明了 Vrep 在 EPD 扰动下是稳定的。具体而言，如果 EPD 经历 $\Delta$ -扰动（Dirac 质量的微小移动），则 Vrep 表示的变化相对于 $\Delta$ 是 Lipschitz 连续的。误差界限取决于码本大小 $k$ 和数据集属性。
与 Wasserstein 相关的界限： 论文提供了一个关于两个 Vrep 向量之间的 $l_1$ 距离与底层 EPD 之间的 Wasserstein 距离 ( $W_1$ ) 相关的条件下界。
$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{近似误差}}{d_{max}(C)}$
这一结果表明，当码本“解析度良好”（即近似误差相对于分布的分离度较小）时，Vrep 能有效保留 Wasserstein 尺度的变化。这并非通用的单调保持保证，而是一个条件一致性陈述。

4. 实验结果

作者在监督点云分类和无监督降维任务上评估了 Vrep 和 Vrepd，并将其与标准方法进行了比较：持久图像 (PI)、持久轮廓 (PS)、持久景观 (PL) 以及端到端网络 PointNet。

分类性能

数据集： 实验在多种数据集上进行，包括蛋白质结构、CAD 机械部件以及通过时间延迟嵌入转化为点云的时间序列数据。
结果： 在大多数对拓扑敏感的数据集上，Vrep 和 Vrepd 的分类准确率（使用随机森林分类器）始终高于或等于 PI、PS 和 PL。
- 在蛋白质数据集上，Vrep 达到了 98.5% 的准确率（PI 为 95.5%）。
- 在 CAD 数据集上，Vrep 和 Vrepd 在无监督方法中表现优异，尽管 PI 在某些噪声设置下也显示出竞争性结果。
码本敏感性： 持久性加权码本采样策略通常产生最佳结果，特别是在噪声环境中，因为它将表示重点放在了显著的拓扑特征上。

稳定性与可扩展性

扰动稳定性： 在一个 3D 动力系统数据集上的实验表明，Vrep 在高斯噪声扰动下是稳定的。有趣的是，Vrepd（带有对角线单元）表现出比 Vrep 更高的稳定性，这可能是由于它能更好地分离对角线附近的噪声。
时间复杂度：
- 对于规模为 $m$ 的数据集，Vrep 的时间复杂度为 $O(m^2tk)$ ，其中 $t$ 是码本数量， $k$ 是码本大小。其复杂度与数据集大小呈二次关系。
- 然而，Vrep 在实际运行时间上快于 PL 和 PS，并且随着采样 PD 数量 ( $n$ ) 的增加，其扩展性更好，因为它通过对 EPD 支持集进行子采样来固定大小，而 PI/PS/PL 必须单独处理每一个采样的 PD。
- 虽然 PointNet（监督学习）实现了高准确率，但 Vrep 为无监督任务（如降维）提供了一个极具竞争力的替代方案，而 PointNet 无法应用于此类任务。

无监督降维

在针对动力系统数据集的 t-SNE 可视化任务中，Vrep 生成的聚类具有更高的 Calinski-Harabasz (CH) 指数（1751），高于 PI（569）和 PL（1655），表明其具有更优越的聚类分离度。

5. 意义与主张

本文将 Vrep 定位为一种补充性表示，而非现有方法的普遍替代品。

自适应 vs. 平滑： 其主要贡献是从平滑的、基于核函数的函数近似转向了自适应的、数据依赖的计数。Vrep 通过由数据本身定义的单元来聚合质量，这使其可能比传统的平滑方法更忠实于经验质量分配。
权衡： 作者明确承认了这种权衡：Vrep 高效地总结了粗粒度的质量分配，但在 Voronoi 单元内的细粒度几何结构方面本质上是有损的。因此，当相关的拓扑变化涉及单元内的细微局部偏移或形状改变时，平滑方法（如 PI 或核方法）可能会优于 Vrep。
无监督效用： 该方法的一个关键意义在于其在无监督学习中的适用性。与监督学习方法（如 PointNet、PersLay）不同，Vrep 不需要标签来进行特征提取，这使其适用于降维和聚类等任务。
适度的声明： 作者并未声称 Vrep 在所有领域都优于现有向量化方法。他们指出，在特定数据集（如 CAD）上，核方法 (PWGK, SWK) 可能优于 Vrep，但其计算成本显著更高。论文结论认为，Vrep 是一个具有竞争力的、自适应的替代方案，它提供了有利于拓扑敏感分类的独特近似偏差，并具有良好的扩展性。