📊 statistics

Prototype Selection Using Topological Data Analysis

本文介绍了两种基于拓扑数据分析的原型选择方法，即 TPS 和 BoundaryTPS，它们利用多尺度持久性结构来有效保留决策边界和类别比例，同时展现出优于现有经典基准方法的稳定性及独特的运行特性。

原作者： Jordan Eckert, Elvan Ceyhan, Henry Schenck

发布于 2026-06-02

📖 1 分钟阅读☕ 轻松阅读

原作者： Jordan Eckert, Elvan Ceyhan, Henry Schenck

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

想象一下你正在试图教一个机器人识别不同类型的水果。你有一个装有 10,000 个苹果、橙子和香蕉的大箱子。如果你向机器人展示每一件水果，它会花很长时间才能学会，而且它可能会被一些有瑕疵或形状奇怪的水果（噪声）搞糊涂。

原型选择（Prototype Selection） 的艺术在于从这个巨大的箱子中挑选出一小把完美的“代表性”水果。你的目标是让机器人既聪明又高效。

长期以来，科学家们都有不同的方法来挑选这把水果：

“清洁工”（The "Cleaner"）： 扔掉那些有瑕疵的水果。
“聚类者”（The "Clusterer"）： 从一组水果中挑选看起来最平均的水果。
“优化者”（The "Optimizer"）： 试图寻找数学上最完美的少数几个。

但这些方法都将水果视为空间中的点。它们并不真正理解问题的形状——具体来说，就是苹果在哪里结束、橙子从哪里开始的那个“决策边界”（decision boundary）。

新的想法：拓扑数据分析 (TDA)

这篇论文引入了两种新方法：TPS 和 BoundaryTPS，它们使用了被称为**拓扑数据分析（Topological Data Analysis, TDA）**的一个数学分支。

请不要把 TDA 看作是在观察单个水果，而是看作在观察整堆水果的形状。

如果你有一堆中间有个洞的水果（像甜甜圈一样的形状），TDA 能看到这个“环”或“洞”。
如果水果只是一个实心的团块，TDA 则看到一个“实心质量体”。

作者认为，学习过程中最重要的部分是边界——即一个类别转变为另一个类别的那个混乱、复杂的边缘。他们的新方法旨在专门保留这些边缘的形状。

两种新方法

1. BoundaryTPS（“边境守卫”）

工作原理： 想象你正在守卫两个国家之间的边界。你想留住那些住在边界线附近的人，因为他们最了解地形。你不太关心那些住在国家深处的人。
诀窍： 这种方法为每个数据点分配一个“权重”。靠近决策边界的点会获得“低权重”（它们会较早进入选择过程）。处于类别深处的点会获得“高权重”（它们会被延迟）。
结果： 它过滤数据，使得最终的一把原型紧密地围绕在决策边界周围，从而保留了边缘复杂的形状。

2. TPS（“两步侦察兵”）

工作原理： 这种方法采取了两步走的方法。
- 第一步： 它观察类别之间的边界（比如把苹果和橙子混合在一起），以找到这些“边缘”点。
- 第二步： 它观察第一步中幸存下来的点，并从中挑选出代表水果堆中心的“典型”点。
结果： 它为你提供了一个平衡的团队：既有处理复杂边缘的专家，也有处理典型、安全内部区域的专家。

他们发现了什么？

作者使用 15 个真实世界的数据集（如医疗记录、卫星图像和葡萄酒化学分析）将这些新方法与七种经典的旧方法进行了对比测试。结果如下：

形状保留（“地图”测试）：
- 如果你拿一张城市地图并移除大部分街道，你仍希望能够看到主要的环路和街区。
- BoundaryTPS 在保持原始数据的“环”和“洞”方面表现最好。它比测试过的任何其他方法都能更好地保留拓扑形状。
- TPS 紧随其后。
- 旧的方法经常会压平这些形状，从而丢失了数据的复杂结构。
稳定性（“重复性”测试）：
- 如果你稍微打乱数据（比如像重新洗牌一样），你会选出相同的原型吗？
- TPS 最为稳定。即使数据发生轻微变化，它每次选出的几乎都是同一组人。
- 许多旧方法具有“跳跃性”，仅仅因为数据被轻微打乱，就会选出完全不同的数据集。
性能（“测试成绩”测试）：
- 这些新方法让机器人变得更聪明了吗？
- 令人惊讶的是： 它们具有竞争力，但并不是绝对的赢家。旧的方法（如 K-Means 或 SPOTGreedy）通常会获得略高的测试分数。
- 然而，新方法在处理不平衡数据（即其中一类水果很稀有的情况）时表现得非常好。它们不会意外地丢弃那些稀有的水果。
速度：
- 两种新方法都很快。它们的扩展性很好，这意味着随着数据集变大，它们不会呈指数级变慢。

核心结论

这篇论文并不声称这些新方法总能给你最高的测试分数。相反，它声称它们提供了另一种价值：

它们更稳定（你每次都能得到相同的结果）。
它们更好地保留了数据的形状（边界）。
它们能自然地处理不平衡数据，而不需要特殊的技巧。

如果你需要一种可靠、能保留数据复杂几何结构、且不会被输入数据的微小变化所迷惑的数据集缩减方法，那么这些拓扑方法就是工具箱中一个强大的新工具。

技术摘要：基于拓扑数据分析的原型选择

