Prototype Selection using Topological Data Analysis

Thomas M. Menino Convention & Exhibition Center 

Prototype selection methods compress a training set, but the existing taxonomy of condensation, edition, hybrid, competence-based, optimization-based, and clustering-based families does not include methods that operate on the multi-scale topological structure of the data. In this talk I will present three new prototype selection methods based on tools from topological data analysis (TDA) that serve as a potential foundation for a new taxonomy of topological-based selection methods. These methods are either persistence-based such as the Topological Prototype Selector (TPS) and Boundary-Conscious Topological Prototype Selector (BoundaryTPS) or graph-based with the Mapper Prototype Selector (MPS). TPS uses two sequential Rips filtrations to retain boundary-relevant and interior-typical points. BoundaryTPS is a single-stage variant whose vertex-weighted filtration concentrates retention near the decision boundary. MPS uses the Mapper graph to generate synthetic observations. We evaluate all methods against seven classical prototype selection baselines across fifteen real datasets. Our analysis shows that the persistence-based topological methods occupy a different operating point in the prototype-selection design space than existing methods. BoundaryTPS achieves the lowest mean Friedman rank on H1 persistence-diagram preservation and is significantly better than five of the seven baselines (Nemenyi, α = 0.05). TPS ranks third on the same endpoint. Both methods are more stable under fold perturbation than any chained-decision selector tested, and both inherit the source set's class proportions without label-aware machinery. Graph-based methods in contrast perform much better on downstream classification tasks and are among the top ranked against other methods. Empirically, all methods scale at worst sub-quadratically in sample size.

Prototype Selection

Instance Selection

Prototype Generation

Mapper Algorithm

Topological Data Analysis

Persistent Homology 

IMS