k-Nearest Neighbors

No training at all — label a new point by the majority vote of the k labelled examples sitting closest to it.

k-nearest-neighbours (k-NN) labels a new point by looking at the labelled examples sitting closest to it and taking a majority vote. There is no training step in the usual sense — it just stores the data and does all the work when a question arrives. It's the textbook lazy learner.

The whole algorithm

1Choose k (how many neighbours to consult) and a distance measure, usually straight-line Euclidean distance.
2When a new point arrives, compute its distance to *every* stored training point.
3Take the k smallest distances — the k nearest neighbours.
4Each neighbour votes for its own class; the class with the most votes wins. (For regression, average the neighbours' values instead.)

def knn_predict(train, labels, query, k=3):
    dists = [(euclidean(query, x), y)
             for x, y in zip(train, labels)]
    dists.sort(key=lambda t: t[0])      # nearest first
    top_k = [y for _, y in dists[:k]]
    return max(set(top_k), key=top_k.count)  # majority vote

Choosing k

k controls the smoothness of the boundary. A small k (like 1) follows the nearest few points slavishly — flexible but jumpy and sensitive to noise (overfitting). A large k averages over a wide neighbourhood — smoother, but it blurs fine detail and can swamp a small class (underfitting). A common trick: pick an odd k for two-class problems so votes can't tie.

Worked example

New point near three neighbours labelled {A, A, B}. With k = 3 the vote is 2-to-1 for A, so it predicts A. Drop to k = 1 and only the single closest neighbour decides — if that nearest point happened to be the B, the prediction flips to B. Same data, different k, different answer.

Scale your features first

Distance treats all features equally, so a feature measured in thousands (salary) will dwarf one measured in single digits (years of experience). Normalize or standardize every feature to a common scale, or the large-range feature silently dominates the vote.

Cheap to train, costly to predict

Storing the data is instant, but each prediction scans all n points — O(n·d) per query. On large datasets people speed this up with spatial indexes like k-d trees or ball trees, which prune away most of the distance checks.

OperationTimeSpace

Train · just store the dataO(1)O(n·d)

Predict (brute force) · distance to every pointO(n·d)O(n)

Predict (k-d tree) · low dimensions only~O(log n·d)O(n)

Check yourself

What is the effect of increasing k in k-NN?