COMP5318 — Week 2 Supplement
Mathematical Foundations
Distance, scaling, voting, and computational trade-offs for nearest-neighbour methods and the rule-based exercises used this week.
Distance measures and neighbour voting
Week 2 treats each example as a vector of feature values. Prediction is then reduced to two steps: compute a distance from the new example to every training example, then let the nearest neighbour or nearest k neighbours decide the class.
For examples \(A=(a_1,\dots,a_d)\) and \(B=(b_1,\dots,b_d)\):
Euclidean distance: \[D_{L2}(A,B)=\sqrt{\sum_{j=1}^d(a_j-b_j)^2}\]
Manhattan distance: \[D_{L1}(A,B)=\sum_{j=1}^d|a_j-b_j|\]
Euclidean distance is the geometric straight-line distance. Manhattan distance measures how much total coordinate movement is required.
For a categorical attribute, use difference \(0\) if the two values match and \(1\) if they differ. The tutorial then sums these per-attribute differences inside the Euclidean square root.
1-NN
Uses the single closest example. Very local, very flexible, but sensitive to noise.
k-NN
Uses the majority label among the closest \(k\) examples. Bigger \(k\) means smoother decisions.
Odd \(k\)
For binary classification, odd values reduce tie frequency, though ties can still happen in multiclass tasks or equal-distance cases.
Why scaling matters before distance is computed
If one feature is measured in dollars and another in years, the large-scale feature can dominate the distance even if it is not more informative. That is why the lecture emphasizes normalization before using k-NN.
Min-max scaling
For one attribute vector \(x\), the scaled value is
\[ x'=\frac{x-\min(x)}{\max(x)-\min(x)} \]
Apply this independently to each feature column. After scaling, all transformed values lie in \([0,1]\).
Mini scaling check
Lecture example: \(A=[20, 40000]\), \(B=[40, 60000]\). Without scaling, Manhattan distance is \(|20-40|+|40000-60000|=20020\), so income overwhelms age. If age is scaled by min \(0\), max \(100\), and income by min \(0\), max \(100000\), then \(A'=[0.2,0.4]\), \(B'=[0.4,0.6]\), and the distance becomes \(0.4\), with both features contributing comparably.
Worked Example 1: numeric 1-NN and 3-NN
This is the same Week 2 tutorial dataset used in the lecture. The new example is \(x_{\text{new}}=(2,4,2)\).
Training data
| Example | \(a_1\) | \(a_2\) | \(a_3\) | Class |
|---|---|---|---|---|
| 1 | 1 | 3 | 1 | yes |
| 2 | 3 | 5 | 2 | yes |
| 3 | 3 | 2 | 2 | no |
| 4 | 5 | 2 | 3 | no |
Distance calculations
\[ D(x_{\text{new}},1)=\sqrt{(2-1)^2+(4-3)^2+(2-1)^2}=\sqrt{3} \]
\[ D(x_{\text{new}},2)=\sqrt{(2-3)^2+(4-5)^2+(2-2)^2}=\sqrt{2} \]
\[ D(x_{\text{new}},3)=\sqrt{(2-3)^2+(4-2)^2+(2-2)^2}=\sqrt{5} \]
\[ D(x_{\text{new}},4)=\sqrt{(2-5)^2+(4-2)^2+(2-3)^2}=\sqrt{14} \]
1-NN: the closest neighbour is example 2, so the prediction is yes.
3-NN: the three closest neighbours are 2 (yes), 1 (yes), 3 (no), so the majority class is still yes.
Worked Example 2: nominal-feature distance
For the iPhone tutorial exercise, the new example is age<=30, income=medium, student=yes, credit=fair. We use difference \(0\) for a match and \(1\) for a mismatch.
Distances to the closest examples
Example 7 is \((\le 30,\ \text{medium},\ \text{no},\ \text{fair})\), so only the student attribute differs:
\[ D(7,\text{new})=\sqrt{0+0+1+0}=1 \]
Example 1 is \((\le 30,\ \text{high},\ \text{no},\ \text{fair})\):
\[ D(1,\text{new})=\sqrt{0+1+1+0}=\sqrt{2} \]
Example 4 is \((>40,\ \text{medium},\ \text{no},\ \text{fair})\):
\[ D(4,\text{new})=\sqrt{1+0+1+0}=\sqrt{2} \]
Vote and interpretation
The smallest distance is \(1\), achieved by example 7, whose class is no. So 1-NN predicts no.
For 3-NN, the three nearest neighbours are example 7 (no), example 1 (no), and example 4 (yes). The majority label is again no.
Key lesson: the mathematics is still the same pattern as with numeric features: define a per-feature difference, aggregate across all features, then vote.
Common mistakes and exam-ready habits
Do this
- Check whether features live on comparable scales before computing distance.
- Sort neighbours by actual distance, not by coordinate difference on one feature.
- State clearly whether you are answering 1-NN or \(k\)-NN.
- Remember that training is cheap for k-NN, but prediction costs \(O(mn)\) for \(m\) training examples and \(n\) features.
Avoid this
- Normalizing the test example differently from the training feature ranges.
- Mixing Euclidean and Manhattan formulas in the same calculation.
- Using even \(k\) in a binary setting without explaining how ties are handled.
- Assuming “nearest” means visually nearest in one plot when the feature space is higher-dimensional.