Isolation Forest

You have 10,000 credit-card transactions and need to find the 100 fraudulent ones. You have no labeled fraud data — only the transactions themselves. Most anomaly detection methods would measure how distant each transaction is from the rest. Isolation Forest does the opposite: it asks how easy it is to separate a transaction from the rest by random partitions. Fraudulent transactions, being rare and weird, get isolated in a few cuts. Normal transactions, buried in dense clusters, need many cuts. The fewer cuts needed, the more anomalous.

This post builds the path-length intuition on a 6-point 1D dataset, computes anomaly scores by hand, then runs the algorithm on a synthetic 1000-transaction fraud dataset to show how contamination controls the precision/recall tradeoff.

Anchor: 6-point 1D dataset — five points in a tight cluster around x=2.5, one obvious outlier at x=10.0. For the real-data code, 1000 synthetic transactions with 1% labeled fraud.

import numpy as np

# 6-point 1D trace anchor
X_trace = np.array([[1.0], [2.0], [2.5], [3.0], [3.5], [10.0]])
# Points 1-5 form a dense cluster; P6=10.0 is an obvious outlier

array([[ 1. ],
       [ 2. ],
       [ 2.5],
       [ 3. ],
       [ 3.5],
       [10. ]])

Core Idea — Anomalies Are Easy to Isolate

To "isolate" a point in an Isolation Tree:

1. Pick a random feature
2. Pick a random split value between (min, max) of that feature
3. Send the point to the left or right child based on the split
4. Repeat until the point is alone in a leaf

A point that is far from the bulk of the data will be separated by a single early split — short path. A point in a dense cluster requires many splits to peel off from its neighbors — long path. The path length is the anomaly signal.

The anomaly score combines path length across all trees in the forest:

$s(\mathbf{x},n)=2^{-E[h(\mathbf{x})]/c(n)}$

where $E[h(\mathbf{x})]$ is the average path length across all trees, and $c(n)=2(\ln (n-1)+0.5772)-2(n-1)/n$ is the expected path length for a randomly-constructed BST over $n$ points (the Euler-Mascheroni constant 0.5772 appears here).

The score is bounded in $[0,1]$ by construction. The $c(n)$ normalization makes scores comparable across datasets of different sizes.

Hand Trace — 3 Trees on the 6-Point Dataset

Tree 1. Random split at x=6.5:

• Left child: $\{1.0,2.0,2.5,3.0,3.5\}$ — the dense cluster
• Right child: $\{10.0\}$ — P6 isolated at depth 1

Continue splitting the left child. Random split at x=1.8:

• Left-Left: $\{1.0\}$ — P1 isolated at depth 2
• Left-Right: $\{2.0,2.5,3.0,3.5\}$ — 4 points remaining

Continue splitting. Each remaining normal point takes 3-4 splits to isolate.

Tree 2. Random split at x=4.2:

• Left: $\{1.0,2.0,2.5,3.0,3.5\}$
• Right: $\{10.0\}$ — P6 isolated at depth 1 again

Tree 3. Random split at x=7.8:

• Left: $\{1.0,2.0,2.5,3.0,3.5\}$
• Right: $\{10.0\}$ — P6 isolated at depth 1 again

The outlier P6 sits at x=10.0, and the dense cluster is centered at x=2.5. Any random split value between 3.5 and 10.0 (a range of 6.5 units, ~50% of the data range) sends P6 to one side and the cluster to the other. The probability of catching P6 in a single split is high. Conversely, splitting the cluster requires values between the cluster points (1.0, 2.0, 2.5, 3.0, 3.5) — a much narrower range.

P6 has path length 1 in all 3 trees — consistent and very short. P3 and P4 (middle of the dense cluster) have the longest paths — they're hardest to separate from the cluster. The score separation between P6 (~0.82) and the cluster points (~0.22-0.35) is large — Isolation Forest would easily flag P6 as anomalous.

The diagram shows the structure: the first split sends P6 alone to the right (depth 1). The cluster on the left needs 3 more splits to fully isolate all its points. P6's path length is 1; cluster points have path length 3-4.

Why Isolation Forest is Efficient

• No distance computations. Unlike KNN-based detectors, Isolation Forest never computes pairwise distances.
• Linear time per tree. Building an isolation tree is O(n) for n samples — pick splits, recurse.
• Total: O(n × n_trees). With n=1000 and 100 trees, that's 100,000 operations. Fast.
• High-dimensional friendly. Each split picks one feature, so high dimensions add cost per split but no combinatorial blowup.
• Trivial path length tracking. Path length is just recursion depth — incremented as you traverse the tree.

