5

私は LOF の独自の実装を作成し、結果を ELKI および RapidMiner の実装と比較しようとしていますが、3 つすべてで異なる結果が得られます! その理由を突き止めようとしています。

私の参照データセットは 1 次元の 102 個の実数値で、多くの重複があります。以下に投稿してみます。

まず、RapidMiner の実装です。LOF スコアは、ELKI と私の結果とは大きく異なります。多くは無限大の LOF で戻ってきます。この実装は正しいと検証されていますか?

私の結果は ELKI に似ていますが、まったく同じ LOF 値が得られません。ELKI ソース コードのコメントをざっと見てみると、これは k 近傍の計算方法の違いによるものと思われます。

LOF 論文では、MinPts パラメーター (別の場所では k と呼ばれる) が最小数を指定します。k-近傍に含まれる点の数。ELKI の実装では、k 距離または k 個別距離内のすべてのポイントではなく、k 近傍を正確に k ポイントとして定義していると思います。ELKI が k 近傍をどのように構築するかを正確に確認できる人はいますか? また、ポイント自体を独自の近隣に含めることができるプライベート変数もありますが、デフォルトではそれを含めないようです。

検証目的で LOF スコアが添付されている公開参照データセットを知っている人はいますか?

--- 詳細は後述 ---

参考：ELKIのソースコードはこちら：

http://elki.dbs.ifi.lmu.de/browser/elki/trunk/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LOF.java

RapidMiner のソース コードは次のとおりです。

http://code.google.com/p/rapidminer-anomalydetection/source/browse/trunk/src/de/dfki/madm/anomalydetection/evaluator/nearest_neighbor_based/LOFEvaluator.java

ここに私のテストデータセットがあります:

4.32323 5.12595 5.12595 5.12595 5.12595 5.7457 5.7457 5.7457 5.7457 5.7457 5.7457 5.97766 5.97766 6.07352 6.07352 6.12015 6.12015 6.12015 6.44797 6.44797 6.48131 6.48131 6.48131 6.48131 6.48131 6.48131 6.6333 6.6333 6.6333 6.70872 6.70872 6.70872 6.70872 6.70872 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 6.77579 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.03654 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.10361 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 7.15651 8.22598 8.22598 8.22598 8.22598 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538 8.5538

たとえば、最初の数値 (4.32323) に対して次の LOF スコアを取得します。

  • RapidMiner: 無限大 (MinPts の下限/上限を 10,100 に設定)
  • ELKI: 2.6774 (k = 10、distfunction/reachdistfunction をデフォルトに設定)
  • 私の実装: 1.9531

私の実装が何をしているかについての詳細:

  1. MinPts は 10 なので、ポイントの 10 個の異なる隣接点を見つけています。したがって、4.32323 の近傍は、実際には 5.12595 から 6.77579 までの 48 ポイントです。
  2. それは私に 2.45256 の k-distinct 距離を与えます
  3. 最初のネイバーの到達可能距離を 1.58277 として計算しています
  4. サンプルの LRD を 1/(99.9103/48) として計算しています。
  5. 48 個のネイバーすべての lrd(o)/lrd(p) の合計は 93.748939 です。
  6. 1.9531 の LOF を取得するには、48 で割ります
4

2 に答える 2

6

私は実際、それらが異なっていても驚かない。Weka の LOF の実装を追加することもできます。おそらく、さらに別の答えが得られるでしょう。

方程式に追加する必要があるもう 1 つの違いがあります。私の知る限り、rapidminer の実装では、同じ座標を持つポイントがマージされます。しかし、最近傍を計算するときにこれらの重みを考慮に入れるのを忘れていたのかもしれません!

従来のデータベース コンテキストでは、重複する座標を 1 つの観測にマージしません。それらはまだ有効なデータベース レコードであり、完全なレコードとしてカウントする必要があります。

それらのいずれかが、データ セットの再スケーリングなどの自動データ前処理を実行するかどうかはわかりません。

ELKI の実装は、私たちが教育に使用する多くの教科書の例に対して検証されています。

ただし、アルゴリズムには 100% 修正されていないコーナー ケースがあるため、アルゴリズムの「文字通りの」実装であっても違いの余地があります。すでに次の 3 つに遭遇しています。

  1. 重複ポイントの処理方法: A) 集約、B) ドロップ、C) 異なると見なす

    データ マイニングの観点からは、C は正しく、A (正しく実装されている場合) は不要な距離計算を節約できる最適化です。B は一般的な数学的ビューですが、データベース コンテキストではあまり意味がありません。「John Doe」が 2 人いる場合、それらは同一人物ですか?

  2. k 最近隣と k 距離の定義。

    k 距離の通常の定義は、少なくとも k 個の観測値が含まれる最小距離です。クエリ ポイントを除外すると、開始点から 5.7457 までの間隔が得られます。半径 5.7457 ～ 4.32323 内に 10 個の他の観測値があります。

    k 個の最近傍点は、通常、この距離内の任意の点として定義されます。この距離は、k より大きい場合があります。ただし、すべての追加オブジェクトは、k 番目と同じ距離でなければなりません。Rapidminer は正確に kを使用しているように見えますが、これは LOF の公開と一致していません (LOF の公開の定義 4 を参照してください!)

    それは実際には k 個の最近傍 (同点を含むが、それ以外は k 個以下のオブジェクト) であり、k 番目の最小の個別のdistanceではありません。「別格」ってどこから出てきたの？

    LOF 出版物の定義 3 と 4 は、LOF が使用する kNN セットについて非常に明確です。

    したがって、48 個のオブジェクトの近傍は正しくありません。

  3. minPts を超える重複ポイントがある場合の対処方法 (リテラル実装ではゼロによる除算が生成されますが、明らかな理由から、ポイントには 1.0 の LOF を指定する必要があります)

    これはおそらく、Rapidminer に起こっていることです。

そして、到達可能距離があります。これは数学的な距離ではないため、非常に注意が必要です。アシンメトリーです。

2番目の観測からの最初の観測の到達可能性は、たまたま2番目のk距離であり、簡単に見ると（再確認しませんでした）reach-dist(x[0], x[1]) = max(5.97766 - 5.12595, 5.12595 - 4.32323) = 0.80272

LOF を計算する方法の段階的なデモンストレーションについては、外れ値検出に関する私の広範なチュートリアル スライドを参照してください。私が知る限り、これは文字通りの LOF です。すべてのコーナー ケースに触れているわけではありませんが、LOF アルゴリズムの設計の動機となり、非常に網羅的です。

于 2013-02-20T19:51:58.743 に答える