Feature Importance in Isolation Forest

Question

In an unsupervised setting for higher-dimensional data (e.g. 10 variables (numerical and categorical), 5000 samples, ratio of anomalies likely 1% or below but unknown) I am able to fit the isolation forest and retrieve computed anomaly scores (following the original paper and using the implementation in scikit-learn). This gives me a ranking of potential anomalies to consider. However, how would I further assess the validity of these flags? How can I understand which feature has contributed to the anomaly score the most? Feature importance techniques usually applied in random forests do not seem to work in case of the isolation forest.

Interested to hear your thoughts. Any help is very appreciated.

Answer 1

I believe it was not implemented in scikit-learn because in contrast with Random Forest algorithm, Isolation Forest feature to split at each node is selected at random. So it is not possible to have a notion of feature importance similar to RF.

Having said that, If you are very confident about the results of Isolation Forest classifier and you have a capacity to train another model then you could use the output of Isolation Forest i.e -1/1 values as target-class to train a Random Forest classifier. This will give you feature importance for detecting anomaly.

Please note that I haven't tried this myself, so I can't comment on accuracy of this proposed approach.

Answer 2

Have you tried looking at SHAP statistics as a way of measuring feature importance for your isolation forest exercise? Here's a good explanation of SHAP https://towardsdatascience.com/explain-your-model-with-the-shap-values-bc36aac4de3d and you can build an explainer object with any tree based model. From there you can also look at how your features affect individual predictions.

Answer 3

Briefly reiterating first what others have mentioned, one could use a surrogate model like a BDT that is intentionally overtrained on the output of the isolation forest (instead of using the binary output as Khurram Majeed suggested, you could directly train it on the anomaly score). However, we cannot be sure that the surrogate model is learning the same decision paths as the iForest.

On the other hand, the principle behind SHAP is clearer than any surrogate model used to explain the iForest (another good explanation of SHAP). Perhaps because the BDT is doing a poorer job, I found that the feature importances derived from a surrogate BDT and SHAP agreed only roughly, and sometimes disagreed wildly. Both local and global feature importances were considered in this comparison.

Despite all this the iForest is interpretable if its underlying principle is taken advantage of: that outliers have short decision paths on average over all the trees in the iForest. The features that were cut on in these short paths must be more important than those cut on in long decision paths. So here's what you can do to get feature importances:

1. Determine a threshold for decision path length. The authors of the iForest algorithm recommend from empirical studies a subsampling size of 256 [ref]. This is the number of events (sampled from all the data) that is fed into each tree. If you're using this subsampling size, the trees in the iForest can only grow up to $\log_2 (256) = 8$ nodes in depth. Thus you might choose a path length threshold of 3 or 4.
2. For each event, loop through the trees in the iForest and select paths that are shorter than the threshold path length. In these paths, count which features are being cut at each node, the depth of each node, and the numbers of events split at that node. If you're using sklearn's implementation of the iForest, this script may help you in digging through their tree structure. This plot shows what you should have at this stage.
3. Now that you have feature counts of all the trees at each cut depth, you can condense these into a final feature ranking. This can be done by assigning weights to each node and adding the counts up. For instance you may want to assign larger weights to feature counts that are cut higher up in the tree (and are thus more responsible in creating a overall shorter decision path), and smaller weights to features cut further down. You can also incorporate the ratio of events split at each node into your weights - if there is a large disparity of events split by a certain cut, then that cut is probably important.

Note that there is a lot of freedom to assign weights here, and it may be that your choices are ad-hoc and dataset dependent. I'm not entirely sure, but this may be the reason that feature importances were not implemented in sklearn's iForest.

Anyway, here's a condensation of the feature counts shown above. I'm using a simple 'geometric weight' of 0.5 - essential the number of counts cut first get no modification, the number of counts counts cut second get halved, and those cut third get quartered. As you can see, there are a lot of features that aren't very important to isolate this particular event. Here is the SHAP force plot for this event, nice agreement even with a very simple weight assignment! I've shown the feature rankings for an individual event, but you can easily get global importances by averaging the feature counts over entire dataset. This way you can drop features that don't contribute much to the iForest classification.

If you're using sklearn or other Python based implementations, the biggest disadvantage to this technique is speed. It takes a while to root through all the trees, and if you're interested in global importances you'll have to loop though all the events as well.

Answer 4

Since a while back one can use SHAP to exlain scikit-learn Isolation Forest models. Example code and output in this answer.

Answer 5

Interpretable Anomaly Detection with DIFFI: Depth-based Isolation Forest Feature Importance

In this paper, they proposed model-specific methods (i.e. methods based on the particular structure of the IF model) to address the mentioned issues.

Specifically,

• A global interpretability method, called Depth-based Isolation Forest Feature Importance (DIFFI), to provide Global Feature Importances (GFIs) which represents a condensed measure describing the macro behaviour of the IF model on training data.
• A local version of the DIFFI method, called Local-DIFFI, to provide Local Feature Importances (LFIs) is aimed at interpreting individual predictions made by the IF model at test time.
• A simple and effective procedure to perform unsupervised feature selection for Anomaly Detection problems based on the DIFFI method.

@article{carletti2020interpretable,
  title={Interpretable anomaly detection with diffi: Depth-based feature importance for the isolation forest},
  author={Carletti, Mattia and Terzi, Matteo and Susto, Gian Antonio},
  journal={arXiv preprint arXiv:2007.11117},
  year={2020}
}
 
https://doi.org/10.48550/arXiv.2007.11117

Code for the paper "Interpretable Anomaly Detection with DIFFI: Depth-based Isolation Forest Feature Importance".