hadoop - hadoop 中的 DBSCAN

Question

其实我不知道 map() 的 key 和 value 应该是什么，输入格式和输出格式应该是什么。如果我通过 map() 一次读取一个点，那么如何使用一个点计算邻居，因为尚未读取剩余点。

Answer 1

DBSCAN 不是一个令人尴尬的并行算法。

将其表示为 map-reduce 并非易事。

您将需要使用一些技巧（例如对数据进行分区，并将每个值映射到分区），或者完全重新设计算法。

有许多关于并行 DBSCAN的文章。您可能能够在类似 map-reduce 的框架中运行其中的一些，或者至少在自定义（非 map-reduce）YARN 引擎上运行。

Answer 2

查看这篇论文：https ://www.researchgate.net/publication/261212964_A_new_scalable_parallel_DBSCAN_algorithm_using_the_disjoint-set_data_structure

以下是我的解决方案，可能比论文中的解决方案更容易理解：

首先，我将计算您的距离矩阵——它可能是一个仅包含那些距离小于 DBSCAN epsilon 参数的稀疏矩阵——找到一种方法来实现它的 map-reduce。

您可以将该距离矩阵映射到多个设备和集群点。您意识到在这种情况下并行集群会破坏输入空间，并且您在一个实例中获得一个集群 id，该集群 id 可能对应于另一个实例中的另一个 id。

为了解决这个问题，在 reduce 步骤中收集所有核心点，然后检查每个核心点的每个邻居（地图，不必是 O(n^2)，要聪明点）。如果您可以找到其他核心元素关闭，请创建 2 个相邻核心的 2 个集群 ID 的条目；收集这些 id 对（减少）。使用这些对，导出正确的全局聚类 ID。

上面的描述可能听起来有点抽象，但它应该给你的想法。