Skip to content

Isolation Forest

Algorithm

Isolation Forest builds trees by randomly selecting a feature and a split value. Observations isolated by fewer splits receive higher anomaly scores. Averaging path lengths across trees reduces the influence of a single random partition.

Inputs and limitations

  • Pass equally sized numeric feature lists with at least two observations and some variation.
  • Choose n_itree >= 1 and, when supplied, 2 <= max_samples <= len(samples).
  • score and predict accept one sample. Higher scores are more anomalous; predict returns -1 for outliers and 1 for normal observations.
  • score_threshold is a score cutoff, not an expected fraction of outliers.
  • Set random_seed to an integer for reproducible fits.

Minimal example

from toyml.ensemble import IsolationForest

samples = [[-0.2], [0.0], [0.1], [0.3], [8.0]]
model = IsolationForest(n_itree=20, random_seed=42).fit(samples)
print(model.score([8.0]))
print(model.predict([8.0]))

API

toyml.ensemble.isolation_forest.IsolationForest dataclass 

IsolationForest(n_itree: int = 100, max_samples: None | int = None, score_threshold: float = 0.5, random_seed: int | None = None)

Isolation Forest.

Examples:

>>> from toyml.ensemble.isolation_forest import IsolationForest
>>> dataset = [[-1.1], [0.3], [0.5], [100.0]]
>>> IsolationForest(n_itree=100, max_samples=4).fit_predict(dataset)
[1, 1, 1, -1]
References

Liu, Fei Tony, Kai Ming Ting, and Zhi-Hua Zhou. "Isolation forest." 2008 eighth ieee international conference on data mining. IEEE, 2008.

n_itree class-attribute instance-attribute 

n_itree: int = 100

The number of isolation tree in the ensemble.

max_samples class-attribute instance-attribute 

max_samples: None | int = None

The number of samples to draw from X to train each base estimator.

score_threshold class-attribute instance-attribute 

score_threshold: float = 0.5

The score threshold that is used to define outlier: If sample's anomaly score > score_threshold, then the sample is detected as outlier(predict return -1); otherwise, the sample is normal(predict return 1)

random_seed class-attribute instance-attribute 

random_seed: int | None = None

Controls sampling and the derived seeds of all isolation trees.

max_samples_ class-attribute instance-attribute 

max_samples_: int | None = field(default=None, init=False)

The actual sample count used by each fitted tree.

itrees_ class-attribute instance-attribute 

itrees_: list[IsolationTree] = field(default_factory=list, init=False)

The isolation trees in the forest.

fit 

fit(dataset: list[list[float]]) -> IsolationForest

Fit the isolation forest model.

Source code in src/toyml/ensemble/isolation_forest.py 
170
171
172
173
174
175
176
177
178
def fit(self, dataset: list[list[float]]) -> IsolationForest:
    """Fit the isolation forest model."""
    # Replay integer-seeded fits; None retains the instance's independent ongoing stream.
    if self.random_seed is not None:
        self.random_state.seed(self.random_seed)
    self.max_samples_ = len(dataset) if self.max_samples is None else min(self.max_samples, len(dataset))

    self.itrees_ = self._fit_itrees(dataset)
    return self

score 

score(sample: list[float]) -> float

Predict the sample's anomaly score.

PARAMETER DESCRIPTION
sample

The data sample.

TYPE: list[float]

RETURNS DESCRIPTION
float

The anomaly score.
Source code in src/toyml/ensemble/isolation_forest.py 
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
def score(self, sample: list[float]) -> float:
    """Predict the sample's anomaly score.

    Args:
        sample: The data sample.

    Returns:
        The anomaly score.
    """
    if self.max_samples_ is None:
        msg = "The model is not fitted yet!"
        raise ValueError(msg)
    itree_path_lengths = [itree.get_sample_path_length(sample) for itree in self.itrees_]
    expect_path_length = sum(itree_path_lengths) / len(itree_path_lengths)
    score: float = 2 ** (-expect_path_length / bst_expect_length(self.max_samples_))
    return score

predict 

predict(sample: list[float]) -> int

