Weighted reward-punishment editing

[abstract]

The Nearest Neighbor classifier is a popular nonparametric classification method that has been successfully applied to many pattern recognition problems. Its usefulness has been limited, however, because of its computational complexity and sensitivity to outliers in the training set. Computational complexity is becoming less of an issue thanks to the availability of inexpensive memory and high processing speeds. To overcome the second limitation, sensitivity to outliers in the training set, researchers have developed editing and condensing techniques that are aimed at selecting a proper set of prototypes from the training set. In this work, we propose a new editing technique based on the idea of rewarding those patterns that make a contribution to a correct classification while punishing those patterns that provide an incorrect classification. This criteria is coupled with an approach for selecting the edited patterns based on the minimization of a criteria index related to the distances in the training patterns and on the calculation of edge and border patterns for determining the number of edited patterns. Extensive experiments were conducted across several classification problems that evaluated both the efficacy of the proposed technique with respect to other editing approaches and the advantages of using our proposed editing technique either in combination with condensing techniques or as a method utilized in the preprocessing stage. Moreover, the proposed editing approach is shown to be particularly effective when combined with a support vector machine (SVM) classifier. The MATLAB code used in the proposed paper will be available at https://www.dei.unipd.it/node/2357.

Keywords Pattern Editing, Nearest Neighbor Classifier, Machine Learning, Ensemble.