Supervised evaluation of Voronoi partitions

Abstract

Since its introduction, the nearest neighbor rule has been widely refined and there exists many techniques for prototypes selection or construction. The underlying structure of such rules is the Voronoi partition induced by the prototypes. Construction of the best Voronoi partition often relies on the generalisation performance and thus faces the risk of overfitting the data.

In this paper, we adopt a descriptive approach for the supervised evaluation of medoid-based Voronoi partitions. The resulting criterion measures the discrimination of the classes, is parameter free and prevents from overfitting. Experiments on real and synthetic datasets illustrate these properties. Although this criterion is not related to the classifying task, the accuracy and robustness of the induced classifier are also compared with standard methods, such as the nearest neighbor rule and the linear vector quantization method.