A novel prototype reduction method for the K-nearest neighbor algorithm with K ≥ 1

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, 6119 LNAI (PART 2), pp. 89 - 100
Issue Date:
Filename Description Size
Thumbnail2009005774OK.pdf334.17 kB
Adobe PDF
Full metadata record
In this paper, a novel prototype reduction algorithm is proposed, which aims at reducing the storage requirement and enhancing the online speed while retaining the same level of accuracy for a K-nearest neighbor (KNN) classifier. To achieve this goal, our proposed algorithm learns the weighted similarity function for a KNN classifier by maximizing the leave-one-out cross-validation accuracy. Unlike the classical methods PW, LPD and WDNN which can only work with K = 1, our developed algorithm can work with K ≥ 1. This flexibility allows our learning algorithm to have superior classification accuracy and noise robustness. The proposed approach is assessed through experiments with twenty real world benchmark data sets. In all these experiments, the proposed approach shows it can dramatically reduce the storage requirement and online time for KNN while having equal or better accuracy than KNN, and it also shows comparable results to several prototype reduction methods proposed in literature. © 2010 Springer-Verlag Berlin Heidelberg.
Please use this identifier to cite or link to this item: