2

階層的クラスタリングを使用して、2次元にフラット化された大量のデータセットを視覚化しようとしています。私がやりたいのは、クラスターを構成点の凸包としてレンダリングすることにより、階層内のさまざまな高さからデータを見ることができる視覚化を作成することです。この問題の最も難しい部分は、階層を上に移動するときにペアクラスターの凸包を効率的にマージできるアルゴリズムが必要なことです。O（n log n）時間で点の凸包を計算するためのアルゴリズムをたくさん見てきましたが、この場合、問題の下部構造を利用する方がはるかに効率的であるように見えますが、私は正確にはわかりません。

編集：

詳細については、データ構造は、クラスタリングの元のポイントで始まり、次のクラスターを形成するために結合されるポイント/クラスターを示す配列です。つまり、ツリー/ポインタ構造のようなものですが、1つの大きな配列に含まれています。重要な部分は、スーパークラスターの2つの構成クラスターが何であるかを確認するのは効率的ですが、クラスターに属するすべてのポイントのセットを取得するのは効率的ではないということです。したがって、合理的なアルゴリズムはすべてボトムアップで機能する必要があります。

つまり、ある場所で階層の真ん中にいて、事前に計算された階層で、クラスターAとBがマージされてクラスターCが生成されたとします。下から上に向かっていくので、すでに凸包を計算しました。クラスターAとBのポイントであるため、これらを組み合わせてクラスターCの凸包を作成する必要があります。クラスターAの凸包は、実際には単一のポイント、ペア、または完全なポリゴンである可能性があります。クラスターBについても同じことが言えます。したがって、これらをマージしてクラスターCの凸包を形成する方法はいくつかありますが、おそらくシングルトンとペア​​をポリゴンと同じように扱う賢いソリューションがあると思います。

最も明白な解決策は、クラスターAとBの凸包からの点の組み合わせを使用して凸包を計算することです。しかし、100kポイントの階層でこれを行う必要があるため、より効率的なものがあるかどうか疑問に思います。 AとBの凸包を組み合わせる方法。

編集2：

         /----5
    1---/    / \
   / \      / B 8
  2 A 3  C 6   /
   \ /      \ /
    4--------7

さて、私は自分の言いたいことのイラストをASCIIで表現しようとしました。クラスターAの凸包は1-2-3-4、Bの凸包は5-6-7-8、Cの凸包は1-2-4-7-8-5です。おそらく、クラスターAとBには船体の内側に追加のポイントが含まれていますが、これらは明らかにCの船体の一部になることはできないため、問題はクラスターAとBの船体を「スプライス」して形成する場所を決定するアルゴリズムです。ポイントの座標に基づくCの船体。これは、プロセス全体の帰納的ステップです。（最終的には、アルゴリズムが最上位のクラスターで終了するまで、CはクラスターDと組み合わされます。最上位のクラスターは、凸包としてすべての点の凸包を持ちます）。

4

2 に答える 2

3

私が知っている凸包マージアルゴリズムは少なくとも2つあります。Toussaintの回転キャリパー法（論文のセクション5）とPreparataとHongのブリッジングアルゴリズム（論文のセクション3を参照）です。これらのアルゴリズムは両方とも、h = h 1 + h 2で線形の時間を要します。ここで、 h1とh2は、それぞれ1番目と2番目の凸包の船体頂点の数です。

于 2012-10-21T11:21:38.707 に答える
2

新しいポイントを追加するときに凸包を「更新」できるようにするさまざまな方法があります。また、凸包とドロネー三角形分割のいくつかの方法は、すでに裏返しにうまく機能しており、これでうまく機能するはずです。s-hullアルゴリズムを見てください。

ただし、階層的クラスタリングについて話しているので、複雑さに関しては、凸包はおそらく最も懸念事項ではありません。

アルゴリズムは通常自然界にあるため、階層的クラスタリングは大規模なデータセットにうまくスケールアップしませんO(n^3)（実際に使用されている中で最も遅いクラスタリングアルゴリズムの1つになります）。したがって、クラスタリングのコストが高いことを考えると、凸包の数をさらに計算しても、それほど大きな違いはありません。おそらく、O(n log n)凸包アルゴリズムの高速でインクリメンタルな実装が必要です。

于 2012-10-19T21:52:30.053 に答える