La classification suivant le plus proche voisin est une règle simple et performante. Sa mise en oeuvre pratique nécessite, tant pour des raisons de coût de calcul que de robustesse, de sélectionner les instances à conserver. La partition de Voronoi induite par les prototypes constitue la structure sous-jacente à cette règle. Dans cet article, on introduit un critère descriptif d'évaluation d'une telle partition, quantifiant le compromis entre nombre de cellules et discrimination de la variable cible entre les cellules. Une heuristique d'optimisation est proposée, tirant partie des propriétés des partitions de Voronoi et du critère. La méthode obtenue est comparée avec les standards sur une vingtaine de jeux de données de l'UCI. Notre technique ne souffre d'aucun défaut de performance prédictive, tout en sélectionnant un minimum d'instances. De plus, elle ne surapprend pas.