孤立した森

アイソレーションフォレストは、異常検出のための教師なし学習アルゴリズムであり、正常点のプロファイリングという最も一般的な手法^{[ 2 ]}ではなく、異常を分離するという原理に基づいて動作します^{[ 1 ] 。}

統計学において、異常値（外れ値とも呼ばれる）とは、他の事象から大きく逸脱し、異なる平均値によって生成されたのではないかと疑われるような観測値または事象のことです。例えば、図1のグラフは、1か月間のWebサーバーへの受信トラフィックを、3時間間隔のリクエスト数として表したものです。グラフを見るだけで、いくつかの点（赤い丸で囲まれた部分）が異常に高いことがすぐにわかります。これは、その時点でWebサーバーが攻撃を受けていたのではないかと疑わせるほどです。一方、赤い矢印で示された平坦な部分も異常に見え、その期間中にサーバーがダウンしていた可能性を示唆しているかもしれません。

大規模なデータセットにおける異常は非常に複雑なパターンを示す場合があり、ほとんどの場合、目視で検出することは困難です。そのため、異常検出の分野は機械学習技術の応用に非常に適しています。

異常検出に用いられる最も一般的な手法は、「正常」のプロファイルの構築に基づいています。異常は、データセット内で正常プロファイルに適合しないインスタンスとして報告されます。^{[ 2 ]} Isolation Forest は異なるアプローチを採用しています。正常インスタンスのモデルを構築しようとするのではなく、データセット内の異常なポイントを明示的に分離します。このアプローチの主な利点は、プロファイルベースの手法では許可されていない範囲でサンプリング技術を活用できることであり、メモリ要求の低い非常に高速なアルゴリズムを作成できます。^{[ 1 ] [ 3 ] [ 4 ]}

Isolation Forest (iForest) アルゴリズムは、2008 年に Fei Tony Liu、Kai Ming Ting、Zhi-Hua Zhou によって最初に提案されました。^{[ 1 ]}著者らは、サンプル内の異常データポイントの 2 つの定量的特性、すなわち次の特性を利用しました。

1. 彼らは少数派であり、事例も少なく、
2. それらは通常のインスタンスとは全く異なる属性値を持っている。

異常値は通常、サンプル内の他の点とは大きく異なり、数も少ないため、正常な点に比べて「分離」しやすいはずです。この原理に基づき、Isolation Forestはデータセットに対して「分離ツリー」（iTrees）の集合を構築し、iTrees上で平均パス長が短い点を異常値としてマークします。

2012年に発表された後の論文^{[ 2 ]}では、同じ著者らがiForestを証明する一連の実験について述べている。

• 線形時間計算量が低く、メモリ要件も小さい。
• 無関係な属性を含む高次元データを処理できる
• トレーニングセットに異常値が含まれている場合でも含まれていない場合でもトレーニングできます。
• 再学習なしで、異なる粒度レベルの検出結果を提供できます。

2013年にZhiguo DingとMinrui Feiは、ストリーミングデータの異常検出の問題を解決するためにiForestに基づくフレームワークを提案した。^{[ 5 ] iForestのストリーミングデータへのさらなる応用については、Swee Chuan Tanら[ 4 ]} 、 GA Sustoら^{[ 6 ]}、Yu Wengら^{[ 7 ]}の論文で説明されている。

iForest を異常検出に適用する際の主な問題の一つは、モデル自体ではなく、「異常スコア」の計算方法にありました。この問題は、Sahand Hariri、Matias Carrasco Kind、Robert J. Brunner が 2018 年の論文^{[ 8 ]}で指摘し、 Extended Isolation Forest (EIF)という改良された iForest モデルを提案しました。同じ論文の中で、著者らは元のモデルに加えられた改良点と、特定のデータポイントに対して生成される異常スコアの一貫性と信頼性をどのように向上させるかについて説明しています。

