Extended Isolation Forest
  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.
