k-nearest-neighbors image classifier

The k-nearest-neighbors classifier is the most literal idea in all of recognition: to label a new image, find the k training images most similar to it and let them vote. There is no training in the usual sense — you simply store every labeled example. At test time you compute a distance between the new image's feature vector and every stored vector, pick the k smallest distances, and assign the majority class among those k neighbors. With k = 1 the new image just copies its single closest match; larger k smooths the decision by averaging over more neighbors and is more robust to noisy outliers.

Made precise, you need two choices: a feature representation and a distance. On raw pixels, distances like L2 (Euclidean, the square root of the summed squared pixel differences) or L1 (sum of absolute differences) are notoriously poor, because they treat a one-pixel shift or a brightness change as a huge difference — two photos of the same object can be farther apart in pixel space than two photos of different objects. kNN only becomes useful on good features: a HOG or color histogram with an appropriate distance (chi-squared or histogram intersection for histograms), and today, deep embeddings from a CNN or CLIP where ordinary cosine distance suddenly groups semantically similar images together. The parameter k and the distance metric are hyperparameters chosen by validation.

kNN's appeal is that it is trivially simple, makes no assumption about the shape of class boundaries (it can carve arbitrarily complex regions), and trivially handles new classes — just add their examples. Its weaknesses are equally famous and define why it is usually only a baseline. Test time is slow and memory-hungry: every prediction scans the entire training set, which is the opposite of a model like an SVM or CNN that does fast fixed-cost inference. It suffers acutely from the curse of dimensionality, where in high-dimensional feature spaces all points become roughly equidistant and the notion of nearest neighbor degrades. And it is only as good as its feature space and distance metric — which is precisely why, in modern systems, kNN shines as the retrieval step on top of learned embeddings (face recognition, image search, retrieval-augmented pipelines) rather than as a classifier on raw images.