The k-nearest-neighbors method (kNN) is the most literal way of learning from experience: store every example and, faced with a new case, look for the most similar ones. Witten et al. (2017) present it as a relative of plain rote learning, in which "the only problem is how to interpret 'resembles'" (2017, p. 84).
How it works
Each example is a vector of attributes with its label. To classify a new point x, one computes its distance to every stored example, keeps the k closest, and assigns the majority class among them; if the target is a number, one uses the distance-weighted average instead (Witten et al., 2017, p. 85). With k = 1 this is the nearest-neighbor rule; with a somewhat larger k (five, say) the vote dampens noisy examples (Witten et al., 2017, p. 141).
The usual distance is Euclidean; the Manhattan distance adds up absolute differences. Since attributes are measured on different scales, they are normalized to lie between 0 and 1; otherwise one measured in thousands would dwarf all the others (Witten et al., 2017, pp. 135–136). For nominal attributes ("red," "green") the difference is 0 if the values match and 1 if not.
There is no training to speak of. kNN is a lazy learner, deferring all the work until classification time, as opposed to eager methods that produce a generalization as soon as they see the data (Witten et al., 2017, p. 85). That is why it has no fitted parameters: k and the metric are hyperparameters, and the "model" is the entire training set.
Boundaries without rules
Although it writes down no rule, kNN draws boundaries. With a single example of each class, space is split by the perpendicular bisector of the segment joining them; with several, by a polygon of bisectors that is implicit in the rule (Witten et al., 2017, p. 86). These are nonlinear decision boundaries, unlike the straight line of Perceptron, and they bend to any shape given enough data.
The idea is old: statisticians analyzed it in the early 1950s (Fix & Hodges (1951), in a report for the U.S. Air Force), and it was adopted as a classification scheme in the 1960s (Witten et al., 2017, p. 141). The classic result is due to Cover & Hart (1967): with unlimited data, the error of the nearest-neighbor rule is at most twice the smallest achievable error (the so-called Bayes error). And if k and the number of examples grow together, with k much smaller than the total, the error approaches that minimum (Witten et al., 2017, p. 141).
Limits
The first is cost: prediction takes time proportional to the size of the training set. Trees such as kD-trees or ball trees speed up the search, but lose their edge as the dimension grows (Witten et al., 2017, pp. 136–141). The second is high dimensionality: because it decides within local neighborhoods, kNN is very susceptible to irrelevant attributes, and the number of examples needed for a given level of performance grows exponentially with their number (Witten et al., 2017, p. 289). This is the practical face of the "curse of dimensionality." The third is that everything hinges on the metric: deciding which attributes count, and how much, is by Witten et al.'s account one of the method's central problems (2017, p. 85).
Where it lives today
kNN was reborn with embeddings. Dense retrieval turns search into finding the nearest neighbors of the query vector (Alammar & Grootendorst, 2024, p. 226); with millions of documents one uses approximate nearest-neighbor libraries (Annoy, FAISS) or vector databases (Alammar & Grootendorst, 2024, pp. 238–239). In high dimensions cosine similarity is usually preferred to Euclidean distance (Alammar & Grootendorst, 2024, p. 142). This is how the retriever in Retrieval-augmented generation (RAG) and semantic search with Sentence-BERT work. What changed is not the algorithm but the space: the attributes are no longer chosen by a human; they are learned (see embeddings).