4

k-means には、Lloyd のアルゴリズム、Elkan のアルゴリズムがあり、k-means の階層バージョンもあります。

これらすべてのアルゴリズムについて、Elkan のアルゴリズムが速度を向上させることができることがわかりました。しかし、私が知りたいのは、これらすべての k-means アルゴリズムの品質です。これらのアルゴリズムを実行するたびに、発見的および確率的な性質により、結果は異なります。さて、私の質問は、k-means のようなクラスタリング アルゴリズムに関して、これらすべての k-means アルゴリズム間で (より少ない歪みなどのように) より良い品質の結果を得たい場合、どのアルゴリズムが与えることができるかということです。あなたはより良い品質ですか?そのようなものを測定することは可能ですか?

4

4 に答える 4

4

より良い解決策は、通常、より良い (より低い)J(x,c)値を持つものです。ここで:

J(x,c) = 1/|x| * Sum(distance(x(i),c(centroid(i)))) for each i in [1,|x|]

場所:

  • xサンプルのリストです
  • |x|x(要素数)のサイズ
  • [1,|x|]1 から|x|(両端を含む)までのすべての数字
  • cクラスタの重心 (または平均) のリストです (つまり、kクラスタ |c| = k)
  • distance(a,b)(||ab|| と表記されることもあり、「点」a から「点」b までの距離です (ユークリッド 2D 空間ではsqrt((a.x-b.x)^2 + (a.y-b.y)^2))
  • centroid(i) - 最も近い重心/平均x(i)

このアプローチは、監視された手法への切り替えを必要とせず、完全に自動化できることに注意してください!

于 2012-12-13T08:40:32.377 に答える
1

2 つの月のデータセットの病的なケースはどうですか? 教師なし k-means はひどく失敗します。私が知っている高品質の方法は、相互情報量と組み合わせ最適化を使用した、より確率論的なアプローチを採用しています。基本的に、クラスタリングの問題を、2 つのクラスターの場合の完全なポイント セットの最適な [クラスター] サブセットを見つける問題としてキャストします。

関連する論文はここ(42 ページ) にあり、対応するMatlab コードはここにあります(2 つの月のケースをチェックしてください)。30 倍以上高速化された C++ の高性能実装に興味がある場合は、ここで HPSFOを見つけることができます。

于 2012-12-13T09:55:54.573 に答える
1

私が理解しているように、クラスタリングアルゴリズムを相互検証するには、ラベル付きのデータが必要です。

于 2012-12-13T07:39:23.473 に答える
0

品質を比較するには、ラベル付けされたデータセットを用意し、 NMIなどの基準で結果を測定する必要があります

于 2012-12-14T16:55:18.700 に答える