6

2Dポイントのセットでkクラスを見つけることを任務とするクラスタリングアルゴリズムを開発しようとしていました（kを入力として）。Kruskalアルゴリズムをわずかに変更して、1つではなくkスパニングツリーを見つけます。

k = 7 の場合、95.5% という結果になりました。比較は以下のリンクで見ることができます。

問題：

セットには、アルゴリズムによって簡単に分類できる 5 つの明確な間隔のクラスターがありますが、k > 5 の場合、結果はかなり期待外れです。私は自分のアルゴリズムが正しいと信じており、おそらくデータはクルスカルのアプローチにとって特に悪いものです. Kruskal のような単一リンケージ凝集クラスタリングは、クラスター品質の評価をポイントのペア間の単一の類似性に還元するため、一部の問題でパフォーマンスが低下することが知られています。

アルゴリズムの考え方は非常に単純です。

  • エッジの重みがペア間のユークリッド距離である、データ セットを使用して完全なグラフを作成します。
  • エッジ リストを重みで並べ替えます。
  • エッジごとに (順番に)、サイクルを形成しない場合はスパニング フォレストに追加します。すべてのエッジがトラバースされたとき、または残りのフォレストに k 個の木があるときに停止します。

ここに画像の説明を入力

結論: アルゴリズムがそのように失敗するのはなぜですか? クラスカルのせい？もしそうなら、なぜ正確に？クラスカルを放棄せずに結果を改善するための提案はありますか?

(1): Gionis、A.、H. Mannila、および P. Tsaparas、クラスタリング集約。ACM Transactions on Knowledge Discovery from Data(TKDD),2007.1(1):p.1-30.

4

3 に答える 3

5

これはシングルリンク効果として知られています。

Kruskal は、単一リンケージ クラスタリングを計算するやや賢い方法のようです。「階層的クラスタリング」の単純なアプローチはO(n^3)であり、クルスカルのアプローチは、エッジO(n^2 log n)をソートする必要があるためです。n^2

SLINK は、O(n^2)実行時およびO(n)メモリ内で単一リンケージ クラスタリングを実行できることに注意してください。

ELKIなどにデータセットをロードしてみて、結果をシングルリンククラスタリングと比較してください。

より良い結果を得るには、他のリンケージ (通常は実行時) またはDBSCANO(n^3)などの密度ベースのクラスタリング(インデックスなしおよびインデックスあり) を試してください。このおもちゃのデータセットでは、うまくいくはずです。O(n^2)O(n log n)epsilon=2minPts=5

于 2013-12-06T09:36:14.410 に答える
0

マンハッタン距離を試すこともできますが、より良くするために、従来の線と円の検出アルゴリズムを試すことができます。

于 2013-12-05T05:37:59.303 に答える