outliar.js

/* A JavaScript port of outliar's detectors and metrics.
 *
 * The deployed demo is a *static* page: there is no server, so the same
 * benchmark has to run in the browser. Every function here mirrors the NumPy
 * implementation in src/outliar/{detectors,metrics}.py, and tests/test_parity.py
 * pins them together to 1e-9 by running this file under Node against the Python
 * results on a shared fixture.
 *
 * Isolation Forest is the one detector not ported — it needs scikit-learn's
 * fitted trees. The static demo omits it and says so.
 */
(function (root) {
  "use strict";

  const EPS = 1e-9;

  // ---------------------------------------------------------------- helpers
  function median(values) {
    if (!values.length) return 0;
    const sorted = Float64Array.from(values).sort();
    const mid = sorted.length >> 1;
    return sorted.length % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2;
  }

  function quantile(values, q) {
    if (!values.length) return 0;
    const sorted = Float64Array.from(values).sort();
    // Linear interpolation between order statistics — numpy's default.
    const pos = (sorted.length - 1) * q;
    const lo = Math.floor(pos), hi = Math.ceil(pos);
    return lo === hi ? sorted[lo] : sorted[lo] + (sorted[hi] - sorted[lo]) * (pos - lo);
  }

  function std(values) {
    if (!values.length) return 0;
    const mean = values.reduce((a, b) => a + b, 0) / values.length;
    let acc = 0;
    for (const v of values) acc += (v - mean) * (v - mean);
    return Math.sqrt(acc / values.length);
  }

  function robustScale(values) {
    const med = median(values);
    const scale = 1.4826 * median(Array.from(values, (v) => Math.abs(v - med)));
    if (scale >= EPS) return scale;
    const sd = std(values);
    return sd > EPS ? sd : 1.0;
  }

  /** Right-aligned rolling windows, front-padded by repeating the first value. */
  function rollingWindows(values, window) {
    const w = Math.max(2, Math.min(window, values.length));
    const padded = new Float64Array(values.length + w - 1);
    padded.fill(values[0], 0, w - 1);
    padded.set(values, w - 1);
    const out = [];
    for (let i = 0; i < values.length; i++) out.push(padded.subarray(i, i + w));
    return out;
  }

  function normalise(scores, probation) {
    const warm = Array.from(scores.slice(0, probation)).filter(Number.isFinite);
    const scale = warm.length ? robustScale(warm) : 1.0;
    return Float64Array.from(scores, (s) => {
      const v = s / (scale + EPS);
      return Number.isFinite(v) ? v : 0;
    });
  }

  const PROBATION_FRACTION = 0.15, PROBATION_MAX = 150;
  function probationLength(n) {
    return Math.min(PROBATION_MAX, Math.floor(PROBATION_FRACTION * n));
  }

  /** mulberry32 — a small seeded PRNG so the noise control is reproducible. */
  function seededRandom(seed) {
    let a = seed >>> 0;
    return function () {
      a = (a + 0x6d2b79f5) >>> 0;
      let t = Math.imul(a ^ (a >>> 15), 1 | a);
      t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
      return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
    };
  }

  // ---------------------------------------------------------------- detectors
  function randomScore(series, seed) {
    const rand = seededRandom((seed || 0) + series.values.length);
    return Float64Array.from({ length: series.values.length }, rand);
  }

  function constantScore(series) {
    return new Float64Array(series.values.length).fill(0.5);
  }

  function lastvalueScore(series) {
    const x = series.values, n = x.length;
    const diff = new Float64Array(n);
    for (let i = 1; i < n; i++) diff[i] = Math.abs(x[i] - x[i - 1]);
    return normalise(diff, probationLength(n));
  }

  function ewmaScore(series, seed, alpha) {
    alpha = alpha === undefined ? 0.05 : alpha;
    const x = series.values, n = x.length;
    const level = new Float64Array(n);
    level[0] = x[0];
    for (let t = 1; t < n; t++) level[t] = alpha * x[t - 1] + (1 - alpha) * level[t - 1];
    const residual = Float64Array.from(x, (v, i) => Math.abs(v - level[i]));
    return normalise(residual, probationLength(n));
  }

  function rollingMadScore(series, seed, window) {
    window = window || 96;
    const x = series.values, n = x.length;
    const probation = probationLength(n);
    const views = rollingWindows(x, window);
    const fallback = robustScale(Array.from(x.slice(0, probation)));
    const out = new Float64Array(n);
    for (let i = 0; i < n; i++) {
      const med = median(views[i]);
      let scale = 1.4826 * median(Array.from(views[i], (v) => Math.abs(v - med)));
      if (scale < EPS) scale = fallback;
      out[i] = Math.abs(x[i] - med) / (scale + EPS);
    }
    return normalise(out, probation);
  }

  function seasonalScore(series) {
    const x = series.values, n = x.length;
    const probation = probationLength(n);
    const buckets = 7 * 24;
    const key = new Int32Array(n);
    for (let i = 0; i < n; i++) {
      const d = new Date(series.timestamps[i]);
      key[i] = d.getUTCDay() === 0 ? 6 * 24 + d.getUTCHours()
        : (d.getUTCDay() - 1) * 24 + d.getUTCHours();
    }
    const fallback = median(Array.from(x.slice(0, probation || n)));
    const profile = new Float64Array(buckets).fill(fallback);
    const groups = new Map();
    for (let i = 0; i < probation; i++) {
      if (!groups.has(key[i])) groups.set(key[i], []);
      groups.get(key[i]).push(x[i]);
    }
    for (const [b, vals] of groups) profile[b] = median(vals);
    const residual = Float64Array.from(x, (v, i) => Math.abs(v - profile[key[i]]));
    return normalise(residual, probation);
  }

  /* Cyclic Jacobi eigendecomposition of a symmetric matrix.
   *
   * Power iteration was tried first and could not separate eigenvalues that
   * sit within a percent of each other — which is exactly what the tail of a
   * sliding-window covariance looks like once the signal has been explained.
   * Jacobi is exact to machine precision and needs no starting guess, and at
   * width 32 the O(width^3) cost is irrelevant.
   *
   * Returns eigenvectors as rows, sorted by descending eigenvalue.
   */
  function symmetricEigen(matrix, width, sweeps) {
    sweeps = sweeps || 60;
    const a = matrix.map((row) => Float64Array.from(row));
    const v = [];
    for (let i = 0; i < width; i++) {
      v.push(new Float64Array(width));
      v[i][i] = 1;
    }

    for (let sweep = 0; sweep < sweeps; sweep++) {
      let off = 0;
      for (let p = 0; p < width; p++)
        for (let q = p + 1; q < width; q++) off += a[p][q] * a[p][q];
      if (off < 1e-24) break;

      for (let p = 0; p < width - 1; p++) {
        for (let q = p + 1; q < width; q++) {
          if (Math.abs(a[p][q]) < 1e-300) continue;
          const theta = (a[q][q] - a[p][p]) / (2 * a[p][q]);
          const t = Math.sign(theta || 1) / (Math.abs(theta) + Math.sqrt(theta * theta + 1));
          const c = 1 / Math.sqrt(t * t + 1);
          const s = t * c;
          for (let i = 0; i < width; i++) {
            const aip = a[i][p], aiq = a[i][q];
            a[i][p] = c * aip - s * aiq;
            a[i][q] = s * aip + c * aiq;
          }
          for (let i = 0; i < width; i++) {
            const api = a[p][i], aqi = a[q][i];
            a[p][i] = c * api - s * aqi;
            a[q][i] = s * api + c * aqi;
          }
          for (let i = 0; i < width; i++) {
            const vip = v[i][p], viq = v[i][q];
            v[i][p] = c * vip - s * viq;
            v[i][q] = s * vip + c * viq;
          }
        }
      }
    }

    const order = Array.from({ length: width }, (_, i) => i).sort((x, y) => a[y][y] - a[x][x]);
    return order.map((idx) => {
      const vec = new Float64Array(width);
      for (let i = 0; i < width; i++) vec[i] = v[i][idx];
      // Fix the sign convention so the basis is reproducible run to run.
      let lead = 0;
      for (let i = 0; i < width; i++) {
        if (Math.abs(vec[i]) > Math.abs(vec[lead])) lead = i;
      }
      if (vec[lead] < 0) for (let i = 0; i < width; i++) vec[i] = -vec[i];
      return vec;
    });
  }

  /** Top-k right singular vectors of `rows`, via the eigenvectors of X'X. */
  function topSubspace(rows, width, k) {
    const cov = [];
    for (let i = 0; i < width; i++) cov.push(new Float64Array(width));
    for (const row of rows) {
      for (let a = 0; a < width; a++) {
        const va = row[a];
        if (!va) continue;
        for (let b = a; b < width; b++) cov[a][b] += va * row[b];
      }
    }
    for (let a = 0; a < width; a++) for (let b = 0; b < a; b++) cov[a][b] = cov[b][a];
    return symmetricEigen(cov, width).slice(0, k);
  }

  function windowPcaScore(series, seed, window, rank) {
    window = window || 32;
    rank = rank || 3;
    const x = series.values, n = x.length;
    const probation = Math.max(window + 1, probationLength(n));
    const views = rollingWindows(x, window);
    const width = views[0].length;

    const centre = new Float64Array(width);
    for (let i = 0; i < probation; i++)
      for (let j = 0; j < width; j++) centre[j] += views[i][j] / probation;

    const warmFlat = [];
    for (let i = 0; i < probation; i++)
      for (let j = 0; j < width; j++) warmFlat.push(views[i][j] - centre[j]);
    const scale = robustScale(warmFlat);

    const warmRows = [];
    for (let i = 0; i < probation; i++) {
      const row = new Float64Array(width);
      for (let j = 0; j < width; j++) row[j] = (views[i][j] - centre[j]) / scale;
      warmRows.push(row);
    }
    const k = Math.min(rank, Math.min(warmRows.length, width) - 1, width);
    if (k < 1) return new Float64Array(n);
    const basis = topSubspace(warmRows, width, k);

    const out = new Float64Array(n);
    const centred = new Float64Array(width);
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < width; j++) centred[j] = (views[i][j] - centre[j]) / scale;
      const recon = new Float64Array(width);
      for (const vec of basis) {
        let dot = 0;
        for (let j = 0; j < width; j++) dot += centred[j] * vec[j];
        for (let j = 0; j < width; j++) recon[j] += dot * vec[j];
      }
      let acc = 0;
      for (let j = 0; j < width; j++) {
        const d = centred[j] - recon[j];
        acc += d * d;
      }
      out[i] = Math.sqrt(acc);
    }
    return normalise(out, probationLength(n));
  }

  const DETECTORS = {
    random: randomScore,
    constant: constantScore,
    lastvalue: lastvalueScore,
    ewma: ewmaScore,
    rolling_mad: rollingMadScore,
    seasonal: seasonalScore,
    window_pca: windowPcaScore,
  };

  const CONTROLS = new Set(["random", "constant", "lastvalue"]);

  const DESCRIPTIONS = {
    random: "Uniform noise — never looks at the data",
    constant: "Untrained: one flat score everywhere",
    lastvalue: "|x_t − x_{t−1}|, no fitting",
    ewma: "EWMA one-step residual",
    rolling_mad: "Trailing median/MAD robust z-score",
    seasonal: "Time-of-day × day-of-week profile residual",
    window_pca: "Low-rank subspace reconstruction error",
  };

  // ---------------------------------------------------------------- metrics
  function contiguousRuns(mask) {
    const runs = [];
    let start = -1;
    for (let i = 0; i < mask.length; i++) {
      if (mask[i] && start < 0) start = i;
      else if (!mask[i] && start >= 0) { runs.push([start, i - 1]); start = -1; }
    }
    if (start >= 0) runs.push([start, mask.length - 1]);
    return runs;
  }

  function prf(tp, fp, fn) {
    const precision = tp + fp > 0 ? tp / (tp + fp) : 0;
    const recall = tp + fn > 0 ? tp / (tp + fn) : 0;
    const f1 = precision + recall > 1e-12
      ? (2 * precision * recall) / (precision + recall) : 0;
    return { precision, recall, f1, tp, fp, fn };
  }

  function pointF1(yTrue, yPred) {
    let tp = 0, fp = 0, fn = 0;
    for (let i = 0; i < yTrue.length; i++) {
      if (yTrue[i] && yPred[i]) tp++;
      else if (!yTrue[i] && yPred[i]) fp++;
      else if (yTrue[i] && !yPred[i]) fn++;
    }
    return prf(tp, fp, fn);
  }

  function adjustPredictions(yTrue, yPred, k) {
    k = k || 0;
    const adjusted = Array.from(yPred, Boolean);
    for (const [s, e] of contiguousRuns(yTrue)) {
      let hits = 0;
      for (let i = s; i <= e; i++) if (adjusted[i]) hits++;
      const length = e - s + 1;
      if (hits > 0 && hits / length > k) for (let i = s; i <= e; i++) adjusted[i] = true;
    }
    return adjusted;
  }

  function paF1(yTrue, yPred, k) {
    return pointF1(yTrue, adjustPredictions(yTrue, yPred, k));
  }

  function eventRecall(yTrue, yPred) {
    const windows = contiguousRuns(yTrue);
    let caught = 0;
    for (const [s, e] of windows) {
      for (let i = s; i <= e; i++) if (yPred[i]) { caught++; break; }
    }
    return [caught, windows.length - caught];
  }

  function compositeF1(yTrue, yPred) {
    let tpT = 0, fpT = 0;
    for (let i = 0; i < yTrue.length; i++) {
      if (yPred[i]) (yTrue[i] ? tpT++ : fpT++);
    }
    const precision = tpT + fpT > 0 ? tpT / (tpT + fpT) : 0;
    const [tpE, fnE] = eventRecall(yTrue, yPred);
    const recall = tpE + fnE > 0 ? tpE / (tpE + fnE) : 0;
    const f1 = precision + recall > 1e-12
      ? (2 * precision * recall) / (precision + recall) : 0;
    return { precision, recall, f1, tp: tpE, fp: fpT, fn: fnE };
  }

  function allProtocols(yTrue, yPred) {
    return {
      point: pointF1(yTrue, yPred),
      pa: paF1(yTrue, yPred, 0),
      pa20: paF1(yTrue, yPred, 0.2),
      pa50: paF1(yTrue, yPred, 0.5),
      composite: compositeF1(yTrue, yPred),
    };
  }

  function candidateThresholds(scores, n) {
    n = n || 200;
    const finite = Array.from(scores).filter(Number.isFinite);
    if (!finite.length) return [0];
    const grid = [];
    for (let i = 0; i < n; i++) grid.push(quantile(finite, i / (n - 1)));
    const unique = Array.from(new Set(grid)).sort((a, b) => a - b);
    unique.push(Math.max(...finite) + 1e-9);
    return unique;
  }

  function sweep(yTrue, scores, nGrid) {
    const best = {};
    for (const name of ["point", "pa", "pa20", "pa50", "composite"]) {
      best[name] = [Infinity, { f1: 0 }];
    }
    for (const threshold of candidateThresholds(scores, nGrid)) {
      const yPred = Array.from(scores, (s) => s >= threshold);
      const results = allProtocols(yTrue, yPred);
      for (const name in results) {
        if (results[name].f1 > best[name][1].f1) best[name] = [threshold, results[name]];
      }
    }
    return best;
  }

  function falseAlarmsPerDay(yTrue, yPred, samplingMinutes) {
    let runs = 0;
    for (const [s, e] of contiguousRuns(yPred)) {
      let overlaps = false;
      for (let i = s; i <= e; i++) if (yTrue[i]) { overlaps = true; break; }
      if (!overlaps) runs++;
    }
    const days = (yTrue.length * samplingMinutes) / (60 * 24);
    return days > 0 ? runs / days : 0;
  }

  // ---------------------------------------------------------------- NAB
  function parseCsv(text) {
    const lines = text.trim().split("\n");
    const timestamps = [], values = [];
    for (let i = 1; i < lines.length; i++) {
      const comma = lines[i].indexOf(",");
      if (comma < 0) continue;
      timestamps.push(lines[i].slice(0, comma).trim());
      values.push(parseFloat(lines[i].slice(comma + 1)));
    }
    return { timestamps, values: Float64Array.from(values) };
  }

  /** NAB window bounds are timestamps; map them onto index positions. */
  function windowsToIndices(timestamps, windows) {
    const ms = timestamps.map((t) => Date.parse(t.replace(" ", "T") + "Z"));
    const out = [];
    for (const [startS, endS] of windows) {
      const start = Date.parse(startS.replace(" ", "T").split(".")[0] + "Z");
      const end = Date.parse(endS.replace(" ", "T").split(".")[0] + "Z");
      let first = -1, last = -1;
      for (let i = 0; i < ms.length; i++) {
        if (ms[i] >= start && ms[i] <= end) { if (first < 0) first = i; last = i; }
      }
      if (first >= 0) out.push([first, last]);
    }
    return out;
  }

  function pointLabels(n, windows) {
    const y = new Array(n).fill(false);
    for (const [s, e] of windows) for (let i = s; i <= e; i++) y[i] = true;
    return y;
  }

  function samplingMinutes(timestamps) {
    if (timestamps.length < 2) return 5;
    const deltas = [];
    for (let i = 1; i < Math.min(timestamps.length, 200); i++) {
      deltas.push(
        (Date.parse(timestamps[i].replace(" ", "T") + "Z") -
          Date.parse(timestamps[i - 1].replace(" ", "T") + "Z")) / 60000
      );
    }
    return median(deltas);
  }

  root.outliar = {
    median, quantile, robustScale, rollingWindows, normalise, probationLength,
    DETECTORS, CONTROLS, DESCRIPTIONS,
    contiguousRuns, pointF1, adjustPredictions, paF1, compositeF1, eventRecall,
    allProtocols, candidateThresholds, sweep, falseAlarmsPerDay,
    parseCsv, windowsToIndices, pointLabels, samplingMinutes,
  };
})(typeof globalThis !== "undefined" ? globalThis : this);

if (typeof module !== "undefined" && module.exports) module.exports = globalThis.outliar;