An isolation tree recursively partitions feature space with random features and split points, seeking regions that isolate observations. It forms the individual-tree basis of an isolation forest rather than learning splits through information gain. section 5.2
An isolation tree is built and interpreted through these steps:
- Start with the full dataset at the root, then assign each child node a progressively smaller data region. section 5.2
- Choose a feature and a split point randomly within the current region, repeating the partition recursively. section 5.2
- Stop when a region contains one observation, only exact duplicates, or reaches the configured maximum depth. section 5.2
- Treat duplicate-only leaves specially by estimating the additional depth needed to isolate their records. section 9.4.2
Two-dimensional partitioning
A two-dimensional dataset can first be split randomly along the x dimension, then divided again into smaller regions. After three steps, one point may already occupy an isolated region while other nodes still contain multiple points. section 5.2
Figure 5.1 The training data for an Isolation Forest is divided randomly in each Isolation Tree. This shows the first three steps, resulting in eight nodes, each covering some subregion of the full dataspace. At this point (in the bottom right pane), one point (in the top right region) has already been isolated.
View the successive random partitions that create eight nodes and isolate an individual point. section 5.2
