距離ベースの外れ値とは？定義と3つの代表的な検出アルゴリズムを解説

データセットS内のオブジェクトoが、パラメータpとdで定義される距離ベース（DB）外れ値、すなわちDB(p, d)外れ値であるとは、「S内の少なくとも割合pのオブジェクトが、oから距離dよりも遠い位置に存在する」場合を指します。言い換えれば、統計的検定に頼るのではなく、「近傍となるオブジェクトが十分に存在しないオブジェクト」を外れ値とみなす考え方です。近傍の有無は、対象オブジェクトからの距離に基づいて判定されます。

統計的手法との関係とメリット

統計的手法と比較すると、距離ベースの外れ値検出は、標準分布を前提とした不一致性検定（discordancy testing）の背後にある考え方を汎用化・統合したものといえます。このため、距離ベースの外れ値は「統一化された外れ値（unified outlier：UO-outlier）」とも呼ばれます。

この手法を用いることで、観測された分布を何らかの標準分布へ当てはめたり、適切な不一致性検定を選び出したりする際に発生しがちな過剰な計算を回避できます。さらに、ある不一致性検定においてオブジェクトoが外れ値と判定されるならば、適切に選んだpとdに対してoは必ずDB(p, d)外れ値でもあることが示されています。

具体例として、正規分布を仮定し「平均から3標準偏差以上離れたオブジェクトを外れ値とする」という基準は、DB(0.9988, 0.13σ)外れ値として統一的に表現できます。

距離ベース外れ値マイニングの主なアルゴリズム

距離ベースの外れ値を効率的に抽出するために、これまでにいくつかの効率的なアルゴリズムが提案されています。代表的なものは以下の3つです。

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

データセットが与えられると、R木やk-d木などの多次元インデックス構造を活用し、各オブジェクトoを中心とする半径d以内の近傍オブジェクトを探索します。Mを外れ値のd近傍内に含まれるオブジェクト数の最大値とすると、オブジェクトoについてM+1個の近傍が見つかった時点で、oは外れ値ではないと判定できます。平均計算量はO(k・n²)で、ここでkは次元数、nはデータセット内のオブジェクト数です。

2. ネステッドループ（入れ子ループ）アルゴリズム

ネステッドループアルゴリズムは、インデックスベースのアルゴリズムと同等の計算量を持ちますが、インデックス構造の構築を行わず、I/Oの発生回数を最小限に抑えることを狙いとした手法です。メモリバッファ領域を半分ずつ2つに分割し、データを複数の論理ブロックに整理して処理を進めます。

3. セルベースのアルゴリズム

O(n²)という計算コストの増大を回避するために、メモリ上に展開可能なデータセット向けに開発されたのがセルベースのアルゴリズムです。その計算量はO(c^k + n)で、ここでcはセルの個数に依存する定数、kは次元数を表します。

この手法では、まずデータ空間を一辺の長さが d/(2√k) のセル群に分割します。各セルの周囲には2つの層が設けられ、第1層は1セル分、第2層は 2√k−1 を切り上げた数のセル分の厚さとなります。アルゴリズムはオブジェクト単位ではなくセル単位で外れ値を判定し、各セルごとに「①セル内のオブジェクト数」「②セル＋第1層内のオブジェクト数」「③セル＋両層を合わせた範囲内のオブジェクト数」という3つのカウントを集計します。

まとめ

距離ベースの外れ値検出は、特定の確率分布や統計的検定を前提とせず、「近傍の不足」という直感的な基準だけで外れ値を定義できる点が大きな特徴です。データの規模や次元数に応じてインデックスベース・ネステッドループ・セルベースの各アルゴリズムを使い分けることで、大規模データに対しても効率的な異常検出が可能になります。