Skip to main content

k neighbours and a vote

One odd example should not decide a prediction. The k-nearest-neighbour classifier asks the k closest stored examples and takes a majority vote. See how a small k follows noise and a large k blurs the boundary, choose k with a validation set, and deal with ties.
ML01.3.2L1 Core25 minIn review

Before this lesson

ML01.3.1 Classify by your nearest neighbour ML01.2.2 Train, validation and test sets

After this lesson you can

  • Classify an example with k nearest neighbours and a majority vote, by hand and in NumPy.
  • Describe how the decision boundary changes as k grows from 1 to the size of the training set.
  • Choose k with a validation set, and explain why the training set cannot choose it.
  • Explain when a vote ties, why an odd k prevents ties between two classes, and what scikit-learn does when one happens.

In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

The question

In the last lesson a fruit shaped like a pear was called an apple, because the single closest fruit on the tray was an odd apple. A careful person would glance at a few more fruit before answering. But how many? Ask too few, and one odd fruit decides. Ask the whole tray, and the answer no longer depends on the fruit in your hand.

From the last lesson

1. What does the nearest-neighbour rule predict for a new example?

Show answer

The label of the stored example at the smallest distance from it.

2. What accuracy does that rule reach on its own stored examples, and why?

Show answer

100%, unless identical examples carry different labels. Each stored example is at distance \(0\) from itself, so it is its own nearest neighbour.

Intuition

Put a circle round the query and let it grow until it holds \(k\) stored fruit. Those are its \(k\) nearest neighbours. Each one casts a single vote for its own label, and the label with the most votes wins. This is the \(k\)-nearest-neighbour classifier, or \(k\)-NN.

A plot of height against width showing the eight stored fruit and the new fruit, a yellow disc with a question mark, at (6, 8). Three dashed vermillion circles are centred on it. The smallest, labelled k equals 1, holds only the apple at (5, 8). The middle one, labelled k equals 3, also holds the pears at (5, 7) and (6, 10). The largest, labelled k equals 5, also holds the pears at (4, 9) and (4, 6). These five fruit have yellow discs behind them and thin lines to the new fruit. Three apples on the right lie outside every circle. Beside the plot are three cards. The first reads k equals 1, 1 apple, predict apple. The second reads k equals 3, 2 pears, 1 apple, predict pear. The third reads k equals 5, 4 pears, 1 apple, predict pear.
ML01.3.2-F1

The same query as in lesson 1, asked with three values of \(k\). With \({k = 1}\) the odd apple decides. With \({k = 3}\) it is outvoted two to one, and with \({k = 5}\) four to one.

The odd apple still gets its vote. It no longer gets the only one. With two classes and \({k \ge 3}\), a wrong or unusual label can win only if it has company.

The number \(k\) is not learned by the method. It is a setting you choose before any prediction is made, a hyperparameter, and most of this lesson is about choosing it honestly.

Build it up

Step 1. Sort the stored examples by distance from the query. Lesson 1 did the work: compute every distance, then put the list in order, nearest first.

Step 2. Keep the first \(k\) and count their votes. The label with the most votes wins. With \({k = 1}\) this is the nearest-neighbour rule again.

Step 3. See what \(k\) does to the whole plane. Eight fruit are too few to show it, so take a larger set: 300 training points in two classes that curl round each other, with plenty of noise.

Three panels showing the same 300 training points, blue circles in an arc at the upper left and sky-blue squares in an arc at the lower right, with the two arcs overlapping in the middle. In each panel the region where the classifier answers with the circles' class is tinted blue, and a vermillion line marks the decision boundary. First panel, k equals 1, captioned follows every point: the boundary is ragged and there are several small islands of one class inside the other. Second panel, k equals 11, captioned about right: the boundary is a single smooth S-shaped curve between the two arcs. Third panel, k equals 151, captioned blurs the curve: the boundary is almost a straight diagonal line and no longer follows the arcs.
ML01.3.2-F2

One dataset, three values of \(k\). Left: \({k = 1}\) gives every training point its own patch, so noise becomes islands. Middle: \({k = 11}\) keeps the curve and drops the islands. Right: \({k = 151}\) averages over half the data and flattens the curve into a near-straight line.

