Simultaneous Selection of Features and Metric for Optimal Nearest Neighbor Classification

Abstract

Given a set of observations in ℝ ⁿ along with provided class labels, 𝒞, one is often interested in building a classifier that is a mapping from ℝ ⁿ  → 𝒞. One way to do this is using a simple nearest neighbor classifier. Inherent in the use of this classifier is a metric or pseudo-metric that measures the distance between the observations. One typically uses the L ₂ metric. We examine the classification benefits of the use of alternative Minkowski p-metrics. We also study the relationship between the selection of the p-metric and the selection of optimal classification features. We compare a simple greedy approach of Minkowski p-metric optimization followed by feature selection, the greedy method, with a simultaneous optimization of the p-metric and feature selection process. We utilize a stochastic optimization methodology to perform the simultaneous optimization.

Key Words:

• Minkowski p-metric
• Simultaneous optimization
• Cross-validated classifier
• Greedy algorithm

Mathematics Subject Classification:

• Primary 62H30
• Secondary 62-07

Acknowledgments

The research of Mr. Johannsen and Dr. Solka was supported by Dr. Wendy Martinez at the Office of Naval Research. The research of Dr. Wegman was supported by the Defense Advanced Research Projects Agency under Agreement 8905-48174 with The Johns Hopkins University.

Notes

Dedicated to Professor Z. Govindarajulu on the occasion of his 70th birthday.