KNN Classifier

Task

Implement class KNNClassifier(k: int). Implement an end-to-end multiclass K-nearest-neighbors classifier with stored training state, batched squared Euclidean distance, deterministic neighbors, probabilities, and predictions.

Requirements

• Require k to be a positive integer.
• fit(x, targets) copies the training features into x_train, labels into y_train, and stores sorted unique labels in classes.
• Use squared Euclidean distance; taking a square root is unnecessary because it does not change neighbor order.
• When distances tie, preserve the original training-row order.
• When k exceeds the number of training rows, use every available row.
• predict_proba(x) returns vote fractions with columns ordered by classes.
• predict(x) chooses the class with the largest vote fraction; a vote tie chooses the smallest class label.
• Do not add backward or gradient state because KNN does not optimize parameters.

Example

model = KNNClassifier(k=1)
model.fit(
    np.array([[0.0, 0.0], [2.0, 2.0], [10.0, 10.0]]),
    np.array([4, 2, 7]),
)
model.predict(np.array([[0.1, 0.2], [9.0, 9.0]]))
# array([4, 7])