A small \(k\) follows the noise: every stray point bends the boundary. A large \(k\) blurs it: the vote covers so wide a neighbourhood that the local shape of the data is lost.

Step 4. Let held-back data choose \(k\). Too small is bad and too large is bad, so a good value lies between. To find it, use a validation set: examples that were not stored, kept aside for this job. Try several values of \(k\), measure the error of each on the validation set, and keep the best.

A line chart of error rate against the number of neighbours k, on a logarithmic axis from 1 to 299. A dashed purple line with hollow dots, labelled training error, starts at 0.00 for k equals 1, rises to about 0.10 by k equals 5, stays near there until k is about 45, then climbs to 0.48 at k equals 299. A solid purple line with filled dots, labelled validation error, starts at 0.23 for k equals 1, falls to its lowest point, 0.13, at k equals 11, stays between 0.14 and 0.19 up to k equals 151, and then rises steeply to 0.52 at k equals 299. A yellow band marks k equals 11 with the note lowest validation error. A note at the left says small k: follows the noise, and a note at the right says k equals 299: almost every point votes.
ML01.3.2-F4

Error against \(k\) for the data of the previous figure, with 300 training points and 100 validation points. The training error is lowest at \({k = 1}\), where it is zero. The validation error is lowest at \({k = 11}\).

The two curves disagree. The next section shows why the training curve cannot choose.

The formal statement

NoteDefinition: the k-nearest-neighbour classifier

For a query \(\vect{x}\), let \(N_k(\vect{x})\) be the set of indices of the \(k\) training examples closest to \(\vect{x}\). The number of votes for a class \(g\) is

\[ v_g(\vect{x}) \;=\; \sum_{i \in N_k(\vect{x})} [\, y_i = g \,] , \]

where \({[\, y_i = g \,]}\) is \(1\) when example \(i\) has label \(g\) and \(0\) otherwise. The prediction is the class with the most votes:

\[ \cmodel{\hat{y}(\vect{x})} \;=\; \argmax_{g} \; v_g(\vect{x}) . \]

The votes add up to \(k\), so \({v_g(\vect{x}) / k}\) is the share of the neighbours in class \(g\), often read as a rough estimate of the probability that the query belongs to class \(g\).

Fact 1: the two ends of the dial. With \({k = 1}\), the set \(N_1(\vect{x})\) holds only the nearest neighbour, so \(k\)-NN is the rule of lesson 1. With \({k = n}\), the set \(N_n(\vect{x})\) holds every training example, whatever \(\vect{x}\) is. The votes are then the class counts of the whole training set, and the prediction is the most common class, the same for every query.

Fact 2: with two classes, an odd \(k\) never ties. Call the two vote counts \(v_A\) and \(v_B\). Every neighbour votes for one of them, so \({v_A + v_B = k}\). A tie means \({v_A = v_B}\), and then \({k = 2v_A}\), an even number. So if \(k\) is odd there is no tie. The argument needs exactly two classes: with three, \({k = 3}\) can split one vote each.

Fact 3: the training set cannot choose \(k\). Lesson 1 showed that, without duplicated inputs, \({k = 1}\) makes no errors on the training set. No error rate is below zero, so judged by training error \({k = 1}\) is never beaten, however noisy the data. To learn which \(k\) predicts new examples best, measure on examples that were not stored. The procedure uses the three sets of lesson ML01.2.2: fit, choose, report.

  1. Store the training set.
  2. For each candidate \(k\), predict the validation examples and record the error rate.
  3. Keep the \(k\) with the lowest validation error.
  4. Report the error of that one \(k\) on the test set, once.

Ties. Two different things can tie.

  • A tied vote. With an even \(k\), or with more than two classes, the top classes can have equal votes. scikit-learn then takes the tied class that comes first when the labels are sorted, which has nothing to do with the data.
  • A tied distance. Two stored examples can be equally far from the query and compete for the last place among the \(k\). scikit-learn’s documentation warns that the result then depends on the order of the training data.
Go deeper: votes that count for more when the neighbour is closer

A plain vote treats the nearest neighbour and the \(k\)-th alike. A common refinement gives neighbour \(i\) the weight \({1 / \operatorname{dist}(\vect{x}, \vect{x}_i)}\): in scikit-learn, weights="distance".

Let all eight fruit vote on the query \({(6, 8)}\). The plain vote ties, four against four. The apples are at distances \({1,\ 3,\ 3.61,\ 4.12}\), so their weights add to \({1 + 0.333} + {0.277 + 0.243} = 1.853\). The pears are at \({1.41,\ 2,\ 2.24,\ 2.83}\), with weights \({0.707 + 0.5} + {0.447 + 0.354} = 2.008\). The pears win. But \(k\) must still be chosen: with \({k = 2}\) the weights are \(1\) for the apple and \(0.707\) for the pear, and the odd apple wins again.

Worked example

Classify the fruit at \({(6, 8)}\) for every \(k\) from 1 to 8.

The distances are those of lesson 1, now sorted. Take the neighbours one at a time and recount after each.

A table drawn as a figure, with one row for each k from 1 to 8. Its columns are k, the k-th nearest fruit, its distance, the pear votes so far drawn as blue circles, the apple votes so far drawn as sky-blue squares, and the prediction. Row 1: apple (5, 8), distance 1.00, no pear votes, one apple vote, prediction apple. Row 2: pear (5, 7), 1.41, one pear and one apple, prediction tie. Row 3: pear (6, 10), 2.00, two pears and one apple, prediction pear. Row 4: pear (4, 9), 2.24, three to one, pear. Row 5: pear (4, 6), 2.83, four to one, pear. Row 6: apple (9, 8), 3.00, four to two, pear. Row 7: apple (9, 6), 3.61, four to three, pear. Row 8: apple (10, 7), 4.12, four pears and four apples, prediction tie.
ML01.3.2-F3

The vote, one neighbour at a time. The prediction is “apple” only at \({k = 1}\). It is “pear” for every \(k\) from 3 to 7. At \({k = 2}\) and \({k = 8}\) the vote ties.

Reading down the figure:

  • \({k = 1}\): the nearest neighbour is the apple at \({(5, 8)}\). One vote, apple.
  • \({k = 2}\): the pear at \({(5, 7)}\) joins. One vote each, a tie.
  • \({k = 3}\): the pear at \({(6, 10)}\) joins. \({v_{\text{pear}} = 2}\), \({v_{\text{apple}} = 1}\): pear, with a vote share of \({2/3}\).
  • \({k = 5}\) and \({k = 7}\): four pears to one apple, then four to three. Still pear.
  • \({k = 8}\): everyone votes, four against four. This is Fact 1: at \({k = n}\) the vote is the class count of the tray, and this tray has no majority.

Both ties fall on even values of \(k\), as Fact 2 says they must.

Which \(k\) would held-back fruit choose? Lesson 1 kept four fruit off the tray. With \({k = 1}\) three of them are classified correctly. With \({k = 3}\) all four are. Four fruit are far too few to trust, though: one fruit is a quarter of the score. The code below uses a hundred.

Code

The classifier from scratch: sort by squared distance, keep \(k\), count.

import numpy as np

X = np.array([[5, 7], [6, 10], [4, 9], [4, 6],        # four pears: width and height in cm
              [5, 8], [9, 8], [9, 6], [10, 7]])       # four apples
y = np.array(["pear"] * 4 + ["apple"] * 4)
query = np.array([6, 8])

def knn_predict(X, y, query, k):
    squared = ((X - query) ** 2).sum(axis=1)
    order = np.argsort(squared, kind="stable")        # nearest first
    labels, votes = np.unique(y[order[:k]], return_counts=True)   # labels come back sorted
    return labels[np.argmax(votes)], dict(zip(labels.tolist(), votes.tolist()))

for k in range(1, 9):
    label, votes = knn_predict(X, y, query, k)
    print(f"k = {k}: votes {votes} -> {label}")
