Locally adaptive metric nearest-neighbor classification

Carlotta Domeniconi, Jing Peng, Dimitrios Gunopulos

Research output: Contribution to journalArticleResearchpeer-review

229 Citations (Scopus)

Abstract

Nearest-neighbor classification assumes locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with finite samples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest-neighbor rule. We propose a locally adaptive nearest-neighbor classification method to try to minimize bias. We use a Chi-squared distance analysis to compute a flexible metric for producing neighborhoods that are highly adaptive to query locations. Neighborhoods are elongated along less relevant feature dimensions and constricted along most influential ones. As a result, the class conditional probabilities are smoother in the modified neighborhoods, whereby better classification performance can be achieved. The efficacy of our method is validated and compared against other techniques using both simulated and real-world data.

Original languageEnglish
Pages (from-to)1281-1285
Number of pages5
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume24
Issue number9
DOIs
StatePublished - 1 Sep 2002

Keywords

  • Chi-squared distance
  • Classification
  • Feature relevance
  • Nearest neighbors

Cite this

Domeniconi, Carlotta ; Peng, Jing ; Gunopulos, Dimitrios. / Locally adaptive metric nearest-neighbor classification. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002 ; Vol. 24, No. 9. pp. 1281-1285.
@article{56dc3e37160a4f70b2e5ef357e4262a5,
title = "Locally adaptive metric nearest-neighbor classification",
abstract = "Nearest-neighbor classification assumes locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with finite samples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest-neighbor rule. We propose a locally adaptive nearest-neighbor classification method to try to minimize bias. We use a Chi-squared distance analysis to compute a flexible metric for producing neighborhoods that are highly adaptive to query locations. Neighborhoods are elongated along less relevant feature dimensions and constricted along most influential ones. As a result, the class conditional probabilities are smoother in the modified neighborhoods, whereby better classification performance can be achieved. The efficacy of our method is validated and compared against other techniques using both simulated and real-world data.",
keywords = "Chi-squared distance, Classification, Feature relevance, Nearest neighbors",
author = "Carlotta Domeniconi and Jing Peng and Dimitrios Gunopulos",
year = "2002",
month = "9",
day = "1",
doi = "10.1109/TPAMI.2002.1033219",
language = "English",
volume = "24",
pages = "1281--1285",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
issn = "0162-8828",
publisher = "IEEE Computer Society",
number = "9",

}

Locally adaptive metric nearest-neighbor classification. / Domeniconi, Carlotta; Peng, Jing; Gunopulos, Dimitrios.

In: IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 9, 01.09.2002, p. 1281-1285.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Locally adaptive metric nearest-neighbor classification

AU - Domeniconi, Carlotta

AU - Peng, Jing

AU - Gunopulos, Dimitrios

PY - 2002/9/1

Y1 - 2002/9/1

N2 - Nearest-neighbor classification assumes locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with finite samples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest-neighbor rule. We propose a locally adaptive nearest-neighbor classification method to try to minimize bias. We use a Chi-squared distance analysis to compute a flexible metric for producing neighborhoods that are highly adaptive to query locations. Neighborhoods are elongated along less relevant feature dimensions and constricted along most influential ones. As a result, the class conditional probabilities are smoother in the modified neighborhoods, whereby better classification performance can be achieved. The efficacy of our method is validated and compared against other techniques using both simulated and real-world data.

AB - Nearest-neighbor classification assumes locally constant class conditional probabilities. This assumption becomes invalid in high dimensions with finite samples due to the curse of dimensionality. Severe bias can be introduced under these conditions when using the nearest-neighbor rule. We propose a locally adaptive nearest-neighbor classification method to try to minimize bias. We use a Chi-squared distance analysis to compute a flexible metric for producing neighborhoods that are highly adaptive to query locations. Neighborhoods are elongated along less relevant feature dimensions and constricted along most influential ones. As a result, the class conditional probabilities are smoother in the modified neighborhoods, whereby better classification performance can be achieved. The efficacy of our method is validated and compared against other techniques using both simulated and real-world data.

KW - Chi-squared distance

KW - Classification

KW - Feature relevance

KW - Nearest neighbors

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

U2 - 10.1109/TPAMI.2002.1033219

DO - 10.1109/TPAMI.2002.1033219

M3 - Article

VL - 24

SP - 1281

EP - 1285

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

SN - 0162-8828

IS - 9

ER -