12

外れ値の検出に関していくつか質問があります。

  1. k-means を使用して外れ値を見つけることはできますか?これは良いアプローチですか?

  2. ユーザーからの入力を一切受け付けないクラスタリング アルゴリズムはありますか?

  3. 外れ値の検出に、サポート ベクター マシンやその他の教師あり学習アルゴリズムを使用できますか?

  4. 各アプローチの長所と短所は何ですか?

4

4 に答える 4

38

これは多くの教科書のトピックであり、おそらく別の質問で対処する方がよいかもしれないので、あなたのすべての質問についていくつかの手がかりを与えるために不可欠だと思うことに限定します.

  1. k-means アルゴリズムはその目的のために構築されていないという単純な理由から、多変量データセットの外れ値を見つけるために k-means を使用しません。平方 (したがって、分散の合計が固定されているため、クラスター間 SS が最大化されます) であり、外れ値は必ずしも独自のクラスターを定義するとは限りません。R で次の例を考えてみましょう。

    set.seed(123)
sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
                                      rnorm(n, mean[2],sd[2]))
# generate three clouds of points, well separated in the 2D plane
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
xy[1,] <- c(0,2)     # convert 1st obs. to an outlying value
km3 <- kmeans(xy, 3) # ask for three clusters
km4 <- kmeans(xy, 4) # ask for four clusters

    次の図からわかるように、範囲外の値はそのままでは復元されません。常に他のクラスターの 1 つに属します。

    ここに画像の説明を入力

    ただし、1 つの可能性は、次の論文で説明されているように、極値点 (ここではクラスターの重心から離れたベクトルとして定義) を反復的に削除する 2 段階のアプローチを使用することです。(ハウタマキら)。

    これは、遺伝学的研究で、ジェノタイピングエラーを示す個体、または兄弟/双子である個体 (または集団の下部構造を特定したい場合) を検出して除外するために行われていることと似ていますが、無関係な個体のみを保持したい場合; この場合、多次元スケーリング (PCA と同等で、最初の 2 つの軸の定数まで) を使用し、上位 10 または 20 軸のいずれかで 6 SD を超えるまたは下回る観測値を削除します (たとえば、人口を参照)。 Structure and Eigenanalysis、Patterson et al.、PLoS Genetics 2006 2(12))。

    一般的な代替方法は、次の論文で説明されているように、カイ 2 乗分布の予想される分位点に対して (QQ プロットで) プロットできる、順序付きのロバストなマハラノビス距離を使用することです。

    RG ギャレット (1989)。カイ二乗プロット: 多変量異常値認識のためのツール。ジャーナル オブ ジオケミカル エクスプロレーション32(1/3): 319-341。

    ( mvoutlier R パッケージで利用可能です。)

  2. ユーザー入力と呼ぶものによって異なります。あなたの質問は、アルゴリズムが距離行列または生データを自動的に処理し、最適な数のクラスターで停止できるかどうかと解釈します。この場合、任意の距離ベースのパーティショニング アルゴリズムでは、クラスター分析に利用可能な妥当性指標のいずれかを使用できます。良い概要が与えられています

    Handl, J.、Knowles, J.、および Kell, DB (2005)。ポストゲノムデータ解析における計算クラスター検証。 バイオインフォマティクス21(15): 3201-3212。

    Cross Validatedで説明しました。たとえば、クラスター番号の範囲 (k=1 から 20 など) に対して、データのさまざまなランダム サンプル (ブートストラップを使用) でアルゴリズムのいくつかのインスタンスを実行し、考慮された最適化された基準 (平均) に従って k を選択できます。シルエット幅、コフェネティック相関など); 完全に自動化できるため、ユーザー入力は必要ありません。

    密度 (クラスターは、オブジェクトが異常に一般的な領域として見なされます) または分布 (クラスターは、特定の確率分布に従うオブジェクトのセットです) に基づく、他の形式のクラスター化が存在します。たとえば、 Mclustで実装されているモデルベースのクラスタリングでは、さまざまな数のクラスターの分散共分散行列の形状の範囲にまたがることで、多変量​​データセット内のクラスターを識別し、最適なモデルを選択することができます。ビック基準。

  3. これは分類のホット トピックであり、特に誤分類された場合に異常値を検出するために SVM に焦点を当てた研究もあります。単純な Google クエリで多くのヒットが返されます。たとえば、Thongkam らによる乳がん生存率予測における外れ値検出のためのサポート ベクター マシンです。(コンピュータサイエンスの講義ノート2008 4977/2008 99-109; この記事には、アンサンブル法との比較が含まれています)。非常に基本的な考え方は、1 クラス SVM を使用して、多変量 (ガウス分布など) 分布を当てはめることで、データの主な構造をキャプチャすることです。境界上または境界のすぐ外側にあるオブジェクトは、潜在的な外れ値と見なされる可能性があります。(ある意味では、密度ベースのクラスタリングは、期待される分布が与えられた場合に外れ値が実際に何であるかを定義する方がより簡単であるのと同じようにうまく機能します。)

    教師なし、半教師あり、または教師あり学習の他のアプローチは、Google で簡単に見つけることができます。


    関連するトピックは異常検出で、これに関する多くの論文があります。

  4. それは本当に新しい（そしておそらくもっと焦点を絞った）質問に値します:-)

