k-nearest neighbors and feature scaling
Classify by distance to stored examples, and see how an unscaled feature can dominate the result.
train = [((1.0, 1000), "A"), ((1.1, 3000), "A"), ((5.0, 1100), "B"), ((5.2, 3100), "B")]
def make_scaler(points):
lows = [min(p[i] for p in points) for i in range(2)]
highs = [max(p[i] for p in points) for i in range(2)]
return lambda p: tuple((p[i] - lows[i]) / (highs[i] - lows[i]) for i in range(2))
def knn(train, query, k, scaled):
scale = make_scaler([point for point, _ in train]) if scaled else (lambda p: p)
q = scale(query)
ordered = sorted(train, key=lambda item: sum((a - b) ** 2 for a, b in zip(scale(item[0]), q)))
votes = [label for _, label in ordered[:k]]
return max(set(votes), key=votes.count)
print(knn(train, (1.2, 2000), 1, False))
print(knn(train, (1.2, 2000), 1, True))B A
Explanation
k-nearest neighbors (k-NN) is one of the simplest learning methods. There is no training phase: the algorithm stores the labelled examples, and to classify a new point it finds the k stored examples closest to it and returns the majority label. It is called a lazy learner because all the work happens at prediction time.
Everything depends on the distance, usually Euclidean. If one feature has a much larger numeric range than another, it dominates the distance and the other feature is effectively ignored. Here the first feature spans about 1 to 5 while the second spans 1000 to 3100. Without scaling, the nearest neighbour of the query point is decided almost entirely by the second feature and the answer is B. After min-max scaling, which rescales each feature to the range 0 to 1, both features contribute equally and the answer flips to A.
Choose k by validation: a small k is flexible but sensitive to noise, while a large k smooths the decision but can blur real structure. k-NN also suffers in many dimensions, where distances between points become less informative, and its prediction cost grows with the size of the stored data unless an index is used. Always scale features before using distance-based methods, fitting the scaling on the training data only.
Explore the dry run
train = [((1.0, 1000), "A"), ((1.1, 3000), "A"), ((5.0, 1100), "B"), ((5.2, 3100), "B")] def make_scaler(points): lows = [min(p[i] for p in points) for i in range(2)] highs = [max(p[i] for p in points) for i in range(2)] return lambda p: tuple((p[i] - lows[i]) / (highs[i] - lows[i]) for i in range(2)) def knn(train, query, k, scaled): scale = make_scaler([point for point, _ in train]) if scaled else (lambda p: p) q = scale(query) ordered = sorted(train, key=lambda item: sum((a - b) ** 2 for a, b in zip(scale(item[0]), q))) votes = [label for _, label in ordered[:k]] return max(set(votes), key=votes.count) print(knn(train, (1.2, 2000), 1, False))print(knn(train, (1.2, 2000), 1, True))Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Sort the stored examples by squared distance to the query. | — | — | |
| Take the labels of the k nearest examples and vote. | — | — | |
| Unscaled, the second feature (differences of hundreds) swamps the first (differences below 4): the nearest point is a B. | — | B | |
| After min-max scaling both features count equally, and the nearest point is an A. | — | B A |
Cost and common mistakes
Prediction is O(n·d) for n stored examples with d features, or O(n·d + n log n) with the full sort used here. Training is O(1), just storing the data.
- Features on different scales distort distances. Scale them, using statistics computed on the training data only.
- k-NN is sensitive to irrelevant features, which add noise to every distance.
- Prediction needs a pass over all stored examples, so it gets slow on large data unless a spatial index is used.
Try it yourself
Why does the answer change when the features are scaled?
Reveal answer and reasoning
Without scaling, the distance is determined almost entirely by the feature with the large numeric range. Scaling puts both features on a 0 to 1 range so each contributes fairly.