Reference set thinning for the k-nearest neighbor decision rule

The k-nearest neighbor decision rule (or k-NNR) is used to classify a point in d-space according to the dominant class among its k nearest neighbors in some reference set (in which each point has a known class). It is useful to find a small subset S´ of S that can be used as the reference set instead. If the k-NNR always makes the same decision using either S or S´ as the reference set, then S´ is called an exact thinning of S for the k-NNR. We show that such an exact thinning can be determined easily from the k-Delaunay graph of S (which is dual to the order-k Voronoi diagram of S). This graph “encodes” a particular subset of S that must be included within any exact thinning for the k-NNR, and it also provides information on how this subset can be augmented into an exact thinning (although perhaps not a minimum one). In addition, we investigate how the k-Gabriel graph (which is a subgraph of the k-Delaunay graph) can be used to derive an inexact thinning of S that performs well in practice for the k-NNR. It is advantageous to use the k-Gabriel graph instead of the k-Delaunay graph, because the k-Gabriel graph is smaller and much easier to compute from the point set S