Computer vision: k nearest neighbours with a vote

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 print accuracy 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

Example 1 · Input
4 2 3
cat 0 0
cat 1 0
dog 5 5
dog 6 5
2
cat 1 1
dog 4 4
Expected output
predicted cat, true cat
predicted dog, true dog
accuracy 2 of 2
Example 2 · Input
3 1 3
a 0
b 10
b 12
1
a 1
Expected output
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 →