k Nearest Neighbors _2

classify an unknown example with the most common class among k closest examples
• “tell me who your neighbors are, and I’ll tell you who you are”
Problems if “tune” k on training data
• meta parameter, overfit if tune these on training data
k = 1 is often used for efficiency, but sensitive to “noise”

Larger k gives smoother boundaries, better for generalization
• But only if locality is preserved. Locality is not preserved if end up looking at samples too far away, not from the same class.
• Interesting theoretical properties if k < sqrt(n), n is # of examples
• Can choose k through cross-validation (study soon)

normalize features to be on the same scale
• Different normalization approaches
• Linearly scale the range of each feature to be, say, in range [0,1]

Linearly scale to 0 mean variance 1:
• If Z is a random variable of mean m and variance ?

Feature normalization does not help in high dimensional
spaces if most features are irrelevant
,
then (Z - m)/? has mean 0 and variance 1

If K=1, select the nearest neighbor
• If K>1,
– For classification select the most frequent
neighbor.
– For regression calculate the average of K
neighbors.