分散システムでのDBSCANの実装

Question

私は大きなデータの問題があり、並列処理とBigデータの経験は非常に限られています。私は緯度と経度のデータといくつかのIDからなる100万の行を持っています。各IDについて、私は10000〜1000万の範囲のデータを持つことができます。

いくつかのビジネス要件を解決するために、密度ベースのクラスタリングアルゴリズム（DBSCAN）を実装しています。クラスタリングアルゴリズムは、各IDに対して独立して実行されます。

現在の実装;

現在の実装はsklearnを使用したPythonコードを基にしています。機械学習ライブラリですが、5,000万のデータポイントに対して1日以上（クラスタリング+その他のビジネスロジック）の処理が必要です。

私はPythonコードを最適化して時間を短縮できますが、もっと実用的な解決策を探しています。

可用性

は私がAPPX 20機accross分散スパーククラスタを持っていますが、pysparkはDBSCANのない実装を持っていません。いくつかの検索で私はいくつかのスカラを見つけることができましたが、信頼性は低いようです。私の検索からのURLがあります。すべての私のコードは、私は解決策は、より多くのニシキヘビのthatsに固執したいPythonで書かれているので

DBSCAN on spark : which implementation

https://github.com/irvingc/dbscan-on-spark

。

クラスタリングアルゴリズムはデバイスごとに独立して実行されると述べましたが、時間を短縮する1つの方法は、各IDの計算をすべての20台のマシンに並列に分散することです。私はatleast 20倍のパフォーマンスを得ることができるように。しかし、私はこれを達成する方法については考えていません。私が考えることができるのはMapReduceだけです。

私はより頑強な解決策には誰でもオープンしています。どんな助けでも大歓迎です。

Answer 1

pySparkのオーバーヘッドは、シリアル化のために無視できません。あなたが本当に速くなりたいなら、オーバーヘッドを減らすためにできるだけ少ないレイヤーを使用してください。

データを目的のパーティションに分割し、別のノードで独立して処理することができます（ベンチマーク！データ索引付けを有効にして、結果が正しいかどうかを確認してください）。スパークのバージョンに間違った結果が報告されました）。最近、DBSCAN実装のランタイム差異が1000倍になったベンチマーク・ペーパーがありました。したがって、別のDBSCANが違いを生むことができます。

Answer 2

この例は、pysparkとscikit-learnでhttps://github.com/bwoneill/pypardisを試すことができます。私はそれをローカルで試しました。 75,000ポイントの計算には、ほぼ1.5時間かかりました。しかし、おそらくclasterでは速くなるでしょう。