Monash University and

• Main Authors: Fei Tony Liu, Kai Ming Ting, Zhi-hua Zhou
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: Categories and Subject Descriptors; H.2.8 [Database Management; Database Applications— Data Mining; I.2.6 [Artificial Intelligence; Learning General Terms; Algorithm; Design; Experimentation Additional Key Words and Phrases; Anomaly detection; outlier detection; ensemble methods; binary tree; Orca
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.673.5779; http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/tkdd11.pdf

Anomalies are data points that are few and different. As a result of these properties, we show that, anomalies are susceptible to a mechanism called isolation. This paper proposes a method called Isolation Forest (iForest) which detects anomalies purely based on the concept of isolation without employing any distance or density measure—fundamentally different from all existing methods. As a result, iForest is able to exploit subsampling (i) to achieve a low linear time-complexity and a small memory-requirement, and (ii) to deal with the effects of swamping and masking effectively. Our empirical evaluation shows that iForest outperforms ORCA, one-class SVM, LOF and Random Forests in terms of AUC, processing time, and it is robust against masking and swamping effects. iForest also works well in high dimensional problems containing a large number of irrelevant attributes, and when anomalies are not available in training sample.