COMP4318 · Machine Learning and Data Mining
Nearest Neighbour & Rule-Based Algorithms
Week 2 introduces instance-based learning — k-nearest-neighbours with its distance metrics and the effect of k — and rule-based learners (1R and PRISM) that build IF–THEN rules. These are direct, hand-computable methods, so they are prime exam material: a typical question gives you a handful of points and asks you to classify a new one with a stated k and distance, or to trace a rule. The weekly homework quiz (h2) drills the same calculations.
What this chapter covers
- 01k-NN: store all training examples, classify a new point by majority vote of its k nearest neighbours
- 02Distance metrics: Euclidean (L2, √ of sum of squares), Manhattan (L1, sum of absolute differences), Minkowski
- 03Feature scaling / min-max normalisation so large-scale features don't dominate the distance
- 04Choosing k: rule of thumb k ≤ √(#training examples); larger k = more robust to noise, k=1 fits the training set perfectly
- 05Weighted k-NN (weight ∝ 1/d²) and regression k-NN (average the neighbours' values)
- 06Complexity: training O(1) (just storing), classification O(mn); speed up with KD-trees / ball trees
- 071R: one rule on the single best attribute (a decision stump), leaf = majority class, chosen by smallest error rate
- 08PRISM covering algorithm: add tests to maximise accuracy p/t for a class until p/t = 1
Classifying a point with k-NN and Manhattan distance
- +1Manhattan distance from (4,7) to each training point = |4−x1| + |7−x2|: (2,2)→2+5=7; (2,8)→2+1=3; (4,4)→0+3=3; (6,5)→2+2=4; (3,6)→1+1=2.
- +1Sort ascending: (3,6)=2, (2,8)=3, (4,4)=3, (6,5)=4, (2,2)=7. The k=3 nearest are (3,6), (2,8) and (4,4).
- +1Read off their labels: (3,6)=+1, (2,8)=+1, (4,4)=−1.
- +1Majority vote of {+1, +1, −1} = +1.
Key terms
- k-nearest neighbours (k-NN)
- An instance-based classifier: store all training examples, and classify a new point by the majority vote of its k closest examples (average their values for regression).
- Euclidean distance
- The L2 distance D(A,B) = √((a1−b1)² + … + (an−bn)²); the straight-line distance and the default for k-NN.
- Manhattan distance
- The L1 distance D(A,B) = |a1−b1| + … + |an−bn|; the sum of absolute coordinate differences.
- Min-max normalisation
- Rescaling each attribute by x' = (x − min)/(max − min) to [0,1] so features on large scales don't dominate distance-based methods.
- 1R (decision stump)
- A one-rule learner: a one-level decision tree testing a single attribute, with each leaf labelled by the majority class; pick the attribute with the smallest training error.
- PRISM
- A covering (rule-based) algorithm: for each class it adds tests to a rule to maximise accuracy p/t (t covered, p of the target class) until p/t = 1, then adds a default rule.
Nearest Neighbour & Rule-Based Algorithms FAQ
How do I choose k in k-NN?
A common rule of thumb is k ≤ √(number of training examples), tuned with a validation set. Small k (down to k=1) fits the training data tightly but is sensitive to noise; larger k is smoother and more robust but can blur genuine class boundaries. In the exam, use the k the question states and show the votes; if asked to choose, pick the k that minimises validation error.
Euclidean or Manhattan — which distance should I use?
Use whichever the question specifies. Euclidean (L2) is the straight-line distance and the usual default; Manhattan (L1) sums absolute differences and is less sensitive to a single large coordinate gap. Both require the features to be on comparable scales, so normalise first.
Why normalise before k-NN?
Because distance sums over all features, an attribute measured on a large scale (say income in thousands) would dominate one on a small scale (say age), so the small-scale feature is effectively ignored. Min-max normalisation puts every attribute on [0,1] so each contributes fairly to the distance.
Where can I find practice for the k-NN and rule questions?
The Week 2 tutorial and homework-quiz (h2) solutions on Canvas are the closest match; work them by hand. This guide's practice exam includes fresh k-NN and rule-tracing questions, and you can ask Sia to generate more at the difficulty you need and explain each step.
Exam move
Drill the mechanical routine until it is automatic: compute the distance from the query to every training point, sort, take the k smallest, then majority-vote (or average for regression). Always write out all the distances — that's where the method marks live. Practise both Euclidean and Manhattan, and rehearse min-max normalisation so you can apply it before a distance calculation when scales differ. For the rule-based side, trace one 1R error table and one PRISM p/t sequence by hand. When a step trips you up, ask Sia to re-run the vote with a fresh point and check your sorting.
Working through Nearest Neighbour & Rule-Based Algorithms in COMP4318? Sia is AskSia’s AI Machine Learning tutor — ask any COMP4318 Nearest Neighbour & Rule-Based Algorithms question and get a clear, step-by-step explanation grounded in how COMP4318 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
