Reducing Nearest Neighbor Training Sets Optimally and Exactly
share
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.
READ FULL TEXT