1

k-meansクラスタリングを実装するプログラムを書いています。

consider a simple input with 4 vertices a,b,c and d with following edge costs

[vertex1] [vertex2] [edge cost]
a b 1
a c 2
a d 3
b d 4
c d 5

次に、2つのクラスターを取得するまでプログラムを実行する必要があります。

私の疑問は、最小距離を計算する最初のステップで、それがa-> b（エッジコスト1）であるということです。ここで、abを単一のクラスターと見なす必要があります。その場合、cとdからのabの距離はどのくらいになりますか？

4

1 に答える 1

3

K-meansアルゴリズムは次のように機能します。

  1. 初期重心としてk点を選択します（したがって、K- *）。
  2. すべての頂点から選択したk重心までの距離を計算します。
  3. 各頂点を最も近い重心に割り当てます。
  4. 重心に属するすべての頂点間の平均を生成することにより、重心の位置を再計算します（したがって、k-means、k個の重心ごとに1つの平均計算）。
  5. ステップで、頂点が別の図心に割り当てられない場合、またはエラー条件が満たされるまで、ステップに移動し2て停止します。3

あなたの場合、無向グラフがあるので、エッジ距離を考慮して各頂点の座標を生成してから、アルゴリズムを適用する方がよいでしょう。

この初期プロセスを実行したくない場合は、頂点から他のすべての到達可能な頂点までの距離を計算できますが、反復ごとにこれを実行する必要があります。これは、非常に不必要なオーバーヘッドです。

無向グラフの場合：

[vertex1] [vertex2] [edge cost]
a b 1
a c 2
a d 3
b d 4
c d 5

距離の表は次のようになります。

     a    b    c    d
a    0    1    2    3
b    1    0   (1)   4
c    2   (1)   0    5
d    3    4    5    0

(1) - b to c = (b to a, a to c) = 3

これがテーブルである必要がある場合は、頂点ごとにグラフにダイクストラアルゴリズムを適用し、結果のテーブルを距離のテーブルと見なします。

テーブルの距離は最小になりますが、それを計算する他のポリシーがある場合は、計算方法を決めるのは完全にあなた次第です。

また、グラフが方向付けられている場合、この場合、行列はそのままでは対称ではないことにも注意してください。

于 2012-12-22T16:10:24.063 に答える