機械学習: 密度ベースの外れ値検出アルゴリズム

外れ値検出 (異常検出とも呼ばれる) は、機械学習において、予想とは大きく異なる動作をするデータ オブジェクトを見つけるプロセスです。これらのオブジェクトは外れ値または異常と呼ばれます。

最も興味深い物体は、普通の物体とは明らかに異なる物体です。外れ値は、残りのデータと同じメカニズムによって生成されるわけではありません。

異常検出は、次のような多くのアプリケーションで重要です。

• 金融データ詐欺
• 通信ネットワークへの侵入
• フェイクニュースと誤情報
• 医療分析
• 産業被害検出
• セキュリティと監視
• 等

外れ値検出とクラスター分析は、非常に関連性の高い 2 つのタスクです。クラスタリングは機械学習データセット内の多数派パターンを見つけ、それに応じてデータを整理します。一方、外れ値検出は多数派パターンから大きく異なる異常を検出しようとします。

この記事では、外れ値検出の基本的な方法を紹介し、近接性に基づくアルゴリズム手法のクラスに焦点を当てます。 LOF アルゴリズムのコード実装も提供します。

[[243914]]

外れ値とノイズの多いデータ

まず、機械学習では、外れ値とノイズの多いデータを区別する必要があります。

外れ値検出を適用するときはノイズを除去する必要があります。正常なオブジェクトが歪んだり、正常なオブジェクトと外れ値の区別が曖昧になったりする可能性があります。外れ値を隠し、外れ値検出の有効性を低下させる可能性があります。たとえば、ユーザーが過去に頻繁に購入していたより高価なランチの購入を検討している場合、この動作は「ランダムエラー」や「差異」などの「ノイズトランザクション」と見なされる必要があります。

外れ値の種類

一般に、外れ値は、グローバル外れ値、コンテキスト (または条件) 外れ値、集合外れ値の 3 つのカテゴリに分類できます。

• グローバル外れ値 - データセットの残りの部分から大きく外れたオブジェクト
• コンテキスト外れ値 - 選択されたコンテキストに基づいて大幅に逸脱するオブジェクト。たとえば、28⁰C はモスクワの冬では外れ値ですが、別の状況では外れ値ではありません。また、28⁰C はモスクワの夏では外れ値ではありません。
• アンサンブル外れ値 - 単一のデータ オブジェクトが外れ値ではない場合でも、データ オブジェクトのサブセットは機械学習データセット全体から大幅に逸脱する可能性があります。たとえば、短期間に少人数の当事者が同じ株を大量に取引した場合、それは市場操作の証拠とみなされる可能性があります。

外れ値を集計する

多くの場合、データセットには異なるタイプの外れ値が含まれることがあり、同時に複数のタイプの外れ値に属することもあります。

外れ値検出方法

文献で取り上げられ、実際に使用されている外れ値検出方法は数多くあります。まず、外れ値検出方法は、分析に使用されるデータ サンプルが、外れ値検出モデルの構築に使用できるドメイン専門家によって提供されたラベルとともに提供されるかどうかに基づいています。第二に、方法は、正常なオブジェクトと外れ値に関する仮定に基づいてグループに分けることができます。

専門家がラベル付けした正常オブジェクトや異常オブジェクトの例が利用できる場合は、それらを使用して外れ値検出モデルを構築できます。使用される方法は、教師あり学習法、半教師あり学習法、教師なし学習法に分けられます。

教師あり手法

外れ値検出を分類問題としてモデル化します。ドメインの専門家によってチェックされたサンプルは、トレーニングとテストに使用されます。

チャレンジ：

• 階級の不均衡。つまり、外れ値の数は、通常、正常なオブジェクトの数よりもはるかに少なくなります。オーバーサンプリングなど、不均衡なクラスを処理するための方法を使用できます。
• できるだけ多くの外れ値を捕捉する。つまり、再現率は精度よりも重要だ（つまり、通常のオブジェクトを外れ値として誤って分類しない）。

教師なし手法

