📊 statistics

Prototype Selection Using Topological Data Analysis

This paper introduces two topological data analysis-based prototype selection methods, TPS and BoundaryTPS, which leverage multi-scale persistence structures to effectively preserve decision boundaries and class proportions while demonstrating superior stability and distinct operating characteristics compared to existing classical baselines.

Original authors: Jordan Eckert, Elvan Ceyhan, Henry Schenck

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jordan Eckert, Elvan Ceyhan, Henry Schenck

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize different types of fruit. You have a massive box of 10,000 apples, oranges, and bananas. If you show the robot every single piece of fruit, it will take forever to learn, and it might get confused by a few bruised or weirdly shaped ones (noise).

Prototype Selection is the art of picking a small, perfect "representative" handful of fruit from that giant box to teach the robot. The goal is to keep the robot smart but make it fast.

For a long time, scientists have had different ways to pick this handful:

The "Cleaner": Throws away the bruised fruit.
The "Clusterer": Picks the average-looking fruit from a group.
The "Optimizer": Tries to find the mathematically perfect few.

But all these methods look at the fruit as just points in space. They don't really understand the shape of the problem—specifically, where the apples end and the oranges begin (the "decision boundary").

The New Idea: Topological Data Analysis (TDA)

This paper introduces two new methods, TPS and BoundaryTPS, that use a branch of math called Topological Data Analysis.

Think of TDA not as looking at individual fruits, but as looking at the shape of the whole pile.

If you have a pile of fruit with a hole in the middle (like a donut shape), TDA sees the "loop" or the "hole."
If the fruit is just a solid blob, TDA sees a "solid mass."

The authors argue that the most important part of learning is the boundary—the messy, complex edge where one class of fruit turns into another. Their new methods are designed to specifically preserve the shape of these edges.

The Two New Methods

1. BoundaryTPS (The "Border Guard")

How it works: Imagine you are guarding a border between two countries. You want to keep the people living right on the border line because they know the terrain best. You don't care as much about the people living deep in the middle of the country.
The Trick: This method assigns a "weight" to every data point. Points near the decision boundary get a "low weight" (they enter the selection process early). Points deep inside a class get a "high weight" (they are delayed).
The Result: It filters the data so that the final handful of prototypes is packed tightly around the decision boundaries, preserving the complex shape of the edge.

2. TPS (The "Two-Step Scout")

How it works: This method takes a two-step approach.
- Step 1: It looks at the boundary between classes (like mixing apples and oranges together) to find the "edge" points.
- Step 2: It looks at the survivors from Step 1 and picks out the "typical" points that represent the middle of the fruit piles.
The Result: It gives you a balanced team: some experts on the messy edges, and some experts on the typical, safe interior.

What Did They Find?

The authors tested these new methods against seven old, classic methods using 15 real-world datasets (like medical records, satellite images, and wine chemical analysis). Here is what happened:

Shape Preservation (The "Map" Test):
- If you take a map of a city and remove most of the streets, you want to make sure you can still see the major loops and neighborhoods.
- BoundaryTPS was the best at keeping the "loops" and "holes" of the original data intact. It preserved the topological shape better than any other method tested.
- TPS was a close second.
- The old methods often flattened these shapes, losing the complex structure of the data.
Stability (The "Repeatability" Test):
- If you shuffle the data slightly (like dealing a deck of cards differently), will you pick the same handful of prototypes?
- TPS was the most stable. It picked almost the same people every time, even when the data changed slightly.
- Many of the old methods were "jumpy," picking totally different sets of people just because the data was shuffled a tiny bit.
Performance (The "Test Score" Test):
- Did these new methods make the robot smarter?
- Surprise: They were competitive, but not the absolute winners. The old methods (like K-Means or SPOTGreedy) often got slightly higher test scores.
- However, the new methods were very good at handling imbalanced data (where one class of fruit is rare). They didn't accidentally throw away the rare fruits.
Speed:
- Both new methods are fast. They scale well, meaning they don't get exponentially slower as the dataset gets bigger.

The Bottom Line

This paper doesn't claim that these new methods will always give you the highest test score. Instead, it claims they offer a different kind of value:

They are more stable (you get the same result every time).
They are better at preserving the shape of the data's boundaries.
They naturally handle imbalanced data without needing special tricks.

If you need a dataset reduction method that is reliable, preserves the complex geometry of your data, and doesn't get confused by small changes in the input, these topological methods are a powerful new tool in the toolbox.

Technical Summary: Prototype Selection Using Topological Data Analysis

