k-Nearest Neighbours Classifier - Supervised Learning

k-Nearest Neighbours Classifier

Implement knn_predict(X_train, y_train, X_test, k): classify each query point by a majority vote of its k nearest training points under Euclidean distance.

Background

k-NN is the canonical lazy learner: "training" is just storing the data, and all the work happens at prediction time. It is a strong baseline, the core of retrieval and recommendation systems (with approximate nearest-neighbour indexes), and a favourite interview question because it tests vectorised distance computation and careful tie-breaking.

Algorithm

For every query x in X_test:

1. Compute the Euclidean distance to every training point:

d(x, x_i) = sqrt( sum_j (x_j - x_ij)^2 )

2. Take the k nearest training points. If several are at the same distance, the one with the smaller training index comes first (a stable sort: np.argsort(d, kind='stable')).
3. Count the labels of those k neighbours and predict the most common one.
4. Vote ties: if two or more classes share the top count, predict the smallest label among them.

All pairwise distances at once, via broadcasting:

diff = X_test[:, None, :] - X_train[None, :, :]   # (m, n, d)
D = np.sqrt((diff ** 2).sum(axis=-1))             # (m, n)

Inputs

• X_train: float array (n, d)
• y_train: non-negative integer labels (n,) (so np.bincount works for the vote)
• X_test: float array (m, d)
• k: int with 1 <= k <= n

Expected Return Format

An integer NumPy array of shape (m,): the predicted label of each query.

Edge Cases and Conventions

• k = 1 is the nearest-neighbour rule; k = n gives every query the overall majority class.
• scikit-learn's KNeighborsClassifier(n_neighbors=k) (uniform weights) also resolves vote ties to the smallest label. For distance ties its docs say the result depends on the order of the training data; here the order is pinned down by the stable sort.
• Features on different scales dominate the distance, so in practice you standardise first (not needed for the tests).

Constraints

• NumPy only; no sklearn or scipy. Compute the distance matrix without Python loops; a loop over queries for the vote is fine.

Follow-up

• The (m, n, d) difference tensor can be huge. Rewrite the squared distances as ||a||^2 - 2 a·b + ||b||^2 to need only (m, n) memory. What numerical issue appears, and how do you guard against it?
• How do KD-trees or approximate indexes (HNSW, IVF) cut the O(m n d) query cost?

Input: knn_predict(np.array([[0, 0], [1, 0], [0, 1], [5, 5], [6, 5]]), np.array([0, 0, 0, 1, 1]), np.array([[0.5, 0.5], [5.5, 5]]), k=3)
Output: array([0, 1])

Input: knn_predict(np.array([[0], [2]]), np.array([1, 0]), np.array([[1]]), k=2)
Output: array([0])

import numpy as np

def knn_predict(X_train, y_train, X_test, k=3):
    """
    k-nearest neighbours classification with Euclidean distance.

    Args:
        X_train: Training features, shape (n, d)
        y_train: Non-negative integer labels, shape (n,)
        X_test: Query points, shape (m, d)
        k: Number of neighbours (1 <= k <= n)

    Returns:
        Predicted labels, int array of shape (m,)
        (distance ties -> smaller training index first;
         vote ties -> smallest label)
    """
    # Your code here
    pass