A stochastic approach to k-nearest neighbors search using a fixed radius method.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• k-nearest neighbors (kNN) search is computationally intensive, especially with large datasets.
• Existing methods often rely on rule-based systems, lacking data-driven stochastic approaches.
• Optimizing kNN search is crucial for efficient machine learning model performance.

Purpose of the Study:

• To develop a stochastic method for optimizing kNN search.
• To reduce the computational burden of the brute-force kNN search.
• To enhance the scalability of kNN search for large datasets while maintaining accuracy.

Main Methods:

• Leveraging data structures and probabilistic assumptions to define a limited sample space for kNN search.
• Employing a fixed radius search for query observations, stochastically linked to the desired number of neighbors.
• Utilizing a fraction of the training set instead of the entire dataset for neighbor identification.

Main Results:

• The stochastic method significantly outperforms the brute-force approach, especially for large training and query sets.
• Demonstrated a 27.57-fold improvement in total elapsed time on an Alzheimer's disease dataset.
• Theoretical computational complexity analysis supports the method's efficiency gains.

Conclusions:

• The proposed stochastic approach offers a viable and accurate alternative to traditional kNN search methods for large-scale applications.
• This method effectively reduces computational load without compromising search accuracy.
• The findings have implications for improving the efficiency of machine learning algorithms dealing with big data.