教師なし学習アルゴリズム: 異常検出

外れ値とは何でしょうか? Hawkins (1980) は外れ値の基本的な定義を与えました: 外れ値とは、データセット内の他のデータと大きく異なるデータであり、そのデータはランダムな偏差ではなく、まったく異なるメカニズムによって生成されたものであると疑われるものです。クラスタリング アルゴリズムの異常の定義: 異常とは、クラスターが埋め込まれているバックグラウンド ノイズです。異常検出アルゴリズムによる異常の定義: 異常とは、クラスターにもバックグラウンド ノイズにも属さないポイントです。その動作は通常の動作とは大きく異なります。ある季節のある日の温度が非常に高かったり、非常に低かったりする場合、この温度データは異常です。異常検出と分析はデータ マイニングの重要な側面であり、非常に興味深いマイニングのトピックでもあります。これは、「小さなパターン」（クラスターとは対照的）を検出するために使用されます。つまり、データセットの中央にあり、データの残りの部分とは大きく異なるオブジェクトを検出します。異常検出は、通信やクレジットカード詐欺、ローン承認、医薬品研究、医療分析、消費者行動分析、天気予報、金融分野の顧客分類、ネットワーク侵入検知など、幅広い用途に使用されています。

1. 異常検知手法の分類

異常データマイニングは非常に興味深い研究テーマです。国内外でこの分野に関するアルゴリズム文献が数多く提案されています。これらの方法は、統計ベースの方法、距離ベースの方法、偏差ベースの方法、密度ベースの方法の4つのカテゴリに大別できます。

1. 統計的手法

与えられたデータセットがランダム分布（正規分布など）に従うと仮定して、不一致テストを使用して異常を識別します。問題は、多くの場合、ユーザーがデータ分布を知らないこと、そして実際のデータが理想的な数学的分布に従わないことが多いことです。たとえ低次元 (1 次元または 2 次元) でデータ分布がわかっていても、高次元でのデータ ポイントの分布を推定することは非常に困難です。

2. 距離ベースの方法

