22

階層的クラスタリングに役立つアルゴリズムはありますか？Googleのmap-reduceには、kクラスタリングの例しかありません。階層的クラスタリングの場合、ノード間で作業をどのように分割できるかわかりません。私が見つけた他のリソースは次のとおりです。http：//issues.apache.org/jira/browse/MAHOUT-19 しかし、どのアルゴリズムが使用されているかは明らかではありません。

4

5 に答える 5

17

まず、階層をボトムアップとトップダウンのどちらで構築するかを決定する必要があります。

ボトムアップは、階層的凝集クラスタリングと呼ばれます。シンプルで十分に文書化されたアルゴリズムは次のとおりです：http：//nlp.stanford.edu/IR-book/html/htmledition/hierarchical-agglomerative-clustering-1.html。

ボトムアップアルゴリズムの配布は、各分散プロセスが適切なクラスターについて選択するためにデータセット全体を必要とするため、注意が必要です。また、同じレベルの複数のクラスターにデータポイントを追加しないように、現在のレベルのクラスターのリストも必要です。

トップダウン階層構造は、分割クラスタリングと呼ばれます。K-meansは、階層のノードを分割する方法を決定するための1つのオプションです。このホワイトペーパーでは、ノード分割のK-meansとPrincipal Direction Divisive Partitioning（PDDP）について説明します：http ：//scgroup.hpclab.ceid.upatras.gr/faculty/stratis/Papers/tm07book.pdf 。最終的には、各親ノードを比較的バランスの取れた子ノードに分割する必要があります。

トップダウンアプローチは配布が簡単です。最初のノード分割後、作成された各ノードを分散プロセスに送信して、再度分割することができます。各分散プロセスは、分割するデータセットのサブセットを認識するだけで済みます。親プロセスのみが完全なデータセットを認識します。

さらに、各分割は並行して実行できます。k-meansの2つの例：

于 2008-10-10T18:45:39.210 に答える
2

クラークオルソンは、階層的クラスタリングのためのいくつかの分散アルゴリズムをレビューします。

CFオルソン。「階層的クラスタリングのための並列アルゴリズム」。Parallel Computing、21：1313-1325、1995、doi：10.1016 / 0167-8191（95）00017-I。

パルナック他 アリが巣を分類する方法に触発されたアルゴリズムを説明します。

H. Van Dyke Parunak、Richard Rohwer、Theodore C. Belding、およびSven Brueckner：「動的分散型のいつでも階層的クラスタリング」。Proc。 第4回工学自己組織化システムに関する国際ワークショップ（ESOA）、2006、doi：10.1007 / 978-3-540-69868-5

于 2008-10-09T18:35:10.460 に答える
2

Olson (1995) による少し古いレビューである場合は、この非常に読みやすいレビューをチェックしてください。それ以来、ほとんどの論文はアクセスに料金が必要です。:-)

R を使用する場合は、別の R モジュールであるsnowを使用して並列処理を実現するpvclustを試すことをお勧めします。

于 2009-05-12T16:56:13.163 に答える
1

また、Newman と Girvan によるネットワーク内のコミュニティ構造の検索と評価も参照できます。ここでは、ネットワーク内のコミュニティを評価するためのアプローチ (およびこのアプローチに基づく一連のアルゴリズム) と、コミュニティの品質へのネットワーク分割の測定 (グラフのモジュール性) を提案しています。

于 2011-05-12T14:35:52.543 に答える
0

自己組織化マップ (Kohonen のニューラル ネットワーク法) で行われている作業の一部を見ることができます...ウィーン工科大学の研究者は、成長する階層マップ アルゴリズムの分散計算に関する作業を行いました。

これはクラスタリングの質問の端に少しあるので、役に立たないかもしれませんが、もっと近いものは考えられません;)

于 2008-09-17T16:28:22.023 に答える