Ask the Nearest Leaves

A garden centre identifies leaves from two measurements, length and width in centimetres, by comparing each new leaf with leaves it has already labelled. That is K-Nearest Neighbors: no formula is learned; every prediction is a fresh look at the stored examples.

To classify one new point, KNN:

1. measures the straight-line (Euclidean) distance from the new point to every training point, using all of the features;
2. takes the $k$ closest training points, its nearest neighbours;
3. lets each of those $k$ neighbours cast one vote for its own label;
4. predicts the label with the most votes.

Real data needs two tie rules, and you must follow both exactly:

• Equal distances. If two training points are exactly the same distance from the new point, the one with the smaller index in X_train counts as nearer. This decides which points make it into the $k$.
• Equal votes. If two or more labels share the top vote count, the winner is the tied label whose neighbour is closest to the new point: go through the $k$ neighbours from nearest to farthest (in the order the first rule fixes) and take the first one whose label is tied for the top.

Task: write knn_classify(X_train, y_train, queries, k).

• X_train is a list of points, each a list of numbers; y_train holds one label per point. Labels may be strings or integers.
• queries is a list of new points with the same number of features.
• k is a whole number from 1 up to the number of training points.

Return a list with one predicted label per query, in the same order as queries.