COMP5318 — Applied Machine Learning

Week 2: k-Nearest Neighbours

This week really has two threads: instance-based learning with k-NN and symbolic rule learners such as 1R and PRISM. The lecture focuses on distance, voting, scaling, and rule construction; the notebook shows the full sklearn workflow on iris; the tutorial makes you compute predictions and rules by hand.

📍Distance

👥Voting

⚖Generalisation

📜Rules

Iris notebook Euclidean / Manhattan MinMaxScaler 1R PRISM

📐 Math Foundations → 🗺 Mind Map →

Course materials

The page below is a synthesis of the local files in this folder. Read the lecture for concepts, run the notebook for the sklearn workflow, and use the tutorial sheet to check whether you can reason through the algorithm without code.

File	What it contributes
w2.ipynb	Iris dataset walkthrough, train/test split, scatter-matrix inspection, `KNeighborsClassifier`, prediction, and `MinMaxScaler`.
ml2.pdf	Lecture theory: nearest neighbour, Euclidean and Manhattan distance, normalisation, computational cost, distance weighting, 1R, and PRISM.
t2.pdf	Hand calculations: numeric 1-NN / 3-NN, nominal-distance k-NN, and PRISM rule generation.
t2-solutions.pdf	Worked distances and the final PRISM rule set.

Core mental model

k-NN does not build an explicit parametric model. It stores the training set and predicts by comparing a new point with remembered examples.

What makes the week tricky

Distance is only meaningful if the features are on compatible scales and if you do not leak test-set statistics into preprocessing.

Exam-style skill

You should be able to compute distances manually, identify nearest neighbours, explain the effect of k, and derive simple rules by hand.

What k-NN is really doing

The lecture frames classification as: given labelled examples, learn something that predicts the class of new unseen examples. For nearest neighbour, the "learning" step is mostly memory; the heavy lifting happens at prediction time.

Classification setup

A dataset contains training examples, features, and class labels. The training set is used to build the classifier; the test set is used later to estimate how well it generalises to unseen data.

1-NN

Store all training examples. For a new point \(x\), find the closest stored example and copy its class label.

\[ \hat{y}(x) = y_{(1)} \]

This is a very local rule: one noisy neighbour can flip the answer.

k-NN

Find the \(k\) closest training examples and combine their labels, usually by majority vote for classification or by averaging for regression.

\[ \hat{y}(x) = \operatorname{majority}(y_{(1)}, \dots, y_{(k)}) \]

More neighbours usually means lower variance but higher bias.

Euclidean distance

\(d_2(A,B)=\sqrt{\sum_j (a_j-b_j)^2}\). This is the default distance used in the notebook via Minkowski distance with p=2.

Manhattan distance

\(d_1(A,B)=\sum_j |a_j-b_j|\). The lecture contrasts it with Euclidean distance and the Week 4 grid-search section later tunes this with p=1 or p=2.

Nominal attributes

For categorical features, the tutorial uses a simple mismatch count: same value contributes 0, different value contributes 1 before taking the square root.

