Online Outlier Detection in a Data Stream

Worked Solution

How to Think About It: The core challenge is that you cannot look at the whole dataset -- you only see one point at a time and need to decide right now whether it is anomalous. The classic offline approach (compute the full-sample mean and standard deviation, flag anything beyond 3 standard deviations) is not available because you do not have the full sample. So you need running statistics that update incrementally. The natural idea is to maintain a running mean and variance, then flag a new point if it is too far from the current mean relative to the current spread. This is essentially a sequential z-score test.

Key Insight: Welford's online algorithm lets you maintain exact running mean and variance in $O(1)$ time and space per update, without storing any past data. Combined with a z-score threshold, this gives you a simple, principled outlier detector.

The Method:

1. Initialize: Set $n = 0$, $\mu_0 = 0$, $M_0 = 0$. Choose a threshold $k$ (typically $k = 3$).

2. On receiving observation $x_n$: - Compute the z-score against the *previous* statistics: $z = |x_n - \mu_{n-1}| \,/\, \sigma_{n-1}$, where $\sigma_{n-1} = \sqrt{M_{n-1} / (n-1)}$. - If $z > k$, flag $x_n$ as an outlier. - Update the running statistics using Welford's recurrence:

$\mu_n = \mu_{n-1} + \frac{x_n - \mu_{n-1}}{n}$

$M_n = M_{n-1} + (x_n - \mu_{n-1})(x_n - \mu_n)$

$\sigma_n^2 = \frac{M_n}{n}$

1. Outlier definition: A point $x_n$ is an outlier if it falls more than $k$ standard deviations from the running mean, i.e., $|x_n - \mu_{n-1}| > k \cdot \sigma_{n-1}$.

1. Important detail: Test against the *previous* mean and variance (before incorporating $x_n$). If you update first and then test, the outlier itself contaminates the statistics you are testing against, reducing your detection power.

Practical Considerations:

• Warm-up period: You need at least 20-30 observations before the running variance stabilizes. During the warm-up, either skip detection or use a wider threshold.
• Non-stationarity: If the data distribution shifts over time (common in financial data), the running mean and variance computed over all history will lag. Fix: use an exponentially weighted moving average (EWMA) with decay factor $\alpha \in (0, 1)$:

$\mu_n = \alpha \, x_n + (1 - \alpha) \, \mu_{n-1}$

$\sigma_n^2 = \alpha \, (x_n - \mu_n)^2 + (1 - \alpha) \, \sigma_{n-1}^2$

This gives more weight to recent data and adapts to regime changes. Typical $\alpha$ values are 0.01-0.05. - Masking by outliers: If you include flagged outliers in the running statistics, they inflate $\sigma$ and make future outliers harder to detect. Consider excluding flagged points from the update step. - Heavy tails: The 3-sigma rule assumes approximate normality. For heavy-tailed distributions (e.g., financial returns), $k = 3$ will flag too many points. Use a higher threshold ($k = 4$ or $5$) or switch to a median/MAD-based detector. - Choice of $k$: Under normality, $k = 3$ gives a false positive rate of about 0.27%. Tighten to $k = 3.5$ or $k = 4$ if false alarms are costly.

Answer: Maintain a running mean and variance via Welford's algorithm. Flag observation $x_n$ as an outlier if $|x_n - \mu_{n-1}| > k \cdot \sigma_{n-1}$ (test before updating). This runs in $O(1)$ time and space. For non-stationary streams, replace the cumulative statistics with EWMA. The method assumes approximate normality -- for heavy-tailed data, increase $k$ or use robust alternatives like median absolute deviation.