An Improved KNN Classification Algorithm based on Sampling
Zhiwei Cheng, Caisen Chen, Xuehuan Qiu, Huan Xie · 2017
K nearest neighbor (KNN) algorithm has been widely used as a simple and effective classification algorithm.The traditional KNN classification algorithm will find k nearest neighbors, it is necessary to calculate the distance from the test sample to all training samples.When the training sample data is very large, it will produce a high computational overhead, resulting in a decline in classification speed.Therefore, we optimize the distance calculation of the KNN algorithm.Since KNN only considers the k samples of the shortest distance from the test sample to the nearest training sample point, the large distance training has no effect on the classification of the algorithm.The improved method is to sample the training data around the test data, which reduces the number of distance calculation of the test data to each training data, and reduces the time complexity of the algorithm.The experimental results show that the optimized KNN classification algorithm is superior to the traditional KNN algorithm.