🌲 Online Isolation Forest Algorithm

🎯 How Online Isolation Forest Works

1. Streaming Processing: Points arrive one by one from a data stream and are processed in real-time.

2. Sliding Window: Only the most recent ω points are kept in memory, older points are forgotten.

3. Dynamic Histograms: Each tree is a multi-dimensional histogram that splits bins when they reach maximum height η.

4. Learning & Forgetting: New points increase bin heights and create splits, while old points decrease heights and merge bins.

5. Anomaly Scoring: Points that require fewer splits to isolate (shorter path depth) get higher anomaly scores.

6. Ensemble Decision: Multiple trees vote to provide robust anomaly detection.

🔄 Split Merging Conditions

Merge Trigger: When left_child.height + right_child.height < η (max leaf samples)

Why Merging Happens:

• 📉 Forgetting Effect: As old points leave the sliding window, bin heights decrease
• 🎯 Sparse Regions: Areas with few data points lose their splits first
• 💾 Memory Efficiency: Removes unnecessary splits in low-density regions
• 🔄 Adaptation: Allows the tree structure to adapt to changing data patterns

Visual Cues: Watch the split colors - Yellow (stable) → Orange (about to merge) → Red (just merged)