Anomaly Detection Outlier Detection Isolation Forest
# Anomaly Detection: Outlier Detection & Isolation Forest
## Introduction & Motivation
Anomaly detection: identify outliers/anomalies. Isolation Forest: random partitioning; anomalies isolated quickly. Autoencoders: reconstruction error; anomalies harder to reconstruct. Local outlier factor (LOF): density-based; local context. Applications: fraud detection, network security, sensor data monitoring, medical diagnosis.
Motivation: Anomalies rare; binary classification inappropriate. Unsupervised: learn normal, detect deviations.
Applications: Fraud, security, medical, sensor monitoring.
---
## Core Concepts & Theory
### Isolation Forest
Random partitioning tree; anomalies isolated early.
### Autoencoders
Reconstruction error high for anomalies.
### Density-Based
LOF: local outlier factor; density context.
---
## Mathematical Formulation
Isolation score:
$$ ext{anomaly\_score} = 2^{-E[h(x)] / c(n)}$$
where h(x) = tree depth, c(n) = normalization.
Reconstruction error:
$$ ext{error} = \|x - ext{decode}( ext{encode}(x))\|^2$$
Local outlier factor:
$$ ext{LOF}_k(x) = \frac{ ext{reachability}_k(x)}{ ext{local\_reachability\_density}(x)}$$
---
## Advanced Theory & Extensions
### One-Class SVM
Support vector machine; outlier boundary.
### DBSCAN
Density-based clustering; outliers unassigned.
### Statistical Methods
Gaussian, Mahalanobis; distribution-based.
---
## Computational Considerations
Isolation Forest: O(N log N) training; O(log N) prediction.
LOF: O(N²) pairwise distances.
Autoencoder: O(encoder + decoder).
---
## Practical Implementation Strategies
### Threshold Selection
Data-dependent; ROC curve typical.
### Feature Scaling
Normalize features; distance metrics.
### Ensemble Methods
Combine multiple detectors; robust.
---
## Benchmark Datasets & Evaluation
KDD CUP 99: Network intrusion detection.
Credit Card Fraud: Highly imbalanced; AUC metric.
Synthetic: Known ground truth.
---
## Key Challenges & Limitations
### Threshold Selection
No universal threshold; context dependent.
### Concept Drift
Anomalies evolve; retrain needed.
### Imbalance Severity
Anomalies rare; metrics: precision, recall, F1.
---
## Hyperparameter Tuning
Isolation Forest contamination: Data-dependent; 5-10%.
Autoencoder threshold: ROC optimization.
LOF neighbors k: Typically 5-20.
---
## Real-World Applications & Case Studies
Credit Card Fraud: Time-series; evolving patterns.
Network Intrusion: KDD benchmark standard.
Medical: Disease detection; patient monitoring.
---
## Integration with Other Methods
Anomaly + Time Series → temporal anomalies.
Anomaly + Active Learning → flag uncertain.
---
## Summary & Key Takeaways
Anomaly detection via isolation forests, autoencoders, and density methods identifies outliers through partitioning, reconstruction error, and local context analysis.
Principles:
1. Isolation: anomalies isolated by partitioning.
2. Reconstruction: high error for anomalies.
3. Density: LOF local context.
4. Threshold: ROC optimization.
5. Ensemble: combine detectors.
---
---
## Appendix: Practical Labs
### Lab 1: Isolation Forest
import numpy as np
class SimpleIsolationForest:
def __init__(self, n_trees=100, max_depth=10):
self.n_trees = n_trees
self.max_depth = max_depth
def _random_partition(self, X):
"""Random partitioning"""
depths = []
for _ in range(self.n_trees):
depth = self._tree_depth(X, max_depth=self.max_depth)
depths.append(depth)
return depths
def _tree_depth(self, X, max_depth=10):
"""Recursively partition"""
if len(X) <= 1 or max_depth == 0:
return max_depth
feature = np.random.randint(0, X.shape[1])
threshold = np.random.uniform(X[:, feature].min(), X[:, feature].max())
mask = X[:, feature] < threshold
left = self._tree_depth(X[mask], max_depth - 1)
right = self._tree_depth(X[~mask], max_depth - 1)
return max(left, right)
def anomaly_score(self, X):
depths = self._random_partition(X)
# Normalize
scores = np.mean(depths) / self.max_depth
return scores
# Test
np.random.seed(42)
forest = SimpleIsolationForest(n_trees=10)
X = np.random.randn(50, 5)
scores = forest.anomaly_score(X)
assert 0 <= scores <= 1, "Score in [0,1]"
print("✓ Isolation Forest working")
if __name__ == "__main__":
print("Lab 1: IsolationForest - PASSED")### Lab 2: Reconstruction Error
import numpy as np
def reconstruction_error(X, X_reconstructed):
"""Compute reconstruction error per sample"""
error = np.mean((X - X_reconstructed) ** 2, axis=1)
return error
def detect_anomalies(error, threshold=None):
"""Detect anomalies via threshold"""
if threshold is None:
threshold = np.percentile(error, 95) # 5% anomalies
anomalies = error > threshold
return anomalies
# Test
np.random.seed(42)
X = np.random.randn(100, 10)
X_recon = X + 0.1 * np.random.randn(100, 10)
error = reconstruction_error(X, X_recon)
anomalies = detect_anomalies(error)
assert len(anomalies) == 100, "Anomalies per sample"
assert anomalies.sum() <= 10, "At most 10% anomalies"
print("✓ Reconstruction error working")
if __name__ == "__main__":
print("Lab 2: ReconError - PASSED")### Lab 3: Local Outlier Factor (LOF)
import numpy as np
def compute_lof(X, k=5):
"""Compute local outlier factor"""
n = len(X)
lof_scores = np.zeros(n)
# Pairwise distances
distances = np.linalg.norm(X[:, np.newaxis] - X[np.newaxis, :], axis=2)
for i in range(n):
# k-nearest neighbors
knn_dist = np.sort(distances[i])[1:k+1]
avg_knn_dist = knn_dist.mean()
# Local density
neighbors = np.argsort(distances[i])[1:k+1]
neighbor_densities = []
for j in neighbors:
neighbor_knn_dist = np.sort(distances[j])[1:k+1]
neighbor_densities.append(neighbor_knn_dist.mean())
# LOF
lof_scores[i] = np.mean(neighbor_densities) / (avg_knn_dist + 1e-8)
return lof_scores
# Test
np.random.seed(42)
X = np.random.randn(50, 5)
lof_scores = compute_lof(X, k=5)
assert lof_scores.shape == (50,), "LOF per sample"
assert (lof_scores > 0).all(), "LOF positive"
print("✓ LOF working")
if __name__ == "__main__":
print("Lab 3: LOF - PASSED")### Lab 4: Anomaly Detection Metrics
import numpy as np
def compute_anomaly_metrics(y_true, y_pred):
"""Compute precision, recall, F1 for anomalies"""
tp = ((y_pred == 1) & (y_true == 1)).sum()
fp = ((y_pred == 1) & (y_true == 0)).sum()
fn = ((y_pred == 0) & (y_true == 1)).sum()
precision = tp / (tp + fp + 1e-8)
recall = tp / (tp + fn + 1e-8)
f1 = 2 * (precision * recall) / (precision + recall + 1e-8)
return precision, recall, f1
# Test
np.random.seed(42)
y_true = np.concatenate([np.ones(5), np.zeros(95)]) # 5% anomalies
y_pred = np.concatenate([np.ones(6), np.zeros(94)]) # Predict 6
precision, recall, f1 = compute_anomaly_metrics(y_true, y_pred)
assert 0 <= precision <= 1, "Precision in [0,1]"
assert 0 <= recall <= 1, "Recall in [0,1]"
assert 0 <= f1 <= 1, "F1 in [0,1]"
print("✓ Anomaly metrics working")
if __name__ == "__main__":
print("Lab 4: Metrics - PASSED")