Problem 215001 · medium · Level 02 Linear Data Structures

Who Is Most Alike Depends on the Scale

normalisation · min-max scaling · standardisation · distance

A club matches a new member with the existing member who is most alike. Each person is a row of numbers, for example [height in cm, yearly income in pounds], and "most alike" means the smallest Euclidean distance. But the answer depends on how the columns are scaled, so the club wants to see all three versions:

  1. raw: distances on the numbers as given;
  2. min-max: every column is mapped with (x - lo) / (hi - lo), where lo and hi are that column's minimum and maximum over rows;
  3. z-score: every column is mapped with (x - mean) / sd, with that column's mean and population standard deviation over rows.

The new member query is scaled with the same numbers as the rows (so its scaled values may fall outside the usual range). A column whose values in rows are all equal is mapped to 0.0 for everybody, including the query.

Write nearest_under_scalings(rows, query) that returns a tuple of three indices into rows: the nearest row under raw, min-max and z-score scaling. If two rows are equally near, the smaller index wins.

The setup provides people(n, seed), which returns n random rows [height, income, age].

Examples

Input:  rows = [[170, 32000], [185, 60000], [175, 76000], [185, 40000]], query = [170, 56000]
Output: (1, 0, 2)
Explanation: raw, the income gap decides everything, and row 1 is only 4000 pounds away.
Min-max maps heights by their range of 15 cm and incomes by their range of 44000 pounds;
now the query is (0.0, 0.545), row 0 is (0.0, 0.0) at distance 0.545, and row 2 is
(0.333, 1.0) at distance 0.564. With z-scores (height sd 6.50, income sd 17205)
row 2 is at 1.3943 and row 0 at 1.3950, so row 2 is nearest by a hair.

Constraints

  • 1 <= len(rows) <= 3000; every row and the query have the same length, between 1 and 10
  • all values are whole numbers with absolute value at most 10**7
  • the tests have no near-ties other than exact duplicate rows

Goals

  • Apply min-max scaling and standardisation to every column of a table
  • Scale a new point with the numbers learnt from the table
  • See how the choice of scale changes which point is nearest
Starting Python…