Large margin nearest neighbor classifiers

Carlotta Domeniconi, Dimitrios Gunopulos, Jing Peng

Research output: Contribution to journalArticleResearchpeer-review

74 Citations (Scopus)

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

Fingerprint

Classifiers
Support vector machines
Computational efficiency
Support Vector Machine
Direction compound

Keywords

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

Cite this

Domeniconi, Carlotta ; Gunopulos, Dimitrios ; Peng, Jing. / Large margin nearest neighbor classifiers. In: IEEE Transactions on Neural Networks. 2005 ; Vol. 16, No. 4. pp. 899-909.
@article{d502b322ebba4bd5bff94a3c3d9c4ccf,
title = "Large margin nearest neighbor classifiers",
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.",
keywords = "Feature relevance, Margin, Nearest neighbor classification, Support vector machines (SVMs)",
author = "Carlotta Domeniconi and Dimitrios Gunopulos and Jing Peng",
year = "2005",
month = "7",
day = "1",
doi = "10.1109/TNN.2005.849821",
language = "English",
volume = "16",
pages = "899--909",
journal = "IEEE Transactions on Neural Networks",
issn = "1045-9227",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

Large margin nearest neighbor classifiers. / Domeniconi, Carlotta; Gunopulos, Dimitrios; Peng, Jing.

In: IEEE Transactions on Neural Networks, Vol. 16, No. 4, 01.07.2005, p. 899-909.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Large margin nearest neighbor classifiers

AU - Domeniconi, Carlotta

AU - Gunopulos, Dimitrios

AU - Peng, Jing

PY - 2005/7/1

Y1 - 2005/7/1

N2 - 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.

AB - 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.

KW - Feature relevance

KW - Margin

KW - Nearest neighbor classification

KW - Support vector machines (SVMs)

UR - http://www.scopus.com/inward/record.url?scp=23044490834&partnerID=8YFLogxK

U2 - 10.1109/TNN.2005.849821

DO - 10.1109/TNN.2005.849821

M3 - Article

VL - 16

SP - 899

EP - 909

JO - IEEE Transactions on Neural Networks

JF - IEEE Transactions on Neural Networks

SN - 1045-9227

IS - 4

ER -