k-Nearest Neighbors Classifier
k-Nearest Neighbors Classifier
Every other model on this site *compresses* the training set into parameters. k-NN throws that idea out: it keeps all the data and defers every decision to prediction time. There is no training loop and no loss function: the "model" is the dataset.
That makes k-NN the standard baseline you run before anything else, and it makes its failure modes worth knowing: prediction cost grows with the training set, and distances become meaningless in high dimensions.
The algorithm. For each test point :
1. Compute the Euclidean distance to every training point: .
2. Take the training points with the smallest distances.
3. Predict the label that appears most often among those neighbors.
Worked example ():
X_train = [[0,0], [1,0], [0,1], [5,5], [6,5]] y_train = [ 0, 0, 0, 1, 1 ] x_test = [0.5, 0.5] distances = [0.707, 0.707, 0.707, 6.364, 7.649] 3 nearest -> labels [0, 0, 0] -> predict 0
Tie-breaking rule: if two or more labels receive the same number of votes, predict the smallest label. Without a fixed rule the output is not reproducible, and non-reproducible predictions are a real production bug.
Your task:
Implement knn_predict(X_train, y_train, X_test, k).
X_train has shape (n_train, n_features), X_test has shape (n_test, n_features).y_train is a 1D array of integer labels.n_test predicted labels.Hint: broadcasting gives you the whole distance matrix in one line: X_test[:, None, :] - X_train[None, :, :]. You never need np.sqrt to *rank* distances, but it costs nothing here.
Example Tests
k=3, two well-separated clusters: point near the origin cluster
Input: {"k":3,"X_test":[[0.5,0.5]],"X_train":[[0,0],[1,0],[0,1],[5,5],[6,5]],"y_train":[0,0,0,1,1]}
Expected: [0]
k=1 reduces to nearest-neighbor lookup
Input: {"k":1,"X_test":[[5.2,5.1],[0.1,0.2]],"X_train":[[0,0],[1,0],[0,1],[5,5],[6,5]],"y_train":[0,0,0,1,1]}
Expected: [1,0]
Larger k pulls in the majority class across the boundary
Input: {"k":5,"X_test":[[4,4]],"X_train":[[0,0],[1,0],[0,1],[5,5],[6,5]],"y_train":[0,0,0,1,1]}
Expected: [0]