An Extensive Experimental Study on the Cluster-based Reference Set Reduction for Speeding-up the k-NN Classifier

Abstract

The k-Nearest Neighbor (k-NN) classification algorithm is one of the most widely-used lazy classifiers because of its simplicity and ease of implementation. It is considered to be an effective classifier and has many applications. However, its ma- jor drawback is that when sequential search is used to find the neighbors, it involves high computational cost. Speeding-up k-NN search is still an active research field. Hwang and Cho have recently proposed an adaptive cluster-based method for fast Nearest Neigh- bor searching. The effectiveness of this method is based on the adjustment of three parameters. However, the authors evaluated their method by setting specific pa- rameter values and using only one dataset. In this pa- per, an extensive experimental study of this method is presented. The results, which are based on five real life datasets, illustrate that if the parameters of the method are carefully defined, one can achieve even better clas- sification performance