2

バイナリ機能のポイントがあります：

id, feature 1, feature 2, ....
1, 0, 1, 0, 1, ...
2, 1, 1, 0, 1, ...

行列のサイズは約20k*200kですが、スパースです。kmeansアルゴリズムによるデータのクラスタリングにMahoutを使用していますが、次の質問があります。

  1. kmeansはバイナリ機能の良い候補ですか？
  2. マンハッタン距離測度の概念を維持しながら寸法を縮小する方法はありますか（コサインや谷本の代わりにマンハッタンが必要です）
  3. kmeansのメモリ使用量は高く、Map / Reduceタスクごとに4GBのメモリが必要です（3kクラスターの400Mbベクターファイルの4Mbブロック）。MahoutのVectorオブジェクトがダブルエントリを使用していることを考えると、ポイントにはブールエントリだけを使用し、センターにはダブルエントリを使用する方法はありますか？
4

2 に答える 2

2

k-meansは、適切な距離メトリックがある場合に適した候補です。マンハッタン距離は問題ないかもしれません。対数尤度が好きです。

好きな次元削減手法を使用できます。私は交互最小二乗が好きです。SVDもうまく機能します。このサイズマトリックスの場合、Hadoopに煩わされることなく、Commons Mathを使用してメモリ内で簡単に実行できます。これは、やり過ぎです。

（http://myrrix.comも参照してください。コア/オンラインモジュールで再利用できる非常に高速なALS実装があります。これは、数十MBのヒープで数秒で処理できます。）

機能マトリックスにバイナリ0/1値がなくなりました。フィーチャスペースでは、コサイン距離が適切に機能するはずです（1-cosineSimilarity）。Tanimoto/Jaccardは適切ではありません。

于 2012-07-11T08:39:16.573 に答える
2

k-means には、見過ごされがちな 1 つの大きな要件があります。それは、適切な平均を計算する必要があるということです。これは、人々が考えるよりもはるかに重要です。

  • 平均が分散を減少させない場合、収束しない可能性があります (算術平均はユークリッド距離に最適です。マンハッタンの場合、中央値がより良いと言われています。非常に異なるメトリックについては、わかりません)
  • 平均はおそらくもうそれほどまばらではありません
  • 平均もバイナリ ベクトルではなくなります。

さらに、特に大規模なデータ セットの場合、どのkを使用しますか?

あなたは本当に他の距離測定を調べる必要があります. データ サイズはそれほど大きくありません。1 台のコンピュータを使用するだけで十分です。コンパクトなベクトル表現を使用すると、メイン メモリに簡単に収まります。最初に ^2 類似度行列を計算するものを使用しないでください。たぶん、バイナリベクトルの類似性のためにインデックスを使って何かを試してみてください.

k-means は、特に事前のシード処理を行わない場合は、実装が非常に簡単です。メモリ使用量を減らすには、データに最適な表現のために自分で実装してください。ビットセットの場合もあれば、ゼロ以外の次元のソート済みリストの場合もあります。マンハッタン距離は、ベクトルが異なる次元の数を数えることに要約されます!

于 2012-07-12T06:44:18.560 に答える