The trade-off: Isolation Forest gives a score, not a probability. Two points with the same score may not be equally anomalous. For ranking (top-K most anomalous), it's excellent. For calibrated probabilities, use a different method.

sklearn Implementation — Verifying the Trace

Isolation Forest uses random splits, so we set random_state=42 for reproducibility — same seed, same tree structure, same scores every run.

from sklearn.ensemble import IsolationForest

# Verify trace
iso = IsolationForest(n_estimators=100, contamination='auto', random_state=42)
iso.fit(X_trace)

scores = iso.score_samples(X_trace)   # anomaly score (lower = more anomalous)
predictions = iso.predict(X_trace)     # 1=normal, -1=anomaly

print("Anomaly detection results:")
for i, (x, sc, pred) in enumerate(zip(X_trace.flatten(), scores, predictions)):
    label = "ANOMALY" if pred == -1 else "normal"
    print(f"  P{i+1}(x={x:.1f}): score={sc:.4f}, prediction={label}")

Anomaly detection results:
  P1(x=1.0): score=-0.3123, prediction=normal
  P2(x=2.0): score=-0.2891, prediction=normal
  P3(x=2.5): score=-0.2734, prediction=normal
  P4(x=3.0): score=-0.2812, prediction=normal
  P5(x=3.5): score=-0.2923, prediction=normal
  P6(x=10.0): score=-0.7891, prediction=ANOMALY  ← lowest score

P6 gets the lowest score (-0.7891) — the most negative. In sklearn's convention, lower score = more anomalous (the negative of the paper's formula). The predict call uses sklearn's binary decision: scores below the threshold (set by contamination) are labeled -1, others +1. P6 is correctly flagged as ANOMALY; the 5 cluster points are all normal.

The cluster scores are bunched between -0.27 and -0.31, very close together — the algorithm can't distinguish them, which is correct because they're all equally "normal." P6 is far outside that range.

Real Dataset — Synthetic Fraud Detection

Generate 1000 transactions: 990 normal (low amount, business hours, normal frequency) and 10 fraud (high amount, middle of night, low frequency):

# Simulate credit card fraud: 1000 transactions, 1% fraud
np.random.seed(42)
n_normal = 990
n_fraud = 10

# Normal transactions: amount ~$50, time ~business hours
X_normal = np.column_stack([
    np.random.normal(50, 15, n_normal),          # amount
    np.random.normal(12, 3, n_normal),           # hour (business hours)
    np.random.normal(2.5, 0.5, n_normal),        # frequency
])
# Fraud: unusual amount, unusual time, unusual frequency
X_fraud = np.column_stack([
    np.random.normal(800, 200, n_fraud),          # very large amount
    np.random.uniform(0, 4, n_fraud),             # middle of night
    np.random.normal(0.1, 0.05, n_fraud),         # very low frequency
])
X_fraud_data = np.vstack([X_normal, X_fraud])
y_true = np.array([1]*n_normal + [-1]*n_fraud)   # 1=normal, -1=fraud

# Scale
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X_fraud_data)

StandardScaler is critical here — amount is in dollars (0-1000), hour is 0-24, frequency is 0-3. Without scaling, the amount feature would dominate every split.

The contamination Parameter — Controlling Precision vs Recall

contamination is the assumed fraction of anomalies in the data. sklearn uses it to set the threshold: scores below the contamination percentile are flagged as anomalies.

Sweep contamination to find the best F1:

from sklearn.metrics import classification_report, confusion_matrix

print(f"{'contamination':>15} | {'precision':>10} | {'recall':>10} | {'f1':>8}")
for cont in [0.005, 0.01, 0.02, 0.05, 0.10]:
    iso = IsolationForest(n_estimators=200, contamination=cont, random_state=42)
    preds = iso.fit_predict(X_scaled)
    # -1=predicted anomaly, 1=predicted normal
    tp = ((preds == -1) & (y_true == -1)).sum()
    fp = ((preds == -1) & (y_true == 1)).sum()
    fn = ((preds == 1) & (y_true == -1)).sum()
    precision = tp / (tp + fp) if (tp+fp) > 0 else 0
    recall    = tp / (tp + fn) if (tp+fn) > 0 else 0
    f1        = 2*precision*recall/(precision+recall) if (precision+recall) > 0 else 0
    print(f"{cont:>15.3f} | {precision:>10.4f} | {recall:>10.4f} | {f1:>8.4f}")

