PaperlayerView exact revision on arXiv

Source-linked AI summary

Extended Isolation Forest

Sahand Hariri, Matias Carrasco Kind, Robert J. Brunner

arXiv:1811.02141v3cs.LGastro-ph.IMstat.ML

TL;DR

The paper addresses biased and inconsistent anomaly scores produced by standard Isolation Forest’s branching criteria. It evaluates random data transformations and EIF’s random-slope hyperplanes, finding more robust scores and consistently better performance without sacrificing computational efficiency.

  • Problem

    Standard Isolation Forest assigns biased and inconsistent anomaly scores because of its tree-branching criteria.

  • Method

    The paper compares randomly transforming data before each tree with EIF, which generalizes branching by using hyperplanes with random slopes.

  • Results

    EIF produces smaller score variances that decrease with extension level and performs consistently better than standard Isolation Forest across the considered examples and real-world benchmarks.

  • Takeaways & Limitations

    EIF provides more reliable and robust anomaly scores, sometimes detects dataset structure more accurately, and preserves computational efficiency.

  • Takeaways & Limitations

    Rotated-tree correction requires per-tree rotation metadata, retains underlying rectangular bias, and can become cumbersome in large or high-dimensional datasets.

Abstract

from arXiv · show

We present an extension to the model-free anomaly detection algorithm, Isolation Forest. This extension, named Extended Isolation Forest (EIF), resolves issues with assignment of anomaly score to given data points. We motivate the problem using heat maps for anomaly scores. These maps suffer from artifacts generated by the criteria for branching operation of the binary tree. We explain this problem in detail and demonstrate the mechanism by which it occurs visually. We then propose two different approaches for improving the situation. First we propose transforming the data randomly before creation of each tree, which results in averaging out the bias. Second, which is the preferred way, is to allow the slicing of the data to use hyperplanes with random slopes. This approach results in remedying the artifact seen in the anomaly score heat maps. We show that the robustness of the algorithm is much improved using this method by looking at the variance of scores of data points distributed along constant level sets. We report AUROC and AUPRC for our synthetic datasets, along with real-world benchmark datasets. We find no appreciable difference in the rate of convergence nor in computation time between the standard Isolation Forest and EIF.

1 Introduction

Isolation Forest is efficient and model-free but its axis-parallel branching introduces bias in anomaly scores. The paper diagnoses this shortcoming and introduces Extended Isolation Forest (EIF) to improve the algorithm without resorting to fundamentally different methods.

  • Isolation Forest detects anomalies using aggregated tree-branch lengths, with shorter branches indicating anomalous points.
  • The standard algorithm suffers from bias arising from how tree branching takes place, affecting anomaly scores assigned to data points.
  • EIF modifies Isolation Forest to remedy this bias while retaining the algorithm’s basic idea and tree-based approach.
  • EIF uses hyperplanes with random slopes rather than only axis-parallel splits, addressing a missing discussion of standard Isolation Forest’s shortcomings.
  • The paper motivates improvement through score maps, analyzes the shortcomings’ causes and consequences, and compares EIF with standard Isolation Forest using variance, convergence, AUROC, and AUPRC.

2 Motivation

Simple synthetic datasets reveal that standard Isolation Forest anomaly-score maps contain axis-aligned artifacts and can misrepresent structure. These examples motivate extending the algorithm’s branching process.

  • For a centered two-dimensional normal distribution, anomaly scores should increase radially outward in an approximately circular and symmetric pattern.
  • Standard Isolation Forest produces lower-score rectangular regions along the x and y directions despite similar radial distances from the center.
  • For two clusters centered near (0, 10) and (10, 0), scores should be lowest at the cluster centers and higher elsewhere.
  • The two-cluster score map contains rectangular bands and amplified intersections that create “ghost” clusters near (0, 0) and (10, 10).
  • For sinusoidal data with Gaussian noise, standard Isolation Forest treats the structure as a rectangular blob with horizontal and vertical bands.
  • The paper proposes extending Isolation Forest to fix these undesirable score-map features.

3 Generalization of Isolation Forest

