monitor.anomaly

def detect_anomaly(history: Sequence[int], value: int, method: AnomalyMethod, threshold_hundredths: int) -> Anomaly

AnomalyMethod = Literal["stddev", "mad"]

AnomalyDirection = Literal["high", "low", "normal"]

@dataclass(frozen=True)
class Anomaly:
    """The verdict, with the numbers behind it."""

    anomaly: bool
    #: high or low when an anomaly, else normal
    direction: AnomalyDirection
    #: mean (half-up) or median, x1000
    center_milli: int
    #: population standard deviation or MAD, x1000, floored
    spread_milli: int
    #: |z| or |modified z|, x100, floored; null when the spread is 0
    score_hundredths: Optional[int]

from fune.monitor.anomaly import detect_anomaly  # monitor.anomaly@^1

import math
from typing import List, Optional, Sequence

from .monitor_anomaly_types import Anomaly, AnomalyMethod


def _half_up(n: int, d: int) -> int:
    # Half-up with halves away from zero, as math.round-div rounds.
    q = (2 * abs(n) + d) // (2 * d)
    return -q if n < 0 else q


def _median_twice(ordered: List[int]) -> int:
    m = len(ordered) // 2
    return 2 * ordered[m] if len(ordered) % 2 == 1 else ordered[m - 1] + ordered[m]


def detect_anomaly(history: Sequence[int], value: int, method: AnomalyMethod, threshold_hundredths: int) -> Anomaly:
    """Whether `value` is an outlier against `history`, by z-score (`stddev`) or
    by Iglewicz and Hoaglin's modified z-score (`mad`). Exact integer
    arithmetic: the threshold comparison never depends on float rounding."""
    if len(history) < 2:
        raise ValueError("history must have at least 2 values, received %d" % len(history))
    if threshold_hundredths < 1:
        raise ValueError("thresholdHundredths must be at least 1, received %d" % threshold_hundredths)
    n = len(history)
    t = threshold_hundredths
    score: Optional[int]
    if method == "stddev":
        s = sum(history)
        ss = sum(x * x for x in history)
        # n^2 * variance and n * (value - mean), both whole numbers.
        q = n * ss - s * s
        signed = n * value - s
        center = _half_up(s * 1000, n)
        spread = math.isqrt(1000000 * q) // n
        if q == 0:
            anomaly = signed != 0
            score = None
        else:
            anomaly = 10000 * signed * signed > t * t * q
            score = math.isqrt((10000 * signed * signed) // q)
    elif method == "mad":
        # Twice the median and four times the MAD are whole numbers.
        med2 = _median_twice(sorted(history))
        mad4 = _median_twice(sorted(abs(2 * x - med2) for x in history))
        signed = 2 * value - med2
        center = med2 * 500
        spread = mad4 * 250
        if mad4 == 0:
            anomaly = signed != 0
            score = None
        else:
            # |M| = 0.6745 * |2v - med2| / 2 / (mad4 / 4) = 1349 * |signed| / (1000 * mad4)
            anomaly = 1349 * abs(signed) * 100 > t * 1000 * mad4
            score = (1349 * abs(signed) * 100) // (1000 * mad4)
    else:
        raise ValueError("unknown anomaly method: %s" % method)
    direction = "normal" if not anomaly else ("high" if signed > 0 else "low")
    return Anomaly(anomaly=anomaly, direction=direction, center_milli=center, spread_milli=spread, score_hundredths=score)

Install

fune build

With that line in your source, in a Python project (language python in fune.project), fune build resolves it and nothing else, pins them in fune.lock, downloads only the Python package of each, and builds the code above into your project’s .fune/build, one readable file per capability with a header linking back here. Or pin a range in fune.project and build in one step:

fune add monitor.anomaly

The manifest, vectors and README with only the Python implementation. Install it without the registry with fune add ./monitor.anomaly-1.0.0-python.fune, or fetch it from a terminal with fune pull monitor.anomaly@1.0.0:python.

The whole function, every language, is one file too: monitor.anomaly-1.0.0.fune, 20,303 bytes, sha256 e8a9775aeb313d5da72d056bf055ca3a55eb60349a14667fe8ac2521749c8642. It installs into a project of any language.

# fune: before monitor.anomaly

# fune: after monitor.anomaly

# fune: step monitor.anomaly after <n|label>

More from the author

## Which to use

The mean and standard deviation are themselves dragged by the outliers you are looking for: one spike in the history inflates the standard deviation and hides the next spike. The median and MAD barely move. With history 10, 11, 12, 13, 50, a new value of 30 scores 0.69 by `stddev` (normal) but 12.14 by `mad` (an anomaly). Use `mad` for anything spiky, which is most operational metrics; `stddev` for smooth, roughly normal ones.

## Exact, not floating point

Everything is integer arithmetic (BigInt in TypeScript, i128 in Rust), so the three languages agree to the last digit and the comparison with the threshold is exact: a z of exactly 3.00 against a threshold of 300 is not an anomaly (`>`, not `>=`), in every language. The reported numbers are rounded as the manifest says: `centerMilli` half-up (halves away from zero), `spreadMilli` and `scoreHundredths` floored. The 0.6745 constant is used as exactly 6745/10000. In Rust, sums of squares must stay under 2^127: values up to about 10^15 with thousands of history points are fine.

## Zero spread

When the history is flat (standard deviation 0) or more than half of it is the same value (MAD 0), there is no scale to measure against: any value different from the center is an anomaly and equal is normal, and the score is null. Iglewicz and Hoaglin note this weakness of the MAD; feed it a longer or more varied history if it matters.

## Errors

- `history must have at least 2 values, received 1` - `thresholdHundredths must be at least 1, received 0` - `unknown anomaly method: iqr`

## Sources

- Boris Iglewicz and David C. Hoaglin (1993), *How to Detect and Handle Outliers*, ASQC Quality Press (ASQC Basic References in Quality Control, vol. 16): the modified z-score and the 3.5 threshold. Summarised by NIST/SEMATECH e-Handbook of Statistical Methods, 1.3.5.17 "Detection of Outliers", https://www.itl.nist.gov/div898/handbook/eda/section3/eda35h.htm

Files