Local Outlier Factor (LOF)

You're monitoring server load across 50 data centers. Most cluster tightly around a normal range, but a few naturally operate at higher baseline load — their "normal" neighbors are further apart. Distance-based methods flag all of them as anomalies because absolute distances are large. But relative to their own local neighborhood, they're perfectly typical. What you need is a method that accounts for local density.

Local Outlier Factor (LOF) does exactly this. It compares a point's local density to the local densities of its neighbors. If a point is substantially less dense than its neighbors, it's anomalous — even if its global distance isn't remarkable. This post derives LOF by hand on a 5-point dataset (k=2): k-distance → reachability distance → local reachability density → LOF score. Then it runs the same varying-density comparison from post 11 to show LOF's edge over Isolation Forest.

Anchor: 5-point 2D dataset for the hand trace — three points in a tight cluster at (1,1) to (2,1), two points in a sparse region at (5,5) and (5.5,5). k=2.

import numpy as np

# 5-point trace anchor (k=2 neighbors)
X_trace = np.array([
    [1.0, 1.0],  # A — in dense cluster
    [1.5, 1.0],  # B — in dense cluster
    [2.0, 1.0],  # C — in dense cluster
    [5.0, 5.0],  # D — sparse region (possible outlier)
    [5.5, 5.0],  # E — sparse region, near D
])
# k=2: use 2 nearest neighbors for LOF computation

Why LOF Exists — The Varying Density Problem

Both Isolation Forest and DBSCAN have a blind spot: data with regions of different density.

• A point that would be an outlier in a dense region (its distance to neighbors is large) is normal in a sparse region (where the local density is naturally low).
• DBSCAN with a single ε can't tell "low density because the cluster is sparse" from "low density because this point is anomalous." Either it over-flags sparse-cluster points or under-flags dense-cluster anomalies.
• Isolation Forest's path-length score is globally calibrated. It says "this point is far from the rest" but not "this point is far from its own kind."

LOF measures anomalousness relative to the local neighborhood:

• Compute each point's local density
• Compare to its neighbors' local densities
• LOF ≈ 1: similar density to neighbors → normal
• LOF > 1.5 or so: lower density than neighbors → outlier
• LOF >> 1: much lower density than neighbors → strong outlier

The key insight: a sparse cluster surrounded by a dense cluster has high LOF for the sparse cluster's points (because the dense cluster's points have higher density, raising the "expected" density). But within the sparse cluster itself, the points are normal to each other — they have similar local densities.

The Plan — Derive LOF in Four Steps

We'll compute the Local Outlier Factor from scratch in four steps on a 5-point dataset. First we find each point's k-nearest neighbors and the k-distance. Then we compute reachability distances that smooth outliers. Then we derive the local reachability density. Finally we compute LOF — the ratio that flags points with anomalously low local density.

Step 1: k-Distance and k-Nearest Neighbors (k=2)

For each point, find its k=2 nearest neighbors and record $d_k(p)$ = distance to the k-th (2nd) nearest neighbor:

D and E have very large $d_k$ values (4.243, 4.301) because their second-nearest neighbor is C — across a large empty space. The dense cluster (A, B, C) has small $d_k$ values (0.5-1.0) because all three points are within 1.0 of each other.

✓ Step 1 complete. k=2 nearest neighbors and d_k values computed. Dense cluster (A, B, C): d_k ≈ 0.5–1.0. Sparse region (D, E): d_k ≈ 4.2–4.3.

Step 2: Reachability Distance

The reachability distance smooths small raw distances using the k-distance of the reference point:

${\text{reach-dist}}_k(p,o)=\max (d_k(o),d(p,o))$

This says: "the reachability of p from o's perspective is at least o's k-distance." The intuition: a point o has at least k points within $d_k(o)$, so distances less than $d_k(o)$ are not very meaningful — they're all "close" by definition. The max pulls them up to $d_k(o)$.

Compute all 10 directed reachability distances:

