K-Nearest Neighbors Classifiermedium

K-Nearest Neighbors Classifier

medium Classical ML from Scratch 15–20 min

NumPy allowed · plain Python earns 10 bonus points

Implement k-nearest neighbors classification with majority voting from scratch.

Related Skills

Task

Implement knn_classify(X_train, y_train, X_test, k): for each test sample, compute Euclidean distance to all training samples, find the k nearest neighbors, and return the majority label.

Function Signature

knn_classify(X_train: list[list[float]], y_train: list[int], X_test: list[list[float]], k: int) -> list[int]

Examples

Example 1: 2D 4 Train Points k=3
Input: X_train = [[0, 0], [0, 1], [5, 5], [5, 6]]
y_train = [0, 0, 1, 1]
X_test = [[0.1, 0.2], [4.9, 5.1]]
k = 3
Output: [0, 1]

Example 2: Nearest Neighbor k=1
Input: X_train = [[1], [2], [10]]
y_train = [0, 0, 1]
X_test = [[1.9]]
k = 1
Output: [0]

Constraints

1 <= len(X_train) <= 500
1 <= len(X_test) <= 100
1 <= k <= len(X_train)

Python3Saved ✓

def knn_classify(X_train: list[list[float]], y_train: list[int], X_test: list[list[float]], k: int) -> list[int]:

"""X_train: training features (n_train x d).

y_train: training integer labels.

X_test: test features (n_test x d).

k: odd integer number of neighbors.

For each test point, predict class label by majority vote among k nearest Euclidean neighbors.

Break vote ties by choosing the smaller label. Return list of predicted labels."""

# Your implementation here

pass

Case 1: 2D 4 Train Points k=3

Input: X_train = [[0, 0], [0, 1], [5, 5], [5, 6]]
y_train = [0, 0, 1, 1]
X_test = [[0.1, 0.2], [4.9, 5.1]]
k = 3

Expected: [0, 1]

Case 2: Nearest Neighbor k=1

Input: X_train = [[1], [2], [10]]
y_train = [0, 0, 1]
X_test = [[1.9]]
k = 1

Expected: [0]