Optimal Selection of Reference Set for the Nearest Neighbor Classification by Tabu Search

In this paper, a new approach is presented to find the reference set forthe nearest neighbor classifier. The optimal reference set, which has minimum samplesize and satisfies a certain error rate threshold, is obtained through aTabu search algorithm. When the error rate threshold is set to zero, thealgorithm obtains a near minimal consistent subset of a given trainingset. While the threshold is set to a small appropriate value, theobtained reference set may compensate the bias of the nearest neighborestimate. An aspiration criterion for Tabu search is introduced, whichaims to prevent the search process from the inefficient wanderingbetween the feasible and infeasible regions in the search space andspeed up the convergence. Experimental results based on a number oftypical data sets are presented and analyzed to illustrate the benefitsof the proposed method. Compared to conventional methods, such as CNNand Dasarathy's algorithm, the size of the reduced reference sets ismuch smaller, and the nearest neighbor classification performance isbetter, especially when the error rate thresholds are set to appropriatenonzero values. The experimental results also illustrate that the MCS(minimal consistent set) of Dasarathy's algorithm is not minimal, andits candidate consistent set is not always ensured to reducemonotonically. A counter example is also given to confirm this claim.