Isolation Forest と One-Class SVM の違いは？

Isolation Forest はランダム分割の経路長で異常度を測り、計算が高速で大規模データに向きます。One-Class SVM は境界を学習する手法で、小〜中規模データで密度の境界を厳密に捉えたい場合に使います。

contamination はどう決める？

想定する異常率を 0.001〜0.1 で指定します。本番環境で異常データが少ない場合は 0.01 程度から始め、誤検知率と検知率のバランスを見て調整します。

ラベル付きデータがあるなら教師ありを使うべき？

ラベルが十分にあれば教師あり分類のほうが精度は高くなりやすいです。ただし、未知の異常パターンへの対応や、クラス不均衡が極端なケースでは Isolation Forest の方が頑健に動くことがあります。

Isolation Forest

入門

02.8.3

Isolation Forest

最終更新 2020-03-11 読了時間 3 分

まとめ

Isolation Forest は、ランダムに選んだ軸とランダムな位置で空間を切る操作を繰り返し、「何回切ったら 1 点だけになるか」で異常度を測る手法です。密集した正常点は何度切っても仲間が残りますが、外れ値は 1〜2 回で孤立するので、経路長（分割回数）が短い点ほど異常スコアが高くなります。scikit-learn の IsolationForest では n_estimators 本の木で経路長を平均し、contamination で指定した割合の点を predict が -1（異常）と返します。読み終えると、score_samples の値の向きと、contamination=0.1 が「スコア上位 10% を異常とする閾値」を決めていることが分かります。

直感 #

教室の 40 人が中央に固まって座り、1 人だけ隅に座っているとします。「縦か横に 1 本ずつ線を引いて、誰かを 1 人だけに区切る」ゲームをすると、隅の 1 人は線 1 本で区切れますが、中央の誰かを 1 人にするには何本も線が要ります。Isolation Forest はこのゲームをランダムな線で 200 回（n_estimators=200）繰り返し、区切れるまでの線の本数の平均が短い点を異常と呼びます。外れ値を「正常の分布を推定してから外側を探す」のではなく、「孤立させやすさ」で直接測るのが特徴です。

データから max_samples 点を抜き出すランダムな軸・位置で 2 分割 1 点になるか深さ上限まで繰り返す木を n_estimators 本作る各点の平均経路長を計算経路長が短い点ほど高い異常スコア contamination で閾値を決め -1 / 1 を返す

何が起きているか（ステップで見る） #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。右下の外れ値（赤）が 1 回で孤立し、中央のまとまり（青）は 8 回切っても残る様子を比べてください。

見るポイント：少ない回数で孤立する点ほど異常。外れ値（赤）は 1 回目の分割で 1 点だけになるが、密集した点（青）は 8 回切っても 5 点が同じ領域に残る。

式で書くと何を測っているか #

1 本の木で点 $x$ が孤立するまでの分割回数を経路長 $h(x)$ と呼び、n_estimators 本の木で平均した $E[h(x)]$ を使います。ただし経路長はサンプル数 $n$ が大きいほど長くなるので、そのままでは比較できません。そこで、$n$ 点をランダムに二分し続けたときの平均経路長 $c(n)$ で割って正規化します。

$$ s(x, n) = 2^{-\frac{E[h(x)]}{c(n)}}, \qquad c(n) = 2H(n-1) - \frac{2(n-1)}{n} $$

ここで $H(i)$ は調和数（$\ln i + 0.5772$ で近似）です。経路長 $E[h(x)]$ が $c(n)$ より十分短いと $s$ は 1 に近づき（異常）、平均的な長さなら 0.5 付近、長ければ 0 に近づきます（正常）。上のステップで 1 回目の分割で孤立した赤い点は $h(x) = 1$ なので、$s$ が 1 に近い点です。

Pythonを用いた実験や説明 #

次のコードは、原点付近に標準偏差 0.3 で散らばる正常点 200 個と、$[-4, 4]$ の範囲に一様に散らばる外れ値 20 個を混ぜ、IsolationForest が付けた異常スコアを色の濃淡で描きます。中央が暗く（スコア低い）、外側ほど明るく（スコア高い）なれば、経路長の短さが異常度として働いている証拠です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
import numpy as np
import matplotlib.pyplot as plt
from sklearn.ensemble import IsolationForest

rng = np.random.default_rng(0)
X_inliers = 0.3 * rng.normal(size=(200, 2))
X_anom = rng.uniform(low=-4, high=4, size=(20, 2))
X = np.vstack([X_inliers, X_anom])

model = IsolationForest(n_estimators=200, contamination=0.1, random_state=0)
model.fit(X)
scores = -model.score_samples(X)
labels = model.predict(X)  # -1 = 異常

plt.figure(figsize=(6, 5))
plt.scatter(X[:, 0], X[:, 1], c=scores, cmap="magma", s=30)
plt.colorbar(label="anomaly score")
plt.title("Isolation Forest のスコア")
plt.tight_layout()
plt.show()

print("異常と判定された数:", np.sum(labels == -1))

コードの解説番号をクリックすると、コード内の該当行がハイライトされます。

