Voting Nearest-Neighbor Subclassifiers

Abstract

Realistic applications of nearest-neighbor classiers suer from capacity-related problems. The size of today's data warehouses renders loading the entire data into the main memory impossible. Moreover, comparing each object with millions of stored examples can be prohibitively expensive. Some researchers have therefore developed methods that replace large sets of examples with their representative subsets. In this paper, we suggest an approach that selects three very small groups of examples such that, when used as 1-NN subclassiers, each tends to err in a dierent part of the instance space. Simple voting then corrects many failures of individual subclassiers. Experiments show that the classication accuracy need not be impaired even after drastic reduction. Computational costs associated with the techique are linear in the size of the original training set. 1. Introduction Suppose an object x is to be classied. Given a similarity metric, and a database of pre...