Unscaled features let the one with the largest units decide everything. Scale first, using the training data's ranges, then vote.
What to build
A program that min-max scales two features and classifies queries with k-nearest neighbours.
Requirements
- Scale each feature as (x − min) / (max − min), with min and max from the training points. If a feature's max equals its min, its scaled value is 0 for every point, queries included.
- Use the Euclidean distance on the scaled features; equally distant training points are ordered by their position in the input.
- Predict the most common label among the k nearest; if labels tie, choose the tied label that appears first among the sorted neighbours.
Input
Line 1: n and k. Then n lines f1 f2 label. Then q and q lines f1 f2.
Output
One label per query.
Constraints
1 ≤ k ≤ n ≤ 200; 1 ≤ q ≤ 50; queries may fall outside the training range.
Example
Input:
6 3
150 7.0 apple
170 7.5 apple
140 6.8 apple
130 7.2 orange
120 6.5 orange
125 7.0 orange
2
135 7.1
160 7.0
Output:
orange
apple
Why it works
Scaling with the training ranges gives each feature the same weight in the distance, and using the same numbers for queries keeps them on the scale the model knows.
Examples
6 3 150 7.0 apple 170 7.5 apple 140 6.8 apple 130 7.2 orange 120 6.5 orange 125 7.0 orange 2 135 7.1 160 7.0
orange apple
2 1 0 0 x 100 1 y 1 60 0
x
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Find each feature's min and max over the training points only, and scale training points and queries with them.
Hint 2
Sort the neighbours by (distance, position in the training list) and take the first k.
Hint 3
On a tied vote, the label whose member comes first in that sorted list wins.
Solution
Show one correct solution (try it yourself first)
n, k = map(int, input().split())
train = [input().split() for _ in range(n)]
points = [(float(a), float(b)) for a, b, _ in train]
labels = [row[2] for row in train]
q = int(input())
queries = [tuple(map(float, input().split())) for _ in range(q)]
ranges = []
for f in range(2):
values = [p[f] for p in points]
ranges.append((min(values), max(values)))
def scale(p):
return [(v - lo) / (hi - lo) if hi > lo else 0.0 for v, (lo, hi) in zip(p, ranges)]
scaled = [scale(p) for p in points]
for query in queries:
s = scale(query)
order = sorted(range(n), key=lambda i: (sum((a - b) ** 2 for a, b in zip(scaled[i], s)), i))[:k]
counts = {}
for i in order:
counts[labels[i]] = counts.get(labels[i], 0) + 1
top = max(counts.values())
print(next(labels[i] for i in order if counts[labels[i]] == top))