Isolataion Tree, Isolation Forest
今回はIsolation Tree、Isolation Forestについてです。異常検知のアルゴリズムで非常に軽量でそれなりの精度が出るモデルだと思います。処理自体も理解しやすいです。
外れ値とは
まず外れ値として、
- 数が少ない
- 通常のサンプルから離れている
上記を仮定しています。
アルゴリズム概要
決定木の分割条件を完全にランダムに決定しながら、分割を繰り返します。その際に外れ値は上記の仮定があるため、通常のサンプルに比べて少ない分割で孤立、もしくは同じ回数の分割でもノード中のサンプル数が少なくなります。概要としてはこれだけで、つまり、
- ランダムに分割
- 同じノードに含まれるサンプル数が少ないほど高い異常スコアを付与（sklearnでは逆。スコアでデフォルトの昇順ソートをした際に先頭からとれるようになっていると思われる）
という単純なものになります。
アルゴリズム詳細
RandomForestなど異なるハイパーパラメータとしてはmax_samplesで、これは一つのTreeに投入するサンプル数を設定します。scikit-learnのデフォルトでは256です。分割に関しては上述の通り、ランダムに決定するだけなので決定木の記事を参照ください。一つ異なる点としては、回帰木を作成しますが、予測を実施した際に各ノードが返す値は「学習時の深さ＋追加の深さ」です。この値を計算する方法について記述します。
算出するために、まず全データを学習したモデルに投入します。この時上記の通り、まず各サンプルがアサインされたノードの学習時のノードの深さが与えられます。ただ、学習時には256個のサンプルだけ与えられましたが、予測時にはこれを大きく上回る数が与えられている可能性が高いです。したがって、学習時は1個しか格納されていなかったノードにも100個のサンプルがアサインされる可能性があります。「追加の深さ」とは、このような複数のサンプルをノードをさらに分割していき、ノード1個につきサンプル1個の状態までもっていくにはどのくらいの深さが必要かという値です。つまり、サンプルN個を与えた場合に、ノード1個につきサンプル1個になるまでに必要な深さは、ということですが以下の式で与えられます。ただしN=1の時は０です。
\text{average_depth} = 2*\left( \log(N-1) + \gamma_E \right)- 2*(N-1)/N
最後に異常スコアへの変換を行います。サンプルxの異常スコアは、
\text{anomaly_score}(x) = 2 ** \left( - \frac{\sum^T_{t=1}h^t(x)}{T}\times \frac{1}{\text{average_depth}(N)}\right)
ここで$T$はアンサンブルの木のインデックス、$h^t(x)$はt番目の木におけるサンプルxの深さです。つまり$\times$記号の左側はサンプルｘの平均的な深さと考えられます。ここで外れ値の過程に戻って考えてみるとその平均深さは0に近いとと考えられます。一方通常のサンプルは記号の右側の分母と同じような値になることが期待されます。したがって異常スコアが
- 1に近い場合、異常値
- 0.5やそれを下回る場合は、通常サンプル
という風に考えることができます。
その他：速度
IsolationForestの速度がsklearnより非常に速い点（約100倍）が気になります。Sklearnの実装を見てみるとランダムな分割のために専用のBaseEstimatorも実装するのではなく、ExtraTreeRegressorをmax_features=1として利用しています。FortLearnerでは専用のクラスを作っているので、ここだとは思うのですが、それだけでここまで劇的に向上するのが非常に気持ち悪いと思っています。ただ違う点があるとすればExtraTreeは本来異常検知に必要のない引数もとっています。FortLearnerでは専用のクラスなので、必要がありません。これだけでこんなに違うものかと疑問に思っています。精度を検証した際には特に違いが見られなかったので、さらに疑問です。
その他：精度改善
非常に簡単な手法で精度を提案している記事があったためご紹介します。
本当に簡単な手順で、
- Treeを余分に作成する（例：max_estimators=100のところ1000に設定する）
- 各Treeの平均深さを計算
- TopN本のTreeのみ残す
後は通常のIsolationForestと変わりがないようです。一つの手法をいろいろな場面で使い、性能や傾向を確認することでこのようなアイデアが生まれるのではないかなと思います。
以上