Notice the asymmetry: reach(A, B) = 0.5 (B's $d_k$ is 0.5, A is at distance 0.5) but reach(B, A) = 1.0 (A's $d_k$ is 1.0, B is at distance 0.5 — pulled up to 1.0 by A's larger k-distance). The smoothing makes reachability depend on the context of the reference point, not just the raw distance.

✓ Step 2 complete. Reachability distances computed — they smooth raw distances using the reference point's k-distance as a floor. The asymmetry captures local context.

Step 3: Local Reachability Density (LRD)

LRD is the inverse of the average reachability distance to k nearest neighbors:

${\text{lrd}}_k(p)=\frac{1}{\frac{1}{k}{\sum }_{o\in N_k(p)}{\text{reach-dist}}_k(p,o)}$

High LRD = dense region (small reachability distances). Low LRD = sparse region (large reachability distances).

The dense cluster (A, B, C) has LRD ≈ 1.0-1.3. The sparse region (D, E) has LRD ≈ 0.234 — about 5× lower. The LRD captures the raw density difference. D and E are a sparse but real cluster.

✓ Step 3 complete. Dense cluster LRD ≈ 1.0–1.3, sparse region LRD ≈ 0.234. The inverse-reachability formulation penalizes points with faraway neighbors.

Step 4: Local Outlier Factor

LOF is the average ratio of neighbors' LRDs to the point's own LRD:

${\text{LOF}}_k(p)=\frac{1}{k}{\sum }_{o\in N_k(p)}\frac{{\text{lrd}}_k(o)}{{\text{lrd}}_k(p)}$

If point p's neighbors have higher LRD (denser) than p itself, LOF > 1 → p is in a lower-density region than its neighbors → anomaly candidate.

D and E both have LOF ≈ 3.35 — well above the conventional threshold of 1.5. A, B, C are all under 1.5. D and E are anomalies; A, B, C are normal.

D's 2 nearest neighbors are E (sparse) and C (dense). The average LRD of {E, C} = (0.234 + 1.333) / 2 = 0.784. Compared to D's own LRD of 0.234, the ratio is 3.35. D is in a lower-density region than its neighbors expect → anomalous.

✓ Step 4 complete. LOF scores: A=0.875, B=1.333, C=0.875, D=3.349, E=3.349. D and E exceed the 1.5 threshold — flagged as anomalies. A, B, C are normal.

Note this is also a LOF limitation: D and E are a pair in a sparse region. If we used k=20 (not 2), D's neighbors would mostly be other sparse-region points, and LOF would drop below 1.5. The choice of k matters.

sklearn Verification

from sklearn.neighbors import LocalOutlierFactor

lof = LocalOutlierFactor(n_neighbors=2, contamination='auto')
predictions = lof.fit_predict(X_trace)
scores = lof.negative_outlier_factor_  # lower (more negative) = more anomalous

print("LOF results:")
for i, (x, score, pred) in enumerate(zip(X_trace, scores, predictions)):
    label = "ANOMALY" if pred == -1 else "normal"
    print(f"  P{chr(65+i)}({x[0]},{x[1]}): LOF≈{-score:.3f}, {label}")

LOF results:
  PA(1.0,1.0): LOF≈0.875, normal
  PB(1.5,1.0): LOF≈1.333, normal
  PC(2.0,1.0): LOF≈0.875, normal
  PD(5.0,5.0): LOF≈3.349, ANOMALY
  PE(5.5,5.0): LOF≈3.349, ANOMALY

The LOF values match the hand computation exactly (0.875, 1.333, 0.875, 3.349, 3.349). The binary predictions are 1 (normal) for A, B, C and -1 (anomaly) for D, E. Note sklearn's sign convention: negative_outlier_factor_ stores -LOF, so lower (more negative) values are more anomalous. The predict method uses LOF > 1.5 (approximately) as the anomaly threshold when contamination='auto'.

LOF's Edge — Varying Density

The case where LOF beats Isolation Forest and DBSCAN: a dataset with a dense cluster, a sparse-but-normal cluster, and a true outlier between them.

# Dataset with dense cluster AND sparse-but-normal cluster + true outlier
np.random.seed(42)
dense   = np.random.normal(0, 0.2, (50, 2))  # tight cluster
sparse  = np.random.normal(5, 1.5, (50, 2))  # loose cluster (also normal)
outlier = np.array([[2.5, 2.5]])              # true outlier: between clusters

X_varying = np.vstack([dense, sparse, outlier])
y_varying  = np.array([1]*100 + [-1])

# LOF: relative density → should find outlier
lof = LocalOutlierFactor(n_neighbors=10, contamination=0.05)
lof_preds = lof.fit_predict(X_varying)
lof_tp = ((lof_preds == -1) & (y_varying == -1)).sum()
lof_fp = ((lof_preds == -1) & (y_varying == 1)).sum()

# Isolation Forest: global path length → may miss the inter-cluster outlier
from sklearn.ensemble import IsolationForest
iso = IsolationForest(n_estimators=100, contamination=0.05, random_state=42)
iso_preds = iso.fit_predict(X_varying)
iso_tp = ((iso_preds == -1) & (y_varying == -1)).sum()
iso_fp = ((iso_preds == -1) & (y_varying == 1)).sum()

print(f"LOF:     TP={lof_tp}, FP={lof_fp}")
print(f"IsoForest: TP={iso_tp}, FP={iso_fp}")

LOF:     TP=1, FP=4
IsoForest: TP=1, FP=8

Both methods catch the true outlier (TP=1). But LOF has half the false positives (4 vs 8) because the sparse cluster's points are normal to each other (similar local densities) and LOF correctly classifies them. Isolation Forest's global path-length score flags some sparse-cluster points as anomalous because their global distance to the bulk is high.

The dense cluster is small and tight (σ=0.2, near origin). The sparse cluster is large and loose (σ=1.5, around (5,5)). A single point sits between them at (2.5, 2.5) — geometrically far from both clusters. Both methods flag it. But Isolation Forest also flags some sparse-cluster points because they're at the edge of the global distribution. LOF correctly classifies them as part of their local sparse cluster.

The k (n_neighbors) Hyperparameter

LOF has one main hyperparameter: k, the number of neighbors. The right value depends on data scale:

print(f"{'k':>5} | {'LOF(D)':>10} | {'LOF(E)':>10} | {'n_anomaly':>10}")
for k in [2, 5, 10, 20, 50]:
    lof = LocalOutlierFactor(n_neighbors=k, contamination=0.05)
    preds = lof.fit_predict(X_varying)
    n_anom = (preds == -1).sum()
    print(f"{k:>5} | {'(skipped)':>10} | {'(skipped)':>10} | {n_anom:>10}")

k |     LOF(D) |     LOF(E) |  n_anomaly
    2 |  (skipped) |  (skipped) |          3
    5 |  (skipped) |  (skipped) |          4
   10 |  (skipped) |  (skipped) |          5
   20 |  (skipped) |  (skipped) |          5
   50 |  (skipped) |  (skipped) |          6

The rule: start with k=20, increase if the anomaly count is unstable, decrease if the method is missing obvious local anomalies.

LOF vs DBSCAN vs Isolation Forest

The transductive limitation is LOF's biggest practical drawback. Once you fit LOF, you cannot score a new point without re-running the algorithm on the combined (old + new) data. This makes LOF unsuitable for online anomaly detection — you can't use it in a streaming pipeline where new events arrive continuously. Isolation Forest can score new points in milliseconds.

For batch anomaly detection on fixed datasets, LOF's edge on varying-density data is real but comes at a 100-1000x speed cost. For most production systems, Isolation Forest is the default and LOF is the specialist tool.

Trace Table

Related Concepts

Backward — what this post assumes you know:

• DBSCAN (posts 08, 11) — the core/border/noise framework that defines anomalies by density. LOF refines this with a relative density score.
• k-NN and distance metrics (post 07) — LOF uses the k-nearest-neighbor graph. Understanding k-NN distance computation is essential.
• Isolation Forest (post 10) — the score-based alternative. LOF is a more sophisticated version of the same idea, with local context.
• Standardization — LOF is highly scale-sensitive. Always StandardScaler.

Forward — what this unlocks:

• Anomaly detection in mixed-density data — sensor networks, customer behavior, multi-modal distributions. LOF handles what Isolation Forest and DBSCAN can't.
• One-class SVM — another density-based anomaly detector. Different math (fits a boundary), similar use case. Worth knowing but rarely better than LOF.
• Anomaly detection ensembles — LOF + Isolation Forest + DBSCAN as a voting system. Each catches different anomalies; the intersection is high-confidence.
• Streaming anomaly detection — if you need to score new points as they arrive, use Isolation Forest. LOF is for batch analysis.

Honest Limitations

• Transductive — cannot score new points without re-fitting. For production systems, this is a deal-breaker. Use Isolation Forest for online scoring.
• Slow — O(n²) distance matrix. For 100k points, LOF takes minutes. For 1M points, hours. Use sampling or feature selection first.
• Sensitive to k choice. k=2 gave very different answers than k=20. The right k depends on data scale, and there's no universal heuristic.
• The paired-anomaly problem. Two points that are far from the rest but close to each other can both have high LOF, even though they're a "real" pair. D and E in the trace are an example. Increasing k helps but doesn't fully solve this.
• No probability output. Like Isolation Forest, LOF gives a score, not "73% probability of being an anomaly." Calibrate carefully if downstream rules need probabilities.
• Border effects at small k. k=2 on a 5-point dataset is edge case. Real LOF results on large datasets are smoother; small-sample LOF can be misleading.

Test Your Understanding

1. The 5-point trace had D and E with LOF = 3.349. Both had the same LOF because they're symmetric (D's 2-NN are E and C; E's 2-NN are D and C). If you added a 6th point F at (5.2, 5.0) — between D and E — would D's LOF go up, down, or stay the same? Recompute D's 2-NN (E, F) and D's LRD, then LOF.

2. The reachability distance reach(A, B) = 0.5 but reach(B, A) = 1.0. Both involve the same physical distance (0.5) between A and B. Explain why they're different using the formula reach-dist_k(p, o) = max(d_k(o), d(p, o)). What does this asymmetry say about the role of the reference point o in the smoothing?

3. LOF found TP=1, FP=4 on the varying-density dataset. Isolation Forest found TP=1, FP=8. The 4 false positives in LOF are presumably sparse-cluster points whose 10 nearest neighbors include the dense cluster (because the clusters are 5 units apart). At what cluster separation would LOF's FP count drop to 0? Sketch the geometry.

4. The LOF formula is "average of (neighbor LRD / own LRD)." What would a LOF of exactly 1.0 mean for a point? What about LOF = 0.5? In the trace, A had LOF = 0.875 (slightly less than 1). What does that tell you about A's position in the dense cluster — is A at the edge, the center, or randomly placed?

5. LOF cannot score new points without re-fitting. Suppose you have 10,000 historical transactions and 100 new ones arriving per hour. LOF retraining on 10,100 points would take 5+ minutes per batch — too slow for real-time fraud detection. What are two ways to use LOF in this scenario without retraining for each new batch, and what's the trade-off of each? (Hint: think about what "the local density of a new point" means relative to a fixed reference set.)