狠狠撸

Isolation Forest
Fei Tony Liu?,Kai Ming Ting?Zhi-Huz Zhou?
2008 Eighth IEEE International
Conference on Data Mining
1

研究背景(1/2)
? モデルに基づく検知方法として異常検知がある
? 異常：通常のデータとは違う特徴量を持ったデータパターン
? 異常検知の例
? クレジットカード処理の異常検知
→クレカの不正利用を発見
? 天体映像の異常検知
→今まで見ていない部分を観察し新しい星を発見
? 異常検知の方法
? 通常のデータのプロファイルを構成
? プロファイルに則っていないものを異常として検知
2
異常検知では高い検知率と実行の速さが必要

研究背景(2/2)
? 既存の異常検知法の欠点
? False Negativeが多い
? 通常のデータのプロファイルに利用されるが、
異常検知には利用されない
? 計算がとても複雑である
? 低次元のデータやデータサイズの小さいものを使わざるを得ない
? 既存手法と異なる、モデルに基づく異常検知法
Isolation Forestを提案
? 異常なデータの持つ特徴を利用する
? 異常なデータは正常なデータに対して少数である
? 異常なデータは正常なデータと大きく異なっている
3
データ群
正常なデータ異常なデータ
データ長
16byte
データ長
128byte

Isolation Forest(iForest)について
? Isolation Tree(iTree)の結果を統合した検知方法
? 作成する木の数、サブサンプリングサイズによって
検知精度が決定する(不定要素はこの2種のみ)
? 既存手法(k近傍法、LOF)で利用される、
密度や距離は利用しない
? 計算量は線形時間、メモリ使用量も少ない
? iTreeについて
? データ集合の要素を機構増に配置する
? 再帰的にパーティションをランダムに行い要素を分割
? 異常なデータはパーティションで早く分割される
? 異常なデータはパーティションの数が少なくなる
4

iTreeの具体的構成方法(1/2)
? ?1を分割するのに必要なパーティションは1つ
? ?2を分割するのに必要なパーティションは5つ
? ?1は異常なデータらしいデータ
? パーティションはランダムに選んだ属性の
最大値～最小値の間からランダムな値で作成
5
0
2
4
0 1 2 3
?1
?1
? < ?. ?
? < ?
?2
x座標 y座標
?0 7 30
?1 5 4
… … …
?? 15 2
??
x座標：5
y座標：4

異常検知の判定方法
? データを分割するのに必要なパーティションの数
＝ルートノードからデータまでの木の深さ
? ?1を分割するためのパーティションは1つ
? パーティションの作成はランダム
? 1つの木での判断では誤判断がある
? 複数の木を用いてパスの長さを収束させる
? 1000個の木を用いた結果
? ?0のパス長は4.02に収束
? ??のパス長は12.82に収束
6
1

異常検知の問題点
? SwampingとMasking問題
? 異常検知において研究され続けている問題
? Swamping
? 通常のデータが異常なデータと近いときに
False Negativeが発生
? Masking
? 異常なデータが多くあり、
それらが密な集合になり検知できない
7
両問題は多くの学習用データを用いることで発生しやすくなる

iForestでの問題点の解決
? 元のデータからサブサンプリングを行い、
部分モデルを作成することによって解決を行う
? 全ての学習データを使用した時のiForestのAUC：0.67
? サブサンプリングを使用した後のiForestのAUC：0.91
? サブサンプルによってswampingとmaskingの影響緩和
8

iTreeの作成方法
? iTreeの定義
? iTreeは二分木
? T：iTreeのノード、葉か二つの子を持つ
? X：入力値{?1, ?2, ?3, … , ? ?}
? q：Xの持つ属性
? p：Xを分割する値で属性qの最小値から最大値までのランダムな値
? iTreeの構成方法
? Xを次の3つの条件になるまで分割
1. 木の高さが事前に決めた最大値と同じ高さになる
2. ? = 1
3. ??が全て同じ値を持つ
? 全てのノードが葉になれば木の構成を終了
? 葉のノード数はn,内部ノードはn-1、iTreeは2n-1のノードを持つ
? iTreeのメモリ使用量はO(n)
9

異常検知の方法
? パス長から異常検知のアノマリースコアを算出
? ? ? ：パス長
? ? ? ：iTree内でのh(x)の正規化
? ? ? ：調和数、? ? = log ? + 0.57721
? ? ? ? ：すべてのiTreeの? ? の平均値
? ? ?, ? ：xのアノマリースコア
? アノマリースコアの算出方法
? ? ? = ? ? ? 1 ? 2 ??1
?
?
? ? ?, ? = 2
?
? ? ?
? ?
? 異常かどうかの判定方法
? sが1に近いとき →異常
? s < 0.5 →異常ではない
? 全ての s = 0.5 →異常なデータはデータセットにない
10
?B.R.Preiss. Data Structures and Algorithms with Object Oriented Design Patterns in Java. Wiley,1999

iForestの全体図
? 学習フェーズ
? 学習用データからサブサンプリングを行い
iTree群を生成
? 評価フェーズ
? iTree群を基にアノマリースコアを算出し異常か判断
11
学習フェーズ評価フェーズ
学習用データ
iTree(s)
評価用データ
正常異常
サブサンプリング
iTree(s)
アノマリー
スコア算出