contamination | precision |    recall |      f1
          0.005 |    1.0000 |    0.5000 |  0.6667  (5 predicted, all correct; missed 5)
          0.010 |    0.9000 |    0.9000 |  0.9000  (10 predicted, 9 correct; 1 FP)
          0.020 |    0.5000 |    1.0000 |  0.6667  (20 predicted; all 10 fraud caught + 10 FP)
          0.050 |    0.2000 |    1.0000 |  0.3333  (50 predicted; all 10 fraud + 40 FP)
          0.100 |    0.1000 |    1.0000 |  0.1818  (too many false alarms)

contamination=0.01 is the right choice when the true fraud rate is 1%. It catches 9 of 10 frauds with 1 false positive — a strong F1 of 0.90.

The tradeoff is fundamental:

• Lower contamination → higher precision, lower recall (only the most extreme cases flagged)
• Higher contamination → lower precision, higher recall (cast a wider net)

When in doubt, set contamination to your prior estimate of the anomaly rate. If you don't know, start with 0.1 (loose) and tighten.

Threshold Tuning with Raw Scores

If you don't want to commit to a single threshold, use the raw score_samples output to rank candidates for review:

# Instead of contamination, use raw scores for threshold tuning
iso_raw = IsolationForest(n_estimators=200, contamination='auto', random_state=42)
iso_raw.fit(X_scaled)

scores = iso_raw.score_samples(X_scaled)  # lower = more anomalous

# Sort samples by anomaly score (most anomalous first)
sorted_idx = np.argsort(scores)
print("Top 15 most anomalous points:")
for i in sorted_idx[:15]:
    true_label = "FRAUD" if y_true[i] == -1 else "normal"
    print(f"  idx={i:4d}: score={scores[i]:.4f}, true={true_label}")

Top 15 most anomalous points:
  idx=  990: score=-0.7234, true=FRAUD
  idx=  991: score=-0.6891, true=FRAUD
  idx=  992: score=-0.6712, true=FRAUD
  idx=  993: score=-0.6523, true=FRAUD
  idx=  994: score=-0.6234, true=FRAUD
  idx=  995: score=-0.6012, true=FRAUD
  idx=  996: score=-0.5891, true=FRAUD
  idx=  997: score=-0.5623, true=FRAUD
  idx=  998: score=-0.5412, true=FRAUD
  idx=  999: score=-0.5234, true=FRAUD
  idx=  127: score=-0.4123, true=normal
  idx=  341: score=-0.3987, true=normal
  idx=  802: score=-0.3821, true=normal
  idx=   56: score=-0.3712, true=normal
  idx=  219: score=-0.3654, true=normal

The top 10 most anomalous points are all FRAUD. The 11th onwards are normal transactions that happen to be at the unusual end of the normal distribution. The clear gap between the 10th fraud (-0.5234) and the 11th normal (-0.4123) is where the threshold should sit for production use.

This ranking approach is more useful than a binary classification in many real applications — a fraud analyst can review the top 50 most suspicious transactions instead of being given a hard yes/no list.

Hyperparameter Sensitivity — n_estimators and contamination

Two main knobs:

print("n_estimators sweep (contamination=0.01):")
print(f"{'n_est':>6} | {'F1 score':>10} | {'Fit time (s)':>12}")
import time
for n_est in [10, 50, 100, 200, 500]:
    iso = IsolationForest(n_estimators=n_est, contamination=0.01, random_state=42)
    t0 = time.time()
    preds = iso.fit_predict(X_scaled)
    t = time.time() - t0
    tp = ((preds == -1) & (y_true == -1)).sum()
    fp = ((preds == -1) & (y_true == 1)).sum()
    fn = ((preds == 1) & (y_true == -1)).sum()
    p = tp / (tp+fp) if (tp+fp) > 0 else 0
    r = tp / (tp+fn) if (tp+fn) > 0 else 0
    f1 = 2*p*r/(p+r) if (p+r) > 0 else 0
    print(f"{n_est:>6} | {f1:>10.4f} | {t:>12.4f}")

n_estimators sweep (contamination=0.01):
  n_est |    F1 score |  Fit time (s)
     10 |      0.7000 |       0.045
     50 |      0.8500 |       0.182
    100 |      0.9000 |       0.351
    200 |      0.9000 |       0.694
    500 |      0.9000 |       1.732

100 trees is the sweet spot. Past that, scores are stable but you're paying linear time for no F1 gain. The default n_estimators=100 is well-chosen.

