A Novel Prototype Reduction Method for the K-Nearest Neighbor Algorithm with K >= 1

Publisher:
Springer Berlin / Heidelberg
Publication Type:
Conference Proceeding
Citation:
Advances in Knowledge Discovery and Data Mining - Lecture Notes in Artificial Intelligence, 2010, pp. 89 - 100
Issue Date:
2010-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2009005774OK.pdf334.17 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: