The bird-call app from before has to decide how many neighbours should vote. Its developers put aside a validation set of labelled calls that the model does not learn from, and try a list of candidate values ks.
Write choose_k(X_train, y_train, X_val, y_val, ks) that returns a tuple (best_k, accuracies):
accuracies[i]is the share of validation calls that the vote of theks[i]nearest training calls labels correctly;best_kis the value inkswith the highest accuracy; among equal accuracies (exactly equal numbers of correct calls), the smallestk.
The vote is the one of the first problem: training calls ordered by Euclidean distance, equal distances by index; the label with the most votes wins, and among labels with equally many votes, the one whose first neighbour comes earliest. If k exceeds the training set, all calls vote.
The setup provides bird_calls(n, seed), which returns (X, y) with whole-number rows [pitch, length] and species "wren", "robin" or "finch".
Examples
Input: X_train = [[0], [1], [2], [3], [7], [8]], y_train = ["a", "b", "a", "a", "b", "b"]
X_val = [[1.2], [0.9], [6], [2.5]], y_val = ["a", "a", "b", "a"], ks = [1, 3, 5, 6]
Output: (3, [0.5, 1.0, 1.0, 0.5])
Explanation: with k = 1 the odd "b" at [1] decides both of the first two calls. With k = 3 and
k = 5 every call is right, and 3 is the smaller. With k = 6 all six vote, "a" and "b" tie 3 to 3,
and the label of the nearest neighbour wins: "b" for the first two calls.
Constraints
1 <= len(X_train) <= 400,1 <= len(X_val) <= 300,1 <= len(ks) <= 60,1 <= ks[i] <= 1000, values inksare distinct- rows have the same length (1 to 5)
- each test must finish in well under a second in your browser: finding the neighbours of every validation call again for each
kis too slow for the larger tests
Goals
- Measure how the accuracy of k-nearest neighbours changes with k on a validation set
- Choose k on validation data rather than the test data
- Sort the neighbours of each validation example once and reuse the order for every k