An Improved k-NN Classification with Dynamic k

Abstract

In the k-NN algorithm, k is the only parameter and often set to a fixed value empirically. However, it is very difficult to choose an appropriate k in practice, and if the choice is not appropriate, the performance of k-NN will be affected greatly. In order to solve this problem, the paper proposes an improved k-NN algorithm, which is denoted as Dk-NN, by using dynamic k in replace of fixed k value. Firstly, a preprocessed step is designed and added to the traditional k-NN algorithm for determining the dynamic k interval. Then, each class's percentage of test sample is calculated within the dynamic k interval. Finally, three criterions are given to determine the class of the test sample according to the variation tendency of the percentage curves. Experimental results on real-world dataset demonstrate that the proposed algorithm is more effective than the k-NN algorithm with fixed k value.