---
title: "An Average-Case Analysis of the k-Nearest Neighbar Classifier for Noisy Domains"
authors:
  - "Seishi Okamoto"
  - "Nobuhiro Yugami"
doi: ""
url: "https://ijcai.org/proceedings/1997/36"
pdf: "https://ijcai.org/proceedings/1997/0036.pdf"
venue: "Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence"
year: 1997
pages: "238-244"
track: "Case-based Reasoning"
keywords:
---

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

Seishi Okamoto, Nobuhiro Yugami

*Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence*, 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.