Problem 398582 · medium · Level 03 Linear Management & Searching

Seconds Should Not Outvote Acidity

feature scaling · standardisation · k-nearest neighbours · data leakage

A roastery labels each batch of coffee "light", "medium" or "dark", and wants a program to guess the label of new batches from four measurements: drum temperature (°C), roast time (seconds), acidity (pH) and the grinder setting. The roast time is in the hundreds, the acidity changes in the second decimal place, so plain distances are decided by the seconds alone.

Write scaled_knn(X_train, y_train, X_test, k) that returns one label per row of X_test:

  1. For every feature j, compute the mean m and the population standard deviation s (divide by n) of that feature over X_train only.
  2. Features with s == 0 are dropped. Every other value v of feature j, in the training rows and in the test rows alike, becomes (v - m) / s with the training m and s.
  3. Predict each test row by the vote of its k nearest scaled training rows (Euclidean distance): equal distances are ordered by training index, smaller first; if several labels share the most votes, the one whose first neighbour comes earliest wins. If k exceeds the training set, all rows vote. If every feature is dropped, all training rows are at distance 0.

The setup provides roast_log(n, seed), which returns (X, y) with rows [temperature, seconds, pH, grinder]; the grinder setting is always 5.

Examples

Input:  X_train = [[1, 100, 7], [2, 280, 7], [3, 320, 7], [4, 140, 7]]
        y_train = ["low", "low", "high", "high"]
        X_test  = [[3, 270, 9], [1.5, 300, 7]], k = 1
Output: ["high", "low"]
Explanation: the third feature is constant and is dropped. Feature 0 has m = 2.5 and s = 1.118,
feature 1 has m = 210 and s = 92.2. [3, 270] becomes [0.447, 0.651]; the nearest scaled row is
row 2, [0.447, 1.193]. Without scaling, row 1 would be nearest (270 is close to 280).

Constraints

  • 1 <= len(X_train) <= 400, 0 <= len(X_test) <= 300, 1 <= k <= 1000, rows have 1 to 6 features
  • the tests contain no near-ties between different distances, so the order of floating-point operations does not change the answers

Goals

  • Standardise every feature with the mean and standard deviation of the training data
  • Scale new examples with the training statistics, never their own
  • Drop a feature that is constant in the training data
  • Run k-nearest neighbours on the scaled features
Starting Python…