The k conditional nearest neighbor algorithm for classification and class probability estimation

Area of Science:

• Machine Learning
• Statistical Classification

Background:

• The k-nearest neighbors (kNN) algorithm is a widely used nonparametric method for classification.
• A key limitation of kNN is its coarse estimation of class probabilities, especially with small k values.

Purpose of the Study:

• To introduce a novel nonparametric classification method addressing the probability estimation limitations of kNN.
• To enhance classification accuracy and probability estimation in machine learning.

Main Methods:

• Proposing a new method using distances to the k-th nearest neighbor conditional on each class.
• Estimating posterior probabilities based on these distances and assigning instances to the class with the highest probability.
• Developing an ensemble version of the proposed method.

Main Results:

• The proposed method and its ensemble version demonstrate superior performance over kNN, weighted kNN, and probabilistic kNN on benchmark datasets.
• Convergence to the Bayes classifier is proven as training data size increases.
• The method shows potential for estimating posterior probabilities in overlapping class distributions.

Conclusions:

• The novel class-conditional nearest neighbor approach offers improved classification accuracy and probability estimation.
• The ensemble extension further enhances performance, providing a robust alternative to existing methods.
• This method is particularly valuable for datasets with overlapping class distributions.