30.1 Outlier vs. Novelty Detection

1. The Anomaly Taxonomy

Your algorithm just flagged 200 data points as suspicious; buried in that list might be a sensor glitch, a batch processing artifact, or the most important scientific finding of the decade, and right now you cannot tell which is which. Before writing any detection code, define precisely what you are detecting. The term "anomaly" is overloaded in practice; different scientific communities use it to mean different things, and conflating these meanings leads to systems that solve the wrong problem.

An outlier is a data point that deviates significantly from the majority of observations in a given dataset. Outlier detection is transductive (where transductive means the algorithm reasons only about the specific data points it has seen, without generalizing to unseen inputs): we have a fixed dataset \(\mathcal{D} = \{x_1, \ldots, x_n\}\), and we want to identify which points in \(\mathcal{D}\) are unusual relative to the others. The training data itself is assumed to contain some contamination. In Hawkins' (1980) classical definition, an outlier is "an observation which deviates so much from other observations as to arouse suspicions that it was generated by a different mechanism."

Contaminated observations distort every downstream statistical estimate: means shift, covariance matrices warp, and models fit noise instead of signal. Each detector assigns every observation a score reflecting how much its local neighborhood (density, distance, or isolation depth) deviates from the majority. You then threshold or rank by that score to separate suspicious points from the bulk. Use outlier detection rather than novelty detection whenever your dataset itself may be contaminated and you have no separate "clean" reference set; if you do have a trusted clean training set, novelty detection (described below) is the better framing.

A novelty is a new observation \(x_{\text{new}}\) that does not conform to the distribution learned from a clean training set. Novelty detection is inductive (where inductive means the algorithm learns a general model of normality from training data, then applies that model to classify new, unseen observations): we learn a model of "normal" from a training set assumed to be free of anomalies, then apply that model to classify new observations as normal or novel. The distinction matters because novelty detectors can overfit to contamination in the training data if it is not clean. In short: outlier detection asks "who here is suspicious?", while novelty detection asks "does this newcomer belong?"

The distinction between these two frameworks is critical because choosing the wrong one changes which algorithms are valid and how you interpret their output. Figure 30.1 summarizes the two workflows side by side.

An out-of-distribution (OOD) sample is an input that falls outside the distribution a supervised model was trained on. OOD detection is particularly important for deployed neural networks that can produce confident but meaningless predictions on inputs far from their training distribution. We cover OOD detection in depth in Section 30.2.

2. Local Outlier Factor (LOF)

When a pharmaceutical company's quality control system fails to distinguish a contaminated batch from a rare but valid compound, the consequences range from costly product recalls to missed drug candidates. Choosing the wrong detection framework (outlier vs. novelty) is often the root cause of these failures, which is why the local approach introduced next has become a workhorse across industries.

The Local Outlier Factor (Breunig et al., 2000) captures the intuition that an outlier is a point whose local density is substantially lower than the local density of its neighbors. "Local" is the key word: LOF can detect outliers in datasets with clusters of varying density, where a global threshold would fail.

For a point \(x\), define the \(k\)-distance \(d_k(x)\) as the distance to its \(k\)-th nearest neighbor. The reachability distance from \(x\) to a neighbor \(o\) is:

This smooths out statistical fluctuations for points deep inside clusters (where \(d(x,o) < d_k(o)\), so the reachability distance is clamped to \(d_k(o)\)). The local reachability density of \(x\) is the inverse of the average reachability distance to its \(k\) nearest neighbors \(N_k(x)\):

Finally, the LOF score is the ratio of the average local reachability density of \(x\)'s neighbors to \(x\)'s own local reachability density:

A LOF score near 1 means the point has similar density to its neighbors (normal). A score significantly greater than 1 means the point is in a sparser region than its neighbors (outlier). The beauty of LOF is that it adapts to local density: a point on the fringe of a dense cluster can score as an outlier even if it is closer to its neighbors than points in a sparser cluster that are perfectly normal.

import numpy as np
from sklearn.neighbors import LocalOutlierFactor
from sklearn.datasets import make_blobs

