Weighted KNN & Issues with KNN

Source: Unit 2 §3

Distance-weighted KNN

Weighted KNN weights each of the $k$ neighbours by its distance to the query, so that closer neighbours get greater weight.

Why bother? In plain KNN all $k$ neighbours vote equally, however far away they are. With weighting, a very close neighbour dominates the vote.

Same three neighbours, opposite answers. Plain KNN counts heads; weighted KNN counts 1/d², and the one very close R outweighs the two distant Gs.

A common weight is

$$w_i = \frac{1}{\text{dist}(x_q, X_i)^2}$$

so that a closer neighbour gets a larger weight.

◎Exam cueThe scenario that shows the difference

Query x with k = 3 and neighbours {G, G, R}. Plain KNN says G, 2 against 1. If R is much closer to x than either G, weighted KNN says R, because R's weight outweighs the two distant Gs.

Inductive bias of KNN

The classification of an instance x will be most similar to the classification of the K nearby instances.

In plain English: birds of the same feather flock together.

Issues with KNN

Issue	Explanation
Slow algorithm	Easy to implement, but as the data set grows, speed declines fast - all the work happens at query time.
Curse of dimensionality	Works well with few input variables; struggles as the number of attributes grows.
Needs homogeneous features	With a common distance (Euclidean, Manhattan) the features must be on the same scale: a given distance in feature 1 must mean the same as the same distance in feature 2.
Optimal K is hard	Choosing the right number of neighbours is a genuine problem in its own right.
Imbalanced data	If most of the training data is class A, the model over-favours A and the rare class B gets misclassified.
Outlier sensitivity	Neighbours are chosen purely by distance, so the method is very sensitive to outliers.
Missing values	KNN inherently cannot handle missing values.

The curse of dimensionality, in depth

As more attributes (dimensions) are added, the radius or circle of influence of each data point becomes smaller and smaller. Points become sparse and everything is far from everything else.

The panels are the same size on purpose. What changes is the ratio nearest / farthest, which climbs towards 1 as dimensions are added - and once it reaches 1, "nearest" carries no information at all.

Dimensions	What the neighbourhood looks like
2 dims	Neighbours are genuinely close.
3 dims	A bit more spread out.
100 dims	Almost every point is roughly the same, large, distance away. The "nearest" neighbour is barely nearer than the farthest, so KNN breaks.

#NumbersRule of thumb for how much data you need

Roughly 5 data instances per attribute are needed for learning. Twenty attributes therefore means at least about 100 instances before KNN has a chance.

≡FactsOvercoming the curse

• Assign weights to attributes when computing distances, so useless features are down-weighted.
• Leave-one-out approach - iteratively drop one attribute and test via cross-validation, to find the best subset of attributes.
• Follow the 5-instances-per-attribute rule of thumb.

Computational complexity

Basic KNN stores all the examples. With $n$ examples, each of dimension $d$:

Operation	Cost
Distance to one example	O(d)
Find one nearest neighbour	O(nd)
Find k closest examples	**O(knd)**

$$\text{Overall complexity} = O(knd)$$

⚠GotchaThe KNN paradox

$O(knd)$ is prohibitively expensive for large $n$ - and yet you need a large $n$ for KNN to work well in the first place. The algorithm gets more accurate exactly as fast as it gets unusable.