学習フェーズのアルゴリズム詳細
? 学習フェーズ
? 必要なパラメータ
? サブサンプリングサイズ：φ
一定のところで効率が打ち止め、以降は時間とメモリ消費量が上昇
? iTreeの数：t
t=100でパス長が収束
? 計算量
? ?(?φ log φ)
12

評価フェーズでのアルゴリズム詳細
? 評価フェーズ
? xが外部ノードに着くまで
木をたどる
? 外部ノードまでのエッジを
数えh(x)を算出
? パスレングスを求め
アノマリースコアを算出
? 計算量
? ? ?? log φ
? n：評価データのデータサイズ
13

評価環境
? 動作環境
? シングルスレッド
? CPU：2.3GHz
? 評価項目
? 処理時間(学習時間と評価時間の合計)とAUC
? 評価対象
? 11個の実データセットと1個の人工的データセット
? n：データの総数
? d：パラメータの数(次元数)
? Satelliteより上は
データ数1000以上
14

評価内容
? 4種の実験を行った
? 既存手法である、ORCA、LOF、RFと提案手法のiForestを
AUCと時間に関して比較
? ORCA：距離をベースにしたk近傍法を用いた異常検知法
? LOF ：密度ベースの異常検知法
? RF ：木を利用した異常検知法
? 大きいデータセットに対してサブサンプリング数を変更
? サブサンプリング数が異常検知にどのような影響を与えるのか
? 高次元データを扱うデータセットに対し、
余分なデータを追加
? データセットに検知には必要のないデータがあっても検知可能か
? 通常のデータのみで異常検知を行う
? 異常なデータを集めるのは大変なため、
通常のデータのみでどこまでの性能を出せるのか
15

ORCAとの比較結果
? AUCに関して
? 多くのデータセットにおいてiForestの性能のほうがよい
? 時間に関して
? データ数が1000以上のデータに関してはiForestの方がよい
16

LOFとRFとの比較結果
? AUCについて
? LOF ：7/8のデータセットにおいてiForestの性能が上
? RF ：全てにおいてiForestの性能が同等or上
? 時間について
? 殆どのデータセットにおいてiForestの性能が上
17
既存の異常検知法よりもiForestは良い結果を出している

サブサンプリング数の変更
? サブサンプリング数φを2,4,8,…,32768まで変更
? グラフについて
? データセットはデータ数の多いHttpとForestCoverを利用
? 実線がAUC、点線がiForest実行時間
? 左軸：時間、右軸：検知精度、x軸：サブサンプリング数
? φがちいさくてもAUCは収束する
? Http ：φ=128で最もよいAUC値と誤差0.00045
? ForestCover ：φ=512で最も良いAUC値と誤差0.00018
? φが大きくなると実行時間が長くなる
? φを大きくすることは必要ではない 18

高次元データの異常検知
? 高次元のデータにはノイズが存在
? 506個の無関係の属性を追加しiForestを実行
? 尖度を利用、分類するのに重要な属性のランキングを作成
? 尖度：確率変数の確率密度関数や頻度関数の鋭さを示す。
? iForestの実行に使う属性の数を決め、ランキングから属性を選択
? 実行結果
? 属性の多いMammography
,Annthyroidを利用
? 実線がAUC、点線が時間
? x軸：iForestに使う属性の数
左軸：時間、右軸：AUC
19
iForestは余分なノイズや属性があったとしても検知可能
しかし除いたほうがよい結果が出るため尖度の利用を推奨

通常のデータのみのiForest
? 異常なデータの収集は難しいケースが多い
? 通常のデータのみで異常検知が可能であるか検証
? データセットはHttpとForestCoverを使用
? データセットから異常なデータを除外しiForestを実行
? 異常なデータを除外すると検知率が下がる
? サブサンプリング数を大きくすると問題がなくなる
20
データセット元のAUC 通常のデータのみ
(φ=256)
通常のデータのみ
(φの値変更)
Http(KDDCUP99) 0.9997 0.9919 0.9997
(φ=8192)
ForestCover 0.8817 0.8802 0.884
(φ=512)
通常のデータのみでiForestを行う場合
サブサンプリング数を挙げたほうが良い結果となる

まとめ
? 異常検知法としてIsolation Forestを提案した
? 異常なデータの持つ「少なく、違っている」点を利用し、
木を構成する
? 異常なデータは構成した木の根から近いところに存在
? iForestはサブサンプリングや少ないデータでも検知可能な
ことにより処理時間やメモリ使用量が少なく済む
? 評価の結果
? データサイズが大きくなるほど既存手法より性能が良い
? 異常検知に関係のないデータが含まれている場合でも
尖度を利用することにより検知が可能となる
? 通常のデータのみを用いても異常検知が可能である
? 通常のデータのみの場合であればデータサイズは大きくするべき
21

狠狠撸

Isolation forest

Recommended

More Related Content

What's hot (20)

Viewers also liked (20)

More from kataware (6)

Isolation forest