Isolation Forest builds binary trees by repeatedly selecting a feature and cutoff, then scores points from their average path depths. The generalization exposes the resulting axis-aligned bias and introduces randomized hyperplane directions to reduce it.

  • Standard Isolation Forest: Isolation Forest randomly selects a feature and cutoff at each split, routes points by the cutoff, and converts mean tree depth into anomaly scores.E(h(x)) is the mean depth reached by point x across trees, while c(n) normalizes the score using unsuccessful binary-search-tree depth.
  • Standard Isolation Forest: Shorter branches indicate anomalies because anomalous points are isolated more quickly, whereas nominal points may reach the tree-depth limit.The standard examples show an anomaly isolated after three cuts and a central nominal point requiring many cuts.
  • Bias in Standard Isolation Forest: Axis-aligned cuts cluster near dense data while also crossing sparse regions, producing biased treatment and different scoring possibilities for similarly anomalous regions.Repeated vertical and horizontal cuts can intersect into artificial “ghost” cluster regions and obscure repeated or nonrectangular structure.
  • Proposed Extensions: Two remedies are proposed: randomly rotate each tree’s training data or directly randomize branch-cut directions using hyperplanes with random slopes.The rotation method averages out bias but requires per-tree transformation bookkeeping; the randomized-direction method is presented as the more general approach.
  • Extended Isolation Forest: Extended Isolation Forest selects intercepts from the node’s data range and random normal vectors, preserving concentration near data clusters without artificially overemphasizing other regions.Its extension levels range from standard Isolation Forest at the lowest level to fully extended hyperplanes, with higher extension reducing bias.

4 Results and Discussion

The results compare Standard, Rotated, and Extended Isolation Forest using score maps, score variance, AUC values, and convergence. EIF removes axis-alignment artifacts, produces more robust scores, generally improves AUC, and does not appreciably change convergence rates or computational efficiency.

  • Score Maps: EIF removes artificial low-score bands and produces expected, more symmetric anomaly-score maps for a single normally distributed blob.Rotating subsampled data averages out artifacts, while EIF eliminates the artificial bands in the x and y directions.
  • Score Maps: Both Rotated and Extended Isolation Forest remove ghost regions for two blobs, while EIF captures the higher anomaly-score region between the blobs.The standard method fails to capture this additional structure.
  • Score Maps: EIF tracks sinusoidal data more tightly than the rotated method and preserves its structure better than Standard Isolation Forest.Standard Isolation Forest treats the sinusoid as a rectangular blob with wide rectangular bands.
  • Variance of the Anomaly Scores: Beyond 3σ, EIF produces lower score variance than Standard Isolation Forest, and variance decreases as the extension level increases.The fully extended case produces the most reliable and robust anomaly scores in the reported higher-dimensional analysis.
  • AUC Comparison: EIF generally achieves better AUC results than Standard Isolation Forest, although improvements range from modest to appreciable across datasets.The reported comparison includes both AUROC and AUPRC values for quantifying performance.
  • Convergence of Anomaly Scores: Scores settle quickly with forest size, with no appreciable convergence-rate difference between Standard Isolation Forest and EIF.The standard method has higher variance, but the reported convergence rates indicate that both methods should use the same number of trees.

5 Conclusions

The paper traces inconsistent anomaly scores to bias in standard Isolation Forest branching and introduces EIF to remedy it. EIF reduces score variance, performs better across evaluated examples, and preserves computational efficiency.

  • 5 Conclusions: Score-map artifacts arise from coordinate-dependent bias in standard Isolation Forest branching, producing artificial regions of higher or lower anomaly scores.Branching along randomly selected features and values makes the number of operations depend on a point’s coordinate-frame location.
  • 5 Conclusions: The paper proposes rotation before each tree and EIF, which uses branching hyperplanes with arbitrary slopes rather than coordinate-parallel hyperplanes.EIF is preferred over rotation and extends to high-dimensional datasets.
  • 5 Conclusions: EIF produces smaller score variances along constant anomaly-score level sets, with variance decreasing as the extension level increases.The standard algorithm shows high variance in anomaly regions, whereas EIF yields remarkably smaller variances.
  • 5 Conclusions: EIF performed consistently better than standard Isolation Forest across the examples and real-world benchmark datasets considered.The paper reports AUC for ROC and PRC across synthetic examples and real-world benchmarks.
  • 5 Conclusions: The extension delivers more reliable and robust anomaly scores without sacrificing computational efficiency.The authors also report improved accuracy in some cases and publicly provide a Python implementation with reproducible notebooks.
Loading 1811.02141v3…