A way to speed up nearest neighbor classification is to replace the training set by a carefully chosen subset of “prototypes”. A good strategy for choosing prototypes from the training set, bearing in mind that the ultimate goal is good classification performance, is implemented here
A K_means clustering based algorithm can be implemented for protoyping for 1 NN classification
Algorithm has been tested on the MNIST dataset, available at: http://yann.lecun.com/exdb/mnist/index.html