3

kmeans を使用してビッグ データ マトリックス (500 万 X 512) を 5000 のセンターにクラスター化したいと考えています。このマトリックスで記憶を吹き飛ばさないように、R を使用しています。

txt マトリックスを xdf に変換してからクラスター化するために、次のコードを作成しました。

rxTextToXdf(inFile = inFile, outFile = outFile)
vars <- rxGetInfo(outFile,getVarInfo=TRUE)
myformula <- as.formula(paste("~", paste(names(vars$varInfo), collapse = "+"), sep=""))

clust <- rxKmeans(formula = myformula, data = outFile,numClusters = 5000, algorithm =     "lloyd", overwrite = TRUE)
write.table(clust$centers, file = centersFiletxt, sep=",", row.names=FALSE,    col.names=FALSE)

しかし、それは現在1週間実行されています。それをより速くする方法はありますか？

4

3 に答える 3

9

  1. 本当に 5000 個のクラスターが必要ですか? k-means のパフォーマンスはクラスターの数に比例するため、クラスターの数が非常に多いとかなりの負担になります。クラスターの数を減らすことができれば、それは大いに役立ちます。

  2. 512次元すべてが必要ですか? これらの寸法の一部を削除または組み合わせることができれば、それも役立つ可能性があります。データに対して PCA を実行してみましたか? たぶん、上位 10 個のコンポーネントなどで k-means を実行してみてください。

  3. k-means である必要がありますか? 階層クラスタリングや自己組織化マップなどの他のアルゴリズムを試して、それらがより高速に実行されないかどうかを確認できます。データのサンプル (おそらく N=100K) を取得し、その上でいくつかのクラスタリング アルゴリズムの速度をテストすることをお勧めします。

  4. Revolution R は、ベース R よりも確実に高速であると考えられていますが、それでも R です。

  5. メモリ使用量を追跡していますか? 率直に言って、あなたはすでにあなたの記憶を吹き飛ばしているのではないかと思います. 1 回の反復で、500 万点のそれぞれと512 次元の 5000 個の重心のそれぞれとの間の距離行列を作成するようにコンピューターに要求しています。これは、距離行列が 5M x 5K x 512、つまり 1.28e13 レコードになることを意味します (これにデータ型のビット エンコーディングを掛けます)。6.9e10 ビットの RAM しかありません。Revolution R が非常に卑劣なことをしていない限り、RAM を大量に購入しない限り、ハードウェアでこの問題に対処する可能性はまったくありません。64 GB であっても、1 回の k-means 反復にはまだ数桁足りません。

  6. あなたは、メモリ使用量を浪費しないために R を使用していると言っています。Revolution R は異なるかもしれませんが、従来の R はメモリ内ですべてを行います。上で説明したように、この問題は従来のハードウェアでは扱いにくいでしょう。Amazon EC2 のようなより強力なコンピューティング クラスターで時間を借りることを検討する必要があります。

  7. k-means は、「恥ずかしいほど並列化できる」アルゴリズムの 1 つです。サーバー スペースを貸し出す場合は、これを Hadoop クラスターで実行でき、非常に役立つはずです。

  8. ここで何を達成しようとしていますか? 5000 クラスターは多いです。5000 個のクラスターの予想される意味は何ですか? ここでの本当の解決策は、より高速な kmeans の実装やより強力なハードウェアではなく、問題と達成しようとしていることを再考することだと思います。

于 2013-08-04T14:36:47.933 に答える
0

データを表すサンプルを作成できる場合は、最初にサンプルをクラスター化してから、分類手法を使用してモデルをトレーニングし、残りのデータのチャンクを予測してクラスターを割り当てることができます。

モデルをトレーニングすると、どの変数が重要でないかがわかるため、その方法で次元を減らすことができます。

問題を少しずつ処理することでより多くの洞察を得ることができるのに、なぜ 500 万行 x 512 フィーチャ x 5000 クラスターで計算の複雑さを増すのでしょうか?

于 2016-02-05T00:09:42.373 に答える