K Nearest Neighbours

Implement k-nearest-neighbours classification with Euclidean distance.

For every row of X_test, find the k closest rows of X_train and return the most common label among them.

Two ties have to be resolved, and the tests check both:

• Distance ties. When two training points are the same distance away, the one with the lower index in X_train comes first.
• Vote ties. When two labels get the same number of votes, return the smaller label.

np.argsort(..., kind="stable") handles the first, since it keeps the original order of equal elements.

Try to avoid a Python loop over training points. The full distance matrix is one broadcast: X_test[:, None, :] - X_train[None, :, :].

Function signature

def knn_predict(X_train, y_train, X_test, k):

Example

Input

X_train = np.array([[0.0], [1.0], [4.0], [5.0]])
y_train = np.array([0, 0, 1, 1])
knn_predict(X_train, y_train, np.array([[0.5], [4.5]]), k=1)

Output

array([0, 1])

Reasoning

0.5 is the same distance from 0.0 and 1.0, so the lower index, 0.0, is chosen, with label 0. 4.5 is the same distance from 4.0 and 5.0, and 4.0 comes first, with label 1.

Constraints and notes

• On equal distances, the lower training index comes first.
• On a vote tie, return the smaller label.