在分布式系统中实现 DBSCAN

Question

我有一个大数据问题，我在并行处理和大数据方面的经验非常有限。我有数百万行由纬度和经度数据和几个 ID 组成。对于每个 ID，我可以拥有 10000 -1000 万的数据。

我正在实施基于密度的聚类算法（DBSCAN）来解决一些业务需求。聚类算法为每个 ID 独立运行。

当前实施；

当前的实现基于使用 sklearn 机器学习库的 Python 代码，但是对于大约 5000 万个数据点执行（集群 + 其他业务逻辑）需要一天或更长时间。

我可以优化 python 代码并减少时间，但我正在寻找更可行的解决方案。

可用性

我有一个分布在 appx 20 机器上的 Spark 集群，但 pyspark 没有实现 DBSCAN。经过一些搜索，我可以找到一些 Scala 实现，但它们似乎不太可靠。我搜索的网址是。 https://github.com/irvingc/dbscan-on-spark

Spark 上的 DBSCAN：哪个实现

由于我所有的代码都是用 python 编写的，我想坚持使用更 pythonic 的解决方案。

就像我提到的，集群算法为每个设备独立运行，减少时间的一种方法是将每个 ID 的计算并行分布到所有 20 台机器。这样我至少可以获得 20 倍更好的性能。但我不知道如何实现这一目标。我能想到的只有 MapReduce。

我对任何更强大的解决方案持开放态度。任何帮助将不胜感激。

Answer 1

由于序列化，pySpark 的开销不可忽略。如果你想非常快，请使用尽可能少的层以减少开销。

我只需将数据拆分到所需的分区，然后使用您能找到的最快的 DBSCAN 在单独的节点上独立处理它们（基准！确保启用数据索引，并检查结果的正确性。报告了 Spark 版本之一）得到不正确的结果）。最近有一篇基准测试论文观察到 DBSCAN 实现有 1000 倍的运行时差异。因此，另一个 DBSCAN 可以发挥作用。