Isolation forest
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/06/29 05:07 UTC 版)
| 機械学習および データマイニング |
|---|
 |
 Category:データマイニング |
Isolation forestは2008年にFei Tony Liu（中：是刘飞）、Kai Ming Ting（中： 陈开明）、Zhi-Hua Zhou（中：周志华(英語版)）によって提案された決定木を用いて異常検知を行う教師なし学習アルゴリズムである。[1][2][3]
統計学において、異常値（別名：外れ値）とは、他の事象から著しく逸脱し、異なる平均値によって生成されたのではないかと疑念を抱かせる観測値または事象を指す。例えば、図1のグラフは、1か月間のウェブサーバーへの流入トラフィックを、3時間ごとのリクエスト数で表したものである。図を見るだけで明らかなように、一部のデータポイント（赤丸で示された箇所）は異常な高値を示しており、その時間帯にウェブサーバーが攻撃を受けていた可能性を疑わせる。一方、赤矢印で示された平坦な区間もまた異常であり、その時間帯にサーバーがダウンしていた可能性がある。
大容量データセット内の異常は極めて複雑なパターンに従うことがあり、ほとんどの場合目視による検出は困難である。これが異常検出分野が機械学習技術の応用に適している理由である。
異常検知で一般的に用いられる手法の多くは、まず「正常な状態」を表すプロファイルを構築し、そのプロファイルに適合しないデータを異常として検出するものである。これに対してIsolation Forestは、正常なデータのモデルを構築するのではなく、データセット内の異常な点を直接孤立させるという異なるアプローチを採用している。この手法の主な利点は、従来のプロファイルベースの手法では難しい規模でサンプリング技術を活用できる点にある。その結果、少ないメモリ使用量で高速[疑問点] に動作する異常検知アルゴリズムを実現している。[2][4]
歴史
Isolation Forest（以下：iForest）アルゴリズムは、2008年にFei Tony Liu、Kai Ming Ting、Zhi-Hua Zhouによって最初に提案された。[2]著者らは、サンプル中の異常データが持つ、次の二つの量的な性質に着目した。
- 正常データと比べて出現数が少なく、少数派であること
- 各特徴量の値が、正常データの値と大きく異なること
異常データは一般に数が少なく、サンプル内のほかのデータとは大きく異なるため、正常データよりも容易に「孤立」させられると考えられる。iForestはこの原理に基づき、データセットに対して複数のIsolation Tree（iTree：孤立木）を構築する。そして、各iTreeにおける平均パス長が短いデータを、異常として判定する。
2012年に発表された後続論文[5]において、同じ著者らは、iForestが以下の性質を持つことを実証するための一連の実験を行った。
- 線形時間に近い低い計算量で動作し、必要とするメモリ容量も小さい
- 異常検知に関係しない特徴量を含む高次元データにも対応できる
- 学習データに異常データが含まれている場合でも、含まれていない場合でも学習できる
- 再学習を行うことなく、異なる粒度で異常検知の結果を得られる
2013年、Zhiguo DingとMinrui Feiは、ストリーミングデータにおける異常検知の問題を解決するため、iForestを基盤としたフレームワークを提案した。[6]ストリーミングデータへのiForestの応用については、このほかにもSwee Chuan Tanら[7]、G. A. Sustoら[8]、Yu Wengら[9]の論文で報告されている。
iForestを異常検知に適用する際の主要な問題の一つは、モデルそのものではなく、異常スコアの算出方法にあった。
Sahand Hariri、Matias Carrasco Kind、Robert J. Brunnerは、2018年に発表した論文でこの問題を指摘し、iForestを改良したモデルであるExtended Isolation Forest（EIF）を提案した。[10]同論文では、従来のiForestに加えられた改良点と、それによって各データ点に対して算出される異常スコアの一貫性および信頼性が、どのように向上するかが説明されている。
アルゴリズム
iForestアルゴリズムは、データセット内の異常データは、正常データと比べてほかのデータから分離、すなわち「孤立」させやすいという性質に基づいている。データ点を孤立させるため、アルゴリズムはまず特徴量をランダムに1つ選択し、次に、その特徴量が取り得る最小値と最大値の間から分割値をランダムに選ぶ。この処理を再帰的に繰り返すことで、サンプルを複数の領域に分割していく。
二次元の正規分布に従うデータセットをランダムに分割する例として、図2では正常なデータ点を、図3では異常である可能性が高いデータ点を、それぞれ孤立させる過程を示している。これらの図から、異常データは正常データに比べて、より少ない回数のランダム分割で孤立させられることが分かる。
数学的には、この再帰的な分割処理は、Isolation Tree（iTree：孤立木）と呼ばれる木構造として表現できる。また、あるデータ点を孤立させるまでに必要な分割回数は、木の根から終端ノードに到達するまでのパス長として解釈できる。
例えば、図2に示された点
従来のiForestにこのような偏りが生じる理由を説明するため、著者らは、平均が0、共分散行列が単位行列である二次元正規分布からランダムに生成したデータセットを用いて、具体的な例を示している。そのようなデータセットの一例を図4に示す。
図を見ると、(0,0) 付近に位置する点は正常データである可能性が高く、(0,0) から大きく離れた点は異常データである可能性が高いことが直感的に分かる。
したがって、本来であれば異常スコアは、分布の中心から外側へ離れるにつれて、ほぼ円形かつ対称的に増加すると考えられる。しかし、実際にはそうならない。著者らは、iForestによって生成された異常スコアマップを用いて、この問題を示している。
異常スコア自体は、点が中心から外側へ離れるにつれて正しく増加しているものの、中心からほぼ同じ距離にある他の点と比べて、x 軸方向および y 軸方向に、異常スコアが不自然に低い長方形状の領域が生じる。
異常スコアマップに現れる予期しない長方形状の領域は、データ本来の性質によるものではなく、アルゴリズムによって生じた人工的な偏りであることが示されている。
その主な原因は、iForestの決定境界が、垂直方向または水平方向の分割に限定されている点にある（図2および図3参照）。[16]
この問題を改善するため、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が実装されており、使用例も提供されている。
参考文献
- ↑ Liu. “First Isolation Forest implementation on Sourceforge”. 2026年6月22日閲覧。
- 1 2 3 Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (December 2008). “Isolation Forest”. 2008 Eighth IEEE International Conference on Data Mining. pp. 413–422. doi:10.1109/ICDM.2008.17. ISBN 978-0-7695-3502-9
- ↑ Liu, Fei Tony; Ting, Kai Ming; Zhou, Zhi-Hua (December 2008). “Isolation-Based Anomaly Detection”. ACM Transactions on Knowledge Discovery from Data 6: 3:1–3:39. doi:10.1145/2133360.2133363.
- ↑ Chuan Tan, Swee; Ming Ting, Kai; Fei Liu, Tony. “Fast anomaly detection for streaming data”. July 2011 2: 1511-1516.
- ↑ Ding, Zhiguo; Fei, Minrui (September 2013). “An Anomaly Detection Approach Based on Isolation Forest Algorithm for Streaming Data using Sliding Window”. 3rd IFAC International Conference on Intelligent Control and Automation Science..
- ↑ Ding, Zhiguo; Fei, Minrui (2013). “An Anomaly Detection Approach Based on Isolation Forest Algorithm for Streaming Data using Sliding Window” (英語). IFAC Proceedings Volumes 46 (20): 12–17. doi:10.3182/20130902-3-CN-3020.00044. ISSN 1474-6670.
- ↑ Tan, Swee Chuan; Ting, Kai Ming; Liu, Tony Fei (2011-07-16). “Fast anomaly detection for streaming data”. Proceedings of the Twenty-Second international joint conference on Artificial Intelligence - Volume Volume Two (Barcelona, Catalonia, Spain: AAAI Press): 1511–1516. ISBN 978-1-57735-514-4.
- ↑ Susto, Gian Antonio; Beghi, Alessandro; McLoone, Seán (2017-05). “Anomaly detection through on-line isolation Forest: An application to plasma etching”. 2017 28th Annual SEMI Advanced Semiconductor Manufacturing Conference (ASMC): 89–94. doi:10.1109/ASMC.2017.7969205.
- ↑ Weng, Yu; Liu, Lei (2019). “A Collective Anomaly Detection Approach for Multidimensional Streams in Mobile Service Security”. IEEE Access 7: 49157–49168. doi:10.1109/ACCESS.2019.2909750. ISSN 2169-3536.
- ↑ Hariri, Sahand; Kind, Matias Carrasco; Brunner, Robert J. (2021-04-01). “Extended Isolation Forest”. IEEE Transactions on Knowledge and Data Engineering 33 (4): 1479–1489. doi:10.1109/TKDE.2019.2947676. ISSN 1041-4347.
- 1 2 3 4 5 Fei, Toni Liu; Ting, Kai Ming; Zhou, Zhi-Hua (December 2008). “Isolation Forest”. 2008 Eighth IEEE International Conference on Data Mining: 413–422.
- ↑ Chandola, Varun; Banerjee, Arindam; Kumar, Kumar (July 2009). “Anomaly Detection: A Survey”. ACM Computing Surveys 41.
- ↑ Dilini Talagala, Priyanga; Hyndman, Rob J.; Smith-Miles, Kate (12 Aug 2019). “Anomaly Detection in High Dimensional Data”. arXiv:1908.04000.
- 1 2 3 4 Fei, Toni Liu; Ting, Kai Ming; Zhou, Zhi-Hua (December 2008). “Isolation-based Anomaly Detection”. ACM Transactions on Knowledge Discovery from Data 6: 1-39.
- ↑ Shaffer, Clifford A. (2011). Data structures & algorithm analysis in Java (3rd Dover ed.). Mineola, NY: Dover Publications. ISBN 9780486485812. OCLC 721884651
- 1 2 Hariri, Sahand; Carrasco Kind, Matias; Brunner, Robert J. (Sep 2, 2013). “Extended Isolation Forest”. arXiv:1811.02141.
- Isolation forestのページへのリンク
