0

こんにちは、私はClusterを初めて使用します。どのアルゴリズムが自分のタスクに適しているかわかりません。私の仕事を説明させてください：

  1. 最初に、一連のポイントとそれらの間の距離が与えられます
  2. 距離に基づいてそれらをいくつかのクラスターにクラスター化します。
  3. いくつかの新しいポイントが追加され、すべてのポイント間の距離も与えられます。
  4. 繰り返し 2

たとえば、最初に次の行列があります

   | p1 | p2 | p3 |  
---|----|----|----|  
p1 |    |    |    |  
p2 | d1 |    |    |  
p3 | d2 | d3 |    |

クラスタリングの後、新しいポイントを追加し、距離も指定します。

   | p1 | p2 | p3 | p4 | 
---|----|----|----|----|  
p1 |    |    |    |    |  
p2 | d1 |    |    |    |  
p3 | d2 | d3 |    |    |  
p4 | d4 | d5 | d6 |    |

ここでの問題は速度です。クラスタリングはインクリメンタル クラスタであると予想されます。つまり、後のクラスタリングは前の結果を利用できます。ポイントを頻繁に追加し (見つかった場合)、毎回ポイントを再クラスター化するためです。クラスター自体が O(n) であっても、クラスターの合計時間は O(n^2) になります。

なにか提案を？

ありがとう

4

1 に答える 1

2

1 つのオプションは、クラスターの数を固定することです (たとえば、K 個のクラスターがあるとします)。新しいポイントを追加するときは常に、重心 (クラスター内のポイントの座標の平均) が追加したポイントに最も近いクラスターに追加します。スペース内のポイント数が 2 の累乗 (1、2、4、8、16、32 ...) になるたびに完全に再クラスター化しても、再クラスター化の償却コストは O(n) のままです。

于 2011-04-07T04:58:20.020 に答える