On the selection of the globally optimal prototype subset for nearest‐neighbor classification

On the selection of the globally optimal prototype subset for nearest‐neighbor classification

0.00 Avg rating0 Votes
Article ID: iaor200953696
Country: United States
Volume: 19
Issue: 3
Start Page Number: 470
End Page Number: 479
Publication Date: Jul 2007
Journal: INFORMS Journal On Computing
Authors: , , ,
Keywords: classification
Abstract:

The nearest–neighbor classifier has been shown to be a powerful tool for multiclass classification. We explore both theoretical properties and empirical behavior of a variant method, in which the nearest–neighbor rule is applied to a reduced set of prototypes. This set is selected a priori by fixing its cardinality and minimizing the empirical misclassification cost. In this way we alleviate the two serious drawbacks of the nearest–neighbor method: high storage requirements and time–consuming queries. Finding this reduced set is shown to be NP–hard. We provide mixed integer programming (MIP) formulations, which are theoretically compared and solved by a standard MIP solver for small problem instances. We show that the classifiers derived from these formulations are comparable to benchmark procedures. We solve large problem instances by a metaheuristic that yields good classification rules in reasonable time. Additional experiments indicate that prototype–based nearest‐neighbor classifiers remain quite stable in the presence of missing values.

Reviews

Required fields are marked *. Your email address will not be published.