Nearest prototype classification: clustering, genetic algorithms, or random search?

Three questions related to the nearest prototype classifier (NPC) are addressed: when is it better to construct the prototypes instead of selecting them as a subset of the given labeled data; how can we trade classification accuracy for a reduction in the number of prototypes; and how good is pure random search (RS) for selection of prototypes from the data? We compare the resubstitution performance of the NPC on the IRIS data set, where the prototypes are either extracted by replacement (R-prototypes) or by selection (S-prototypes). Results for the R-prototypes are taken from a previous study and are contrasted with S-prototype results obtained by a genetic algorithm (GA) or by RS. The best results reached by both algorithms (GA and RS), followed by resubstitution NPC, are two errors with sets of three S-prototypes. This compares favorably to the best result found with R-prototypes, viz., three errors with five R-prototypes. Based on our results, we recommend GA selection for the NPC. A by-product of this research is a counter example to minimality of a recently published minimal consistent set selection procedure.