Isolation forest

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Isolation forest is an unsupervised learning algorithm for anomaly detection that works on the principle of isolating anomalies, instead of the most common techniques of profiling normal points. In statistics, an anomaly (a.k.a. outlier) is an observation or event that deviates so much from other events to arouse suspicion it was generated by a different mean. For example, the graph in Fig.1 represents ingress traffic to a web server, expressed as the number of requests in 3-hours intervals, for a period of one month.

It is quite evident by simply looking at the picture that some points (marked with a red circle) are unusually high, to the point of inducing suspect that the web server might have been under attack at that time. On the other hand, the flat segment indicated by the red arrow also seems unusual and might possibly be a sign that the server was down during that time period. Anomalies in a big dataset may follow very complicated patterns, which are difficult to detect "by eye" 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 is an unsupervised learning algorithm for anomaly detection that works on the principle of isolating anomalies, instead of the most common techniques of profiling normal points. In statistics, an anomaly (a.k.a. outlier) is an observation or event that deviates so much from other events to arouse suspicion it was generated by a different mean. For example, the graph in Fig.1 represents ingress traffic to a web server, expressed as the number of requests in 3-hours intervals, for a period of one month.

It is quite evident by simply looking at the picture that some points (marked with a red circle) are unusually high, to the point of inducing suspect that the web server might have been under attack at that time. On the other hand, the flat segment indicated by the red arrow also seems unusual and might possibly be a sign that the server was down during that time period. Anomalies in a big dataset may follow very complicated patterns, which are difficult to detect "by eye" 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 an extent that is not allowed to the profile-based methods, creating a very fast algorithm with a low memory demand. More formally, let X = { x 1 , ..., x n } be a set of d-dimensional points and X' ⊂ X a subset of X.

Evidence and sources

An Isolation Tree (iTree) is defined as a data structure with the following properties: for each node T in the Tree, T is either an external-node with no child, or an internal-node with one "test" and exactly two daughter nodes (T l , T r ) a test at node T consists of an attribute q and a split value p such that the test q l or T r . In order to build an iTree, the algorithm recursively divides X' by randomly selecting an attribute q and a split value p, until either (i) the node has only one instance or (ii) all data at the node have the same values.

When the iTree is fully grown, each point in X is isolated at one of the external nodes. Intuitively, the anomalous points are those (easier to isolate, hence) with the smaller path length in the tree, where the path length h(x i ) of point x_i \in X is defined as the number of edges x i traverses from the root node to get to an external node.

A probabilistic explanation of iTree is provided in the iForest original paper. c(m) = \begin{cases} 2H(m-1)-\frac{2(m-1)}{n} & \text{for }m>2 \\ 1 & \text{for }m=2 \\ 0 & \text{otherwise} \end{cases} where m is the testing data size, m is the size of the sample set and H is the harmonic number, which can be estimated by H(i)=ln(i)+\gamma , where \gamma=0.5772156649 is the Euler-Mascheroni constant.

Impact

The value of c(m) above represents the average of h(x) given m, so we can use it to normalise h(x) and get an estimation of the anomaly score for a given instance x: s(x,m)=2^\frac{-E(h(x))}{c(m)} where E(h(x)) is the average value of h(x) from a collection of iTrees.

It is interesting to note that for any given instance x: if s is close to 1 then x is very likely to be an anomaly if s is smaller than 0.5 then x is likely to be a normal value if for a given sample all instances are assigned an anomaly score of around 0.5, then it is safe to assume that the sample doesn't have any anomaly

Text derived from https://en.wikipedia.org/w/index.php?oldid=1377013056 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001377013056 · captured 1790505402.0 · version history

Cite this page as: encyclopegia.org, “Isolation forest”, snapshot enwiki-001377013056. https://encyclopegia.org/a/isolation-forest

Sources cited in this revision

5 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.