于 2011-05-25T09:58:28.547 に答える
3

1) k-means を使用して外れ値を見つけることはできますか?それは良いアプローチですか?

クラスターベースのアプローチは、クラスターを見つけるのに最適であり、副産物として外れ値を検出するために使用できます。クラスター化プロセスでは、外れ値がクラスターの中心の位置に影響を与える可能性があり、マイクロクラスターとして集約することさえあります。これらの特性により、クラスターベースのアプローチは複雑なデータベースには実行できません。

2) ユーザーからの入力を受け付けないクラスタリング アルゴリズムはありますか?

このトピックに関する貴重な知識を得ることができるかもしれません: Dirichlet Process Clustering

ディリクレに基づくクラスタリング アルゴリズムは、観測データの分布に応じてクラスタ数を適応的に決定できます。

3) サポート ベクター マシンまたはその他の教師あり学習アルゴリズムを外れ値検出に使用できますか?

教師あり学習アルゴリズムでは、分類器を構築するために十分なラベル付きトレーニング データが必要です。ただし、バランスのとれたトレーニング データセットが、侵入検知や医療診断などの現実の問題に常に利用できるとは限りません。Hawkins Outlier ("Identification of Outliers". Chapman and Hall, London, 1980) の定義によると、正常なデータの数は外れ値の数よりもはるかに多くなります。ほとんどの教師あり学習アルゴリズムは、上記の不均衡なデータセットに対して効率的な分類器を実現できません。

4) それぞれのアプローチの長所と短所は何ですか?

過去数十年にわたって、外れ値検出に関する研究は、グローバル計算からローカル分析まで変化し、外れ値の記述はバイナリ解釈から確率的表現まで変化しました。外れ値検出モデルの仮説によると、外れ値検出アルゴリズムは、統計ベースのアルゴリズム、クラスター ベースのアルゴリズム、最近傍ベースのアルゴリズム、および分類子ベースのアルゴリズムの 4 種類に分けることができます。外れ値の検出に関するいくつかの貴重な調査があります。

  • Hodge, V. および Austin, J. 「外れ値検出方法論の調査」、Journal of Artificial Intelligence Review、2004 年。

  • Chandola, V. および Banerjee, A. および Kumar, V. 「外れ値の検出: 調査」、ACM Computing Surveys、2007 年。

于 2012-04-18T09:26:13.277 に答える
2

  1. k-meansは、データセット内のノイズにかなり敏感です。事前に外れ値を削除すると最も効果的です。

  2. いいえ。パラメーターがないと主張するクラスター分析アルゴリズムは、通常、厳しく制限されており、多くの場合、非表示のパラメーターがあります。たとえば、一般的なパラメーターは距離関数です。柔軟なクラスター分析アルゴリズムは、少なくともカスタム距離関数を受け入れます。

  3. 1クラス分類器は、外れ値を検出するための一般的な機械学習アプローチです。ただし、監視ありアプローチは、_previously_unseen_オブジェクトの検出に常に適しているとは限りません。さらに、データにすでに外れ値が含まれている場合、過剰適合する可能性があります。

  4. すべてのアプローチには長所と短所があり、それがそれらが存在する理由です。実際の設定では、データと設定で何が機能するかを確認するために、それらのほとんどを試す必要があります。外れ値の検出が知識発見と呼ばれるのはそのためです-何か新しいものを発見したい場合は、探索する必要があります...

于 2011-11-26T10:51:25.917 に答える
1

ELKI データ マイニング フレームワークを参照してください。これはおそらく、外れ値検出データ マイニング アルゴリズムの最大のコレクションです。Java で実装されたオープン ソース ソフトウェアであり、20 以上の異常値検出アルゴリズムが含まれています。利用可能なアルゴリズムのリストを参照してください。

これらのアルゴリズムのほとんどはクラスタリングに基づいていないことに注意してください。多くのクラスタリング アルゴリズム (特に k-means) は、「何があっても」インスタンスをクラスタ化しようとします。一部のクラスタリング アルゴリズム (DBSCAN など) だけが、すべてのインスタンスがクラスタに属していない可能性がある場合を実際に考慮します。そのため、一部のアルゴリズムでは、外れ値は実際には適切なクラスタリングを妨げます!

于 2012-12-31T15:54:15.557 に答える