K-Nearest Neighbours

Source: Unit 2 §2

The algorithm's idea

≡FactsThe three assumptions KNN makes

• All instances are points in $n$-dimensional space.
• "Nearest neighbours" are defined by a distance measure $\text{dist}(X_1, X_2)$.
• The target function may be discrete or real-valued:
  • discrete - return the most common value (mode) among the $k$ nearest neighbours;
  • real-valued - return the mean of the $k$ nearest neighbours' values.

k = 3 draws a circle around the query just wide enough to swallow three points, then takes the majority class inside it. Nothing else in the plot matters.

The training and classification algorithms

Training is trivial, because KNN is lazy:

For each training example (x, f(x)):

add the example to the list of training examples.

Classification, given a query instance xq:

1. Let X₁ … Xₖ = the k instances nearest to xq.

2. Return:

- Discrete target: the MODE (most common label) of X₁…Xₖ

- Real-valued: the MEAN of the values of X₁…Xₖ

→StepsHow to actually do it

1. Load the data (CSV / XLS).
2. Initialize K, the hyperparameter: 3, 5, 7, …
3. For each sample in the training data:
   • calculate distance(query, current point);
   • add the pair (distance, index) to an ordered collection.
4. Sort the collection by distance, ascending.
5. Take the first K entries.
6. Get the labels of those K entries.
7. If classification, return the mode of the K labels.
8. If regression, return the mean of the K values.

Choosing K

⚠GotchaK must be odd

Use 3, 5, 7, … so that a binary vote cannot tie. With k = 4 and two neighbours of each class you cannot decide at all - see the worked example below.

Small K	Large K
Captures the structure of the problem space better	Less sensitive to noise, especially class noise
May be necessary for a small training set	Gives better probability estimates for discrete classes
Prone to noise	Needs a large training set

?DECISIONSmall K or large K?

The training set is small→Small Ka large K would reach past the data you actually have

The class labels are noisy→Large Kthe extra votes average the noise away

You need calibrated class probabilities→Large Kmore neighbours means a finer-grained vote share

The class boundary is intricate→Small Klarge K smooths the structure out of the boundary

Pick this when: the training set is small, or the labels are noisy

With K = 1 the space is divided into regions called the Voronoi partition: each region contains exactly the points closest to one training example.

With k = 1 the stored examples carve the space into cells; every query inherits the label of whichever cell it lands in. The cell walls are the decision boundary.

The elbow method

→StepsPicking the best K empirically

1. Compute the error rate for different K values.
2. Plot error rate against K. The elbow of that curve is the optimal K.
3. Retrain with the best K and redo the classification report and confusion matrix.

Pick K at the elbow: the last value of K where the error is still dropping steeply. Past it you are buying nothing for the extra smoothing.

Worked example

The data set has two attributes and a binary class:

Attribute1	Attribute2	Class
7	7	False
7	4	False
3	4	True
1	4	True

Several distance measures are available - Euclidean, Manhattan, Minkowski and others. Here we use Euclidean:

$$\text{dist}\big((x, y), (a, b)\big) = \sqrt{(x - a)^2 + (y - b)^2}$$

≡FactsWhen do all attributes get equal weight?

Only if all three of these hold:

1. the attributes have a similar scale;
2. the attributes are scaled to equal range and equal variance;
3. the classes are spherical.

The problem: classify x = (Attribute1 = 3, Attribute2 = 7) with k = 3.

Point	Distance to (3,7)	Class
(7,7)	√((3−7)² + (7−7)²) = √16 = 4	False
(7,4)	√((3−7)² + (7−4)²) = √25 = 5	False
(3,4)	√((3−3)² + (7−4)²) = √9 = 3	True
(1,4)	√((3−1)² + (7−4)²) = √13 = 3.6	True

The three shortest distances are 3, 3.6 and 4. Two of those three points are True, so the query is True.

→StepsTaking the vote

1. Sort by distance: 3 at (3,4), 3.6 at (1,4), 4 at (7,7), then 5 at (7,4).
2. Take the first $k = 3$: (3,4) True, (1,4) True, (7,7) False.
3. The majority is True, two votes against one.
4. Prediction: x is classified as True.
5. Now try $k = 4$: the neighbours become 2 True and 2 False, a tie, and the query cannot be classified. This is why K must be odd.

KNN for regression

For a real-valued target, KNN returns the average of the target values of the $k$ nearest neighbours:

$$\hat{f}(x_q) = \frac{1}{k}\sum_{i=1}^{k} f(X_i)$$

taken over the $k$ nearest $X_i$.