The goal of this project is to implement the original Isolation Forest algorithm by Fei Tony Liu, Kai Ming Ting, and Zhi-Hua Zhou. (A later version of this work is also available: Isolation-based Anomaly Detection.)
There are two general approaches to anomaly detection:
- model what normal looks like and then look for nonnormal observations
- focus on the anomalies, which are few and different. This is the interesting and relatively-new approach taken by the authors of isolation forests.
The isolation forest algorithm is original and beautiful in its simplicity; and also seems to work very well, with a few known weaknesses. The academic paper is extremely readable so you should start there.
For this project, we'll use three data sets:
-
Kaggle credit card fraud competition data set; download, unzip to get
creditcard.csv
-
Download the cancer dataset: cancer.csv;
-
Download the http dataset: http.csv;
My code assumes the data files are in the same directory as the code.
Using plot_anomalies.py, you can see the results of the isolation forest trying to detect anomalies. These data sets all have known targets indicating normal versus anomaly, but this information is only used during testing and not during training. In other words, we use this information to discover how well we can separate the distribution of normal versus anomalous observations. The section provides a number of results, but yours might look different because of the inherent randomness involved in selecting subsets of the data and constructing random trees. (click on the images to enlarge.)
http.csv, 200 trees, 99% desired TPR |
creditcard.csv, 200 trees, 80% desired TPR | creditcard.csv, 200 trees, 90% desired TPR |
cancer, 300 trees, 70% desired TPR | cancer, 300 trees, 80% desired TPR |
Running score.py, here is a sample run:
Running noise=False improved=False
INFO creditcard.csv fit time 0.23s
INFO creditcard.csv 18804 total nodes in 200 trees
INFO creditcard.csv score time 14.54s
SUCCESS creditcard.csv 200 trees at desired TPR 80.0% getting FPR 0.0300%
INFO http.csv fit time 0.28s
INFO http.csv 22430 total nodes in 300 trees
INFO http.csv score time 23.08s
SUCCESS http.csv 300 trees at desired TPR 99.0% getting FPR 0.0053%
INFO cancer.csv fit time 0.08s
INFO cancer.csv 8204 total nodes in 1000 trees
INFO cancer.csv score time 0.73s
SUCCESS cancer.csv 1000 trees at desired TPR 75.0% getting FPR 0.2857%
Due to the subsampling of the original data said and the inherent random nature of isolation forest, your results will differ even from run to run. I'm hoping that the variance is not so high that valid programs fail the scoring, but let me know.
Hooray !