1

ほとんどの質問は、類似性 (ピジョンホール) に基づいてノードをグループ化することに関するものですが、単純に近接性に基づいてノードをグループ化したいと思います。

ノードの大規模で高密度のコレクションがあります。数百万になる可能性があります。画面上である程度のスペースを占めるため、サイズがあると考えることができます。

私がやろうとしているのは、処理時間とコンテナーごとにより多くのノードを収集することの両方で、これらのノードを単一の包含ノードに効率的にグループ化することです。

私の現在の試みは遅すぎるか、機能しませんでしたが、すべて私が念頭に置いている同じ解決策に基づいています。ノードを取り、ノードをランダムに囲んでグループ化し、次に最も効果的なコンテナを選択します。

具体的にはどの言語でも構いませんが、これには PHP または JavaScript を使用します。

Edit

ノードがストリームインされることを忘れていたので、無制限のノードを受け入れる必要があり、それらをコンテナに入れ、新しいコンテナを作成したり、必要に応じて削除したりして、最大数百万のコンテナを処理する必要があります。それが一番理想でしょう。

4

1 に答える 1

1

この問題はクラスタリングと呼ばれます。ノードのセットと、m任意の 2 つのノード間の距離を計算する関数があります。ここで、各クラスター内のすべてのノード間のすべての距離の合計が最小になるようにクラスターを検索します。

これを行う簡単なアルゴリズムがいくつかあります。たとえば、 k-Meansandを検索します。k-Medoidこれら2つはあなたのアプローチに非常に似ています。より効率的なバージョンは、CLARANSアルゴリズム [NH94] です。私はあなたのための良い情報源を見つけられませんでしたが、ここに行きます：

(ドイツ語) クラスタリング全般に関するスクリプト。45 ページの疑似コードに CLARANS が含まれています 。

CLARANSを説明する英語スクリプト http://bib.dbvis.de/uploadedFiles/232.pdf

CLARANSに関する論文 http://www.comp.nus.edu.sg/~atung/publication/pakdd002.pdf

名前の「k」はクラスターの数です。これらの 3 つのアルゴリズムでは、アプリオリにクラスターの数を指定する必要があります。

別のアプローチについては、DBSCANアルゴリズムを参照してください。このアルゴリズムにはクラスターの数は必要ありませんが、ノードに関するその他の知識を提供する必要があります。ウィキペディアの記事はこれを非常によく説明しています。:-)

于 2012-04-10T03:25:35.017 に答える