k-Nearest Neighbours

Get access to whole semester resourcesSemester Pass

Chapter Fifty-Three

Syllabus topic Module 2, "k-NN"

Pages 290 to 295 of 591

In one line

To classify something new, find the training examples most like it and let them vote.

In the wording a student can write in an examination: the k-nearest neighbours algorithm classifies a new instance by finding the k training instances closest to it under a distance measure and assigning the majority class among them. It is an instance-based or lazy learner: there is no training phase beyond storing the data, and all the work happens at prediction time. It is nonparametric, since the model is the whole training set.

The algorithm

Five lines, and it is worth writing them out because the whole method is here.

to classify a new point x, given k:
    1. compute the distance from x to EVERY training instance
    2. sort by that distance
    3. take the k closest
    4. count the classes among them
    5. return the class with the most votes    (ties: see below)

There is no step for training. k-NN stores the data and does nothing else until asked. That is why it is called lazy: the work is deferred to prediction, which is the opposite trade from the fitted line of What Machine Learning Is.

The distance measures

MU's label names k-NN without naming a distance, and a paper expects at least two.

Measure	Formula for two points	Character
Euclidean, or L2	the square root of the sum of squared differences	straight-line distance; the default
Manhattan, or L1	the sum of absolute differences	distance along the grid; less affected by one large difference
Minkowski	the `p`-th root of the sum of `p`-th powers	the family: `p = 2` is Euclidean, `p = 1` is Manhattan
Hamming	the number of features that differ	for categorical features, where subtraction is meaningless
Cosine	the angle between the two vectors	for text and other data where direction matters and length does not

A categorical feature has no arithmetic. The difference between Mumbai and Pune is not a number, so Euclidean distance cannot be used on it. Either use Hamming distance, or encode each category as its own 0/1 feature, which is called one-hot encoding.

It worked, by hand and then run

Twelve students, each with hours studied and attendance, and whether they passed. A new student has studied 5 hours with 72 per cent attendance.

# k-nearest neighbours, worked BY HAND on a table the reader can check, then run.
# Twelve students: hours studied, attendance per cent, and whether they passed.
TRAIN = [
    (2, 55, "fail"), (3, 60, "fail"), (3, 80, "fail"), (4, 65, "fail"),
    (4, 85, "pass"), (5, 70, "pass"), (5, 90, "pass"), (6, 60, "pass"),
    (6, 88, "pass"), (7, 75, "pass"), (2, 95, "fail"), (8, 50, "pass"),
]