k = 1: votes {'apple': 1} -> apple
k = 2: votes {'apple': 1, 'pear': 1} -> apple
k = 3: votes {'apple': 1, 'pear': 2} -> pear
k = 4: votes {'apple': 1, 'pear': 3} -> pear
k = 5: votes {'apple': 1, 'pear': 4} -> pear
k = 6: votes {'apple': 2, 'pear': 4} -> pear
k = 7: votes {'apple': 3, 'pear': 4} -> pear
k = 8: votes {'apple': 4, 'pear': 4} -> apple

At \({k = 2}\) and \({k = 8}\) the vote is tied, yet the function prints “apple”: np.unique sorts the labels and np.argmax returns the first of the equal counts, so “apple” wins by the alphabet. scikit-learn behaves the same way.

from sklearn.neighbors import KNeighborsClassifier

for k in [1, 2, 3, 8]:
    model = KNeighborsClassifier(n_neighbors=k).fit(X, y)
    shares = dict(zip(model.classes_.tolist(), model.predict_proba([query])[0].round(3).tolist()))
    print(f"k = {k}: {model.predict([query])[0]:5s}  vote shares {shares}")

weighted = KNeighborsClassifier(n_neighbors=8, weights="distance").fit(X, y)
print("k = 8, votes weighted by 1/distance:", weighted.predict([query])[0])
k = 1: apple  vote shares {'apple': 1.0, 'pear': 0.0}
k = 2: apple  vote shares {'apple': 0.5, 'pear': 0.5}
k = 3: pear   vote shares {'apple': 0.333, 'pear': 0.667}
k = 8: apple  vote shares {'apple': 0.5, 'pear': 0.5}
k = 8, votes weighted by 1/distance: pear

Now choose \(k\) properly. The data are 500 points from scikit-learn’s make_moons generator, two interleaved arcs with noise, split 300 / 100 / 100 into training, validation and test sets.

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split

X_all, y_all = make_moons(n_samples=500, noise=0.35, random_state=0)
X_train, X_rest, y_train, y_rest = train_test_split(X_all, y_all, test_size=0.4, random_state=0)
X_val, X_test, y_val, y_test = train_test_split(X_rest, y_rest, test_size=0.5, random_state=0)

candidates = [1, 3, 5, 7, 9, 11, 15, 21, 31, 45, 61, 91, 121, 151, 201, 299]
errors = {}
for k in candidates:
    model = KNeighborsClassifier(n_neighbors=k).fit(X_train, y_train)
    errors[k] = (1 - model.score(X_train, y_train), 1 - model.score(X_val, y_val))
    print(f"k = {k:3d}   training error {errors[k][0]:.3f}   validation error {errors[k][1]:.2f}")

best_k = min(candidates, key=lambda k: errors[k][1])
final = KNeighborsClassifier(n_neighbors=best_k).fit(X_train, y_train)
test_error = 1 - final.score(X_test, y_test)
print(f"chosen by the validation set: k = {best_k}.  Test error, measured once: {test_error:.2f}")
k =   1   training error 0.000   validation error 0.23
k =   3   training error 0.077   validation error 0.17
k =   5   training error 0.100   validation error 0.16
k =   7   training error 0.100   validation error 0.15
k =   9   training error 0.097   validation error 0.14
k =  11   training error 0.100   validation error 0.13
k =  15   training error 0.107   validation error 0.15
k =  21   training error 0.107   validation error 0.14
k =  31   training error 0.110   validation error 0.15
k =  45   training error 0.100   validation error 0.17
k =  61   training error 0.120   validation error 0.15
k =  91   training error 0.130   validation error 0.16
k = 121   training error 0.140   validation error 0.19
k = 151   training error 0.163   validation error 0.19
k = 201   training error 0.217   validation error 0.23
k = 299   training error 0.483   validation error 0.52
chosen by the validation set: k = 11.  Test error, measured once: 0.15

Three things stand out.

  • At \({k = 1}\) the training error is \(0\) and the validation error is \(0.23\), the worst of all the values below 200.
  • The validation error is lowest, \(0.13\), at \({k = 11}\). One validation example moves the error by \(0.01\), so anything from about \(7\) to \(31\) would be a defensible choice.
  • At \({k = 299}\) the validation error is \(0.52\), worse than tossing a coin. The training set holds 155 points of one class and 145 of the other, and 299 of the 300 vote, so the larger class wins every time.

