A reduction technique for nearest-neighbor classification: Small groups of examples

Article type: Research Article

Authors: Kubat, Miroslav^a | Cooperson Jr., Martin^b

Affiliations: [a] Department of Electrical and Computer Engineering, University of Miami, Coral Gables, FL 33146, USA | [b] Center for Advanced Computer Studies, University of Louisiana at Lafayette, Lafayette, LA 70504-4330, USA

Abstract: An important issue in nearest-neighbor classifiers is how to reduce the size of large sets of examples. Whereas many researchers recommend to replace the original set with a carefully selected subset, we investigate a mechanism that creates three or more such subsets. The idea is to make sure that each of them, when used as a 1-NN subclassifier, tends to err in a different part of the instance space. In this case, failures of individuals can be corrected by voting. The costs of our example-selection procedure are linear in the size of the original training set and, as our experiments demonstrate, dramatic data reduction can be achieved without a major drop in classification accuracy.

Keywords: nearest-neighbor classifiers, example selection, voting

DOI: 10.3233/IDA-2001-5603

Journal: Intelligent Data Analysis, vol. 5, no. 6, pp. 463-476, 2001