# Synthetic dataset: two clusters with different densities + outliers
rng = np.random.default_rng(42)
X_dense, _ = make_blobs(n_samples=300, centers=[[0, 0]], cluster_std=0.5, random_state=42)
X_sparse, _ = make_blobs(n_samples=100, centers=[[5, 5]], cluster_std=1.5, random_state=42)
X_outliers = rng.uniform(low=-4, high=9, size=(15, 2))  # scattered anomalies
X = np.vstack([X_dense, X_sparse, X_outliers])
true_labels = np.array([0]*300 + [0]*100 + [1]*15)  # 0=normal, 1=outlier

# LOF with k=20 neighbors
lof = LocalOutlierFactor(n_neighbors=20, contamination=0.05)
predictions = lof.fit_predict(X)  # -1 for outliers, 1 for inliers
scores = -lof.negative_outlier_factor_  # higher = more anomalous

# Evaluate: how many true outliers were caught?
detected_as_outlier = predictions == -1
true_positive_rate = true_labels[detected_as_outlier].sum() / true_labels.sum()
print(f"Total points: {len(X)}")
print(f"Flagged as outlier: {detected_as_outlier.sum()}")
print(f"True outliers caught: {true_labels[detected_as_outlier].sum()}/{true_labels.sum()}")
print(f"Recall: {true_positive_rate:.2%}")

Total points: 415
Flagged as outlier: 20
True outliers caught: 12/15
Recall: 80.00%

3. HDBSCAN Outlier Scores

LOF measures local density by comparing each point to its immediate neighbors, but it treats every point independently and ignores the broader cluster structure of the dataset. A complementary approach is to let a clustering algorithm discover that structure first, then score the points it cannot place.

HDBSCAN (Campello et al., 2013), which we encountered as a clustering algorithm in Chapter 25, provides a natural byproduct that is often overlooked: outlier scores. When HDBSCAN builds its hierarchical density tree, some points are never assigned to any cluster. These are labeled as "noise" (cluster label \(-1\)). But HDBSCAN goes further: it computes an outlier score for every point, reflecting how far it is from the nearest cluster in the density hierarchy.

The outlier score is based on the concept of GLOSH (Global-Local Outlier Score from Hierarchies). For each point \(x\), GLOSH compares the density at which \(x\) "falls out" of the condensed cluster tree (the simplified hierarchy that retains only the clusters that persist over a range of density thresholds; see Chapter 25) to the maximum density within the cluster it was closest to joining. Points that never integrate into any cluster at any density level receive the highest scores.

import hdbscan  # as of 2024, HDBSCAN is also available natively in scikit-learn (v1.3+) as sklearn.cluster.HDBSCAN

# Use the same dataset from the LOF example
clusterer = hdbscan.HDBSCAN(min_cluster_size=15, min_samples=5, prediction_data=True)
cluster_labels = clusterer.fit_predict(X)

# GLOSH outlier scores: 0 (inlier) to 1 (strong outlier)
outlier_scores = clusterer.outlier_scores_

# Threshold at 0.9 for high-confidence anomalies
hdbscan_outliers = outlier_scores > 0.9
print(f"Clusters found: {len(set(cluster_labels)) - (1 if -1 in cluster_labels else 0)}")
print(f"Noise points (label -1): {(cluster_labels == -1).sum()}")
print(f"High-confidence outliers (score > 0.9): {hdbscan_outliers.sum()}")
print(f"True outliers among high-confidence: "
      f"{true_labels[hdbscan_outliers].sum()}/{hdbscan_outliers.sum()}")

4. Kernel Density Estimation (KDE)

Kernel Density Estimation provides a non-parametric estimate of the probability density function \(\hat{f}(x)\) from observed data. Points where \(\hat{f}(x)\) is low are, by definition, improbable under the estimated distribution, making them candidate anomalies. KDE is arguably the most probabilistically principled of these four methods: it directly estimates a density, and anomaly scoring reduces to thresholding that density.

