ELKI の OPTICS アルゴリズムを使用してクラスター化したい 100,000 点があります。このポイント セットには、約 50 億エントリの上三角距離行列があります。ELKI がマトリックスを希望する形式では、約 100 GB のメモリが必要になります。ELKI はその種のデータ ロードを処理するのでしょうか? 以前にこの作業を行ったことがあるかどうか、誰でも確認できますか?
質問する
732 次
1 に答える
5
10万ポイント、最大1000万ポイントのELKIをよく利用しています。
ただし、これを高速にするには、 indexs を使用する必要があります。
明らかな理由から、密な行列ベースのアプローチはせいぜいスケーリングし、メモリO(n^2)が必要です。O(n^2)R、Weka、または scipy でこれらのデータセットを処理できないのはそのためです。彼らは通常、最初に全距離行列を計算しようとし、途中で失敗するか、途中でメモリ不足になるか、負の割り当てサイズで失敗します (Weka、データセットが 2^31 の正の整数をオーバーフローする場合、つまり約 46k です)オブジェクト)。
float 精度のバイナリ形式では、ELKI マトリックス形式は約100000*999999/2*4 + 4バイトである必要があり、サイズ情報のためにさらに 4 バイトを追加することもできます。これは20 GBです。「使いやすい」ascii 形式を使用すると、実際にはさらに多くなります。ただし、gzip 圧縮を使用すると、ほぼ同じサイズになる可能性があります。そのようなデータを生のサイズの 10 ～ 20% に gzip 圧縮するのが一般的です。私の経験では、 gzip で圧縮された ascii は、バイナリ エンコードされた double と同じくらい小さくすることができます。バイナリ形式の主な利点は、実際にディスク上に存在し、メモリ キャッシュがオペレーティング システムによって処理されることです。
いずれにせよ、最初から距離行列をまったく計算しないことをお勧めします。
10 万から 100 万にすると、生のマトリックスは 2 TB に増加し、1,000 万にすると 200 TB になるためです。倍精度が必要な場合は、その 2 倍にします。
距離行列を使用している場合、メソッドはせいぜいO(n^2)であるため、スケーリングされません。最初にすべてのペアごとの距離を計算しないようにすることは、重要な速度要因です。
すべてにインデックスを使用します。kNN または半径範囲のアプローチ (OPTICS の場合は、epsion パラメータを使用してインデックスを有効にします! 低いイプシロンを選択してください!) では、これらのクエリが繰り返し必要になる場合は、これらのクエリを一度事前計算できます。
私が頻繁に使用するデータ セットでは、75,000 インスタンスと 27 次元で、事前計算された 101 個の最近傍 + 結合を倍精度で格納するファイルは 81 MB になります (注: これはまばらな類似度行列と見なすことができます)。このキャッシュの事前計算にインデックスを使用すると、計算に数分しかかかりません。そして、LOF などのほとんどの kNN ベースのアルゴリズムを、この 75k データセットで 108 ミリ秒(kNN キャッシュの読み込みに +262 ミリ秒 + 生の入力データの解析に 2364 ミリ秒、合計実行時間は 3 秒) で実行できます; double 値の解析が支配的です。 ）。
于 2013-09-11T07:35:57.700 に答える