6

14039 個のユーザー ベクトルで構成されるデータセットに階層クラスタリングを適用しようとしています。各ベクトルには 10 個の特徴があり、各特徴は基本的にそのユーザーによってタグ付けされたタグの頻度です。クラスタリングに Scipy API を使用しています。ここで、これら 14039 人のユーザー間のペアごとの距離を計算し、この距離行列をリンケージ関数に渡す必要があります。

  import scipy.cluster.hierarchy as sch
  Y = sch.distance.pdist( allUserVector,'cosine')
  set_printoptions(threshold='nan')
  print Y

しかし、私のプログラムは、距離行列自体の計算中に MemoryError を返します

  File "/usr/lib/pymodules/python2.7/numpy/core/numeric.py", line 1424, in array_str
    return array2string(a, max_line_width, precision, suppress_small, ' ', "", str)
  File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 306, in array2string
    separator, prefix)
  File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 210, in _array2string
    format_function = FloatFormat(data, precision, suppress_small)
  File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 392, in __init__
    self.fillFormat(data)
  File "/usr/lib/pymodules/python2.7/numpy/core/arrayprint.py", line 399, in fillFormat
    non_zero = absolute(data.compress(not_equal(data, 0) & ~special))
MemoryError

これを修正する方法はありますか？データセットが大きすぎますか? しかし、14,000 ユーザーのクラスタリングは、メモリ エラーが発生するほど多すぎてはいけないと思います。i3 および 4 Gb RAM で実行しています。DBScan クラスタリングも適用する必要がありますが、これも入力として距離行列が必要です。

任意の提案をいただければ幸いです。

編集:Yを印刷したときにのみエラーが発生します。理由はありますか?

4

2 に答える 2

5

階層的クラスタリングは、大規模なデータセットにはあまり意味がありません。私の意見では、これは実際にはほとんど教科書の例です。階層的クラスタリングの問題は、それが実際に賢明なクラスターを構築しないことです。樹状図を作成しますが、14000個のオブジェクトを使用すると、樹状図はほとんど使用できなくなります。また、階層的クラスタリングの実装には、樹状図から適切なクラスターを抽出するための重要な方法があります。さらに、一般的なケースでは、階層的クラスタリングは複雑O(n^3)であるため、大規模なデータセットへのスケーリングは非常に悪くなります。

DBSCANは、技術的には距離行列を必要としません。実際、距離行列を使用する場合、距離行列の計算はすでにであるため、速度は遅くO(n^2)なります。それでも、O(n^2)距離をそれぞれ2回計算するコストで、その場で距離を計算することにより、DBSCANのメモリコストを安全に保つことができます。DBSCANは各ポイントに1回アクセスするため、対称性の向上を除いて、距離行列を使用してもほとんどメリットはありません。また、技術的には、DBSCANはどのオブジェクトがイプシロンのしきい値を下回っているかを知る必要があるだけなので、それを減らすためにいくつかの巧妙なキャッシングトリックを行うことができます。イプシロンが合理的に選択されている場合、隣接セットをオンザフライで管理するとO(n^2)、距離行列を計算する同じCPUコストよりも大幅に少ないメモリを使用します。

DBSCANの本当に優れた実装（スキャンではなく省略形であるため、すべて大文字で綴られています）は、インデックス構造をサポートしている必要があり、実行時にO(n log n)実行する必要があります。

http://elki.dbs.ifi.lmu.de/wiki/Benchmarkingでは、 110250オブジェクトデータセットと8つのディメンションでDBSCANを実行し、インデックス付けされていないバリアントは1446秒かかり、インデックスは219秒です。インデックスの蓄積を含めて7倍高速。（ただし、Pythonではありません）同様に、OPTICSはインデックスを使用すると5倍高速になります。そして、私の実験でのkmeansの実装は、WEKA kmeansよりも約6倍速く、使用するメモリもはるかに少なくなりました。それらのシングルリンク階層的クラスタリングも最適化O(n^2)された実装です。実際、私がこれまでに見たのは、単純なO(n^3)マトリックス編集アプローチではない唯一のものです。Pythonを超えても構わないと思っているなら、それは良い選択かもしれません。

于 2012-04-12T05:34:53.130 に答える
5

本当にRAMが不足している可能性があります。N 個のオブジェクト間のペアごとの距離を見つけることは、N^2 の距離を格納することを意味します。あなたの場合、N^2 は 14039 ^ 2 = 1.97 * 10^8 になります。各距離が 4 バイトしかないと仮定すると (一定でないオーバーヘッドを持つ可能性のある何らかのデータ構造に保持する必要があるため、ほぼ確実にそうではありません)、800 メガバイトになります。これは、インタプリタが処理するための大量のメモリです。32 ビット アーキテクチャでは最大 2 GB のプロセス メモリしか使用できず、生データだけでその約 50% を占めています。データ構造のオーバーヘッドにより、それよりもはるかに高い使用量が見られる可能性があります.SciPy / numpyの背後にあるメモリモデルがわからないため、どの程度かはわかりません.

データセットを小さなセットに分割するか、完全な距離行列を構築しないようにします。それをより管理しやすいチャンク (たとえば、約 1000 要素の 14 サブセット) に分割し、各チャンクとすべてのベクトルの間で最近傍を実行することができます。 1 回 (14000 * 1000、14000 * 14000 1 回の代わりに 14 回)。

編集: agf は両方の点で完全に正しいです: 私はあなたの編集を逃しました.行列を表す巨大な文字列を構築しようとすると問題が発生する可能性があります. 浮動小数点値を出力していて、要素ごとに 10 文字が出力され、文字列が 1 文字あたり 1 バイトで格納されていると仮定すると、文字列だけで正確に 2 GB のメモリ使用量を見ていることになります。

于 2012-04-11T23:55:01.127 に答える