Given \(n\) observations \(\{x_1, \ldots, x_n\}\) in \(\mathbb{R}^d\), the kernel density estimate with bandwidth \(h\) and kernel function \(K\) is:

The most common choice is the Gaussian kernel \(K(u) = (2\pi)^{-d/2} \exp(-\|u\|^2 / 2)\). The bandwidth \(h\) controls the trade-off between bias and variance: too small and the estimate is spiky (overfitting to individual points); too large and real structure is smoothed away. Scott's rule (\(h = n^{-1/(d+4)}\), which minimizes integrated mean squared error for Gaussian data) and Silverman's rule provide reasonable defaults, but cross-validated bandwidth selection is preferable for anomaly detection because the tails of the distribution matter most.

from sklearn.neighbors import KernelDensity

# Fit KDE on the dataset (log-density for numerical stability)
kde = KernelDensity(kernel='gaussian', bandwidth=0.5)
kde.fit(X)

# Score all points: lower log-density = more anomalous
log_densities = kde.score_samples(X)

# Threshold at the 5th percentile of log-density
threshold = np.percentile(log_densities, 5)
kde_outliers = log_densities < threshold

print(f"KDE bandwidth: {kde.bandwidth}")
print(f"Log-density range: [{log_densities.min():.2f}, {log_densities.max():.2f}]")
print(f"Threshold (5th percentile): {threshold:.2f}")
print(f"Flagged as outlier: {kde_outliers.sum()}")
print(f"True outliers caught: {true_labels[kde_outliers].sum()}/{true_labels.sum()}")

KDE's main limitation is the curse of dimensionality: in high-dimensional spaces, the kernel mass spreads across exponentially many directions, and the density estimate becomes unreliable. As a rule of thumb, KDE works well up to roughly 10 dimensions on datasets of typical scientific size (thousands to tens of thousands of points). For higher-dimensional data, project first using Principal Component Analysis (PCA) or UMAP (Chapter 25), or switch to the deep methods of Section 30.2.

5. Isolation Forest

Both LOF and KDE define anomalies by estimating density and flagging regions where it is low, but density estimation itself becomes unreliable in high dimensions and expensive on large datasets. An entirely different strategy sidesteps density altogether by asking how easy each point is to separate from the crowd.

Isolation Forest (Liu et al., 2008) takes a beautifully different approach. Instead of estimating density and labeling low-density points as anomalous, it directly measures how easy a point is to isolate from the rest of the data using random recursive partitions.