The test error of the chosen model is \(0.15\), a little above its validation error. That is normal: \({k = 11}\) was picked for scoring best on the validation set, so that score flatters it. The test set took no part in the choice, so report its figure.

Explore

ML01.3-X1

Neighbour explorer

Drag the disc marked “?” or click on the plot to move the query, then change \(k\). On the fruit tray at \({(6, 8)}\), \({k = 1}\) says apple, \({k = 2}\) ties and \({k = 3}\) says pear. Then switch to the noisy data and slide \(k\) upwards: the boundary smooths out, and near the top it loses its shape. The distance switch and the unit slider belong to lesson 3.

A static picture of the eight stored fruit with the new fruit at (6, 8) and three dashed circles round it, holding its 1, 3 and 5 nearest neighbours. Cards beside the plot give the votes: k equals 1 predicts apple, k equals 3 and k equals 5 predict pear.

Pitfalls

Two panels, each a close-up of the plot round the new fruit at (6, 8). The left panel is marked with a cross and titled k equals 2: one vote each. A dashed circle holds two neighbours, the apple at (5, 8) and the pear at (5, 7), both joined to the new fruit by thick lines. A note says 1 pear, 1 apple: no majority, and another says an arbitrary rule must decide. The right panel is marked with a tick and titled k equals 3: two votes to one. A larger dashed circle also holds the pear at (6, 10). A note says 2 pears, 1 apple, and another says predict pear.
ML01.3.2-F5

Wrong beside right. With two classes an even \(k\) can leave the vote tied, and then something that has nothing to do with the fruit decides. An odd \(k\) always produces a majority.

“An even \(k\) is as good as an odd one.”

With two classes an even \(k\) can tie, and the tie is settled by a rule you did not choose. In the code above, \({k = 2}\) answered “apple” only because “apple” sorts before “pear”. Rename the classes and the prediction flips.

“Pick the \(k\) with the best accuracy on the training data.”

By Fact 3 nothing beats \({k = 1}\) there, and on the moons it was the worst small \(k\) for new points: training error \(0\), validation error \(0.23\). And if the test set chooses \(k\), its score stops being an honest estimate. Choosing is the validation set’s job.

“A larger \(k\) uses more data, so it is always safer.”

A larger \(k\) uses data from farther away, and distant examples say little about the query. At \({k = n}\) the classifier ignores the query altogether. A rare class disappears long before that: with two classes, one that has only 40 training examples can never win a vote once \(k\) is above 80.

Check yourself

Recall

1. How does the \(k\)-nearest-neighbour classifier label a query?

Show answer

It finds the \(k\) stored examples closest to the query and predicts the label with the most votes among them.

2. What happens to the decision boundary as \(k\) grows from 1?

Show answer

It goes from following every point, noise included, to smooth, to too blurred to follow the data.

3. What does \(k\)-NN predict when \(k\) equals the number of training examples?

Show answer

The most common class in the training set, for every query.

4. Why can the training set not choose \(k\), and what does?

Show answer

Without duplicated inputs, its error is \(0\) at \({k = 1}\) however noisy the labels, so it never prefers a larger \(k\). A validation set chooses.

5. Why use an odd \(k\) with two classes, and what does scikit-learn do with a tied vote?

Show answer

The two vote counts add to \(k\), so they can be equal only if \(k\) is even. On a tie scikit-learn predicts the tied class that comes first in sorted order.

Exercises

1. ★ With the eight stored fruit, classify the fruit at \({(7, 9)}\) using \({k = 1}\), \({k = 3}\) and \({k = 5}\).

Show solution

The squared distances from \({(7, 9)}\) are \({8, 2, 9, 18}\) to the pears at \({(5, 7)}\), \({(6, 10)}\), \({(4, 9)}\), \({(4, 6)}\) and \({5, 5, 13, 13}\) to the apples at \({(5, 8)}\), \({(9, 8)}\), \({(9, 6)}\), \({(10, 7)}\). In order: pear (\(2\)), apple (\(5\)), apple (\(5\)), pear (\(8\)), pear (\(9\)), then the rest. So \({k = 1}\) gives pear, \({k = 3}\) gives apple (two votes to one) and \({k = 5}\) gives pear (three to two).