アイソレーションフォレストアルゴリズムの基本原理は、データセット内の異常なインスタンスは、正常なインスタンスに比べて、サンプルの残りの部分から分離（隔離）しやすいという性質に基づいています。データポイントを隔離するために、このアルゴリズムは、属性をランダムに選択し、その属性に対して許容される最小値と最大値の間で分割値をランダムに選択することによって、サンプル上に再帰的にパーティションを生成します。

正規分布する点の2次元データセットにおけるランダム分割の例を、図2に異常でない点について、図3に異常である可能性が高い点について示します。これらの図から、異常点は正常点に比べて、分離に必要なランダム分割の回数が少ないことがわかります。

数学的な観点から見ると、再帰的分割は分離木と呼ばれる木構造で表すことができ、点を分離するために必要な分割数は、木構造内で根から終点ノードに到達するまでのパスの長さとして解釈できます。例えば、図2の点x _iのパスの長さは、図3の点x _jのパスの長さよりも長くなります。

より厳密に言うと、X = { x ₁ , ..., x _n } を d 次元点の集合とし、X' ⊂ X を X の部分集合とする。分離木 (iTree) は、以下の特性を持つデータ構造として定義される。

1. ツリー内の各ノード T について、T は子を持たない外部ノードか、1 つの「テスト」とちょうど 2 つの娘ノード (T _l、 T _r )を持つ内部ノードのいずれかです。
2. ノード T でのテストは、属性 q と分割値 p から構成され、テスト q < p によってデータ ポイントが T _lまたは T _rのどちらに移動するかが決定されます。

iTreeを構築するために、アルゴリズムは、(i)ノードにインスタンスが1つだけになるか、(ii)ノードのすべてのデータが同じ値になるまで、属性qと分割値pをランダムに選択してX'を再帰的に分割します。

iTreeが完全に成長すると、X内の各点は外部ノードのいずれかに分離されます。直感的に、異常な点は、ツリー内のパス長が短い点（したがって分離しやすい点）であり、点のパス長h(x _{i )は}${\displaystyle x_{i}\in X}$は、ルートノードから外部ノードに到達するためにx _iがたどるエッジの数として定義されます。

iTreeの確率論的な説明は、iForestのオリジナル論文に記載されています。^{[ 1 ]}

• サブサンプリング：iForestはすべての正常インスタンスを分離する必要がないため、トレーニングサンプルの大部分を無視することができます。その結果、iForestはサンプリングサイズを小さく保つと非常にうまく機能します。これは、通常大きなサンプリングサイズが望ましい既存の方法の大部分とは対照的な特性です。^{[ 1 ] [ 2 ]}
• スワンピング：正常インスタンスが異常に近すぎると、異常を分離するために必要なパーティションの数が増加します。これはスワンピングと呼ばれる現象で、iForest が異常と正常ポイントを区別するのが難しくなります。スワンピングの主な原因の 1 つは、異常検出の目的に対してデータが多すぎることです。これは、この問題の解決策の 1 つはサブサンプリングであることを意味します。iForest はパフォーマンスの面でサブサンプリングに非常によく反応するため、サンプルのポイント数を減らすことは、スワンピングの影響を軽減する良い方法でもあります。^{[ 1 ]}
• マスキング：異常の数が多い場合、それらのいくつかが密集して大きなクラスターに集まる可能性があり、個々の異常を分離することがより困難になり、結果としてそのような点を異常として検出することがより困難になります。スワンピングと同様に、この現象（「マスキング」として知られています）もサンプル内の点の数が多い場合に発生しやすく、サブサンプリングによって軽減できます。^{[ 1 ]}
• 高次元データ: 標準的な距離ベースの手法の主な制限の 1 つは、高次元データセットの処理が非効率的であることです。^{[ 9 ]}その主な理由は、高次元空間ではすべての点が等しく疎であるため、距離ベースの分離尺度を使用してもあまり効果的ではないからです。残念ながら、高次元データは iForest の検出パフォーマンスにも影響しますが、サンプル空間の次元を削減するために尖度などの特徴選択テストを追加することでパフォーマンスを大幅に向上させることができます。^{[ 1 ] [ 3 ]}
• 正常インスタンスのみ: iForest は、トレーニング セットに異常点が含まれていない場合でも良好なパフォーマンスを発揮します。^{[ 3 ]}その理由は、iForest がパス長 h(x _i ) の値が大きいほどデータ ポイントが存在することを示すようにデータ分布を記述しているためです。結果として、異常の存在は iForest の検出パフォーマンスにはほとんど関係ありません。

Isolation Forest を使用した異常検出は、主に 2 つの段階から構成されるプロセスです。^{[ 3 ]}

1. 最初の段階では、前のセクションで説明したように、トレーニングデータセットを使用してiTreeを構築します。
2. 第2段階では、テストセット内の各インスタンスが前の段階で構築されたiTreesを通過し、以下に説明するアルゴリズムを使用してインスタンスに適切な「異常スコア」が割り当てられます。

テストセット内のすべてのインスタンスに異常スコアが割り当てられると、分析が適用されるドメインに応じて事前に定義された閾値よりもスコアが大きいポイントを「異常」としてマークすることが可能になります。

前述のセクションで説明したように、Isolation Forest アルゴリズムは、計算とメモリ消費の両方の観点から非常に優れたパフォーマンスを発揮します。元のアルゴリズムの主な問題点は、ツリーの分岐方法にバイアスが生じ、データのランキングのための異常スコアの信頼性が低下する可能性があることです。これが、Hariri ら^{[ 8 ]}によるExtended Isolation Forest (EIF) アルゴリズムの導入の主な動機です。

オリジナルのIsolation Forestがなぜそのようなバイアスを受けるのかを理解するために、著者らは、平均がゼロで共分散が単位行列で与えられる2次元正規分布から抽出したランダムデータセットに基づく実例を示している。そのようなデータセットの例を図4に示す。

図を見れば、(0, 0) に近い点は正常点である可能性が高く、(0, 0) から遠く離れた点は異常点である可能性が高いことが容易に理解できます。したがって、点が分布の「中心」から放射状に外側へ移動するにつれて、点の異常スコアはほぼ円形かつ対称的なパターンで増加するはずです。しかし、著者らが Isolation Forest アルゴリズムによって生成された分布の異常スコア マップを生成することで示すように、実際にはそうではありません。点が放射状に外側へ移動するにつれて異常スコアは正しく増加しますが、中心からほぼ同じ放射距離にある他の点と比較して、x 方向と y 方向に異常スコアが低い長方形の領域も生成されます。

異常スコアマップに現れるこれらの予期せぬ長方形領域は、実際にはアルゴリズムによって導入されたアーティファクトであり、主にアイソレーションフォレストの決定境界が垂直または水平のいずれかに限定されていることに起因することが証明できる（図2および図3を参照）。^{[ 8 ]}

これが、Haririらが論文で、元のIsolation Forestを次のように改良することを提案している理由です。データの範囲内でランダムな特徴と値を選択するのではなく、ランダムな「傾き」を持つ分岐カットを選択します。EIFによるランダム分割の例を図5に示します。

著者らは、この新しいアプローチがどのようにして従来のアイソレーションフォレストの限界を克服し、最終的に異常スコアマップの改善につながるかを示している。

• Spark iForest - Apache Spark上で動作する、ScalaとPythonによる分散実装。Yang , Fangzhou著。
• Isolation Forest - LinkedInの不正対策AIチームのJames Verbus氏が作成した、Spark/Scalaによる実装。
• EIF – 異常検知のための拡張隔離森林の実装（Sahand Hariri著）
• scikit-learnのサンプルを含むPython 実装。

• 異常検知– データ分析におけるアプローチ 
• Apache Spark – オープンソースのデータ分析クラスタコンピューティングフレームワーク 
• ランダムフォレスト– ツリーベースのアンサンブル機械学習手法 
• 統計的プロセス管理– 品質管理手法