Knorr と Ng (VLDB'1998) は、距離ベースの異常検出方法を提案しました。距離ベースの異常の定義は、データセット S 内のオブジェクト O が次の特性を満たす場合、DB(p,D) 外れ値と呼ばれます。データセット S 内のオブジェクトの少なくとも p*100% が、O からの距離 D よりも大きい距離にあります。簡単に言えば、距離ベースの外れ値は「十分な」近傍を持たないオブジェクトです。異なるパラメータ p と D を取ると、DB(p,D) 外れ値は統計に基づくすべての異常を表すことができます。距離ベースの異常検出アルゴリズムは、インデックスベースのアルゴリズム、ネストされたループ アルゴリズム、セルベースの方法の 3 つの基本的なタイプに分けられます。

1. インデックスベースのアルゴリズム

すべての DB(p,D) 外れ値を見つけるには、O を中心とした最近傍クエリまたは範囲クエリに回答します。多次元インデックス構造 R-Tree または kd-Tree に基づくアルゴリズムの複雑さは O(kN2) です。ここで、k は次元、N はデータ ポイントの数です。デメリット: 多次元のインデックス構造を確立する必要があり、時間がかかり複雑です。

2. ネストループアルゴリズム NL

メモリ バッファ スペースは 2 つの等しい部分に分割され、データ セットは各バッファと同じサイズの複数の論理ブロックに分割されます。各バッファへの呼び出し順序を慎重に選択することで、I/O 回数が最小限に抑えられます。アルゴリズムの複雑さは O(kN2) です。ここで、k は次元、N はデータ ポイントの数です。 特徴: 多次元インデックス構造を構築する必要がなく、時間の複雑さが比較的高くなります。

3. ユニットベースのアプローチ

データ空間は、辺の長さが D/(2k1/2) のセルに分割されます。各セルには 2 つの囲み層があり、最初の層はセルの厚さの 1 倍、2 番目の層はセルの厚さの int(2k1/2 -1) + 1 倍です。

cell_+_1_layer_count>M の場合、セル内のすべてのオブジェクトは異常ではありません。

cell_+_2_layer_count<=M の場合、セル内のすべてのオブジェクトが異常です。

そうしないと、ユニット内の一部のオブジェクトが異常である可能性があり、1 つずつ処理する必要があります。アルゴリズムの複雑さはO(ck+N)です。

インデックス作成のオーバーヘッドが非常に高いため、単純なインデックス アルゴリズムは競争力がありません。k<=4 の場合、N が大きいほど、ユニット ベースのアルゴリズムの方が明らかに有利です。k>=5 の場合、ネストされたループ アルゴリズムの利点が現れ始めます。

4. 距離ベースのアルゴリズムの改善

Knorr と Ng (VLDB'1998) の距離ベースの異常検出方法の欠陥のある入力パラメータ p と D は特定が難しく、パラメータが異なると結果が非常に不安定になります。この場合、ユーザーは満足のいく解決策を決定するために p と D を繰り返し入力してテストする必要があり、異常の度合いを示すことはできず、アルゴリズムは非常に複雑です。ラストギとラマスワミ（SIGMOD'2000）は距離に基づく異常の新しい定義を提案した。

: Dnk 異常、Dk(p) は点 p とその k 番目に近い点の間の距離を表します。d 次元空間に N 個の点を含むデータセットがあり、パラメータ n と k (自然数) が指定されている場合、Dk(p')>Dk(p) を満たす点 p' が n-1 個以下であれば、p は Dnk 異常と呼ばれます。データ ポイントが Dk(p) 距離に従って並べ替えられる場合、最初の n ポイントは外れ値と見なされます。ネストループアルゴリズム: 各ポイント p について、k 番目に近い隣接ポイントまでの距離 Dk(p) を計算し、Dk 値が最大となる最初の n ポイントを異常として取ります。上記のアルゴリズムは、一度に 1 つのポイント p を処理するため、データベースを 1 回スキャンし、合計 N 回スキャンする必要があります (N はデータ ポイントの数)。 ストレージに R* ツリーなどの空間インデックス構造を使用するインデックス ベースのアルゴリズム。パーティションベースのアルゴリズムに基づくと、ある点の Dk(p) が小さい場合、それが Dnk 異常である可能性は低くなります。データセットを最初にパーティションに分割し、各パーティションの Dk(p) の上限と下限を推定できます。特定のパーティションに異常が含まれないと判断できる場合は、そのパーティションを直接削除し、残りのパーティション (候補パーティション) から異常を計算できます。 BIRCH など、データ セットを分割するために使用できる既存のクラスタリング アルゴリズムは多数あります。

3. バイアスに基づく方法

Argrawal と Ragaran (KDD'1995) は、「シーケンシャル例外」の概念を提案しました。アルゴリズムの紹介 n個のオブジェクトの集合Sが与えられたとき、2≤m≤nでSj-1を満たすサブセットシーケンス{S1, S2, ..., Sm}を確立する。

4. 密度ベースの方法

距離異常の欠陥、密度ベースの方法における概念オブジェクト p の k 距離は、p とオブジェクト o の間の距離として定義されます。ここで、o は次の条件を満たします。

d(p, o') ≠ d(p, o) となるオブジェクト o'∈D\{p} は少なくとも k 個存在し、d(p, o') < d(p, o) となるオブジェクト o'∈D\{p} は最大で k-1 個存在します。 密度ベースの方法に関連する概念、

1. オブジェクト p の k 距離近傍 (Nk 距離)。p の k 距離、k 距離 (p) が与えられると、p の k 距離近傍には、p までの距離が k 距離 (p) を超えないすべてのオブジェクトが含まれます。

2. オブジェクト o に対するオブジェクト p の到達可能距離。自然数 k が与えられた場合、オブジェクト o に対するオブジェクト p の到達可能距離は次のようになります。

3. オブジェクト p のローカル到達可能距離。オブジェクト p のローカル到達可能密度は、オブジェクト p とその MinPts 近傍間の平均到達可能距離の逆数です。

4. オブジェクト p のローカル外れ値係数。ローカル異常の性質。オブジェクト p のローカル外れ値係数は、p の異常の度合いを示します。ローカル外れ値係数が大きいほど、異常である可能性が高くなります。そうでない場合、可能性は低くなります。クラスター内のコアポイントに近いオブジェクトの LOF は 1 に近いため、ローカル異常とは見なされません。クラスターの端またはクラスターの外側にあるオブジェクトの LOF は比較的大きくなります。

ローカル異常要因の計算: 最初のステップは、すべてのポイントの MinPts 近傍を生成し (同時に MinPts 距離も取得)、その中の各ポイントまでの距離を計算することです。低次元データの場合、グリッドを使用して k-NN クエリを実行でき、全体の計算時間は O(n) です。中次元または中高次元データの場合、X ツリーなどのインデックス構造を使用する必要があります。これにより、k-NN クエリの時間は O(logn)、全体の計算時間は O(n logn) になります。非常に高次元のデータの場合、インデックス構造は効果がなく、時間の計算量は O(n2) に増加します。 2 番目のステップは、各ポイントのローカル外れ値係数を計算することです。

2. アルゴリズムの概要

統計的異常検出の応用は、主にデータの分布特性を事前に知る必要があり、その適用範囲が制限されるため、科学研究コンピューティングに主に限定されています。 シーケンス異常検出アルゴリズムによって提案されたシーケンス異常の概念は、広く認識されていません。これは、シーケンス異常の概念にはまだ欠陥があり、多くの異常なデータを見逃してしまうためです。統計ベースのアルゴリズムと比較して、距離ベースのアルゴリズムでは、ユーザーがドメイン知識を持っている必要がありません。 「シーケンス異常」と比較すると、概念がより直感的です。さらに重要なのは、距離異常はホーキンスの異常の性質の定義に近いということです。密度ベースの異常ビューは、距離ベースの異常ビューよりも Hawkins の異常定義に近いため、距離ベースの異常アルゴリズムでは識別できない種類の異常データ (ローカル異常) を検出できます。ローカル異常の観点は、これまでのすべての異常の定義における「これかあれか」という絶対的な異常の概念を放棄し、現実の生活での応用に沿ったものになっています。

上記の異常検出アルゴリズムは、静的なデータセットを研究対象として取り、出力結果を取得するためにデータセットを複数回スキャンする必要があります。現実の世界では、動的なデータセット、つまりストリーミングデータのオンライン処理の需要がより切実になっています。そのため、たった 1 回のスキャンで結果を取得できるデータ ストリーム異常検出アルゴリズムが、現在研究のホットスポットになっています。