scikit-learn DBSCANメモリの使用

Question

UPDATED：最後に、私の大きなデータセットをクラスタリングするために使用したソリューションは、以下のAnony-Mousseの提案でした。つまり、ELKIのDBSCANのインプリメンテーションを使って、scikit-learnではなくクラスタリングを行います。これは、コマンドラインから実行し、適切なインデックスを付けて、数時間以内にこのタスクを実行します。 GUIと小さなサンプルのデータセットを使用して、使用したいオプションを見つけて町に行きます。探し求める価値がある。私の元の問題の説明と興味深い議論については、誰でも読んでください。

私はクラスター化しようとしている35個のフィーチャー（浮動小数点値）を持つ250万個のサンプルを持つデータセットを持っています。私は、スケッチ学習のDBSCANの実装で、マンハッタンの距離メトリックとデータから抽出された小さなランダムサンプルから推定されるイプシロンの値を使ってこれを実行しようとしていました。ここまでは順調ですね。 （ここには参考用にスニペットがあります）

db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata) 

私の問題は、私が簡単にメモリが足りなくなることです。 （私は現在、16GBのRAMを搭載したマシンで作業しています）

私の質問は、DBSCANが実行中にその場でペアワイズ距離行列を計算していることです。これが私の記憶を揺さぶっていますか？ （250万^ 2）* 8バイトは明らかに愚かに大きいです、私はそれを理解するでしょう。 fit()メソッドを使用しないでください。そして、より一般的には、この問題を回避する方法があるのでしょうか、あるいは私は一般的に間違ったツリーをここで吠えていますか？

答えが明らかな場合は謝罪してください。私は数日間これを困惑させてきた。ありがとう！

補遺：誰も私にfit(X)とfit_predict(X)の違いを説明できる場合にも、より明確に私もそれをいただければと思います - - 私は恐れて私はかなりそれを得ることはありません。

付録＃2：550GBのRAMを搭載したマシンでこれを試したところ、まだ爆発していましたので、DBSCANがペアワイズ距離行列を作成しようとしているような気がします。それがしたい。私は今、大きな問題はその行動を止める方法か、自分のニーズに合った方法を見つけることだと思います。ここで私と一緒にお会いになりました。

補遺＃3（！）：私はトレースバックを添付するのを忘れて、ここではDBSCANアルゴリズムは、実際の距離行列を計算していないんので、ここではチャンス、

Traceback (most recent call last): 
    File "tDBSCAN.py", line 34, in <module> 
    db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict 
    self.fit(X) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit 
    **self.get_params()) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan 
    D = pairwise_distances(X, metric=metric) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances 
    return func(X, Y, **kwds) 
    File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances 
    D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :]) 
MemoryError 

Answer 1

明らかに問題は、scikitの低品質DBSCANの実装です。

DBSCANには距離行列は必要ありません。このアルゴリズムは、regionQuery関数を高速化し、クエリ半径内の近傍を効率的に返すデータベースを使用して設計されました（空間インデックスはO(log n)でそのようなクエリをサポートする必要があります）。

ただし、scikitの実装では、完全にO(n^2)の距離行列が計算されますが、これはメモリとランタイムの両方のコストがかかります。あなたがRで使用した場合* -treeインデックスは通常、ナイーブな実装よりも実質的に高速である、代わりにELKIでDBSCAN実装を試してみたいことがあり

1. ：

   だから私は2つの選択肢を参照してください。

2. の実装を再実装すると、scikitが明らかにあまり良くないと思われる場合があります。それを恐れないでください：DBSCANはあなた自身を実装するのが本当に簡単です。良いDBSCAN実装の中でもっともトリッキーな部分は、実際にはregionQueryの関数です。このクエリを高速に実行できる場合、DBSCANは高速になります。実際にこの関数を他のアルゴリズムにも再利用することができます。

更新：今によって、sklearnはもはや距離行列を計算しないと、例えば、kdツリーインデックスを使用することができます。しかし、 "ベクトル化"のために、それはまだすべてのポイントの近傍を事前計算するので、大きなイプシロンのsklearnのメモリ使用量はO（n²）ですが、ELKIのバージョンはO（n）メモリのみを使用します。したがって、メモリが足りなくなった場合は、より小さなイプシロンを選択してください。ELKIを試してみてください。

Answer 2

です。 この多くのデータについては、MiniBatchKMeansの使用をお勧めします。 マンハッタンメトリックをそのまま使用することはできませんが、独自の実装を行うことができます。おそらくユークリッドメトリックで標準実装を試してみてください。

ペアワイズ距離を実行しない多くのクラスタリングアルゴリズムはわかりません。

新しい埋め込みを使用してcheat-sheetボトムセンター：運がいいですが。

Answer 3

haversineメトリックとボールツリーアルゴリズムを使用して、scikit-learnのDBSCANを使用してこれを行うことができます。距離行列を事前計算する必要はありません。 DBSCAN /半正矢と

この例clusters over a million GPS latitude-longitude pointsとメモリ使用量の問題回避：いくつかの以前/以降のバージョンでは、完全な距離を必要とするように見えるとして、これは具体的には、scikit-学ぶv0.15を使用していることを

df = pd.read_csv('gps.csv') 
coords = df.as_matrix(columns=['lat', 'lon']) 
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords)) 

注意を行列を計算する必要があります。しかし、あなたがアナコンダを使用している場合、あなたはすぐにこれを設定することができます

conda install scikit-learn=0.15 

それとも、このクラスタリングタスクのためのクリーンな仮想環境を作成：その場でそれらを計算する方法はありません

conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter 
activate clusterenv