问题陈述
现代分类流水线经常面临瓶颈，即训练集的规模而非单次预测的成本主导了推理时间。虽然参数化模型（如 SVM、随机森林）将负担转移到了训练时间，但它们仍然随训练实例的数量而缩放。原型选择通过将训练集压缩为一小部分具有代表性的子集来解决这一问题。现有的原型选择分类法——包括凝聚式（condensation）、编辑式（edition）、混合式（hybrid）、基于能力（competence-based）、基于优化（optimization-based）和基于聚类（clustering-based）家族——在运行时并未显式利用数据的拓扑结构。因此，类间决策边界的几何结构（这些边界可能在多个空间尺度上表现出复杂结构）仅被隐式地捕捉。本文旨在填补利用多尺度拓扑结构作为直接原型选择标准的空白。

方法论
作者引入了两种拓扑原型选择器（TPS）的变体，它们利用持续同调（persistent homology，拓扑数据分析的核心工具）来识别并保留原型。两种方法都依赖于 Rips 过滤（Rips filtration），但在编码边界信息的方式上有所不同：

边界感知拓扑原型选择器 (BoundaryTPS)：
- 机制： 这是一种单阶段方法，使用顶点加权的 Rips 过滤。它根据目标类点与非目标类的接近程度（具体为到 $k$ 个最近非目标邻居的距离之和）为目标类点分配权重。
- 过程： 靠近决策边界的点获得较低权重并较早进入过滤过程，而内部点获得较高权重并被延迟。这确保了边界区域的拓扑结构能在更精细的尺度上得到解析。
- 选择： 通过在指定的生命周期分布分位数处识别持久性特征来选择原型。容差参数 $\tau$ 允许在目标分位数周围选择一个特征窗口，以提高鲁棒性。
拓扑原型选择器 (TPS)：
- 机制： 这是一种两阶段方法，通过构建包含目标类和非目标类观测值的混合点云来隐式编码边界信息。
- 第一阶段（边界邻域）： 在混合点云上构建标准的 Rips 过滤，以捕捉类间拓扑结构。特征基于生命周期的分位数进行选择，并保留存活的目标类点。
- 第二阶段（内部）： 在第一阶段的存活点上构建第二次 Rips 过滤，以捕捉类内拓扑结构。特征基于平均生命周期进行选择，以保留典型的内部样本。
- 结果： 最终集合结合了来自第一阶段的边界相关点和来自第二阶段的内部支撑点。

核心贡献

新颖准则： 本文引入了将持续同调作为原型选择准则的方法，这是此前在该领域未被利用的能力。
双重实现： 文中展示了 TPS 和 BoundaryTPS，证明了通过混合类过滤（TPS）与顶点权重（BoundaryTPS）来编码边界信息会导致经验上的不同专业化表现。
全面基准测试： 通过嵌套交叉验证，在 15 个真实世界数据集和 6 个下游分类器上，将两种方法与七种经典基准模型（CNN、CNN+ENN、DROP3、ICF、IB3、KMeans、SPOTGreedy）进行了评估。
拓扑保持： 研究表明，拓扑方法在保持 $H_1$ 持久图结构方面显著优于基于密度或链式决策的基准方法。
稳定性： 与任何测试的链式决策选择器相比，这两种方法都表现出更高的选择稳定性（通过折叠间 Jaccard 相似度衡量）。
类别不平衡： 这些方法在不需要标签感知机制的情况下，继承了源集的类别比例。

结果

拓扑保真度： 在 $H_1$ Wasserstein-1 距离上，BoundaryTPS 实现了最低的平均 Friedman 秩（2.00），显著优于七个基准中的五个。TPS 的排名第三（3.60）。两种方法在保持环结构（ $H_1$ ）方面都聚集在性能谱顶端，而经典方法往往会使这些特征平坦化。
选择稳定性： TPS 在各折叠间的平均 Jaccard 相似度最高（0.225），其次是 BoundaryTPS（0.202）。两者都明显比 CNN+ENN（0.057）和 DROP3（0.080）等链式决策方法更稳定。
分类性能： 在总体几何平均值（G-Mean）方面，拓扑方法具有竞争力但并非领先。SPOTGreedy 和 KMeans 实现了最高的总体 G-Mean（0.84）。TPS 和 BoundaryTPS 分别达到 0.79 和 0.76。论文指出，虽然它们在原始分类准确率方面并不占优势，但它们在设计空间中提供了一个独特的运行点，特别是在结构保持和稳定性方面。
可扩展性： 从经验上看，两种方法在样本量上的扩展速度均为亚二次方级。

意义与主张
本文声称，其主要意义在于将原型选择的范式从纯粹的几何或统计启发式方法转向基于多尺度拓扑不变性的框架。作者认为，虽然现有方法隐式地假设了边界接近原则，但它们未能解析决策边界复杂的、多尺度的结构。通过显式利用持续同调，所提出的方法提供了一种原则性的方式，用以保留定义数据“形状”的点，特别是那些在基于密度的约减过程中经常丢失的环和边界。

作者对结果进行了谦逊的定性：拓扑方法并不普遍优于现有基准模型的下游分类准确率（G-Mean），但它们通过提供卓越的拓扑保持能力和选择稳定性，占据了设计空间中一个独特且有价值的区域。这项工作表明，对于决策边界的结构完整性或选择过程的可复现性至关重要的应用场景，拓扑准则提供了一种不同于且有效的替代方案。