Reducing Nearest Neighbor Training Sets Optimally And Exactly

Abstract

In nearest-neighbor classification, a training set \(P\) of points in \(\mathbb\{R\}^d\) with given classification is used to classify every point in \(\mathbb\{R\}^d\): Every point gets the same classification as its nearest neighbor in \(P\). Recently, Eppstein [SOSA'22] developed an algorithm to detect the relevant training points, those points \(p\in P\), such that \(P\) and \(P\setminus\\{p\\}\) induce different classifications. We investigate the problem of finding the minimum cardinality reduced training set \(P'\subseteq P\) such that \(P\) and \(P'\) induce the same classification. We show that the set of relevant points is such a minimum cardinality reduced training set if \(P\) is in general position. Furthermore, we show that finding a minimum cardinality reduced training set for possibly degenerate \(P\) is in P for \(d=1\), and NP-complete for \(d\geq 2\).

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyrohrer2023reducing

Related papers

• Finding Relevant Points For Nearest-neighbor Classification (2021)4.52
• Social Distancing Is Good For Points Too! (2020)0.00
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Sublinear Data Structures For Nearest Neighbor In Ultra High Dimensions (2025)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00
• Learning Space Partitions For Nearest Neighbor Search (2019)0.00