2. ★★ A training set has 60 examples of class A and 40 of class B. (a) What does \(k\)-NN predict with \({k = 100}\), and what is its training accuracy? (b) Show that B can never be predicted when \({k \ge 81}\).

Show solution

(a) Every example votes for every query: 60 votes for A, 40 for B. The prediction is always A, which is right for 60 training examples out of 100: \(60\%\).

(b) B needs at least \({k / 2}\) votes to win, even on a tie. It has at most 40. If \({k \ge 81}\) then \({k / 2 \ge 40.5 > 40}\), so B cannot win.

3. ★★★ Two classes, A and B, each with at least \(m\) examples, and an odd \({k = 2m - 1}\), with no two training examples equally far from the query. Show that \(k\)-NN predicts A exactly when the \(m\)-th nearest A is closer to the query than the \(m\)-th nearest B.

Show solution

With \(k\) odd, a class wins exactly when it has at least \(m\) of the \(k\) votes. Let \(a\) and \(b\) be the distances to the \(m\)-th nearest A and the \(m\)-th nearest B.

If \({a < b}\), then within distance \(a\) of the query there are exactly \(m\) A’s and fewer than \(m\) B’s, at most \({m + (m - 1) = k}\) examples in all. So all of them are among the \(k\) nearest, and they include \(m\) A’s: A wins. If \({b < a}\), exchange the letters: B wins. The boundaries in this lesson’s figures were drawn this way, as the places where \({a = b}\).

Summary card

Ask the \(k\) nearest and take a vote. Let held-back data choose \(k\).

The anchor figure again: the new fruit at (6, 8) with dashed circles holding its 1, 3 and 5 nearest stored fruit. One neighbour predicts apple; three or five predict pear.
ML01.3.2-F1

One vote per neighbour.

  • Rule. \({\hat{y}(\vect{x})} = {\argmax_g \sum_{i \in N_k(\vect{x})} [\, y_i = g \,]}\), with \(N_k(\vect{x})\) the \(k\) nearest training examples.
  • The dial. Small \(k\) follows noise. Large \(k\) blurs. At \({k = n}\) the answer is the most common class.
  • Choosing \(k\). Lowest validation error, never training error. Report on the test set once.
  • Ties. With two classes an odd \(k\) cannot tie, because \({v_A + v_B = k}\).
  • By hand. Query \({(6, 8)}\): apple at \({k = 1}\), a tie at \({k = 2}\), pear for \({k = 3}\) to \(7\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 12 November 2026.

  • scikit-learn 1.9 user guide, Section 1.6.2, Nearest Neighbors Classification. Classification is “computed from a simple majority vote of the nearest neighbors”. A larger \(k\) suppresses noise but makes the boundaries less distinct, and weights="distance" weights each neighbour by the inverse of its distance.
  • scikit-learn 1.9 documentation, KNeighborsClassifier. Warns that when neighbours \(k\) and \({k + 1}\) have identical distances but different labels, the result depends on the ordering of the training data. The rule for a tied vote is not stated there: this lesson reports what the code cells above show for version 1.9.
  • Trevor Hastie, Robert Tibshirani and Jerome Friedman, The Elements of Statistical Learning, 2nd edition, Section 2.3.2. Defines the \(k\)-nearest-neighbour fit (equation 2.8) and notes that the training error is always 0 for \({k = 1}\), so it cannot be used to pick \(k\).
  • Stanford University, CS231n: Deep Learning for Computer Vision, course notes: Image Classification. Higher values of \(k\) have a smoothing effect, and the test set cannot be used for tweaking hyperparameters: it is evaluated a single time, at the very end.

The larger example is synthetic: make_moons(n_samples=500, noise=0.35, random_state=0).

Next. ML01.3.3 Distance and feature scaling asks what “nearest” means when one feature is in grams and another in centimetres.

This lesson unlocks

ML01.3.3 Distance and feature scaling

Your progress is saved in this browser only. No account, no tracking.
Back to top