論文メモ Isolation Forest

February 13, 2021

Isolation Forestは、完全二分木による異常検知の手法で、iForestともよばれる。時間計算量が線形で、ハイパーパラメタがわずか2つで、メモリ効率がよい。 時間、空間計算量が少なく高次元のデータに向く。

手法にあるisolationは事例をほかの事例と分けることに由来する。 似た事例の少ないものを異常とみなし、正常な事例と分けられるように学習する。 iForestは、サブサンプリングされた事例を分ける完全二分木の集まりで、個別の木は、根からのパスが短かい事例を異常と推定する。 木のノードは、無作為に選んだある特徴と特徴の境界値で事例を分離する。 異常であれば簡単に分けられるので、異常な事例は木の根からのパスが短かい葉になりやすい。 ハイパーパラメタは、木の数とサブンサンプリングのサイズの2つだけで、実験から木の数は100、サブサンプリングサイズは256が推奨されている。

確信度のスコアは根からのパスの長さにもとづく。 パスの長さは、事例数で変わり、また、0から1の間に収まらないので、パスの長さをそのまま確信度に使うことはできない。 iForestの木を二分探索木とみなすと、事例数\(n\)の木で検索に失敗するときのパスの平均\(c(n)\)は $$ c(n) = 2H(n-1)-(2(n-1)/n) $$ になる。\(H(i)\)は調和数で、\(\ln(i)+0.5772156649\)に近似できる。 \(E(h(x))\)を事例\(x\)のiForestのそれぞれの木におけるパスの長さの平均として $$ s(x, n) =2^{-\frac{E(h(x))}{c(n)}} $$ で算出される値をスコアとみなす。

論文をこちらからダウンロードできます。