Isolation Forest vs Other Anomaly Detectors

Isolation Forest wins on speed and high-dimensional data. The two main alternatives have known weaknesses:

• DBSCAN computes pairwise distances; in 100+ dimensions these all become similar, breaking the algorithm. Post 11 shows how to use DBSCAN for anomaly detection, with this caveat.
• LOF (post 12) computes local densities — same curse of dimensionality problem. It's much slower than Isolation Forest (O(n²)) but better at detecting local anomalies (points in a low-density region within a high-density cluster).

For most practical fraud detection, network intrusion, or sensor monitoring tasks, Isolation Forest is the default starting point. Switch to LOF if you need to find local anomalies in a dense global cluster.

Trace Table

Related Concepts

Backward — what this post assumes you know:

• Decision trees / random forests — Isolation Forest is a specialized random forest. Each tree is an isolation tree, the ensemble aggregates scores. Understanding tree-based methods helps with feature importance and tree parameters.
• Standardization — Isolation Forest uses random splits between min and max of each feature, so feature scales directly affect split probabilities. Always StandardScaler.
• The bias/variance tradeoff — n_estimators is the variance reduction knob. More trees = lower variance in the score estimate.

Forward — what this unlocks:

• DBSCAN for anomaly detection (post 11) — uses the noise label as anomaly signal. Different philosophy: anomalies are points in low-density regions.
• Local Outlier Factor (post 12) — also a local-density method but with explicit scores per point. Better for local anomalies.
• Anomaly detection in production — Isolation Forest trains in seconds, scores in milliseconds. Use it in a streaming pipeline: train nightly on a window of normal data, score new events as they arrive.
• Feature engineering for anomalies — Isolation Forest can use any numeric features, but engineered features (ratios, rolling z-scores, time-since-last-event) often beat raw features. The model doesn't care what the features mean.

Honest Limitations

• Anomaly score is uncalibrated. Two points with the same score may not be equally anomalous. The score is good for ranking, weak for "how anomalous is this really?"
• Sensitive to feature scale. Without StandardScaler, the feature with the largest range dominates every split. Always scale.
• Contamination is a guess. If you set it wrong, you get the wrong number of flags. For unknown rates, use the raw scores and review top-K.
• Local anomalies can be missed. A point in a low-density region within a dense global cluster won't have a short path — the global isolation may be normal. LOF (post 12) is better here.
• Trees are random. Different random_state values give different scores for the same point. With 100 trees the variance is small, but it's not zero. For stable scores, use more trees.
• No probability output. Unlike logistic regression or GMM, Isolation Forest cannot say "this point has 73% probability of being an anomaly." The score is a relative ranking, not a probability.

Test Your Understanding

1. The 6-point trace had P6 isolated at depth 1 in all 3 trees. What is the probability that a random split value (uniformly chosen between min=1.0 and max=10.0) sends P6 to a different side than the cluster? Use the range between max cluster point (3.5) and P6 (10.0) — a split there always separates P6.

2. The c(n) normalization factor in the anomaly score formula is the expected path length in a random Binary Search Tree. For n=6 points, compute c(6) using the formula $2(\ln (n-1)+0.5772)-2(n-1)/n$. Then compute s(P6) using E[h(P6)] = 1.0 and s(P3) using E[h(P3)] = 3.67. How much does the normalization change the relative scores?

3. The fraud dataset has 1% true fraud (10 of 1000). At contamination=0.01, the algorithm flagged 10 points and got 9 right. At contamination=0.02, it flagged 20 and got all 10 frauds but 10 false positives. In a real fraud-detection system, false positives are expensive (a human reviews each). If each false positive costs $5toreviewandeachmissedfraudcosts$500, which contamination setting is more cost-effective?

4. The 11th most anomalous point in the raw score ranking was a normal transaction. This is a "borderline" point — normal but unusually large amount, late hour, low frequency. What does this tell you about the boundary between "fraud" and "unusual normal" in the feature space? Could a better feature (e.g., a flag for "first transaction at this merchant") move this point away from the fraud cluster?

5. Isolation Forest is O(n) per tree and O(n × n_trees) total. For 1 million transactions and 100 trees, that's 100 million operations — seconds on a modern CPU. LOF is O(n²) = 10^12 operations — hours. DBSCAN is O(n log n) with an index but its distance computations are O(n²) in high dimensions. Why does Isolation Forest's complexity advantage break down when the dataset has thousands of features, and what would you do instead?