0

このスキームに従って、インクリメンタル クラスタリング アルゴリズムを使用しています。

Let x a new data-point, and c the centroid that is closest from x
if( distance(x, c) > threshold )
   x becomes a new cluster center (i.e. a new centroid)
else assign x to c (i.e. update the centroid by taking x)

x から最も近い中心の検索を高速化するために、新しいデータポイントが考慮されるたびに段階的に更新できる中心の階層構造 (ツリーを使用) が必要です。

ツリーの各内部ノードは、そのノードの下の重心の平均として表されます。特定の重心を更新する場合 (新しいデータポイントがこの重心に割り当てられたため)、この重心の上にあるすべてのノードを再構築する必要があります。

したがって、アルゴリズムは次のようになります。

Let x a new data-point
c = searchClosestCenter(x, tree) // return the centroid closest to x
if( distance(x, c) > threshold )
   x becomes a new cluster center (i.e. a new centroid)
   AddCenterToTree(x, tree)
else
   assign x to c (i.e. update the centroid by taking x)
   UpdateTree(c) // update all nodes that are  on top of c

この場合、この関数はどのように定義できますか? それに対するより良い解決策はありますか？

4

1 に答える 1

1

R-treeを使用するのはどうですか? 最小の境界四角形を使用して、リーフ ページのオブジェクトを要約します。kd ツリーを使用することもできますが、バランスが崩れる可能性があるため、時間の経過とともに (再構築しない限り) パフォーマンスが低下します。

とにかく、R ツリーは、このタイプのデータで非常に人気のあるデータ構造です。Oracle、SQLite、Postgres、MySQL などで使用されています。

R* ツリーは、R ツリーの改良版です。それらは、はるかに優れた分割戦略、挿入へのわずかな変更、およびツリーのバランスを改善するための分割の代替としての再挿入を備えています。検索は同一です。

最適化として、次の最適化で R ツリーを拡張できます。古いエントリを削除して新しいエントリを挿入する代わりに、「置換」操作を追加することもできます。最初に、新しい平均が挿入される場所を確認します。以前と同じページである場合は、ページ内で置き換えて、最終的に境界ボックスを更新します。

于 2012-09-24T07:55:19.950 に答える