Slide heuristic, not a theorem: the lecture gives a rule of thumb \(k \le \sqrt{\#\text{training examples}}\). Treat this as a starting point. Real selection should be done with validation or cross-validation.

Computational profile: training is cheap because the model just stores data, but prediction is expensive because each query is compared to many stored points. The lecture explicitly states naive lookup for one unseen example costs \(O(mn)\) for \(m\) training examples of dimensionality \(n\), with the same order of memory usage.

Quick check - Data splitting

Why does the notebook stress shuffling before the train/test split on iris?

To make Euclidean distance smaller

Because the examples are ordered by class and we want both splits to contain all classes

Because KNeighborsClassifier only works on shuffled arrays

Notebook workflow on the iris dataset

The notebook is not just about calling sklearn. It demonstrates the full pattern you will reuse all semester: inspect data, make a reproducible split, fit the estimator on training data only, and report performance on held-out data.

1

Load and inspect

load_iris() returns a dictionary-like object with data, target, target_names, and feature_names. The dataset has 150 flowers, 4 numeric features, and 3 classes.

2

Split reproducibly

train_test_split(..., random_state=0) gives a 75/25 split by default. Fixing the seed matters so your results are repeatable and debuggable.

3

Visualise before modelling

The notebook converts X_train to a pandas DataFrame and plots a scatter-matrix. This is your reminder that inspection comes before blind fitting.

4

Fit and evaluate

KNeighborsClassifier(n_neighbors=1), then fit, then predict or score. The notebook reports roughly 97% test accuracy on its split.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

iris_dataset = load_iris()
X_train, X_test, y_train, y_test = train_test_split(
    iris_dataset["data"], iris_dataset["target"], random_state=0
)

knn = KNeighborsClassifier(n_neighbors=1)
knn.fit(X_train, y_train)
test_accuracy = knn.score(X_test, y_test)

Prediction for a new example

The notebook creates X_new = np.array([[5, 2.9, 1, 0.2]]) and predicts its species. This is the minimal shape sklearn expects: one row per example, one column per feature.

Generalisation principle: evaluating on the training set tells you how well the algorithm can match memorised data. Evaluating on a held-out test set tells you something about new data. Those are different questions.

Scaling, leakage, and practical behavior

The lecture's age-income example shows exactly why raw distances can be misleading: one large-scale feature can dominate the calculation and effectively erase smaller-scale features.

Why normalise

If age is in years and income is in tens of thousands, income can overwhelm the distance. The lecture explicitly recommends normalisation for distance-based methods such as nearest neighbour.

The notebook uses MinMaxScaler, which maps training features into a bounded range using training-set minima and maxima.

What not to do

Never fit the scaler on the test set. The scaler must learn its min/max from the training data, then apply the same transformation to both train and test.

Otherwise you leak future information into preprocessing and inflate your reported accuracy.

from sklearn.preprocessing import MinMaxScaler

scaler = MinMaxScaler()
scaler.fit(X_train)
X_train_norm = scaler.transform(X_train)
X_test_norm = scaler.transform(X_test)

Weighted k-NN

The lecture also mentions distance-weighted voting: closer neighbours contribute more than farther ones, which helps when a fixed k includes some less-relevant points.

Voronoi view

In 1-NN, each training example owns a region of space whose points are closest to it. The decision boundary is made of Voronoi edges, which explains why it can look irregular.

Regression mode

The lecture notes that k-NN is not only for classification. For regression, the prediction is the average target value of the nearest neighbours.

Quick check - Leakage

Which statement about scaling for k-NN is correct?

Fit one scaler on the training set and a different scaler on the test set

Fit the scaler on the full dataset so train and test use the same statistics

Fit the scaler on the training set, then transform both train and test with it

Rule-based classifiers: 1R and PRISM

Week 2 is not only about distances. The lecture also introduces simple symbolic learners that produce explicit if-then rules. These are interpretable, hand-checkable, and good preparation for later decision-tree ideas.

1R

1R = one rule. Build one rule per attribute, where each attribute value is assigned the majority class of the training examples matching that value. Count training errors for each attribute-specific rule and keep the attribute with the smallest error.

Produces a single-attribute decision stump.
Very simple and fast.
Numeric data needs discretisation first.

PRISM

PRISM is a covering algorithm. It takes one class at a time and keeps adding conditions that maximise rule accuracy \(p/t\) until the current rule becomes perfect, then removes the covered examples and repeats.

Rules for a class are order-independent.
Uncovered test examples need a default rule.
Numeric data again needs discretisation.

PRISM pseudocode from the lecture

Choose a target class \(C\).
Start a new empty rule that predicts \(C\).
Add the condition that maximises rule accuracy \(p/t\) on the remaining examples.
Repeat until the rule is perfect.
Remove covered examples of class \(C\), then continue until none remain.

Final PRISM rules from t2-solutions.pdf:

Class = no: if outlook=rainy and windy=true then no
Class = no: if outlook=sunny and humidity=high then no
Class = yes: if outlook=overcast then yes
Class = yes: if humidity=normal and windy=false then yes
Class = yes: if temperature=mild and humidity=normal then yes
Class = yes: if temperature=mild and windy=false then yes

Quick check - PRISM

What does the lecture recommend if a new example is not covered by any PRISM rule?

Discard the example and make no prediction forever

Use a default rule that predicts the class with the most training examples

Force the first rule in the rule list to fire

Tutorial reasoning you should be able to reproduce

Exercise 1

Numeric k-NN

The tutorial asks for 1-NN and 3-NN on a new numeric example \(a_1=2, a_2=4, a_3=2\).

\(D(\text{new}, ex1)=\sqrt{3}\), class yes
\(D(\text{new}, ex2)=\sqrt{2}\), class yes
\(D(\text{new}, ex3)=\sqrt{5}\), class no
\(D(\text{new}, ex4)=\sqrt{14}\), class no

So 1-NN predicts yes (closest is example 2), and 3-NN also predicts yes because the three closest labels are yes, yes, no.

Exercise 2

Nominal-distance k-NN

For the iPhone dataset, each attribute mismatch contributes 1 and each match contributes 0.

The closest neighbour is example 7 with distance 1 and class no, so 1-NN predicts no. The three closest neighbours are example 7 (no), example 1 (no), and example 4 (yes), so 3-NN also predicts no.

Exercise 3

Interpretability

The tutorial's PRISM exercise matters because it forces you to reason about rule coverage and rule accuracy \(p/t\) rather than just memorising final if-then statements.

For class no, the solution first finds outlook=sunny as a strong test, then refines it to the perfect rule outlook=sunny and humidity=high. It then builds a second perfect rule outlook=rainy and windy=true.

For class yes, PRISM generates a direct rule for overcast days and then several additional rules involving humidity=normal, temperature=mild, and windy=false.

Chapter quizzes

Self-test and math questions for this week are in the Quiz Hub (practice or exam mode).

Open Quiz Hub Chapter flashcards