def euclid(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def classify(point, k, dist=euclid, show=False):
    scored = sorted(((dist(point, (h, at)), lab) for h, at, lab in TRAIN))
    near = scored[:k]
    votes = {}
    for d, lab in near:
        votes[lab] = votes.get(lab, 0) + 1
    if show:
        for d, lab in near:
            print("      distance %7.3f   %s" % (d, lab))
        print("      votes:", ", ".join("%s %d" % (l, n) for l, n in sorted(votes.items())))
    return max(sorted(votes), key=lambda l: votes[l])

NEW = (5, 72)
print("a new student: %d hours studied, %d%% attendance" % NEW)
print()
print("STEP 1 measure the distance to every training student (Euclidean)")
for h, at, lab in TRAIN:
    print("   (%d, %d) %-5s  distance = sqrt((%d-%d)^2 + (%d-%d)^2) = %7.3f"
          % (h, at, lab, NEW[0], h, NEW[1], at, euclid(NEW, (h, at))))
print()
print("STEP 2 take the k nearest and let them vote")
for k in (1, 3, 5, 7):
    print("   k = %d" % k)
    ans = classify(NEW, k, show=True)
    print("      ANSWER: %s" % ans)
print()
print("THE DISTANCE MEASURE also changes the answer:")
for name, d in (("Euclidean", euclid), ("Manhattan", manhattan)):
    print("   %-10s k=3 -> %s" % (name, classify(NEW, 3, d)))
print()
print("AND THE SCALE MATTERS. attendance runs 50 to 95 and hours 2 to 8, so")
print("attendance dominates the distance. the same student, with hours and")
print("attendance both rescaled to 0..1:")

def scaled(p):
    return ((p[0] - 2) / 6.0, (p[1] - 50) / 45.0)

def classify_scaled(point, k):
    s = scaled(point)
    scored = sorted((euclid(s, scaled((h, at))), lab) for h, at, lab in TRAIN)
    votes = {}
    for d, lab in scored[:k]:
        votes[lab] = votes.get(lab, 0) + 1
    return max(sorted(votes), key=lambda l: votes[l])

for k in (1, 3, 5, 7):
    print("   k = %d  unscaled %-5s   scaled %-5s" % (k, classify(NEW, k), classify_scaled(NEW, k)))
print()
print("on THIS student the two agree. on a student with 2 hours and 75% attendance")
print("they do not, and that is the warning:")
OTHER = (2, 75)
for k in (1, 3, 5):
    print("   k = %d  unscaled %-5s   scaled %-5s"
          % (k, classify(OTHER, k), classify_scaled(OTHER, k)))
print("   unscaled, attendance swamps the distance and the nearest students are")
print("   whoever attended about 75 per cent, several of whom passed. scaled,")
print("   the two hours studied count as much, and 2 hours is the lowest in")
print("   the table, where every student failed.")

k-Nearest Neighbours

a new student: 5 hours studied, 72% attendance

STEP 1 measure the distance to every training student (Euclidean)
   (2, 55) fail   distance = sqrt((5-2)^2 + (72-55)^2) =  17.263
   (3, 60) fail   distance = sqrt((5-3)^2 + (72-60)^2) =  12.166
   (3, 80) fail   distance = sqrt((5-3)^2 + (72-80)^2) =   8.246
   (4, 65) fail   distance = sqrt((5-4)^2 + (72-65)^2) =   7.071
   (4, 85) pass   distance = sqrt((5-4)^2 + (72-85)^2) =  13.038
   (5, 70) pass   distance = sqrt((5-5)^2 + (72-70)^2) =   2.000
   (5, 90) pass   distance = sqrt((5-5)^2 + (72-90)^2) =  18.000
   (6, 60) pass   distance = sqrt((5-6)^2 + (72-60)^2) =  12.042
   (6, 88) pass   distance = sqrt((5-6)^2 + (72-88)^2) =  16.031
   (7, 75) pass   distance = sqrt((5-7)^2 + (72-75)^2) =   3.606
   (2, 95) fail   distance = sqrt((5-2)^2 + (72-95)^2) =  23.195
   (8, 50) pass   distance = sqrt((5-8)^2 + (72-50)^2) =  22.204

STEP 2 take the k nearest and let them vote
   k = 1
      distance   2.000   pass
      votes: pass 1
      ANSWER: pass
   k = 3
      distance   2.000   pass
      distance   3.606   pass
      distance   7.071   fail
      votes: fail 1, pass 2
      ANSWER: pass
   k = 5
      distance   2.000   pass
      distance   3.606   pass
      distance   7.071   fail
      distance   8.246   fail
      distance  12.042   pass
      votes: fail 2, pass 3
      ANSWER: pass
   k = 7
      distance   2.000   pass
      distance   3.606   pass
      distance   7.071   fail
      distance   8.246   fail
      distance  12.042   pass
      distance  12.166   fail
      distance  13.038   pass
      votes: fail 3, pass 4
      ANSWER: pass

THE DISTANCE MEASURE also changes the answer:
   Euclidean  k=3 -> pass
   Manhattan  k=3 -> pass

AND THE SCALE MATTERS. attendance runs 50 to 95 and hours 2 to 8, so
attendance dominates the distance. the same student, with hours and
attendance both rescaled to 0..1:
   k = 1  unscaled pass    scaled pass
   k = 3  unscaled pass    scaled pass
   k = 5  unscaled pass    scaled pass
   k = 7  unscaled pass    scaled pass

on THIS student the two agree. on a student with 2 hours and 75% attendance
they do not, and that is the warning:
   k = 1  unscaled pass    scaled fail
   k = 3  unscaled pass    scaled fail
   k = 5  unscaled pass    scaled fail
   unscaled, attendance swamps the distance and the nearest students are
   whoever attended about 75 per cent, several of whom passed. scaled,
   the two hours studied count as much, and 2 hours is the lowest in
   the table, where every student failed.

k-Nearest Neighbours

Every distance is printed with its arithmetic, which is what a by-hand question wants. For the training student at 6 hours and 60 per cent, the distance is the square root of (5-6)2 + (72-60)2, which is the square root of 145, that is 12.042.

Choosing k

k is a hyperparameter and the three things to say about it are these.

Small k is sensitive to noise. At k = 1 a single mislabelled training point creates a small region of wrong predictions around itself. The decision boundary is jagged.

Large k smooths, and eventually destroys. At k equal to the size of the training set, every prediction is the majority class of the whole dataset, whatever the input. The boundary becomes a straight line and then disappears.

k-Nearest Neighbours

So k controls the bias-variance tradeoff directly. Small k, low bias and high variance. Large k, high bias and low variance. It is the clearest example in this module of the tradeoff being a single dial, and a paper can ask you to say which end is which.

Two practical rules. Choose k by cross-validation, as Overfitting and Underfitting requires of every hyperparameter. And for a two-class problem use an odd k, so a simple majority cannot tie. With more than two classes an odd k does not prevent ties, and the usual tie-breaks are to prefer the class of the single nearest neighbour, or to weight each vote by 1 / distance.

Weighted voting

A refinement a paper may ask for. In plain k-NN the nearest neighbour and the k-th nearest have equal votes, which is odd when one is very close and the other far away.

Distance-weighted k-NN gives each neighbour a vote of 1 / distance, or 1 / distance squared. Close neighbours then dominate, ties become almost impossible, and the method is much less sensitive to k: raising k adds only distant, lightly weighted votes.

What it costs

The complexity table, which is the practical reason k-NN is used less than its simplicity suggests.

	k-NN	A fitted model
Training time	`O(1)`, just store the data	often substantial
Memory	`O(n * d)`, the whole dataset	the parameters only
One prediction	`O(n * d)`, every row, every feature	`O(d)` or better
Adding one training example	free	usually a refit

For a million training rows and a hundred features, one prediction reads a hundred million numbers. The standard remedies are spatial index structures such as a k-d tree or a ball tree, which cut the search when the dimension is low; in high dimensions they degrade to examining everything, for the reason in the next chapter.

Why it works at all: Cover and Hart

The theoretical result that makes k-NN respectable, and MU's syllabus mentions the method without it, so knowing it is a distinguishing answer.

Cover and Hart proved in 1967 that as the amount of training data grows without limit, the error rate of the 1-nearest-neighbour rule is at most twice the Bayes error, the least error any classifier could achieve given the true distributions.

Read the conditions, because they are the whole content: it is an asymptotic result, holding in the limit of infinite data, and the bound is on the 1-nearest-neighbour rule specifically. What it says is remarkable all the same: a rule that does no learning at all, given enough data, is within a factor of two of the best possible. With larger k the bound improves and approaches the Bayes error.

k-Nearest Neighbours

And it explains where k-NN fails. The result needs the neighbours to be genuinely near, which needs the data to be dense. That is exactly what the next chapter shows is impossible in high dimensions.

Distinctions

	k-NN	A parametric model
Training	stores the data	fits parameters
Called	lazy, instance-based	eager, model-based
Prediction cost	grows with `n`	constant
Data needed at prediction time	all of it	none

	Small k	Large k
Boundary	jagged	smooth
Bias	low	high
Variance	high	low
Sensitive to a mislabelled point	yes	no
At the extreme	`k = 1` copies the nearest label	`k = n` always predicts the majority class

	Euclidean	Manhattan	Hamming
For	continuous features	continuous features	categorical features
Sensitive to one large difference	more	less	not applicable

What it does not mean

k-NN does not learn anything at training time. It stores the data. All the work is at prediction.

The k neighbours are not a region of fixed size. The region grows or shrinks to contain exactly k points, so it is small where the data is dense and large where it is sparse.

An odd k does not prevent ties in general. It prevents them only for two classes.

Nonparametric does not mean no hyperparameters. k, the distance measure and the scaling are all chosen by the designer.

The Cover and Hart bound does not hold on your dataset. It is asymptotic, in the limit of infinite data.

A categorical feature cannot be given numeric codes and measured with Euclidean distance. Coding Mumbai as 1 and Pune as 2 asserts that Pune is twice Mumbai and that they are one unit apart.

Quick revision

k-NN: compute the distance from the new point to every training instance, take the k nearest, and return the majority class. Lazy, instance-based, nonparametric; no training phase.
Distances: Euclidean (L2), Manhattan (L1), Minkowski (the family), Hamming (categorical), cosine (text). Categorical features need Hamming or one-hot encoding.
k is the bias-variance dial. Small k: jagged boundary, low bias, high variance, sensitive to one bad label. Large k: smooth, high bias, low variance; at k = n it always predicts the majority class.
Choose k by cross-validation; use an odd k for two classes. Distance-weighted voting gives each neighbour 1 / distance and makes the method less sensitive to k.
Cost: training O(1), memory O(nd), one prediction O(nd). Remedied by a k-d tree or ball tree, which fail in high dimensions.
Cover and Hart 1967: as data grows without limit, the 1-nearest-neighbour error is at most twice the Bayes error. Asymptotic, and for k = 1; larger k approaches the Bayes error.

k-Nearest Neighbours

Test yourself

1. Give the k-NN algorithm in five steps. Compute the distance from the new point to every training instance; sort by distance; take the k closest; count the classes among them; return the class with the most votes, breaking ties by the nearest neighbour or by weighting votes by inverse distance.

2. Why is k-NN called a lazy learner, and what does that cost? Because it does no work at training time beyond storing the data, deferring everything to prediction. It costs memory proportional to the whole dataset and a prediction time proportional to the number of training rows times the number of features.

3. Name three distance measures and say when each is appropriate. Euclidean, the straight-line distance, for continuous features and the usual default. Manhattan, the sum of absolute differences, for continuous features when one large difference should not dominate. Hamming, the count of features that differ, for categorical features where subtraction has no meaning.

4. How does k affect bias and variance? A small k gives a jagged boundary that follows individual points, which is low bias and high variance and is easily upset by one mislabelled example. A large k averages over many points, giving a smooth boundary with high bias and low variance, until at k equal to the dataset size every prediction is the overall majority class.

5. Why use an odd k, and what does that not fix? So that a simple majority vote cannot tie when there are two classes. It does not prevent ties with three or more classes, for which the usual remedies are to fall back on the nearest neighbour's class or to weight votes by inverse distance.

6. State Cover and Hart's result with its conditions. As the training set grows without limit, the error rate of the one-nearest-neighbour rule is at most twice the Bayes error, the least error achievable by any classifier given the true distributions. It is an asymptotic result for k equal to one, and larger k improves the bound towards the Bayes error itself.

7. Why can a categorical feature not simply be numbered and used with Euclidean distance? Because numbering imposes an order and a spacing that do not exist. Coding Mumbai as 1 and Pune as 2 asserts that they are one unit apart and that Pune is in some sense twice Mumbai, both of which are meaningless. Use Hamming distance, or one-hot encode each category as its own indicator feature.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue