Problem 663817 · medium · Level 06 Heuristics & Optimization

Readings Far From Any Normal Neighbour

anomaly detection · k-nearest neighbours · standardisation · percentile threshold · leave-one-out

The z-score alarm misses readings whose values are each normal but whose combination never happens (hot but barely vibrating). A reading that lies in a crowded part of the normal data has close normal neighbours; a strange one does not. Build that detector.

Write neighbour_alarm(normal, readings, k, share) that returns a tuple (threshold, flags):

  1. Standardise with the statistics of normal: every feature minus its mean, divided by its standard deviation (divide by n inside the square root). Apply the same transformation to the new readings.
  2. The score of a standardised point is the Euclidean distance to its k-th nearest standardised normal reading.
  3. Threshold: score every normal reading the same way, but leave the reading itself out of its own neighbours. Sort these n scores in increasing order; the threshold is the one at position int(share * n) (or the last one if that position is past the end).
  4. flags[i] is True if the score of readings[i] is greater than the threshold (a new reading is compared with all n normal readings).

machine_log(n, seed) gives normal readings [temperature, vibration, current] of the kind the tests use; it is available in your code.

Examples

Input:  normal = [[0, 0], [1, 0], [0, 1], [1, 1], [0.5, 0.5], [3, 3]],
        readings = [[0.5, 0.4], [2, 2], [1, 3]], k = 1, share = 0.5
Output: (0.6951413356361907, [False, True, True])

Input:  normal = machine_log(200, 1), readings = [[50.2, 4.9, 13.0], [75.0, 8.3, 19.0], [59.0, 2.6, 17.5],
        [43.0, 7.5, 9.0], [58.1, 7.6, 17.1]], k = 5, share = 0.99
Output: (0.6843816307484193, [False, True, True, True, False])
Explanation: the three strange readings are all flagged, and the two ordinary ones are not.

Constraints

  • 2 <= len(normal) <= 400, 1 to 6 features, no feature is constant in normal
  • 1 <= k <= len(normal) - 1, 0 <= share <= 1, 0 <= len(readings) <= 400
  • floats are compared with a tolerance of 1e-6

Goals

  • Score a reading by its distance to the k-th nearest normal reading
  • Set the alarm threshold from the scores of the normal data itself, leaving each reading out
  • Catch unusual combinations of values that per-feature checks miss
Starting Python…