Anomaly Detection in Machine Learning: A Technical Overview

Introduction

A card that has been used in Istanbul all year suddenly pays for three laptops in another country within ten minutes. A bearing in a factory motor starts vibrating at a slightly different frequency. A server that normally sends a few megabytes an hour starts sending gigabytes. In each case the interesting event is the one that doesn't look like the rest, and finding it automatically is called anomaly detection.

It is used in fraud detection, cybersecurity, quality control and predictive maintenance. What sets it apart from ordinary classification is imbalance: anomalies are rare, often well under one percent of the data, and frequently there are no labelled examples of them at all. That calls for its own set of methods. This overview draws partly on Andriy Burkov's The Hundred-Page Machine Learning Book.

What counts as an anomaly

Formally, let X ⊆ ℝd be a dataset of N independent observations x1, x2, …, xN. An anomaly is an instance xi ∈ X that deviates significantly from the distribution of normal instances. In practice anomalies come in three kinds:

• Point anomalies: single observations far away from everything else, like the three-laptop purchase. They are usually caught with probability distributions or distance measures.
• Contextual anomalies: values that are only strange in context. 30 °C is normal in July and alarming in January, so time or location has to be part of the model.
• Collective anomalies: a group of observations that is unusual as a whole even though each one looks fine on its own, such as a slow, steady series of small transfers.

The problem in mathematical terms

Given a dataset X, the goal is to learn a function

f: X → {0, 1}
f(x) = 1 if x is an anomaly
       0 otherwise

Most methods actually learn a continuous anomaly score and then apply a threshold. How that score is learned depends on how much labelled data you have, which gives three families of methods: supervised, unsupervised and semi-supervised.

1. Supervised anomaly detection

With labelled training data {(xi, yi)}i=1N, where yi ∈ {0, 1} marks whether an instance is anomalous, anomaly detection becomes a classification problem. Logistic regression, decision trees, gradient-boosted trees and neural networks all work. Logistic regression, for example, predicts

ŷ = σ(wᵀx + b)
σ(z) = 1 / (1 + e⁻ᶻ)

The catch is the data. You need enough labelled anomalies to learn from, which is rarely realistic, and with heavy imbalance a model can reach 99% accuracy simply by never flagging anything. Supervised methods also only recognise the kinds of anomalies they have already seen.

2. Unsupervised anomaly detection

Unsupervised methods assume no labels at all and look for points that don't fit the structure of the data.

Statistical methods

Model the distribution of normal data with a probability density p(x) and treat anything unlikely enough as an anomaly:

x is anomalous if p(x) < ε

If the data is roughly Gaussian with mean μ and covariance Σ, the Mahalanobis distance is a natural score. Unlike plain Euclidean distance, it takes into account the scale of each feature and the correlations between features:

dM(x) = √((x − μ)ᵀ Σ⁻¹ (x − μ))

Clustering-based methods

Algorithms such as k-means group the data into clusters, and points that are far from every cluster centre μk are suspicious:

s(x) = mink ‖x − μk‖₂

DBSCAN goes a step further and labels points that don't belong to any dense region as noise outright.

Density-based methods

The Local Outlier Factor (LOF) compares the local density around a point with the density around its k nearest neighbours Nk(x):

LOF(x) = (1 / |Nk(x)|) · Σy ∈ Nk(x) lrd(y) / lrd(x)

Here lrd is the local reachability density. A value close to 1 means the point is about as densely surrounded as its neighbours. Values well above 1 mean it sits in a much sparser area than they do.

Isolation-based methods

Isolation Forest takes a different route. It builds random trees that split the data on random features at random values. Anomalies are few and different, so they are isolated after only a handful of splits, while normal points need many. The average path length across all trees becomes the anomaly score. It is fast and copes well with high-dimensional tabular data, which is why it is often the first method people try.

3. Semi-supervised anomaly detection

Quite often you have plenty of data you know to be normal and almost no examples of anomalies. Semi-supervised methods train only on the normal data and flag whatever doesn't resemble it.

Autoencoders

An autoencoder is a neural network trained to compress its input and then reconstruct it. Trained on normal data only, it becomes good at reconstructing normal patterns. If the reconstruction error ‖x − x̂‖₂ is high, the input looks like nothing the network has seen, so x is probably an anomaly.

One-class SVM

A one-class support vector machine maps the data into a high-dimensional feature space through a mapping φ and learns a boundary that separates the normal data from the origin with as wide a margin as possible. New points that fall on the wrong side of it are treated as anomalies:

f(x) = sign(wᵀφ(x) − ρ)

Putting it into practice

1. Prepare the data. Normalise features, deal with missing values and keep the features that actually carry signal. Many distance-based methods fall apart if one feature is measured in thousands and another in fractions.
2. Choose a method. Let the data decide: whether you have labels, how many dimensions there are, how large the dataset is, whether time matters.
3. Evaluate honestly. With imbalanced data, accuracy tells you almost nothing. Precision-recall curves are usually more informative than ROC curves, because they show how many of your alerts are real.
4. Deploy and monitor. What counts as normal changes over time, so the model needs regular retraining and its alert rate needs watching.

What makes it hard

• Imbalanced data. Oversampling, undersampling and cost-sensitive learning help keep the model from simply ignoring the rare class.
• Concept drift. Customer behaviour, network traffic and machine wear all change. A model that is never updated slowly starts treating normal behaviour as an alarm, or the other way round.
• False positives. An alert system that cries wolf gets ignored. Careful threshold tuning, ensembles of several methods and a human review step for borderline cases keep the volume of alerts manageable.

In practice the choice of method tends to matter less than people expect. Most of the work goes into understanding what "normal" means for your particular data, and into deciding how many false alarms the people receiving them can live with.