Adaptive metric nearest neighbor classification

Carlotta Domeniconi, Jing Peng, Dimitrios Gunopulos

Research output: Contribution to journalConference articleResearchpeer-review

8 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 tend to be 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 a variety of simulated and real world data.

Original languageEnglish
Pages (from-to)517-522
Number of pages6
JournalProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
Volume1
StatePublished - 1 Jan 2000
EventCVPR '2000: IEEE Conference on Computer Vision and Pattern Recognition - Hilton Head Island, SC, USA
Duration: 13 Jun 200015 Jun 2000

Cite this

@article{d0734cdad836487691b1bc7439bbc7de,
title = "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 tend to be 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 a variety of simulated and real world data.",
author = "Carlotta Domeniconi and Jing Peng and Dimitrios Gunopulos",
year = "2000",
month = "1",
day = "1",
language = "English",
volume = "1",
pages = "517--522",
journal = "Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition",
issn = "1063-6919",
publisher = "IEEE Computer Society",

}

Adaptive metric nearest neighbor classification. / Domeniconi, Carlotta; Peng, Jing; Gunopulos, Dimitrios.

In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 1, 01.01.2000, p. 517-522.

Research output: Contribution to journalConference articleResearchpeer-review

TY - JOUR

T1 - Adaptive metric nearest neighbor classification

AU - Domeniconi, Carlotta

AU - Peng, Jing

AU - Gunopulos, Dimitrios

PY - 2000/1/1

Y1 - 2000/1/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 tend to be 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 a variety of 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 tend to be 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 a variety of simulated and real world data.

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

M3 - Conference article

VL - 1

SP - 517

EP - 522

JO - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

JF - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

SN - 1063-6919

ER -