# Anomaly Detection - A Survey - Chapter 1: Introduction > 次: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 2 Different Aspects of an Anomaly Detection Problem]] | 全体: [[Anomaly Detection - A Survey]] ## 要約 第1章は、本サーベイ全体の導入部である。異常検知を「期待される振る舞いに適合しないデータ中のパターンを見つける問題」と定義し(§1.1)、隣接分野(ノイズ除去・ノイズ許容・ノベルティ検知)との違いを明確にする。次に、異常検知が本質的に難しい理由を6点挙げ(§1.2)、関連する既存サーベイを概観したうえで(§1.3)、本サーベイが既存サーベイに対してどう差別化されるかを述べる(§1.4)。差別化の核は、技法を6カテゴリに整理し、各カテゴリの「正常/異常を区別する仮定」を明示し、基本技法とその変種という形で記述する方法論そのものにある。 ## 分類軸(taxonomy) ### 異常の呼称と応用領域 異常(anomaly)を指す語は文献によって様々であり、outliers、discordant observations、exceptions、aberrations、surprises、peculiarities、contaminants などが使われる。中でも anomaly と outlier が最も一般的で、しばしば同義に使われる。応用領域として、クレジットカード・保険・医療の不正検知、サイバーセキュリティの侵入検知、安全性が重視されるシステムの障害検知、軍事監視が挙げられる。異常の検出が重要である理由は、異常が業務上重大な行動可能情報(actionable information)に直結するからであり、具体例として、コンピュータネットワークの異常トラフィックパターン(乗っ取られた計算機による機密データの不正送信 [Kumar 2005])、MRI 画像の異常(悪性腫瘍の兆候 [Spence et al. 2001])、クレジットカード取引の異常(カード詐欺・アイデンティティ詐欺 [Aleskerov et al. 1997])、宇宙船センサの異常読み取り(部品故障の兆候 [Fujimaki et al. 2005])が挙げられる。異常・外れ値の検出自体は統計学コミュニティで19世紀から研究されてきた([Edgeworth 1887])。 ### §1.1 異常とは何か——隣接分野との切り分け 異常は「正常な振る舞いについての明確に定義された概念に適合しないパターン」である。**Figure 1** は2次元データ集合での例を示す。データには2つの正常領域 N1・N2 があり、大半の観測点はそこに属する。N1・N2 から十分離れた点(o1、o2)や、離れた領域を形成する点群(O3)が異常である。 **Figure 1: 2次元データ集合における異常の例** ![[_attachments/survey-chandola-2009-anomaly-detection/ch01-fig1-anomaly-example-2d.png]] (Fig. 1. 正常領域 N1・N2 に属さない点 o1・o2 と、それ自体が小さな集合を成す領域 O3 が異常として図示される。) 異常が生じる理由は、クレジットカード詐欺・サイバー侵入・テロ活動・システム故障など多様だが、共通するのは分析者にとって「興味深い(interesting)」という点であり、この興味深さ・実生活での関連性が異常検知の重要な特徴である。 異常検知は、隣接するが異なる問題である**ノイズ除去**([Teng et al. 1990])および**ノイズ許容**([Rousseeuw and Leroy 1987])とは区別される。ノイズとは分析者にとって関心の対象でなくデータ分析の妨げとなる現象であり、ノイズ除去は分析の前に不要な対象を取り除くことを目的とし、ノイズ許容は統計的モデル推定を異常な観測から免疫化することを指す([Huber 1974])。 もう一つの関連分野は**ノベルティ検知**([Markou and Singh 2003a, 2003b]、[Saunders and Gero 2000])であり、これはデータ中で以前観測されなかった(創発的・新規な)パターンを検出することを目的とする(例: ニュースグループの新しい話題)。新規パターンと異常の違いは、新規パターンは検出後に正常モデルへ組み込まれるのが一般的である点にある。これらの関連問題に対する解法は、異常検知にもしばしば流用され、その逆も成り立つため、本サーベイでもあわせて扱う。 ### §1.2 異常検知が難しい理由 素朴なアプローチは、正常な振る舞いを表す領域を定義し、その領域に属さない観測をすべて異常と宣言することである。しかし、これを難しくする要因が複数ある。 - あらゆる正常な振る舞いを包含する正常領域を定義するのは非常に困難であり、正常と異常の境界は不明瞭であることが多い。境界に近い異常な観測は実は正常である可能性があり、その逆もある。 - 異常が悪意ある行為の結果である場合、悪意ある敵対者はしばしば異常な観測が正常に見えるよう適応し、正常な振る舞いの定義をさらに困難にする。 - 多くのドメインで正常な振る舞いは進化し続けるため、現在の正常概念が将来も十分に代表的であるとは限らない。 - 異常の正確な概念は応用ドメインごとに異なる。例えば医療ドメインでは体温の小さな変動が異常となりうるが、株式市場ドメインでは株価の同程度の変動は正常と見なされうる。あるドメインで開発された技法を別のドメインへ適用するのは単純ではない。 - 異常検知技法が用いるモデルの訓練・検証用のラベル付きデータの入手可能性は、通常大きな課題である。 - データにはしばしば実際の異常と類似したノイズが含まれ、区別・除去が難しい。 これらの課題により、異常検知問題は最も一般的な形では容易に解けない。実際、既存の異常検知技法の大半は問題の特定の定式化を解いている。定式化はデータの性質、ラベルの入手可能性、検出すべき異常の型などの要因によって決まり、これらの要因はしばしば応用ドメインによって定まる。研究者は統計学・機械学習・データマイニング・情報理論・スペクトル理論など多様な分野の概念を採用し、特定の問題定式化に適用してきた。**Figure 2** は、任意の異常検知技法に関わる主要な構成要素を示す。 **Figure 2: 異常検知技法に関わる主要な構成要素** ![[_attachments/survey-chandola-2009-anomaly-detection/ch01-fig2-key-components.png]] (Fig. 2. 機械学習・データマイニング・統計学・情報理論・スペクトル理論などの研究領域が、データの性質・ラベル・異常の型・出力形式という問題特性を介して個々の異常検知技法に落とし込まれ、その技法は侵入検知・詐欺検知・障害/損傷検知・医療情報学などの応用ドメインからの要請と対応づく。) ### §1.3 関連する既存サーベイ 異常検知は多数のサーベイ・レビュー論文・書籍の主題となってきた。[Hodge and Austin 2004] は機械学習・統計ドメインで開発された異常検知技法の広範なサーベイを提供する。[Agyemang et al. 2006] は数値データ・記号データ双方の異常検知技法を幅広くレビューする。[Markou and Singh 2003a] と [Markou and Singh 2003b] はそれぞれニューラルネットワークと統計的アプローチを用いたノベルティ検知技法の詳細なレビューである。[Patcha and Park 2007] と [Snyder 2001] はサイバー侵入検知に特化した異常検知技法のサーベイを提示する。統計学分野での外れ値検知の研究は、[Rousseeuw and Leroy 1987]、[Barnett and Lewis 1994]、[Hawkins 1980] などの書籍や、[Beckman and Cook 1983]、[Bakar et al. 2006] などのサーベイ論文でレビューされている。 ## 代表手法・システムの比較 第1章は個々の検知技法をまだ扱わないが、**Table I** で本サーベイと既存の関連サーベイ論文がカバーする技法カテゴリ・応用ドメインを比較する。 **Table I: 本サーベイと関連サーベイ論文の比較** ![[_attachments/survey-chandola-2009-anomaly-detection/ch01-table1-survey-comparison.png]] | | 1 (本サーベイ) | 2 (Hodge and Austin 2004) | 3 (Agyemang et al. 2006) | 4 (Markou and Singh 2003a) | 5 (Markou and Singh 2003b) | 6 (Patcha and Park 2007) | 7 (Beckman and Cook 1983) | 8 (Bakar et al. 2006) | |---|---|---|---|---|---|---|---|---| | 技法: Classification Based | ✓ | ✓ | ✓ | ✓ | | ✓ | | | | 技法: Clustering Based | ✓ | ✓ | ✓ | | | ✓ | | | | 技法: Nearest Neighbor Based | ✓ | ✓ | ✓ | | | ✓ | | ✓ | | 技法: Statistical | ✓ | ✓ | ✓ | | ✓ | ✓ | ✓ | ✓ | | 技法: Information Theoretic | ✓ | | | | | | | | | 技法: Spectral | ✓ | | | | | | | | | 応用: Cyber-Intrusion Detection | ✓ | | | | | ✓ | | | | 応用: Fraud Detection | ✓ | | | | | | | | | 応用: Medical Anomaly Detection | ✓ | | | | | | | | | 応用: Industrial Damage Detection | ✓ | | | | | | | | | 応用: Image Processing | ✓ | | | | | | | | | 応用: Textual Anomaly Detection | ✓ | | | | | | | | | 応用: Sensor Networks | | | | | | | | | (Table I. 本サーベイ(列1)は、既存の関連サーベイ7本のいずれよりも技法カテゴリ数(6)・応用ドメイン数(6ドメインに✓、Sensor Networks は本文中で扱うが表では無印)ともに広くカバーすることを示す。情報理論的手法とスペクトル手法は本サーベイのみが扱う。) ### §1.4 本サーベイの貢献——記述様式そのものが方法論 本サーベイは、複数の研究領域・応用ドメインにまたがる異常検知研究について、構造化され広範な概観を提供する試みである。既存サーベイの大半は特定の応用ドメインか単一の研究領域に焦点を絞る。[Agyemang et al. 2006] と [Hodge and Austin 2004] は異常検知技法を複数カテゴリに分けて各カテゴリの技法を論じる点で関連するが、本サーベイはこの2本の先行研究を土台に、複数の方向へ議論を大きく拡張する。 **本サーベイ固有の記述様式**は次の3点に要約される。 1. **カテゴリの拡張と仮定の明示**: [Agyemang et al. 2006] と [Hodge and Austin 2004] が扱う4カテゴリ(分類ベース・クラスタリングベース・近傍ベース・統計的)に、情報理論的手法とスペクトル手法の2カテゴリを追加し、計6カテゴリとする。6カテゴリそれぞれについて技法を論じるだけでなく、**そのカテゴリに属する技法群が異常の性質について依拠する固有の仮定を特定する**。この仮定は、あるカテゴリの技法がいつ異常を検出でき、いつ失敗するかを判断するための決定的な材料になる。 2. **基本技法とその変種という記述単位**: 各カテゴリについて**基本となる異常検知技法を1つ定め**、そのカテゴリに属する既存の多様な技法を、この基本技法の変種として位置づけて説明する。このテンプレートにより、カテゴリに属する技法群をより容易かつ簡潔に理解できるとする。さらに各カテゴリについて、技法の利点・欠点、および実応用ドメインで重要となる計算量についても議論する。 3. **応用ドメインの詳細な記述**: 既存サーベイの多くは異常検知の応用に言及するにとどまるが、本サーベイは応用ドメインごとに、異常の概念・異常検知問題の異なる側面・直面する課題を詳細に論じ、そのドメインで用いられた技法一覧を提示する。 加えて本サーベイは、**単純な異常(simple anomaly)と複雑な異常(complex anomaly)を区別する**。既存サーベイが論じる異常検知技法は最も単純な形の異常を検出するものにとどまるが、応用ドメインの議論を通じて、大半の応用ドメインで関心が持たれる異常は複雑な性質を持つのに対し、アルゴリズム研究の大半は単純な異常に焦点を絞ってきたことが明らかになる。 ## 傾向と未解決課題 - 第1章の時点で、異常検知の一般形(正常領域の完全な定義)は次の6要因により本質的に難しいと述べられている: (1) 正常領域の完全な定義困難と境界の不明瞭さ、(2) 悪意ある敵対者による適応、(3) 正常概念の経年変化、(4) ドメインごとに異なる異常の概念、(5) ラベル付きデータの不足、(6) 実際の異常と類似したノイズの混入(§1.2)。 - 既存の研究がカバーする異常が単純な異常に偏る一方、応用ドメインで関心が持たれる異常の多くは複雑な性質を持つという乖離を、本サーベイは自ら課題として明示する(§1.4)。この乖離をどう埋めるかは、後続の章(応用ドメインごとの議論、および文脈異常・集合異常を扱う第2章)で展開される。 - 異常検知・ノイズ除去・ノイズ許容・ノベルティ検知という4つの関連問題の境界は概念的に整理されているが、実務上どこまで解法が相互流用可能かは第1章の時点では検証されておらず、以降の章で技法ごとに評価される。 ## 関連 - 次章: [[@2009__CSUR__Anomaly Detection - A Survey - Chapter 2 Different Aspects of an Anomaly Detection Problem]](点異常・文脈異常・集合異常の分類を導入) - ハブ: [[Anomaly Detection - A Survey]] - 概念: [[異常検知]] - 著者: [[Varun Chandola]] / [[Arindam Banerjee]] / [[Vipin Kumar]] - 所属: [[University of Minnesota]] - MOC: [[異常検知 - MOC]] ## 出典 - Chandola, V., Banerjee, A., and Kumar, V. 2009. Anomaly detection: A survey. ACM Comput. Surv. 41, 3, Article 15 (July 2009), 58 pages. DOI: 10.1145/1541880.1541882 - 原本: `.raw/theses/survey-chandola-2009-anomaly-detection/chapters/ch-01.txt`(PDF p1–5)