25 / 27 · Learning Without Labels
Anomaly detection
Finding the rare points that do not fit: supervised, novelty and outlier settings, density scores from a Gaussian or a mixture, distance scores from nearest neighbours and the local outlier factor, the isolation forest and its path-length score, the one-class SVM, and how to evaluate a detector and choose a threshold when anomalies are rare.
Mixtures and the EM algorithm · Nearest neighbours · Support vector machines · Classification metrics
On this page 12
The previous note ended with models that are densities: a Gaussian mixture or probabilistic PCA says not only where the data are but how probable each point is. A fraudulent transaction, a failing sensor, a corrupted record or an intrusion is usually a point that such a model finds improbable. Anomaly detection turns that observation into a method: assign every point a score, high for points that do not fit, and flag the points above a threshold. Anomalies are rare, varied and often never seen before, so there is rarely a labelled training set for them, and the notion of “not fitting” has the same freedom as the notion of a cluster had. This note goes through the main families of scores, each with its own definition of unusual: low density, far from neighbours, quick to isolate, outside a learned boundary. It ends with the question that decides whether a detector is useful in practice: how to evaluate it and set its threshold when only a handful of points are anomalies.
Notation. are the training points, an anomaly score (higher means more anomalous) and a threshold: is flagged when . marks a true anomaly when labels exist for evaluation. is the assumed share of anomalies (the contamination); the one-class SVM’s parameter below is a different quantity. is the distance from to its -th nearest neighbour among the training points.
Three settings#
What can be learned depends on what is labelled.
- Supervised. Normal points and anomalies are both labelled. This is classification with very unequal classes, handled with the tools of the classification metrics note: class weights, resampling, and metrics that do not reward always predicting “normal”. It finds anomalies of the kinds it was shown and can miss new kinds.
- Semi-supervised, or novelty detection. The training set contains only normal points, known to be clean. The model describes them, and a new point is flagged if it does not fit the description. Most of the methods below are designed for this setting.
- Unsupervised, or outlier detection. The training set is unlabelled and contaminated with a small share of anomalies; the task is to find them in the same data. The methods are the same, but they must be robust to the anomalies they are fitted on, and often sets the threshold.
Most methods find point anomalies, single points unusual in themselves. A contextual anomaly is unusual only given a context: C is normal in January and anomalous in July. Such cases are reduced to point anomalies by adding the context as features or by modelling the conditional distribution given the context.
Density scores#
The most direct definition: an anomaly is a point of low probability under a model of the normal data. Fit a density by maximum likelihood and use .
One Gaussian. For , the negative log-density is, up to constants, half the squared Mahalanobis distance
the distance from the mean measured in standard deviations along each principal axis. If the normal data are Gaussian and the mean and covariance are the true ones, has the chi-squared distribution with degrees of freedom, which gives a threshold with a known false-alarm rate. For the 99% quantile is : flagging points with , a Mahalanobis distance above , flags 1% of normal points. With an estimated and the chi-squared law is only an approximation, good when is large compared with . In a simulation with Gaussian points in and the usual covariance estimate, the same threshold flags about 0.4% of the points the estimates were fitted on and 2.3% of new normal points. A threshold calibrated on independent normal validation data, as in the section on evaluation below, avoids the question. Without the Gaussian assumption, Chebyshev’s inequality still bounds the share of normal points beyond standard deviations in one dimension by , a much more conservative threshold.
The mean and covariance are themselves pulled by the anomalies they should detect: a few far points inflate and hide each other (masking). Robust estimates fit the covariance to the most concentrated part of the data, for example the minimum covariance determinant (Rousseeuw and Van Driessen, 1999). They assume one cluster of normal points: on the two-cluster data of the Code section, a robust fit describes the dense cluster only and flags the whole second cluster, and its ROC-AUC drops from 0.886 for the ordinary Gaussian to 0.738.
A mixture. Normal data with several modes need a Gaussian mixture, with ; on the same data a two-component mixture reaches ROC-AUC 0.911. Kernel density estimates and probabilistic PCA are other choices; for PCA, the reconstruction error , the distance from the principal subspace, is a common score in its own right.
Density scores have two weaknesses. Estimating a density needs many points per dimension, which limits nonparametric estimates to a few dimensions. And in high dimension high density is not typicality: the samples of a standard Gaussian in 100 dimensions lie in a thin shell far from the mode, where the density is highest, so a point at the mode would be highly unusual and yet get the best score. Deep generative models show the same effect on images: models trained on CIFAR-10 assign higher likelihood to house numbers from SVHN than to CIFAR-10 test images, the likelihood paradox discussed with energy-based models and normalizing flows.
Distance scores: nearest neighbours and LOF#
A density-free definition: an anomaly is far from the other points. The -nearest-neighbour score is , the distance to the -th nearest neighbour (Ramaswamy, Rastogi and Shim, 2000), or the mean distance to the nearest. It needs no model, works for any distance and adapts to clusters of any shape. It inherits the weaknesses of nearest neighbours: the cost of neighbour search, the dependence on feature scaling, and distances that concentrate in high dimension.
It also uses one global scale. Next to a dense cluster, a point at distance 1 is clearly anomalous; inside a sparse cluster, distance 1 is ordinary. A single threshold on either misses the first or flags the edge of the sparse cluster. The local outlier factor (LOF) of Breunig et al. (2000) compares each point’s density with the density of its neighbours. With the nearest neighbours of :
- The reachability distance of from a neighbour is : the true distance, but never less than ‘s own -distance, which smooths the statistics for points very close to .
- The local reachability density is the inverse of the mean reachability distance from the neighbours, .
- The local outlier factor is the ratio of the neighbours’ density to the point’s own,
Deep inside a cluster, dense or sparse, a point is as dense as its neighbours and . A point next to a dense cluster but in a sparse spot has neighbours much denser than itself, and its LOF is large, even though its absolute distances are small.
Worked example. On a line, take and the points . Every point except and has its nearest neighbour at distance 1; so do and (each other). All , all reachability distances are 1, all densities are 1, and every LOF equals 1: two well-separated groups of equal density contain no local outlier. Add the point : its nearest neighbour is at distance 3, so , while , and .
Four anomaly scores on the same data
The figure puts four scores side by side on data built to separate them: a dense and a sparse cluster, six anomalies far from everything and two close to the dense cluster. The two local anomalies are closer to their neighbours than the fringe points of the sparse cluster are to theirs, so the 10-nearest-neighbour distance ranks the fringe first; LOF, which compares densities locally, is the only score that puts all eight anomalies on top. The comparison is built to show what LOF adds, not to rank the methods in general: on the uniform anomalies of the Code section, LOF has the lowest ROC-AUC of the distance-based scores.
Isolation forest#
The scores so far model the normal data and measure the distance from it. The isolation forest (Liu, Ting and Zhou, 2008) measures how easy a point is to separate from the rest. Split the data recursively at random: pick a coordinate at random and a threshold uniformly between the minimum and maximum of the current points in that coordinate, and continue in each part until every point is alone. An anomaly, few and different, tends to be cut off after a few splits; a point in a dense region needs many. The number of splits on the path from the root to a point’s leaf, its path length , is the score, averaged over many random trees, as in the random forests of the bagging note.
Isolation by random cuts
The path length needs a reference scale, because trees on more points are deeper. A tree that isolates points has internal nodes, like a binary search tree with keys, and for random binary search trees the average depth of an unsuccessful search, which ends at one of the leaves, is known (Liu et al., Section 2, citing Preiss). It gives the normalizer
the average path length of a point in a tree on points. Since , the same quantity is . The anomaly score is
which is when the average path length equals , tends to 1 as it shrinks to 0, and tends to 0 as it grows to . Liu et al. read the score this way: points with close to 1 are clear anomalies, points with well below are normal, and when all points have the sample has no distinct anomalies (Section 2). These are readings of an isolation score, not a calibrated probability that a point is an anomaly: what means depends on the data, and a threshold on needs calibration like any other score.
Worked example. For , , so . A point isolated after 3 splits on average scores ; one that needs 10.249 scores ; one that needs 15 scores . The paper approximates the harmonic number by (Euler’s constant), which gives , a negligible difference. For small the approximation is poor: exactly, against with the logarithm. This matters for the adjustment below, applied to leaves with a few points; scikit-learn uses the exact values and and the logarithmic approximation from on.
Three design choices make the method fast and robust (Section 4). Each tree is grown on a subsample of points drawn without replacement, by default, with trees. Small subsamples help: fewer normal points crowd around the anomalies (swamping), and fewer anomalies shield each other (masking). Trees are grown only to the height limit , the average depth, because only short paths matter; a point that reaches a leaf still holding points gets , its depth plus the average depth of the unbuilt subtree. And the score uses only comparisons, no distances, so training costs , scoring per point, independent of , and the method is insensitive to the scale of each feature. Its weakness is the axis-aligned cuts: anomalies that differ from the data only along a diagonal, or that sit in a hole surrounded by normal points, are hard to isolate with cuts parallel to the axes, and the score map shows axis-aligned artefacts. The comparison figure above also shows the global view: like the neighbour distance, the isolation forest misses the two local anomalies of the comparison figure.
One-class SVM#
The one-class SVM (Schölkopf et al., 2001) learns a boundary around the normal data instead of a score. In the feature space of a kernel, it separates the mapped points from the origin with the largest margin, allowing a share of them on the wrong side:
The decision function is , negative for anomalies, and as for the support vector machine the dual depends on the data only through the kernel: with and . The parameter has a direct meaning, the ν-property: it is an upper bound on the share of training points outside the boundary and a lower bound on the share of support vectors. In the Code section, with , 18.7% of the training points fall outside and 21.4% are support vectors. So is a setting of the optimization, not the true share of anomalies: it controls how many training points the boundary leaves out, whatever their status, and the real contamination can be larger or smaller. Setting is a reasonable choice when is known, not an identity. With the Gaussian kernel, is a weighted sum of bumps around the support vectors minus a threshold; for the constraints force all and becomes a thresholded kernel density estimate. The method describes boundaries of any shape, but the kernel width and must be chosen without labels, the cost grows faster than linearly in , and like all kernel methods it needs scaled features.
Evaluating with rare labels#
Even when training uses no labels, evaluation needs some: a set of points with known status, often a few hundred normal points and a few dozen anomalies collected from incidents. Three things make this evaluation unlike ordinary classification.
Accuracy is meaningless. With 1% anomalies, flagging nothing is 99% accurate. Detectors are compared by their ranking of the points, since the threshold comes later: the ROC-AUC, the probability that a random anomaly scores above a random normal point, as derived in the classification metrics note, and the average precision (AP), the area under the precision–recall curve.
ROC-AUC flatters rare positives. The false-positive rate divides by the large number of normal points, so a detector can have a small false-positive rate and still bury its true alarms among false ones. Precision shows this directly, by the base-rate calculation: with 1% anomalies, a detector that finds 90% of them at a false-positive rate of 1% has precision
so half of its alarms are false. On the 513 points of the Code section, with 13 anomalies, the methods’ ROC-AUC values lie between 0.74 and 0.92 and look similar; their AP values lie between 0.15 and 0.69 and separate them far more. For rare anomalies, report the precision–recall curve and the AP (Saito and Rehmsmeier, 2015; the precision–recall section of the metrics note), and precision among the top alarms when the alert budget is fixed.
Few labels, wide error bars. With 13 anomalies, recall moves in steps of 7.7%, and a difference of one or two detections between methods is noise. A bootstrap over the labelled points, as in the confidence intervals note, shows how much.
Choosing the threshold. The score ranks; the threshold decides how many points become alarms. Three common ways:
- From the contamination. In the unsupervised setting, flag the top share of the training scores. scikit-learn’s
contaminationparameter does this; it needs a guess of . - From a false-alarm rate. In the novelty setting, score clean validation data and set at its quantile; about a share of future normal points will be flagged. In the Code section the 99% quantile of 10,000 clean validation scores gives a false-alarm rate of 0.9% on fresh normal data, against the target 1%.
- From costs or capacity. If an analyst can review 50 alerts a day, the threshold is the score of the 50th point; if a missed anomaly costs a hundred false alarms, the cost rule of the classification metrics note applies, but that rule needs a calibrated probability of being an anomaly, and the scores above are not probabilities. Either calibrate the score on labelled validation data first, or search over thresholds on such data for the lowest total cost.
What changed#
| Density (Gaussian, mixture) | kNN distance | LOF | Isolation forest | One-class SVM | |
|---|---|---|---|---|---|
| An anomaly is | improbable under a model | far from its neighbours | sparser than its neighbours | quick to isolate | outside a learned boundary |
| Scale | global | global | local | global | global |
| Needs | a family of densities | a distance | a distance, | nothing but comparisons | a kernel, |
| Cost to score | cheap | neighbour search | neighbour search | kernel sum over support vectors | |
| Threshold | chi-squared quantile, likelihood | quantile | LOF well above 1 | near 1 | , share bounded by |
| Weak at | high dimension, multimodal data | varying densities | high dimension, cost | diagonal structure, local anomalies | choosing the kernel, large |
Limitations#
- No definition fits all anomalies. Each score encodes one notion of unusual; anomalies of another kind pass unnoticed. Combining scores, or choosing by labelled incidents, is the practical answer.
- High dimension. Densities cannot be estimated, distances concentrate, and irrelevant features hide the relevant ones; scores are usually computed on a few principal components or on learned representations.
- Contaminated training data. Models fitted on data that contain anomalies learn them as normal, and robust estimates assume structure (one cluster) that may not hold.
- Rare and changing labels. Evaluation rests on a few dozen known anomalies, the error bars are wide, and new kinds of anomalies appear after deployment. A detector needs monitoring, like any model whose input distribution drifts.
- A score is not an explanation. An analyst needs to know why a point was flagged; LOF and isolation forests give a number, not a reason.
What you should remember#
- Supervised detection is imbalanced classification; novelty detection learns from clean normal data; outlier detection finds anomalies in contaminated data without labels.
- Density scores use ; for one Gaussian this is the Mahalanobis distance, with a chi-squared threshold that is exact for known parameters and approximate for estimated ones. High density is not typicality in high dimension.
- The -NN distance flags points far from their neighbours on a global scale; LOF compares a point’s local density with its neighbours’ and finds local outliers.
- The isolation forest scores with ; short paths mean anomalies, means average. Subsamples of 256 and height limit 8 keep it fast.
- The one-class SVM separates the data from the origin in feature space; bounds the share of training points outside from above and the share of support vectors from below.
- With rare anomalies, compare detectors by average precision, not accuracy or ROC-AUC alone; precision is ruled by the base rate.
- Set the threshold from the contamination, a target false-alarm rate on clean data, or the cost and capacity of reviewing alarms.
Code#
The isolation-forest normalizer, a chi-squared threshold, seven scores on contaminated data, the ν-property, the base rate and a quantile threshold:
import numpy as np
from scipy import stats
from sklearn.covariance import EmpiricalCovariance, MinCovDet
from sklearn.mixture import GaussianMixture
from sklearn.neighbors import NearestNeighbors, LocalOutlierFactor
from sklearn.ensemble import IsolationForest
from sklearn.svm import OneClassSVM
from sklearn.metrics import roc_auc_score, average_precision_score
# the isolation-forest normalizer c(n) = 2 H(n - 1) - 2 (n - 1) / n, exact and with H(i) ~ ln i + 0.5772
H = lambda m: sum(1 / i for i in range(1, m + 1))
c = lambda n: 2 * H(n - 1) - 2 * (n - 1) / n
c_ln = lambda n: 2 * (np.log(n - 1) + np.euler_gamma) - 2 * (n - 1) / n
print([round(c(n), 4) for n in (3, 256)], [round(float(c_ln(n)), 4) for n in (3, 256)], round(2 * H(256) - 2, 4))
# [1.6667, 10.2487] [1.2074, 10.2448] 10.2487: c(n) = 2 H(n) - 2
# a Gaussian threshold: squared Mahalanobis distance against the chi-squared quantile, d = 2
print(round(stats.chi2(2).ppf(0.99), 2), round(np.sqrt(stats.chi2(2).ppf(0.99)), 2)) # 9.21 3.03
# contaminated data: a dense and a sparse cluster, 13 uniform anomalies (2.5%); labels only for evaluation
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([0, 0], 0.3, (300, 2)), rng.normal([4, 3], 1.2, (200, 2)), rng.uniform([-4, -4], [9, 8], (13, 2))])
y = np.r_[np.zeros(500), np.ones(13)]
d10 = NearestNeighbors(n_neighbors=11).fit(X).kneighbors(X)[0][:, 10] # distance to the 10th neighbour
scores = {
'gaussian': EmpiricalCovariance().fit(X).mahalanobis(X),
'robust gaussian': MinCovDet(random_state=0).fit(X).mahalanobis(X),
'gmm, K=2': -GaussianMixture(2, random_state=0).fit(X).score_samples(X),
'10-nn distance': d10,
'lof': -LocalOutlierFactor(n_neighbors=10).fit(X).negative_outlier_factor_,
'isolation forest': -IsolationForest(random_state=0).fit(X).score_samples(X),
'one-class svm': -OneClassSVM(nu=0.05, gamma=0.5).fit(X).decision_function(X),
}
for name, s in scores.items():
print(f'{name:17s} ROC-AUC {roc_auc_score(y, s):.3f} AP {average_precision_score(y, s):.3f}')
# gaussian ROC-AUC 0.886 AP 0.512
# robust gaussian ROC-AUC 0.738 AP 0.145
# gmm, K=2 ROC-AUC 0.911 AP 0.644
# 10-nn distance ROC-AUC 0.915 AP 0.693
# lof ROC-AUC 0.871 AP 0.515
# isolation forest ROC-AUC 0.915 AP 0.636
# one-class svm ROC-AUC 0.893 AP 0.516
# the nu-property of the one-class SVM, solved to a tight tolerance: share outside <= nu <= share of support vectors
for nu in (0.05, 0.2):
oc = OneClassSVM(nu=nu, gamma=0.5, tol=1e-7).fit(X)
print(nu, round((oc.decision_function(X) < -1e-6).mean(), 3), round(len(oc.support_) / len(X), 3))
# 0.05 0.023 0.086 | 0.2 0.187 0.214
# rare anomalies: precision of a detector with recall 0.9 and false-alarm rate 0.01 at a 1% base rate
print(round(0.9 * 0.01 / (0.9 * 0.01 + 0.01 * 0.99), 3)) # 0.476
# a threshold for a target false-alarm rate: the 99% quantile of scores on clean validation data
normal = lambda m: np.vstack([rng.normal([0, 0], 0.3, (m // 2, 2)), rng.normal([4, 3], 1.2, (m // 2, 2))])
iso = IsolationForest(random_state=0).fit(normal(1000))
tau = np.quantile(-iso.score_samples(normal(10000)), 0.99)
print(round((-iso.score_samples(normal(20000)) > tau).mean(), 4)) # 0.0087: the false-alarm rate on fresh normal data
score_samples of scikit-learn’s isolation forest returns , so its negative is the score of the paper.
Next#
Every detector in this note ends with a score per point, and in practice an analyst reads the list of points from the top: what matters is that the true anomalies come first, not the value of the score. That is a ranking problem, solved here without labels. The next note supervises it: search engines, catalogues and retrievers learn to order items from relevance labels, with metrics and losses built for the top of the list.
References#
- V. Chandola, A. Banerjee, V. Kumar. Anomaly detection: A survey. ACM Computing Surveys, 41(3), 1–58, 2009.
- P. J. Rousseeuw, K. Van Driessen. A Fast Algorithm for the Minimum Covariance Determinant Estimator. Technometrics, 41(3), 212–223, 1999.
- S. Ramaswamy, R. Rastogi, K. Shim. Efficient algorithms for mining outliers from large data sets. SIGMOD, 427–438, 2000.
- M. M. Breunig, H.-P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-Based Local Outliers. SIGMOD, 93–104, 2000.
- F. T. Liu, K. M. Ting, Z.-H. Zhou. Isolation Forest. ICDM, 413–422, 2008. Section 2 (path length, and the score), Section 3 (swamping and masking), Section 4 (training and evaluation, , , the height limit).
- F. T. Liu, K. M. Ting, Z.-H. Zhou. Isolation-Based Anomaly Detection. ACM Transactions on Knowledge Discovery from Data, 6(1), 1–39, 2012.
- B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, R. C. Williamson. Estimating the Support of a High-Dimensional Distribution. Neural Computation, 13(7), 1443–1471, 2001.
- E. Nalisnick, A. Matsukawa, Y. W. Teh, D. Gorur, B. Lakshminarayanan. Do Deep Generative Models Know What They Don’t Know? ICLR, 2019.
- T. Saito, M. Rehmsmeier. The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets. PLOS ONE, 10(3), e0118432, 2015.
- E. Sokolov et al. Машинное обучение (HSE), lecture notes, lecture 16: one-class methods and anomaly detection (2025).