Coresets for the Nearest-Neighbor Rule
Given a training set $P$ of labeled points, the nearest-neighbor rule predicts the class of an unlabeled query point as the label of its closest point in the set. To improve the time and space complexity of classification, a natural question is how to reduce the training set without significantly affecting the accuracy of the nearest-neighbor rule. Nearest-neighbor condensation deals with finding a subset $R \subseteq P$ such that for every point $p \in P$, $p$'s nearest-neighbor in $R$ has the same label as $p$. This relates to the concept of coresets, which can be broadly defined as subsets of the set, such that an exact result on the coreset corresponds to an approximate result on the original set. However, the guarantees of a coreset hold for any query point, and not only for the points of the training set. This paper introduces the concept of coresets for nearest-neighbor classification. We extend existing criteria used for condensation, and prove sufficient conditions to correctly classify any query point when using these subsets. Additionally, we prove that finding such subsets of minimum cardinality is NP-hard, and propose quadratic-time approximation algorithms with provable upper-bounds on the size of their selected subsets. Moreover, we show how to improve one of these algorithms to have subquadratic runtime, being the first of this kind for condensation.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Discriminative Learning of the Prototype Set for Nearest Neighbor Classification
The nearest neighbor rule is a classic yet essential classification model, particularly in problems where the supervising information is given by pairwise dissimilarities and the embedding function are not easily obtaine…
ClassificationGeneral ClassificationPrototype SelectionAn upper bound on prototype set size for condensed nearest neighbor
The condensed nearest neighbor (CNN) algorithm is a heuristic for reducing the number of prototypical points stored by a nearest neighbor classifier, while keeping the classification rule given by the reduced prototypica…
General ClassificationConvergence of Nearest Neighbor Pattern Classification with Selective Sampling
In the panoply of pattern classification techniques, few enjoy the intuitive appeal and simplicity of the nearest neighbor rule: given a set of samples in some metric domain space whose value under some function is known…
ClassificationGeneral ClassificationClassification with the nearest neighbor rule in general finite dimensional spaces: necessary and sufficient conditions
Given an $n$-sample of random vectors $(X_i,Y_i)_{1 \leq i \leq n}$ whose joint law is unknown, the long-standing problem of supervised classification aims to \textit{optimally} predict the label $Y$ of a given a new obs…
General ClassificationA Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces
The property of almost every point being a Lebesgue point has proven to be crucial for the consistency of several classification algorithms based on nearest neighbors. We characterize Lebesgue points in terms of a 1-Near…
ClassificationGeneral Classificationregression