一部のアプリケーション シナリオでは、正常または異常としてマークされたオブジェクトは使用できません。したがって、教師なし学習方法を使用する必要があります。教師なし外れ値検出法では、通常のオブジェクトはある程度「クラスター化」されているという暗黙の仮定が立てられます。言い換えれば、教師なし外れ値検出方法では、外れ値よりも正常なオブジェクトの方がパターンに従う頻度が高いと予想されます。

チャレンジ：

• 通常のオブジェクトは強いパターンを共有しないかもしれませんが、コレクションの外れ値は小さな領域で高い類似性を持つ可能性があります。
• 通常のアクティビティが多様で、高品質のクラスターに該当しない場合、教師なし手法では偽陽性率が高くなり、実際の外れ値の多くが検出されない可能性があります。

最近の教師なし手法では、クラスターを明示的に検出せずに外れ値に直接対処するスマートなアイデアが開発されています。

半教師あり学習法

多くのアプリケーションでは、ラベル付けされた例をいくつか取得することは可能ですが、そのようなラベル付けされた例の数は通常は少数です。利用可能なタグ付きプレーンオブジェクトがある場合:

• ラベル付けされた例と近くのラベル付けされていないオブジェクトを使用して、一般的なオブジェクトのモデルをトレーニングします。
• 共通オブジェクトモデルに適合しないオブジェクトは外れ値として検出されます
• ラベル付けされた外れ値が少数しか利用できない場合、ラベル付けされた外れ値の数が少なすぎると、可能性のある外れ値を十分にカバーできない可能性があります。

統計的手法

統計的手法（モデルベース手法とも呼ばれる）では、通常のデータが何らかの統計モデル（確率モデル）に従うと想定します。アイデアは、特定のデータセットに適合する生成モデルを学習し、モデルの低確率領域内のオブジェクトを外れ値として識別することです。

パラメータメソッド

パラメトリック アプローチでは、正規データ オブジェクトがパラメーター θ を持つパラメトリック分布によって生成されると想定します。パラメトリック分布の確率密度関数 f(x, θ) は、分布を通じてオブジェクト x を生成する確率を与えます。値が小さいほど、x が外れ値である可能性が高くなります。

通常のオブジェクトはランダム モデルの高確率領域に表示され、低確率領域のオブジェクトは外れ値になります。

統計的手法の妥当性は、分布に関する仮定に大きく依存します。

たとえば、正規分布を持つ単変量データを考えてみましょう。外れ値を検出するには、最大尤度法を使用します。

パラメータ μ と σ を推定するための最大尤度法

μとσ²の導関数をとり、その結果得られる一階条件の系を解くと、次の最大尤度推定値が得られる。

μとσ²の最大尤度推定

Python の例を見てみましょう。

 numpyをnpとしてインポートする 
平均温度= np .array([24.0, 28.9, 28.9, 29.0, 29.1, 29.1, 29.2, 29.2, 29.3, 29.4])  平均= avg_temp.mean () 
 
 std =平均温度.std ()  
シグマ=標準偏差^2  
印刷 (平均、標準偏差、シグマ) //28.61 1.54431214461 2.3849

最も外れた値は 24⁰ で、平均値 4.61 から大きく離れています。正規分布を仮定すると、μ +/- 3σ 領域にデータの 97% が含まれることがわかります。 4.61/1.54>3 なので、24⁰ は外れ値であると考えられます。

また、グリブス検定と呼ばれる別の統計手法を使用して、Z スコアを計算することもできます。

s - 標準偏差

しかし、属性が 1 つだけのデータを使用することはほとんどありません。 2 つ以上の属性を含むデータは多変量データと呼ばれます。これらの方法の中心的な考え方は、多変量データを単変量外れ値検出問題に変換することです。

人気のある方法の 1 つは、² 統計です。

Oi - i 番目の次元における O の値。 Ei - すべてのオブジェクトにわたる i 番目の次元の平均、n 次元。

χ²- が大きい場合、オブジェクトは外れ値です。

パラメトリック モデルの主な欠点は、多くの場合、データの分布が不明な場合があることです。

たとえば、2 つの大きなセットがある場合、正規分布に関する仮定はうまく当てはまりません。

