Voting among several neighbours makes nearest-neighbour classification more robust.
What to build
A program that classifies test images with k-NN and reports its accuracy.
Requirements
- Distance is the squared L2 distance, Σ (a − b)². The k nearest training images are chosen by distance, then by training order.
- The prediction is the label with the most votes among them; on a tie, the tied label whose member is nearest (earliest in the sorted neighbour list).
- For each test image print
predicted P, true T; finally printaccuracy A of M, where A counts correct predictions.
Input
Line 1: N, D and k. Then N lines label v1 … vD. Then M and M lines label v1 … vD (the true label first).
Output
M lines and the accuracy line.
Constraints
1 ≤ k ≤ N ≤ 200; D ≤ 400; M ≤ 200.
Example
Input:
4 2 3
cat 0 0
cat 1 0
dog 5 5
dog 6 5
2
cat 1 1
dog 4 4
Output:
predicted cat, true cat
predicted dog, true dog
accuracy 2 of 2
Why it works
A vote among several close neighbours outweighs one unusual or mislabelled example, and the tie rule keeps the answer well defined.
Examples
4 2 3 cat 0 0 cat 1 0 dog 5 5 dog 6 5 2 cat 1 1 dog 4 4
predicted cat, true cat predicted dog, true dog accuracy 2 of 2
3 1 3 a 0 b 10 b 12 1 a 1
predicted b, true a accuracy 0 of 1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the training indices by (squared distance, index) and keep the first k.
Hint 2
Count votes per label; among the labels with the most votes, choose the one that appears first in the sorted neighbour list.
Solution
Show one correct solution (try it yourself first)
n, d, k = map(int, input().split())
train = []
for _ in range(n):
parts = input().split()
train.append((parts[0], list(map(int, parts[1:]))))
m = int(input())
right = 0
for _ in range(m):
parts = input().split()
truth, x = parts[0], list(map(int, parts[1:]))
ranked = sorted(range(n), key=lambda i: (sum((a - b) ** 2 for a, b in zip(x, train[i][1])), i))[:k]
votes = {}
for i in ranked:
votes[train[i][0]] = votes.get(train[i][0], 0) + 1
top = max(votes.values())
guess = next(train[i][0] for i in ranked if votes[train[i][0]] == top)
right += guess == truth
print(f"predicted {guess}, true {truth}")
print(f"accuracy {right} of {m}")
Lesson: Classifying images with features and nearest neighbours →