Another move toward the minimum consistent subset: A tabu search approach to the condensed nearest neighbor rule

This paper presents a new approach to the selection of prototypes for the n earest neighbor rule which aims at obtaining an optimal or close-to-optimal solution. The problem is stated as a constrained optimization problem usin g the concept of consistency. In this context, the proposed method uses tab u search in the space of all possible subsets. Comparative experiments have been carried out using both synthetic and real data in which the algorithm has demonstrated its superiority over alternative approaches. The results obtained suggest that the tabu search condensing algorithm offers a very go od tradeoff between computational burden and the optimality of the prototyp es selected.