Условие

Опишите Isolation Forest: как работает, почему быстрее density-based методов, как настраивать.

Решение

Подход

Isolation Forest (Liu et al., 2008) изолирует точки через серию случайных разделений. Аномалия — точка, которая изолируется за малое число шагов; нормальная — за много.

Алгоритм:

Строим T случайных деревьев (по умолч. 100).
Каждое дерево: subsample ψ точек, рекурсивно выбираем случайную фичу и случайный порог.
Путь от корня до изоляции точки h(x) — её «глубина».
Anomaly score: s(x, n) = 2^{−E[h(x)]/c(n)}, где c(n) ≈ 2H(n−1) − 2(n−1)/n — средняя глубина BST.
Близко к 1 → аномалия; ~0.5 → норма.

Почему быстрее density

Density-based (LOF, DBSCAN): O(n²) для расчёта расстояний. IF: O(n·log(ψ)) — sublinear в n, потому что subsample фиксированный ψ (обычно 256).

Реализация

from sklearn.ensemble import IsolationForest
import numpy as np
 
iforest = IsolationForest(
    n_estimators=100,
    max_samples=256,        # ψ
    contamination=0.05,     # ожидаемая доля аномалий
    max_features=1.0,
    random_state=42
)
iforest.fit(X_train)
scores = -iforest.score_samples(X_test)  # выше = аномальнее
preds = iforest.predict(X_test)           # 1=norm, -1=anomaly

Гиперпараметры

max_samples (ψ): 256 — sweet spot. Больше → точнее, медленнее. Меньше → шум.
contamination: задаёт порог через perсentile scores. Если не знаете — пробуйте 0.01-0.1.
n_estimators: 100 обычно достаточно. Больше → стабильнее, медленнее.
max_features: для high-dim полезно <1, помогает с irrelevant features.

Сравнение методов anomaly detection

	Isolation Forest	LOF	One-class SVM	Autoencoder
Сложность	O(n·log ψ)	O(n²)	O(n²-n³)	O(n·d·h)
Высокая размерность	OK (curse меньше)	плохо	плохо	хорошо
Категориальные	Плохо	Плохо	Плохо	Plug embeddings
Online	Нет (refit)	Нет	Нет	Streaming

Подводные камни

Контаминация неверна → порог сдвинут. Лучше брать scores и выставлять порог вручную по recall@k.
Высокая cardinality categorical (после encoding) делает random splits бесполезными → подавайте плотные эмбеддинги.
IF плохо на «cluster anomalies» (группа похожих аномалий): дерево их вместе изолирует на той же глубине что norm.
Scaling не нужен (splits — это quantiles), но extreme values полезно clip — иначе одно дерево их сразу режет.
На time series: IF не учитывает порядок. Нужны features (rolling mean, diffs) или separate temporal model.

Эталонный ответ

Isolation Forest изолирует точки случайными splits; аномалия — изолируется за малое число шагов. Score s = 2^{−E[h(x)]/c(n)}, ψ=256 по умолч., n_est=100. Быстрее density-based за счёт subsampling. Плохо для cluster anomalies и temporal data без feature engineering.

Сценарий ML: Isolation Forest для аномалий