5

大規模な（ギガバイト）データセットをクラスター化しようとしています。クラスター化するには、すべてのポイントから1つおきのポイントまでの距離が必要なので、N ^ 2サイズの距離行列になります。これは、私のデータセットの場合、エクサバイトのオーダーになります。もちろん、MatlabのPdistは即座に爆発します;）

最初に大きなデータのサブセットをクラスター化し、次に同様のクラスターをマージする方法はありますか？

これが役立つかどうかはわかりませんが、データは固定長のバイナリ文字列であるため、ハミング距離（Distance = string1 XOR string2）を使用して距離を計算しています。

4

3 に答える 3

1

Tabei et al., Single vs Multiple Sorting in All Pairs Similarity Searchのナイス メソッドの簡略化されたバージョンで、Hammingdist 1 のペアについては、次のようになります。

  • 最初の 32 ビットですべてのビット文字列を並べ替える
  • 最初の 32 ビットがすべて同じである文字列のブロックを見てください。これらのブロックは比較的小さくなります
  • Hammingdist( 左 32 ) 0 + Hammingdist( 残り ) <= 1 について、これらのブロックのそれぞれを pdist します。

これは、ハミングディスト ( 左 32 ) 1 + ハミングディスト ( 残り ) 0 を持つ近くのペアのたとえば 32/128 の割合を逃します。これらが本当に必要な場合は、「最初の 32」->「最後の 32」で上記を繰り返します。

メソッドは拡張できます。たとえば、4 つの 32 ビット ワードで Hammingdist <= 2 を取ります。不一致は 2000 0200 0020 0002 1100 1010 1001 0110 0101 0011 のいずれかのように分割する必要があるため、2 つの単語は 0 でなければならず、同じように並べ替えます。

(ちなみに、sketchsort-0.0.7.ta​​r は 99% src/boost/, build/, .svn/ です。)

于 2011-04-08T14:32:19.037 に答える
0

LMW-treeプロジェクトの EM-tree および K-tree アルゴリズムは、これほど大きな問題をクラスター化できます。最新の結果では、7 億 3,300 万の Web ページを 600,000 のクラスターにクラスター化しています。データセットが反復ごとにディスクからストリーミングされる EM ツリーのストリーミング バリアントもあります。

さらに、これらのアルゴリズムは、すべてのクラスター代表とデータ ポイントがビット文字列であるビット文字列を直接クラスター化することができ、使用される類似度はハミング距離です。これにより、検出された各クラスター内のハミング距離が最小化されます。

于 2015-05-17T05:17:22.400 に答える
0

まずは並べてみてはどうでしょうか。たぶん、変更されたマージソートのようなものですか？通常の並べ替えを実行するためにメモリに収まるデータセットのチャンクから始めることができます。

並べ替えられたデータを取得したら、クラスタリングを繰り返し行うことができます。おそらく、N-1 ポイントのローリング セントロイドを保持し、読み込まれている N 番目のポイントと比較します。その後、クラスター距離のしきい値に応じて、現在のクラスターにプールするか、新しいクラスターを開始することができます。

于 2011-03-29T17:56:21.323 に答える