5-8 行目正常 200 点と外れ値 20 点を混ぜる
正常点は 0.3 * rng.normal で原点のまわり半径 1 程度に密集させ、外れ値は rng.uniform(-4, 4) で広い範囲にまばらに置いています。全 220 点のうち外れ値は 20 点、つまり約 9% です。この比率を知っていると、次の行の contamination=0.1 が妥当な値だと判断できます。default_rng(0) で種を固定しないと、実行のたびに外れ値の位置と判定数が変わります。
10 行目木の本数と異常の割合を決める
n_estimators=200 は作る木の本数で、多いほど経路長の平均が安定します（既定は 100）。contamination=0.1 は「全体の 10% を異常とみなす」という宣言で、スコアの上位 10% の位置に閾値が自動で置かれます。max_samples は省略しているので既定の min(256, n_samples)、つまり今回は 220 点全部を各木が使います。random_state=0 を外すと、木ごとのランダム分割が変わって判定が 1〜2 点ずれます。
11-12 行目スコアの符号を反転して「大きいほど異常」にする
score_samples は論文の異常スコア $s(x, n)$ の符号を反転した値を返し、-1 に近いほど異常、0 に近いほど正常です。そのまま色にすると異常点が暗くなって直感に反するので、先頭にマイナスを付けて「大きいほど異常」に直しています。この 1 文字を忘れると、カラーバーの読み方が逆になります。
13 行目閾値を越えた点だけ -1 にする
predict は score_samples を contamination で決めた閾値と比べ、異常なら -1、正常なら 1 を返します。スコアが連続値なのに対し、こちらは「アラートを出すかどうか」の二値です。閾値を自分で決めたいときは decision_function の値（閾値を引いたスコア）を使い、0 より小さい点を異常として扱います。
16-17 行目スコアを色にして空間上で確認する
c=scores で各点をスコアの大きさで塗り分け、cmap="magma" で小さい値を黒、大きい値を黄色にしています。カラーバーを付けておくと、密集部と孤立点のスコア差がどれくらいあるかを数値で読めます。ラベルの -1 / 1 だけを色にすると、閾値付近の微妙な点とはっきりした外れ値の区別が消えてしまいます。
22 行目判定数が contamination と合うか確かめる
contamination=0.1 なら、220 点の 10% にあたる約 22 点が -1 になります。出力がこの数とかけ離れていたら、スコアの符号や閾値の扱いを間違えています。元データの外れ値は 20 点なので、2 点ほどは正常点のうち端にあるものが異常側に入る計算です。

Python 実装の図

実行結果の読み方 #

中央の密集部は何度切っても仲間が残るので経路長が長く、-score_samples が小さいため暗い色になります。外側にまばらに散った点は 1〜2 回の分割で孤立するので明るい色です。密集部の縁にある正常点はスコアが中間の値になり、contamination=0.1 の閾値を越えると -1 に入ります。これが「異常と判定された数」が元の外れ値 20 点より少し多い約 22 点になる理由です。

ハイパーパラメータの効果 #

n_estimators は木の本数で、100 本から 200 本に増やしても判定はほとんど変わりませんが、点ごとのスコアのばらつき（乱数シードによる差）が小さくなります。max_samples は各木が使うサンプル数で、既定の min(256, n_samples) のままで十分なことが多く、数万点のデータでも 256 点の部分木で動くのがこの手法が速い理由です。contamination は異常率の想定値で、スコアそのものは変えず、predict が -1 を返す閾値だけを動かします。max_features は各分割で候補にする特徴量の数で、既定の 1.0（全特徴量）から減らすと、特定の列だけが外れている点を見逃しやすくなります。

長所と短所 #

長所	短所
高次元でも比較的高速	乱数シードで結果が多少変わる
スケーリングが不要（ただし推奨）	小さな局所異常は見逃すことがある
モデル学習・推論がシンプル	`contamination` の設定が難しい場合がある

短所の 2 つ目は、密集したクラスタが 2 つあり、その間に落ちた点のような「局所的には孤立しているが全体では端ではない」点で起きます。このような点は経路長が中くらいになり、contamination を上げないと拾えません。密度の違いを見たいときは DBSCAN や LOF（LocalOutlierFactor）を、正常領域の境界を厳密に引きたいときは One-Class SVM を候補にします。

まとめ #

Isolation Forest は「孤立するまでの分割回数」を異常の指標にする木ベースの手法で、正常分布の推定をしないため分布の形や次元数に強く、max_samples=256 の部分木で済むため数万点のデータでも速く動きます。score_samples は -1 に近いほど異常、predict は contamination で決めた閾値を越えた点に -1 を返します。ログ検知やセンサーデータのように、まず異常候補を 10% に絞り込んでから人が確認するような場面で最初に試す手法です。

参考文献 #

Liu, F. T., Ting, K. M., & Zhou, Z.-H. (2008). Isolation Forest. Proceedings of the 8th IEEE International Conference on Data Mining (ICDM), 413–422.

異常検知① — ADTK による時系列の異常検知
DBSCAN — 密度ベースの外れ値検出
ランダムフォレスト — ツリーベースの手法
One-Class SVM — SVMベースの異常検知手法

クラスタ数と分離 #

下の図では k-means のクラスタ数を 2〜10 に変えたとき、同じ 2 次元データがどう分かれるかを確認できます。密集したクラスタが複数ある場合、Isolation Forest はクラスタの「間」に落ちた点を、全体の端にある点ほどには異常とみなしません。