An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains

Okamoto, Seishi; Yugami, Nobuhiro

An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains

Download BibTeX Cite

Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Case-based Reasoning. Pages 238-244.

Abstract

This paper presents an average-case analysis of the k-nearest neighbor classifier(k-NN). Our analysis deals with m-of-n/l concepts, and handles three types of noise: relevant attribute noise, irrelevant attribute noise, and class noise. We formally compute the expected classification accuracy of k-NN after a certain fixed number of training instances. This accuracy is represented as a function of the domain characteristics. Then, the predicted behavior of k-NN for each type of noise is explored by using the accuracy function. We examine the classification accuracy of k-NN at various noise levels, and show how noise affects the accuracy of kNN. We also show the relationship between the optimal value of k and the number of training instances in noisy domains. Our analysis is supported with Monte Carlo simulations.

Seishi Okamoto, and Nobuhiro Yugami. 1997. An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97. IJCAI, 238–244. https://ijcai.org/proceedings/1997/36

@inproceedings{ijcai1997p36,
  title     = {An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains},
  author    = {Okamoto, Seishi and Yugami, Nobuhiro},
  booktitle = {Proceedings of the Fifteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-97}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Martha E. Pollack},
  pages     = {238--244},
  year      = {1997},
  note      = {Case-based Reasoning},
  url       = {https://ijcai.org/proceedings/1997/36},
}

TY  - CPAPER
TI  - An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains
AU  - Okamoto, Seishi
AU  - Yugami, Nobuhiro
T2  - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1997
SP  - 238
EP  - 244
UR  - https://ijcai.org/proceedings/1997/36
ER  -