Large margin nearest neighbor classifiers

Carlotta Domeniconi, Dimitrios Gunopulos, Jing Peng

Research output: Contribution to journalArticle

75 Scopus citations

Abstract

The nearest neighbor technique is a simple and appealing approach to addressing classification problems. It relies on the assumption of locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with a finite number of examples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest neighbor rule. The employment of a locally adaptive metric becomes crucial in order to keep class conditional probabilities close to uniform, thereby minimizing the bias of estimates. We propose a technique that computes a locally flexible metric by means of support vector machines (SVMs). The decision function constructed by SVMs is used to determine the most discriminant direction in a neighborhood around the query. Such a direction provides a local feature weighting scheme. We formally show that our method increases the margin in the weighted space where classification takes place. Moreover, our method has the important advantage of online computational efficiency over competing locally adaptive techniques for nearest neighbor classification. We demonstrate the efficacy of our method using both real and simulated data.

Original languageEnglish
Pages (from-to)899-909
Number of pages11
JournalIEEE Transactions on Neural Networks
Volume16
Issue number4
DOIs
StatePublished - 1 Jul 2005

Keywords

  • Feature relevance
  • Margin
  • Nearest neighbor classification
  • Support vector machines (SVMs)

Fingerprint Dive into the research topics of 'Large margin nearest neighbor classifiers'. Together they form a unique fingerprint.

  • Cite this