15

q-gram距離や単純な「バッグ距離」、またはPythonのレーベンシュタイン距離などで、〜100,000個の短い文字列をクラスター化したいと考えています。私は距離行列 (100,000 は 2 つの比較を選択) を記入し、pyClusterで階層的クラスタリングを行うことを計画していました。しかし、地面に着く前に、いくつかのメモリの問題に遭遇しています。たとえば、numpy には距離行列が大きすぎます。

aa = numpy.zeros((100000, 100000))
ValueError: array is too big.

これは合理的なことのように思えますか? または、このタスクでメモリの問題が発生する運命にありますか? ご協力いただきありがとうございます。

4

4 に答える 4

8

100,000 * 100,000 * 32 ビット = 40 G バイト、これは大量の RAM になるため、別の方法を見つける必要があります。(そして、このデータをメモリに収めることができたとしても、計算に時間がかかりすぎます。)

一般的で簡単な近道の 1 つは、データの小さなランダムなサブセットをクラスター化することです。このサブセットのクラスターを見つけたら、残りのポイントを最適なクラスターに配置します。

于 2010-11-22T02:35:31.663 に答える
3

100 億要素はすごい量です。q-gramからはわかりませんが、その行列がまばらな場合は、200,000個の要素のdictを使用できます。

于 2010-11-22T02:38:28.693 に答える
2

マトリックスが必要ですか？速度のためにマトリックスを使用したいと思いますか？

私は（階層的クラスターアルゴリズムではなく）k-meansクラスターアルゴリズムを持っており、これは必要に応じてノード距離を計算します。ただし、おそらく高速距離メトリックでのみ実行可能です。そして、あなたは私よりも多くのデータを持っています-しかし、あなたはメモリの制限に縛られています。

于 2010-11-23T18:20:46.283 に答える
2

  1. 機械学習には埋め込みと呼ばれる方法があり、原則として、 O (n*m) (n=10^5 アイテム、m=10^)の代わりにO (n+m) メモリを使用してこの問題の解決策を検索できます。5つの特徴）。残念ながら、O(m+n) で実装されている利用可能なソース コードを知りません。見る：

    共起データのユークリッド埋め込み。アミール・グロバーソン、ガル・チェチック、フェルナンド・ペレイラ、ナフタリ・ティシュビー。Journal of Machine Learning Research、JMLR、8 (10 月)、2007.pdf / Matlab コード

  2. 他の解決策があるかもしれません。機械学習関係者のフォーラム ( https://stats.stackexchange.com/など) でこの質問をするか、言語処理に特化したフォーラム ( http://metaoptimize.com/qa/ ) で質問する必要があると思います。

于 2011-10-09T18:18:34.607 に答える