Minimal consistent set (MCS) identification for optimal nearest neighbor decision systems design

Abstract

A new approach is presented in this study for tackling the problem of high computational demands of nearest neighbor (NN) based decision systems. The approach, based on the concept of an optimal subset selection from a given training data set, derives a consistent subset which is aimed to be minimal in size. This minimal consistent subset (MCS) selection, in contrast to most of the other previous attempts of this nature, leads to an unique solution irrespective of the initial order of presentation of the data. Further, consistency property is assured at every iteration. Also, unlike under most prior approaches, the samples are selected here in the order of significance of their contribution for enabling the consistency property. This provides insight into the relative significance of the samples in the training set. Experimental results based on a number of independent training and test data sets are presented and discussed to illustrate the methodology and bring to focus its benefits. These results show that the nearest neighbor decision system performance suffers little degradation when the given large training set is replaced by its much smaller MCS in the operational phase of testing with an independent test set. A direct experimental comparison with a prior approach is also furnished to further strengthen the case for the new methodology.>