Isolation Forest
異常検知手法 Isolation Forestの解説、スクラッチでの実装 では、以下のように説明されています。
決定木を各データが孤立するまで分割を繰り返し、データが孤立するまでの距離（深さ）から異常値を推定しよう、というのが基本的なアイディアです（Isolate＝孤立）。全データを使って決定木を一つだけ作成すると過学習してしまうので、データをサンプリングした上で、大量の決定木を作成し、作成した決定木の各データが孤立するまでの距離の平均を使用して異常値スコアを算出します。
異常値スコアを算出する際は、孤立するまでの深さの平均をそのまま使用するのではなく、二分探索する際の平均の深さ$c(n)$で正規化します。これによりスコアは0~1に収まる用になり、比較がしやすくなります。二分探索する際の平均の深さ $c(n)$ $n$は、サンプルのサイズ
$H(i)=\ln (i)+0.5772156649$ (Euler’s constant)
$c(n)=2 H(n-1)-(2(n-1) / n)$
異常スコア $s(x,n)$
$s(x, n)=2^{-\frac{E(h(x))}{c(n)}}$ ※ $E(h(x))$ は $x$の平均の深さ
異常検知手法 Isolation Forestの解説、スクラッチでの実装
「全データを使って決定木を一つだけ作成すると過学習してしまうので、データをサンプリングする」というのは、ランダムフォレストの前段階です。ランダムフォレストでは、サンプリングしたデータとランダムに選択された説明変数をもちいて決定木を作成し、アンサンブルを取ることによって、最終的な学習器を作ります。
決定木では、分割をするのに、分割した後のサブセットがなるべく同質になるように分割します。それに対して、Isolation forest は、決定木ではなく、閾値をランダムに選んでデータが孤立するまで分割します。
多数のサンプリングしたデータにたいして、孤立するまでの深さを平均し、その距離で異常を判定しようとするものです。ここで、孤立するまでの平均深さをそのままではなく、ふつうに二分探索する際の平均深さ $c(n)$ で正規化するというところがポイントです。
では、普通に二分探索をするというのは、どういうことでしょうか。それは、サンプリングしたデータを分割するのに、中央値をもちいて二分割していくということです。異常データは、閾値をランダムに決定するとすぐに孤立しますので、平均深さは二分探索したときの平均深さより小さくなります。孤立するまでの平均深さを二分探索をしたときの平均深さで割ったものを、異常スコアとします。
標準正規分布をするデータに、異常値として、例えば１０００というデータが混じっていたとき、中央値で分割していくのにたいして、最大値／最小値の値の間から、ランダムに閾値を決定すると、１０００というデータが孤立する確率は非常に高くなります。これが閾値をランダムに選んだときに孤立が早くなるという直感的な説明です。
二分探索したときの平均深さが、すでに計算された式で与えられているので、理解しにくいですね。
