Isolation forestは2008年にFei Tony Liu（中：是刘飞）、Kai Ming Ting（中： 陈开明）、Zhi-Hua Zhou（中：周志华(英語版)）によって提案された決定木を用いて異常検知を行う教師なし学習アルゴリズムである。
代替文=Anomalous Web Traffic|左|サムネイル|320x320ピクセル|図1 - 異常値の可能性のあるポイントを含むウェブトラフィックの例統計学において、異常値（別名：外れ値）とは、他の事象から著しく逸脱し、異なる平均値によって生成されたのではないかと疑念を抱かせる観測値または事象を指す。例えば、図1のグラフは、1か月間のウェブサーバーへの流入トラフィックを、3時間ごとのリクエスト数で表したものである。図を見るだけで明らかなように、一部のデータポイント（赤丸で示された箇所）は異常な高値を示しており、その時間帯にウェブサーバーが攻撃を受けていた可能性を疑わせる。一方、赤矢印で示された平坦な区間もまた異常であり、その時間帯にサーバーがダウンしていた可能性がある。
大容量データセット内の異常は極めて複雑なパターンに従うことがあり、ほとんどの場合目視による検出は困難である。これが異常検出分野が機械学習技術の応用に適している理由である。
異常検知で一般的に用いられる手法の多くは、まず「正常な状態」を表すプロファイルを構築し、そのプロファイルに適合しないデータを異常として検出するものである。これに対してIsolation Forestは、正常なデータのモデルを構築するのではなく、データセット内の異常な点を直接孤立させるという異なるアプローチを採用している。この手法の主な利点は、従来のプロファイルベースの手法では難しい規模でサンプリング技術を活用できる点にある。その結果、少ないメモリ使用量で高速に動作する異常検知アルゴリズムを実現している。
歴史 Isolation Forest（以下：iForest）アルゴリズムは、2008年にFei Tony Liu、Kai Ming Ting、Zhi-Hua Zhouによって最初に提案された。著者らは、サンプル中の異常データが持つ、次の二つの量的な性質に着目した。
正常データと比べて出現数が少なく、少数派であること 各特徴量の値が、正常データの値と大きく異なること
異常データは一般に数が少なく、サンプル内のほかのデータとは大きく異なるため、正常データよりも容易に「孤立」させられると考えられる。iForestはこの原理に基づき、データセットに対して複数のIsolation Tree（iTree：孤立木）を構築する。そして、各iTreeにおける平均パス長が短いデータを、異常として判定する。
2012年に発表された後続論文において、同じ著者らは、iForestが以下の性質を持つことを実証するための一連の実験を行った。
線形時間に近い低い計算量で動作し、必要とするメモリ容量も小さい 異常検知に関係しない特徴量を含む高次元データにも対応できる 学習データに異常データが含まれている場合でも、含まれていない場合でも学習できる 再学習を行うことなく、異なる粒度で異常検知の結果を得られる
2013年、Zhiguo DingとMinrui Feiは、ストリーミングデータにおける異常検知の問題を解決するため、iForestを基盤としたフレームワークを提案した。ストリーミングデータへのiForestの応用については、このほかにもSwee Chuan Tanら、G. A. Sustoら、Yu Wengらの論文で報告されている。
iForestを異常検知に適用する際の主要な問題の一つは、モデルそのものではなく、異常スコアの算出方法にあった。
Sahand Hariri、Matias Carrasco Kind、Robert J. Brunnerは、2018年に発表した論文でこの問題を指摘し、iForestを改良したモデルであるExtended Isolation Forest（EIF）を提案した。同論文では、従来のiForestに加えられた改良点と、それによって各データ点に対して算出される異常スコアの一貫性および信頼性が、どのように向上するかが説明されている。 アルゴリズム 代替文=|サムネイル|300x300ピクセル|図2―二次元ガウス分布において、正常なデータ点を孤立させる例。 iForestアルゴリズムは、データセット内の異常データは、正常データと比べてほかのデータから分離、すなわち「孤立」させやすいという性質に基づいている。データ点を孤立させるため、アルゴリズムはまず特徴量をランダムに1つ選択し、次に、その特徴量が取り得る最小値と最大値の間から分割値をランダムに選ぶ。この処理を再帰的に繰り返すことで、サンプルを複数の領域に分割していく。 代替文=Isolating an Anomalous Point|サムネイル|300x300ピクセル|図3―二次元ガウス分布において、異常なデータ点を孤立させる例。 二次元の正規分布に従うデータセットをランダムに分割する例として、図2では正常なデータ点を、図3では異常である可能性が高いデータ点を、それぞれ孤立させる過程を示している。これらの図から、異常データは正常データに比べて、より少ない回数のランダム分割で孤立させられることが分かる。
数学的には、この再帰的な分割処理は、Isolation Tree（iTree：孤立木）と呼ばれる木構造として表現できる。また、あるデータ点を孤立させるまでに必要な分割回数は、木の根から終端ノードに到達するまでのパス長として解釈できる。
例えば、図2に示された点のパス長は、図3に示された点のパス長よりも長い。これは、正常なデータ点の方が、異常なデータ点よりも孤立させるために多くの分割を必要とすることを示している。
より形式的には、 を d 次元のデータ点からなる集合とし、 をその部分集合とする。このとき、iTreeは、次の性質を持つデータ構造として定義される。
木を構成する各ノード は、子ノードを持たない外部ノードであるか、1つの判定条件と、ちょうど2つの子ノードおよびを持つ内部ノードである。 ノードにおける判定条件は、特徴量と分割値から構成される。データ点は、条件 の判定結果に応じて、左の子ノード または右の子ノードのいずれかへ進む。
iTreeを構築する際、アルゴリズムは特徴量と分割値をランダムに選択し、部分集合を再帰的に分割する。この処理は、次のいずれかの条件を満たすまで繰り返される。
ノードに含まれるデータが1件だけになった場合 ノード内のすべてのデータが同じ値を持つ場合
iTreeの構築が完了すると、集合に含まれる各データ点は、いずれかの外部ノードにおいて孤立する。直感的には、異常データは正常データよりも容易に孤立させられるため、木におけるパス長が短くなる。ここで、データ点 のパス長は、ルートノードから外部ノードに到達するまでに通過する辺の数として定義される。
iTreeの確率的な説明については、iForestの原論文で示されている。
特性
サブサンプリング: iForestでは、すべての正常データを個別に孤立させる必要がないため、学習サンプルの大部分を無視しても異常検知を行える。このため、サンプルサイズを小さく設定した場合でも良好な性能を示す。 これは、一般にサンプル数が多いほど望ましいとされる既存手法の多くとは対照的な性質である。 スワンピング: 正常データが異常データの近くに存在すると、異常データを分離するために必要な分割回数が増加する。この現象はスワンピングと呼ばれ、iForestが正常データと異常データを区別することを難しくする。 スワンピングが発生する主な原因の一つは、異常検知に用いるデータ点が多すぎることである。そのため、対策の一つとしてサブサンプリングが挙げられる。iForestは少数のサンプルでも高い性能を示すため、サンプル内のデータ点を減らすことは、スワンピングの影響を軽減するうえでも有効である。 マスキング: 異常データの数が多い場合、その一部が密集して大きなクラスタを形成することがある。このような状態では、個々の異常データをほかのデータから分離することが難しくなり、結果として異常として検出されにくくなる。 この現象はマスキングと呼ばれる。スワンピングと同様に、サンプル内のデータ点が多いほど発生しやすく、サブサンプリングによって影響を軽減できる。 High Dimensional Data: 従来の距離に基づく異常検知手法には、高次元データを効率的に扱いにくいという大きな制約がある。 高次元空間では、各データ点が同程度に疎な状態となるため、点同士の距離を用いて分離度を評価する方法が有効に機能しにくくなるためである。 高次元性はiForestの検出性能にも影響を与える。ただし、尖度などを用いた特徴選択を導入し、サンプル空間の次元を削減することで、性能を大幅に改善できる。 Normal Instances Only: iForestは、学習データに異常データが含まれていない場合でも良好に動作する。 これは、iForestがデータの分布を、データ点の存在する領域ではパス長が長くなるように表現するためである。そのため、学習データ内に異常データが含まれているかどうかは、iForestの検出性能に大きな影響を与えない。
異常検知 iForestを用いた異常検知は、主に二つの段階から構成される。
学習データセットを用いて、前節までに説明した方法によりiTreeを構築する。 テストデータセット内の各データを、第1段階で構築したiTreeに入力する。そして、後述するアルゴリズムに基づき、それぞれのデータに適切な異常スコアを割り当てる。
テストデータセット内のすべてのデータに異常スコアを割り当てた後、あらかじめ設定したしきい値を上回るデータ点を「異常」として判定する。このしきい値は、異常検知を適用する対象分野や分析目的に応じて設定される。
異常スコア データ点の異常スコアを算出するアルゴリズムは、iTreeの構造が二分探索木と等価であるという考え方に基づいている。iTreeにおいて外部ノードで探索が終了することは、二分探索木における探索の失敗に相当する。.そのため、外部ノードに到達する場合の平均パス長 は、二分探索木における探索失敗時の平均探索長と同様に推定でき、次式で表される。
ここで、はテストデータの件数、はサンプル集合の大きさ、は調和数を表す。
調和数は、次の式によって近似できる。
ここで、はオイラー定数である.
上式のは、サンプルサイズがのときの平均パス長を表す。したがって、を用いてを正規化することで、任意のデータ点 に対する異常スコアを推定できる。
ここで、は、複数のiTreeから得られたデータ点のパス長 の平均値を表す。
任意のデータ点について、次の点に注目できる。
異常スコアが1に近い場合、データ点は異常である可能性が高い。 が0.5未満の場合、は正常なデータである可能性が高い。 あるサンプル内のすべてのデータに対して、異常スコアがおおむね0.5となる場合、そのサンプルには明確な異常が含まれていないと考えられる。
Extended Isolation Forest：EIF 前節までに述べたとおり、iForestは、計算量とメモリ使用量の両面で優れた性能を示す。一方、従来のアルゴリズムには、木の分岐方法によって判定に偏りが生じるという問題がある。この偏りにより、データを異常度の高い順に並べる際、異常スコアの信頼性が低下する可能性がある。
HaririらがExtended Isolation Forest（EIF）を提案した主な動機は、この問題を改善することにあった。 代替文=Normally Distributed Data|左|サムネイル|240x240ピクセル|図4―平均が0、共分散行列が単位行列である二次元正規分布に従うデータ点。 従来のiForestにこのような偏りが生じる理由を説明するため、著者らは、平均が0、共分散行列が単位行列である二次元正規分布からランダムに生成したデータセットを用いて、具体的な例を示している。そのようなデータセットの一例を図4に示す。
図を見ると、(0,0) 付近に位置する点は正常データである可能性が高く、(0,0) から大きく離れた点は異常データである可能性が高いことが直感的に分かる。
したがって、本来であれば異常スコアは、分布の中心から外側へ離れるにつれて、ほぼ円形かつ対称的に増加すると考えられる。しかし、実際にはそうならない。著者らは、iForestによって生成された異常スコアマップを用いて、この問題を示している。
異常スコア自体は、点が中心から外側へ離れるにつれて正しく増加しているものの、中心からほぼ同じ距離にある他の点と比べて、x 軸方向および y 軸方向に、異常スコアが不自然に低い長方形状の領域が生じる。 代替文=Random Partitioning with Extended Isolation Forest|サムネイル|Fig. 5 - random partitioning with EIF 異常スコアマップに現れる予期しない長方形状の領域は、データ本来の性質によるものではなく、アルゴリズムによって生じた人工的な偏りであることが示されている。
その主な原因は、iForestの決定境界が、垂直方向または水平方向の分割に限定されている点にある（図2および図3参照）。
この問題を改善するため、Haririらは論文において、従来のiForestを次のように拡張することを提案した。従来手法のように、特徴量を1つランダムに選び、その値域内から分割値を選択するのではなく、ランダムな傾きを持つ分割境界を用いてデータを分割する。EIFによるランダム分割の例を図5に示す。
著者らは、この新しい手法によって従来のiForestが持つ制約を克服でき、結果として、より一貫性と信頼性の高い異常スコアマップを得られることを示した。
実装例
Spark iForest - Apache Spark上で動作する分散実装であり、Scala版とPython版が提供されている。Fangzhou Yangによって開発された。 Isolation Forest - LinkedInのAnti-Abuse AIチームに所属するJames Verbusが開発した、Spark／Scalaによる実装である。 EIF – Sahand Haririによる、異常検知向けのExtend Isolation Forestの実装である。 scikit-learn - Python向け機械学習ライブラリscikit-learnにもIsolation Forestが実装されており、使用例も提供されている。
参考文献