代わりに、正規データオブジェクトは複数の正規分布Θ(μ1,σ1)とΘ(μ2,σ2)によって生成されると仮定し、データセット内の各オブジェクトoについて、分布の混合によって生成される確率を計算します。

P(o|Θ1,Θ2)=fΘ1(o)+fΘ2(o) である。

ここでfΘ1(o)はΘ1とΘ2の確率密度関数です。パラメータ μ と σ を学習するには、EM アルゴリズムを使用できます。

ノンパラメトリック法

外れ値検出のためのノンパラメトリック手法では、事前に想定されるのではなく、入力データから「正常データ」モデルが学習されます。ノンパラメトリック法では、一般的にデータに関する仮定が少なくなるため、より多くのシナリオに適用できます。例として、ヒストグラムを使用できます。

最も単純なアプローチでは、オブジェクトが 1 つのヒストグラム ビンで失敗した場合、そのオブジェクトは正常であると見なされます。短所 - ビンのサイズを選択するのが難しい。

近接性に基づくアルゴリズム

特徴空間内のオブジェクトのセットが与えられた場合、距離メトリックを使用してオブジェクト間の類似性を定量化できます。直感的には、他のオブジェクトから遠く離れたオブジェクトは外れ値と見なすことができます。近接ベースの方法では、外れ値オブジェクトとその最も近い隣接オブジェクトとの近接性が、データセット内の他のほとんどのオブジェクトとの近接性とは大幅に異なると想定されます。

近接ベースのアルゴリズムは、距離ベース（オブジェクトに十分なポイントがない場合、オブジェクトは外れ値になります）と密度ベースの方法（オブジェクトの密度が近隣のオブジェクトよりも相対的に大幅に低い場合、オブジェクトは外れ値になります）に分けられます。

密度ベース

距離ベースの外れ値検出方法は、指定された半径によって定義されるオブジェクトの近傍を参照します。オブジェクトの近傍に十分な数のポイントがない場合、そのオブジェクトは外れ値と見なされます。

しきい値の距離は、オブジェクトの適切な近傍として定義できます。各オブジェクトについて、そのオブジェクトの適切な数の近隣オブジェクトを見つけることができます。

r (r>0) を距離閾値、π (0<π<1) をスコア閾値とします。オブジェクトoはDB(r,π)である

DIST - 距離測定

これにはO(n²)の時間がかかります。

距離ベースの外れ値をマイニングするためのアルゴリズム:

• インデックスベースのアルゴリズム
• ネストループアルゴリズム
• ユニットベースのアルゴリズム

密度ベースの方法

密度ベースの外れ値検出方法では、オブジェクトの密度とその隣接オブジェクトの密度を調べます。ここで、あるオブジェクトの密度が隣接するオブジェクトの密度に比べて大幅に低い場合、そのオブジェクトは外れ値となります。

現実世界のデータセットの多くはより複雑な構造を示し、オブジェクトはグローバルなデータ分布ではなく、ローカルな近隣オブジェクトに対する外れ値として見られる場合があります。

上記の例を考えてみましょう。距離ベースの方法では o3 を検出できますが、o1 と o2 の場合はそれほど明白ではありません。

密度の背後にある考え方は、物体の周囲の密度をその近傍の周囲の密度と比較する必要があるということです。密度ベースの外れ値検出方法の基本的な前提は、外れ値でないオブジェクトの周囲の密度は隣接するオブジェクトの周囲の密度と類似しているが、外れ値の周囲の密度は隣接するオブジェクトの周囲の密度とは大きく異なるというものです。

dist_k(o) – オブジェクト o とその k 個の最も近い隣接オブジェクト間の距離。 o の k 距離近傍には、o までの距離が o の k 番目の距離 dist_k(o) より大きくないすべての近傍が含まれます。

Nk(o) から o までの平均距離を、o の局所密度の尺度として使用できます。o に非常に近い近傍点 o' があり、dist(o,o') が非常に小さい場合、距離尺度の統計的変動は非常に大きくなる可能性があります。これを克服するには、スムージング効果を追加して、次の到達可能距離測定に切り替えることができます。

