Isolation forest
Isolation Forest is an algorithm for data anomaly detection. It detects anomalies using isolation (how far a data point is from the rest of the data), rather than modeling the normal points. It was initially developed by Fei Tony Liu and Zhi-Hua Zhou in 2007. The significance of his research lies in its deviation from the mainstream philosophy underpinning most existing anomaly detectors at the time, where all the normal instances are profiled before anomalies are identified as instances that do not conform to the distribution of the normal instances. Isolation forest introduces a different method that explicitly isolates anomalies using binary trees, demonstrating a new possibility of a faster anomaly detector that directly targets anomalies without profiling all the normal instances. The algorithm has a linear time complexity with a low constant and a low memory requirement, which works well with high volume data. Isolation forest split the data space using lines that are orthogonal to the origin and assigns higher anomaly scores to data points that need few splits to be isolated. In Fig.1, Isolation Forest was applied to the waiting time between eruptions and the duration of the eruption of the Old Faithful geyser in Yellowstone National Park. Darker shades of red indicate higher estimated anomaly scores. Anomalies in a big dataset may follow very complicated patterns, which are difficult to detect visually in the great majority of cases. This is the reason why the field of anomaly detection is well suited for the application of machine learning techniques. The most common techniques employed for anomaly detection are based on the construction of a profile of what is “normal”: anomalies are reported as those instances in the dataset that do not conform to the normal profile. Isolation Forest uses a different approach: instead of trying to build a model of normal instances, it explicitly isolates anomalous points in the dataset. The main advantage of this approach is the possibility of exploiting sampling techniques to the extent that is not allowed to the profile-based methods, creating a very fast algorithm with a low memory demand. (Wikipedia).
