Discriminative Learning of the Prototype Set for Nearest Neighbor Classification
This work addresses efficiency and generalization in classification for scenarios with pairwise dissimilarities, but it is incremental as it builds on existing prototype selection approaches.
The paper tackles the problem of prototype selection for nearest neighbor classification by proposing a parametrized model that minimizes violations of an extended rule, resulting in empirical advantages over other methods.
The nearest neighbor rule is a classic yet essential classification model, particularly in problems where the supervising information is given by pairwise dissimilarities and the embedding function are not easily obtained. Prototype selection provides means of generalization and improving efficiency of the nearest neighbor model, but many existing methods assume and rely on the analyses of the input vector space. In this paper, we explore a dissimilarity-based, parametrized model of the nearest neighbor rule. In the proposed model, the selection of the nearest prototypes is influenced by the parameters of the respective prototypes. It provides a formulation for minimizing the violation of the extended nearest neighbor rule over the training set in a tractable form to exploit numerical techniques. We show that the minimization problem reduces to a large-margin principle learning and demonstrate its advantage by empirical comparisons with other prototype selection methods.