ラベルなし異常検出アルゴリズムIsolationForestについて解説する

2019/12/06

Python 機械学習

t f B! P L
教師あり学習が研究でもビジネス応用でも花形ですが、フリーランスをやるからには教師なしの手法に関しても、さくっと説明できる状態になっておくのが望ましいです。

そんななのでお勉強も兼ねて異常検知手法であるisolation forestから。
ラベルなしでできる手法は(主に教師データを用意できないという理由で)変な人気がありますが、しっかり理解して使えるケース、使えないケースを判断できるようにしておきたいです。

sklearnのdocument

有名な機械学習アルゴリズムについて勉強するときは、scikit-learnのドキュメントを読むのがおすすめです。


有名手法はそれなりに網羅されている上、ドキュメントの説明文がアルゴリズムのいい感じのサマリーになっているので、さらっと理解するにはうってつけです。
あと(ドキュメントなので当たり前ですが)ハイパーパラメータが一覧になっているのも、そのアルゴリズムを理解する上で地味に有用。

さて、このドキュメントからわかることは
  • 入力:データ
  • 出力:各データ点の異常スコア
  • 決定木でデータ点の集合を分割していく
  • 特徴量をランダムに選ぶ、さらにその特徴量の(最小値, 最大値)区間で分割点をランダムに選ぶ
  • 最終的には、上記の分割点が節、データ点が葉である木構造になる
  • (例外はあるが)葉にはデータ点がひとつだけになるように分割する(これがisolationの所以?)
  • 各データ点に対して、葉にたどり着くまでの分割数は、ルートノードから葉までの距離そのもの
  • この距離が異常スコアを表し、距離が小さい=異常スコアが高い
  • なぜなら異常な外れ値的データ点は、早い段階で(木の浅い段階で)分割される確率が高いため

ランダムに特徴量を選ぶ、ランダムに分割する値を選ぶ、というアルゴリズムで分割していくと、異常値を含むデータは早い段階でisolateされることは、直感的にも理解できます。

例えば、IQはだいたい100を中心に分布するよう調整されていますが、たまたまIQ3億のデータがあると、そのデータの区間は(80くらい,  3億)になります。
この区間で分割する値をランダムに決める(一様分布とする)と、3億のデータ点がisolateされる確率はめちゃくちゃ高いですよね。

このような操作を、葉にデータ点がひとつになるまで適用していきます。

また、Random Forestと同様、
  • データをサブサンプリングして木を作る
  • 木は複数(100個)作る=森
といったモデルをロバストにするための工夫もしています。

最終的には、各データ点に対して、ルートノードからの距離(=深さ)を、すべての木(=森)に対して平均します。
この値(平均深さ)が異常スコアに対応します。

論文を読む

sklearnで何となくお気持ちを理解した段階で論文を読みましょう。

Liu, F. T., Ting, K. M., & Zhou, Z. H. (2008, December). Isolation forest. In 2008 Eighth IEEE International Conference on Data Mining (pp. 413-422). IEEE.

異常スコアの計算方法

異常な値をもつデータはたしかに早い段階でisolateされますが、その平均深さをそのままではなく、その木でふつうに二分探索する際の平均深さ \( c(n) \) で正規化しています。

\( s(x, n) = 2^{- \frac{E(h(x))}{c(n)}} \)

このように正規化することで、異常スコアを(0,1)区間に収めることができるので扱いやすくなります。

\( E(h(x)) \) はそのデータ点までの平均深さです。
異常データはこの値がふつうに二分探索する際の平均深さに比べて小さい(浅い)のでした。
これが小さい(=異常値)と指数部分は0に、探索の平均深さと同じくらい(=正常値)だと指数部分は-1に近づきます。

そのため、\( s(x, n) \)が、1に近いと異常値、0.5に近いと正常値と見なせるようになります。

ちなみに論文では特徴量のことをattribute(属性)といっていますが、sklearnのドキュメントでは、feature-valueになってます。

葉が1つのデータ点にならないパターン

  1. まったく同一のデータ点がデータに含まれている場合
  2. 平均深さ(サブサンプルサイズの対数)で打ち切り

後者に関しては、分割が深い場合は打ち切りしています。

もともと興味があるのは、異常データ(早い段階でisolateされるデータ)だけなので、深いところまでisolateされないデータはそこまで重要視されてないんですね。

深いところまでisolateされずに残っているデータは正常データです。
これは「そのデータが外れ値的なデータではなく、似たデータが周辺にたくさん分布しているため」と考えるとわかりやすいです。

訓練データ・評価データ

Isolation Forestは、教師あり学習ではないのですが、訓練データと評価データがあります。

訓練データでは、Isolation Forestの森自体を作ります。
評価データでは、データを森に入れて、各データ点に対して異常スコアを取得します。

ふつう、教師あり学習というと、ラベル付きデータで学習させるイメージですが、この手法では訓練・評価データはあるものの、訓練データにもラベルがついている必要はありません。
こういう場合、教師あり学習って言うんですかねw?
細かい用語の使い方がよくわかりません。

このブログを検索

QooQ