A Proposal for Local $k$ Values for $k$ -Nearest Neighbor Rule

Area of Science:

• Machine Learning
• Computer Science
• Pattern Recognition

Background:

• The k-nearest neighbor (k-NN) classifier is a widely used, simple yet effective classification method.
• A key challenge in k-NN is selecting an optimal, fixed value for k (number of neighbors) across the entire feature space.
• Different regions of the feature space may require different k values due to varying data distributions and class boundaries.

Purpose of the Study:

• To propose a novel, simple, and powerful approach for determining a local value of k for the k-NN classifier.
• To address the limitation of a single, globally optimal k value in k-NN classification.
• To improve the performance of k-NN, especially in scenarios with varying data distributions and class imbalances.

Main Methods:

• Developed a method to associate a potentially different k value with each prototype (training instance).
• Optimized the local k value by considering both local and global effects within the neighborhood of each prototype.
• The training stage is fast, and the testing stage complexity remains comparable to the standard k-NN algorithm.

Main Results:

• The proposed method significantly outperforms the standard k-NN rule across a diverse range of problems.
• Demonstrated superior performance on both standard and class-imbalanced datasets.
• The local adjustment of k accounts for varying data densities and class separability.

Conclusions:

• The presented approach offers a significant improvement over the standard k-NN classifier by adapting k locally.
• This method provides a robust solution for optimizing k-NN performance in diverse and challenging classification tasks.
• The approach is computationally efficient, maintaining practical applicability for large datasets.