Problem Statement
Modern classification pipelines often face bottlenecks where the size of the training set, rather than the cost of a single prediction, dominates inference time. While parametric models (e.g., SVMs, Random Forests) shift the burden to training time, they still scale with the number of training instances. Prototype selection addresses this by compressing the training set into a small, representative subset. Existing taxonomies of prototype selection—including condensation, edition, hybrid, competence-based, optimization-based, and clustering-based families—operate without an explicit representation of the data's topological structure. Consequently, the geometry of between-class decision boundaries, which may exhibit complex structure across multiple spatial scales, is captured only implicitly. This paper addresses the gap in utilizing the multi-scale topological structure of data as a direct criterion for prototype selection.

Methodology
The authors introduce two variants of a Topological Prototype Selector (TPS) that utilize persistent homology, a core tool in Topological Data Analysis (TDA), to identify and retain prototypes. Both methods rely on the Rips filtration but differ in how they encode boundary information:

Boundary-Conscious Topological Prototype Selector (BoundaryTPS):
- Mechanism: This is a single-stage method that uses a vertex-weighted Rips filtration. It assigns weights to target-class points based on their proximity to non-target classes (specifically, the sum of distances to $k$ nearest non-target neighbors).
- Process: Points near the decision boundary receive low weights and enter the filtration early, while interior points receive high weights and are delayed. This ensures that boundary-region topology is resolved at finer scales.
- Selection: Prototypes are selected by identifying persistence features at a specified quantile of the lifetime distribution. A tolerance parameter $\tau$ allows for the selection of a window of features around the target quantile to improve robustness.
Topological Prototype Selector (TPS):
- Mechanism: This is a two-stage method that encodes boundary information implicitly by constructing a mixed point cloud containing both target and non-target observations.
- Stage 1 (Boundary-Neighborhood): A standard Rips filtration is built on the mixed cloud to capture between-class topological structure. Features are selected based on a quantile of the lifetime distribution, and the surviving target-class points are retained.
- Stage 2 (Interior): A second Rips filtration is built on the survivors from Stage 1 to capture within-class topology. Features are selected based on the mean lifetime to retain interior-typical samples.
- Outcome: The final set combines boundary-relevant points from Stage 1 with interior-support points from Stage 2.

Key Contributions

Novel Criterion: The paper introduces persistent homology as a prototype-selection criterion, a capability not previously utilized in this domain.
Dual Realizations: It presents TPS and BoundaryTPS, demonstrating that encoding boundary information via mixed-class filtrations (TPS) versus vertex weights (BoundaryTPS) leads to empirically different specializations.
Comprehensive Benchmarking: Both methods are evaluated against seven classical baselines (CNN, CNN+ENN, DROP3, ICF, IB3, KMeans, SPOTGreedy) across fifteen real-world datasets and six downstream classifiers under nested cross-validation.
Topological Preservation: The study demonstrates that topological methods preserve the $H_1$ persistence-diagram structure significantly better than density-based or chained-decision baselines.
Stability: Both methods exhibit higher selection stability (measured by fold-to-fold Jaccard similarity) than any chained-decision selector tested.
Class Imbalance: The methods inherit the source set's class proportions without requiring label-aware machinery.

Results

Topological Fidelity: BoundaryTPS achieves the lowest mean Friedman rank (2.00) on $H_1$ Wasserstein-1 distance, significantly outperforming five of the seven baselines. TPS ranks third (3.60). Both methods cluster at the top of the performance spectrum for preserving loop structures ( $H_1$ ), whereas classical methods often flatten these features.
Selection Stability: TPS achieves the highest mean Jaccard similarity (0.225) across folds, followed by BoundaryTPS (0.202). Both are significantly more stable than chained-decision methods like CNN+ENN (0.057) and DROP3 (0.080).
Classification Performance: On aggregate Geometric Mean (G-Mean), the topological methods are competitive but not leading. SPOTGreedy and KMeans achieve the highest aggregate G-Mean (0.84). TPS and BoundaryTPS achieve 0.79 and 0.76, respectively. The paper notes that while they do not dominate raw classification accuracy, they offer a distinct operating point in the design space, particularly regarding structural preservation and stability.
Scalability: Empirically, both methods scale sub-quadratically in sample size.

Significance and Claims
The paper claims that the primary significance of this work lies in shifting the paradigm of prototype selection from purely geometric or statistical heuristics to a framework grounded in multi-scale topological invariants. The authors argue that while existing methods implicitly assume a boundary-proximity principle, they fail to resolve the complex, multi-scale structure of decision boundaries. By explicitly utilizing persistent homology, the proposed methods offer a principled way to retain points that define the topological "shape" of the data, particularly the loops and boundaries that are often lost in density-based reduction.

The authors modestly characterize the results: the topological methods do not universally outperform existing baselines in downstream classification accuracy (G-Mean), but they occupy a unique and valuable region of the design space by offering superior topological preservation and selection stability. The work suggests that for applications where the structural integrity of the decision boundary or the reproducibility of the selection process is paramount, topological criteria provide a distinct and effective alternative to classical approaches.