Predict the sample is outlier ot not.

PARAMETER DESCRIPTION
sample

The data sample.

TYPE: list[float]

RETURNS DESCRIPTION
Outlier

-1; Normal: 1.

TYPE: int

Source code in src/toyml/ensemble/isolation_forest.py 
197
198
199
200
201
202
203
204
205
206
207
208
209
210
def predict(self, sample: list[float]) -> int:
    """Predict the sample is outlier ot not.

    Args:
        sample: The data sample.

    Returns:
        Outlier: -1; Normal: 1.
    """
    score = self.score(sample)
    # outlier
    if score > self.score_threshold:
        return -1
    return 1

toyml.ensemble.isolation_forest.IsolationTree dataclass 

IsolationTree(max_height: int, random_seed: int | None = None)

The isolation tree.

Note

The isolation tree is a proper(full) binary tree, which has either 0 or 2 children.

max_height instance-attribute 

max_height: int

The maximum height of the tree.

random_seed class-attribute instance-attribute 

random_seed: int | None = None

Controls feature selection, split values, and derived child seeds.

sample_size_ class-attribute instance-attribute 

sample_size_: int | None = field(default=None, init=False)

The sample size.

feature_num_ class-attribute instance-attribute 

feature_num_: int | None = field(default=None, init=False)

The number of features at each sample.

left_ class-attribute instance-attribute 

left_: IsolationTree | None = field(default=None, init=False)

The left child of the tree.

right_ class-attribute instance-attribute 

right_: IsolationTree | None = field(default=None, init=False)

The right child of the tree.

split_at_ class-attribute instance-attribute 

split_at_: int | None = field(default=None, init=False)

The index of feature which is used to split the tree's samples into children.

split_value_ class-attribute instance-attribute 

split_value_: float | None = field(default=None, init=False)

The value of split_at feature that use to split samples

fit 

fit(samples: list[list[float]]) -> IsolationTree

Fit the isolation tree.

Source code in src/toyml/ensemble/isolation_forest.py 
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
def fit(self, samples: list[list[float]]) -> IsolationTree:
    """Fit the isolation tree."""
    # Refit from the same seed rather than from the end of the previous fit's stream.
    if self.random_seed is not None:
        self.random_state.seed(self.random_seed)
    self.left_ = self.right_ = None
    self.split_at_ = self.split_value_ = None
    self.sample_size_ = len(samples)
    self.feature_num_ = len(samples[0])
    # exNode
    if self.max_height == 0 or self.sample_size_ == 1:
        return self
    # inNode
    left_itree, right_itree = self._get_left_right_child_itree(samples)
    self.left_, self.right_ = left_itree, right_itree
    return self

get_sample_path_length 

get_sample_path_length(sample: list[float]) -> float

Get the sample's path length to the external(leaf) node.

PARAMETER DESCRIPTION
sample

The data sample.

TYPE: list[float]

RETURNS DESCRIPTION
float

The path length of the sample.
Source code in src/toyml/ensemble/isolation_forest.py 
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
def get_sample_path_length(self, sample: list[float]) -> float:
    """Get the sample's path length to the external(leaf) node.

    Args:
        sample: The data sample.

    Returns:
        The path length of the sample.
    """
    if self.sample_size_ is None:
        msg = "The model is not fitted yet!"
        raise ValueError(msg)
    if self.is_external_node():
        assert self.sample_size_ is not None
        if self.sample_size_ == 1:
            return 0
        return bst_expect_length(self.sample_size_)

    assert self.split_at_ is not None
    assert self.split_value_ is not None
    if sample[self.split_at_] < self.split_value_:
        assert self.left_ is not None
        return 1 + self.left_.get_sample_path_length(sample)
    assert self.right_ is not None
    return 1 + self.right_.get_sample_path_length(sample)

is_external_node 

is_external_node() -> bool

The tree node is external(leaf) node or not.

Source code in src/toyml/ensemble/isolation_forest.py 
88
89
90
def is_external_node(self) -> bool:
    """The tree node is external(leaf) node or not."""
    return bool(self.left_ is None and self.right_ is None)