A Fast Exact k-Nearest Neighbors Algorithm for High Dimensional Search Using k-Means Clustering and Triangle...

Area of Science:

• Machine Learning
• Data Mining
• Computational Science

Background:

• The k-nearest neighbors (k-NN) algorithm is a fundamental machine learning technique for classification and regression.
• Efficiently finding nearest neighbors in high-dimensional datasets presents significant computational challenges.

Purpose of the Study:

• To introduce and evaluate kMkNN, a novel exact k-NN algorithm designed for accelerated nearest neighbor searches.
• To leverage k-means clustering and triangle inequality for improved performance in high-dimensional spaces.

Main Methods:

• kMkNN employs a two-stage approach: a preprocessing buildup stage using k-means clustering and a searching stage utilizing the triangle inequality.
• Unlike traditional methods, kMkNN avoids complex tree structures like kd-trees or ball-trees during preprocessing.

Main Results:

• kMkNN demonstrated substantial reductions in distance calculations (2- to 80-fold) and speedups (2- to 60-fold) over traditional k-NN on 16 out of 20 datasets.
• The algorithm outperformed kd-tree and ball-tree based k-NN methods in terms of efficiency and accuracy across various high-dimensional datasets.

Conclusions:

• kMkNN is an effective and efficient algorithm for nearest neighbor searches in high-dimensional feature spaces.
• The proposed method offers a promising alternative to existing k-NN algorithms, particularly for large-scale and high-dimensional data analysis.