Reducing Nearest Neighbor Training Sets Optimally and Exactly

2023/02/04 by Josiah Rohrer, Rohrer, Josiah, Simon Weber +1
Computer Science · #Machine Learning and Algorithms #Machine Learning and Data Classification #Image and Object Detection Techniques

paper · pdf · doi:10.48550/arxiv.2302.02132

Abstract

In nearest-neighbor classification, a training set P of points in ℝ^d with given classification is used to classify every point in ℝ^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∈ P, such that P and P∖\p\ induce different classifications. We investigate the problem of finding the minimum cardinality reduced training set P'⊆ 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≥ 2.

Related

• Improved Search of Relevant Points for Nearest-Neighbor Classification
• Finding Relevant Points for Nearest-Neighbor Classification
• Coresets for the Nearest-Neighbor Rule
• Discriminative Learning of the Prototype Set for Nearest Neighbor Classification
• An adaptive nearest neighbor rule for classification