The algorithm builds an ensemble of isolation trees. Each tree randomly selects a feature and a split value (uniform between the feature's min and max in the current subset), then recursively partitions the data. Partitioning stops when every point occupies its own leaf or the tree reaches maximum depth. The key insight: anomalies, being few and different, require fewer random splits to isolate. Normal points, being dense and similar, require many splits.

The anomaly score for a point \(x\) is derived from its average path length \(E[h(x)]\) across all trees in the ensemble, normalized by the expected path length in a binary search tree (BST) of the same size:

where \(c(n) = 2H(n-1) - 2(n-1)/n\) is the average path length of unsuccessful search in a BST, and \(H(i) = \sum_{j=1}^{i} 1/j\) is the \(i\)-th harmonic number (the sum of reciprocals from 1 to \(i\)). Scores near 1 indicate anomalies (short paths); scores near 0.5 indicate normal points; scores near 0 indicate extremely dense regions.

from sklearn.ensemble import IsolationForest

# Isolation Forest with 200 trees
iso_forest = IsolationForest(
    n_estimators=200,
    contamination=0.05,
    random_state=42,
    max_samples='auto'  # subsample size = min(256, n_samples)
)
iso_predictions = iso_forest.fit_predict(X)  # -1 for outliers, 1 for inliers
iso_scores = -iso_forest.score_samples(X)    # higher = more anomalous

# Compare with ground truth
iso_outliers = iso_predictions == -1
print(f"Isolation Forest flagged: {iso_outliers.sum()} outliers")
print(f"True outliers caught: {true_labels[iso_outliers].sum()}/{true_labels.sum()}")

# Show score distribution difference
normal_scores = iso_scores[true_labels == 0]
anomaly_scores = iso_scores[true_labels == 1]
print(f"Mean score (normal): {normal_scores.mean():.3f}")
print(f"Mean score (anomaly): {anomaly_scores.mean():.3f}")
print(f"Score separation: {anomaly_scores.mean() - normal_scores.mean():.3f}")

Isolation Forest flagged: 20 outliers
True outliers caught: 13/15
Mean score (normal): 0.437
Mean score (anomaly): 0.598
Score separation: 0.161

Key Insight: Isolation Forest Scales Linearly

Unlike LOF and KDE, which require computing pairwise distances (\(O(n^2)\) without spatial indexing), Isolation Forest's time complexity is \(O(t \cdot n \log n)\) where \(t\) is the number of trees. In practice, this often makes it the preferred choice for large datasets. It also handles high-dimensional data naturally because random feature selection acts as implicit dimensionality reduction. The subsample size (default 256) keeps individual tree construction constant-time regardless of dataset size, a design decision that makes the algorithm embarrassingly parallel (each tree can be built independently, so all trees can be constructed simultaneously across available processors).

6. When Anomalies Are Errors vs. Discoveries

The four algorithms above each produce a score quantifying how unusual a point is, but a high anomaly score alone says nothing about whether the point is a sensor glitch or a genuine scientific finding.

The critical step follows the ranking: deciding which flagged observations warrant investigation. Most anomalies fall into one of four categories, and distinguishing them demands domain knowledge that no algorithm can supply.

The Four Categories of Anomaly

Measurement errors arise from faulty instruments, miscalibrated sensors, or data entry mistakes. These are the most common source of anomalies in scientific data. A temperature sensor that occasionally reads \(-9999\) is producing measurement errors, not discovering cryogenic phenomena.

Processing artifacts arise from data cleaning, normalization, or transformation steps. A batch effect in gene expression data can make an entire experimental run look anomalous relative to other runs, even though the underlying biology is identical.

Known rare events are unusual but understood phenomena. A solar flare causing a spike in satellite radiation measurements is anomalous in the statistical sense but scientifically unremarkable. These are important to detect for operational reasons but are not discoveries.

Genuine novelties are the gold: observations that cannot be explained by any known error source or known phenomenon. The excess brightness of certain Type Ia supernovae that led to the discovery of dark energy (Riess et al., 1998; Perlmutter et al., 1999) fell into this category. So did the anomalous precession of Mercury's perihelion that confirmed general relativity.

from pyod.models.iforest import IForest
from pyod.models.lof import LOF
from pyod.models.kde import KDE

# All three with identical API
models = {
    'LOF': LOF(n_neighbors=20, contamination=0.05),
    'IForest': IForest(n_estimators=200, contamination=0.05, random_state=42),
    'KDE': KDE(contamination=0.05),
}
for name, model in models.items():
    model.fit(X)
    scores = model.decision_function(X)  # unified anomaly scores
    preds = model.predict(X)             # 0=inlier, 1=outlier
    print(f"{name}: {preds.sum()} outliers flagged")

Exercises

1. (Conceptual) A genomics lab runs LOF on gene expression data and finds that all samples from one batch are flagged as outliers. Is this a measurement error, a processing artifact, or a discovery? What additional information would you need to distinguish these possibilities? How does this relate to the batch effect correction techniques used in bioinformatics?
2. (Coding) Implement a comparison of LOF, KDE, and Isolation Forest on the ODDS benchmark datasets (start with the "shuttle" and "mammography" datasets). For each method, compute precision, recall, and AUROC. Which method wins on each dataset, and why? Hint: consider the dimensionality and contamination ratio of each dataset.
3. (Analysis) The bandwidth parameter \(h\) in KDE and the number of neighbors \(k\) in LOF both control a locality scale. Design an experiment to measure how anomaly detection performance (AUROC) varies as a function of these parameters on a dataset with clusters of three different densities. Plot the results and identify the "sweet spot" for each method. What happens when you use too few neighbors or too narrow a bandwidth?