A Novel Pre-Classification Based kNN Algorithm

摘要

kNN (k nearest neighbors) is widely adopted because of its simplicity. However, its shortcomings can not be neglected, especially its time complexity. Consequently a great amount of approaches emerged in large numbers in decades to cope with this issue with a tradeoff in performance of the classification. In this paper, a novel improved kNN algorithm is proposed with a better performance than traditional kNN when its time complexity is meanwhile reduced. In the proposed algorithm, a pre-classification which cost little time is to be conducted before proposed kNN algorithm. Then the training set can be divided into several parts according to the classification probability with some thresholds. After that the parts with probability nearer to 1 or 0 are selected to be training sets. The accuracy rate and the area under the ROC curve (the receiver operating characteristic curve) of the proposed algorithm is calculated and compared with basic kNN algorithm in the experiments. The experiment results show that not only the pre-classification based kNN algorithm greatly reduced the time cost, but it also performs better than the original kNN algorithm in accuracy and AUC (the area under the ROC curve).