距離ベースの外れ値とは何ですか？

データセットS内のオブジェクトoは、パラメーターpおよびdを持つ距離ベース（DB）の外れ値です。つまり、S内のオブジェクトの最小部分pがdよりも高い距離にある場合はDB（p、d）です。 o。言い換えると、統計的検定に依存する代わりに、距離ベースの外れ値を、十分な近傍がないオブジェクトと見なすことができます。

ネイバーは、指定されたオブジェクトからの距離に基づいて表されます。統計ベースの方法と比較して、距離ベースの外れ値検出は、標準分布の不一致テストの背後にある考え方を一般化またはマージします。したがって、距離ベースの外れ値は、統一外れ値またはUO外れ値とも呼ばれます。

距離ベースの外れ値検出は、観測された分布をいくつかの標準分布に適合させたり、不一致テストを選択したりすることに関連する可能性のある過度の計算を防ぎます。一部の不一致テストでは、オブジェクトoが特定のテストに従って外れ値である場合、oは適切に表されたpおよびdのDB（p、d）外れ値でもあると表示できます。

たとえば、平均から3標準偏差以上離れているオブジェクトが、正規分布を考慮して外れ値として扱われる場合、この表現はDB（0.9988、0.13s）（外れ値）によって「統合」できます。次のように作成された距離ベースの外れ値をマイニングするためのいくつかの効率的なアルゴリズムがあります-

インデックスベースのアルゴリズム −データセットが与えられると、インデックスベースのアルゴリズムは、Rツリーまたはk-dツリーを含む多次元インデックス構造を容易にして、そのオブジェクトの周囲の半径d内の各オブジェクトoの近傍を検索します。 Mを外れ値のd近傍内のオブジェクトの最大数とします。したがって、オブジェクトoのM + 1の近傍が検出されると、oが外れ値ではないことにアクセスできます。このアルゴリズムは、O（k * n2）の最小の場合の複雑さを持ちます。ここで、kは次元であり、nはデータセット内のオブジェクトの数です。

ネストされたループアルゴリズム −ネストされたループアルゴリズムは、インデックスベースのアルゴリズムと同じ評価の複雑さを持ちますが、インデックス構造の構築を回避し、I/Oの数を最小限に抑えようとします。メモリバッファ領域を2つに分割し、データをいくつかの論理ブロックに設定します。

セルベースのアルゴリズム − O（n ² を回避できます ）計算の複雑さ、セルベースのアルゴリズムがメモリ常駐データセット用に開発されました。その複雑さはO（e ^k + n）、ここで、cはセルの数に基づく定数、kは次元です。

このメソッドでは、データスペースは$ \ frac {d} {\ sqrt [2]{k}}$のような一辺の長さのセルに分割されます。各セルには、その周囲に2つの層があります。

最初のレイヤーは1セルの厚さで、2番目のレイヤーは$ \ sqrt [2] {k} $セルの厚さで、最も近い整数に切り上げられます。アルゴリズムは、オブジェクトごとではなく、セルごとに外れ値をカウントします。特定のセルについて、セル内、セル内と最初のレイヤーを一緒にしたオブジェクトの数、およびセルと両方のレイヤーを一緒にしたオブジェクトの数を含む3つのカウントを累積します。