k は、スムージング効果を制御するユーザー指定のパラメーターです。基本的に、k はオブジェクトのローカル密度を決定するために検査する最小の近傍を指定します。到達距離は非対称です。

オブジェクトoの局所到達可能性密度は

オブジェクトのローカル到達可能性密度を計算し、それを近隣の比較可能な密度と比較して、オブジェクトが外れ値と見なされる範囲を定量化します。

ローカル外れ値係数は、o のローカル到達可能性密度と o の k 近傍の比率の平均です。 o のローカル到達可能性密度が低いほど、k の最近傍のローカル到達可能性密度が高くなり、LOF 値が高くなります。これは、ローカル密度が比較的低い場合や、ローカル密度が比較的低い場合に、ローカル外れ値を捕捉するために発生します。その k 個の最も近い近傍。

LOFアルゴリズム

data.csv のクリックストリーム イベント頻度パターンに基づいて、次の初期設定で LOF アルゴリズムを適用し、各ポイントの LOF を計算します。

• k = 2 でマンハッタン距離を使用します。
• k = 3 でユークリッド距離を使用します。

その結果、5つの外れ値とそのLOF_k(o)が見つかります。

データはgithubリポジトリ（https://github.com/zkid18/Machine-Learning-Algorithms）からダウンロードできます。

Python 実装は次のとおりです。

 pandasをpdとしてインポートする 
 Seaborn を SNS としてインポートする 
 scipy.spatial.distance から pdist、squareform をインポートします。  
 data_input = pd .read_csv('../../data/clikstream_data.csv')  
 #Reachdist 関数 
 def reachdist(distance_df, 観測値, インデックス):  
 distance_df[観測][インデックス]を返す 
 #LOF アルゴリズムのゼロからの実装 
 LOF_algorithm(data_input, distance_metric = "cityblock" , p = 5 )を定義します。  
距離= pdist (data_input.values、メトリック= distance_metric )  
 dist_matrix = squareform (距離)  
距離_df = pd.DataFrame (dist_matrix)  
 distance_metric == "cityblock"の場合はk = 2 、それ以外の場合は 3  
観測値= distance_df.columns  
 lrd_dict = {}  
 n_dist_index = {}  
到達配列辞書= {}  
 観察のための観察:  
 dist = distance_df [観測値].nsmallest(k+1).iloc[k]  
インデックス= distance_df [distance_df[観測] < = dist].drop(観測).index  
 n_dist_index[観測] = インデックス 
到達距離配列= []  
 インデックス内のインデックスの場合:  
 #関数reachdist(observation, index)を作成する 
 dist_between_observation_and_index = reachdist (距離自由度、観測値、インデックス)  
 dist_index = distance_df [インデックス].nsmallest(k+1).iloc[k]  
到達距離=最大(距離インデックス、観測値とインデックス間の距離)  
 到達距離配列に追加(到達距離)  
 lrd_observation = len (インデックス)/sum(reach_dist_array)  
 reach_array_dict[観測] = reach_dist_array  
 lrd_dict[観測] = lrd_観測 
 #LOFを計算する 
 LOF_dict = {}  
 観察のための観察:  
 lrd_array = []  
 n_dist_index[観測値]のインデックス:  
 lrd_array.append(lrd_dict[インデックス])  
 LOF =合計(lrd_array)*合計(reach_array_dict[観測値])/np.square(len(n_dist_index[観測値]))  
 LOF_dict[観測] = LOF  
 ソートされた値を返す(LOF_dict.items(), key = lambda x: x[1], reverse = True )[:p]  
 LOF_アルゴリズム(データ入力、 p = 5 )  
 # [(19, 11.07),  
 # (5​​25, 8.8672286617492091)、  
 # (66, 5.0267857142857144)、  
 # (638, 4.3347272196829723)、  
 # (177, 3.6292633292633294)]  
 LOF_アルゴリズム(データ入力、 p = 5 、距離メトリック= 'ユークリッド' )  
 # [(638, 3.0800716645705695),  
 # (5​​25, 3.0103162562616288)、  
 # (19, 2.8402916620868903)、  
 # (66, 2.8014102661691211)、  
 # (65, 2.6456528412196416)]