Pre-cut kNN Algorithm Based on Threshold of Distance
Chen Lü, Dong Liang, Shan Wang, Lili Zeng, Yilin Zhao · 2018
In this paper, a novel approach to the k-Nearest Neighbors ( kNN) algorithm is proposed. As one of the ten classical algorithms of data mining, KNN algorithm has a very good performance in classification problems such as pattern recognition. However, it undergoes an undeniable weakness that is high complexity, especially when the training set is huge. The motivation behind this proposed algorithm is to increase the computational efficiency of the traditional kNN algorithm, without sacrificing the accuracy, or even improve it. This key idea of the proposed algorithm is to pre-cut the comparison procedure of distance comparison through a predefined threshold. The experimental results reveal that this improved pre-cut k NN algorithm, based on the threshold value of the smallest k distance, greatly increases computational efficiency, and do not cause any precision deduction, even improve an amount of accuracy. It can be concluded that this proposed algorithm achieves superior computational efficiency compared to the traditional kNN and previously proposed FkNN algorithm, especially when the data set is very large.