IsolationbasedAnomalyDetection（IsolationbasedAnomalyDetection）.pdfVIP

Isolation-based Anomaly Detection Fei Tony Liu and Kai Ming Ting Gippsland School of Information Technology Monash University and Zhi-Hua Zhou National Key Laboratory for Novel Software Technology Nanjing University 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. 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, random tree ensemble, isolation, isolation forest 1. INTRODUCTION Anomalies are data patterns that have different data characteristics from normal instances. The ability to detect anomalies has significant relevance, and anomalies Author’s addresses: F. T. Liu K. M. Ting, Monash University, Gippsland Campus, Churchill, Victoria, 3842, Aus- tralia; email: {tony.liu},{kaiming.ting