使用 R 树实现 DBSCAN

Question

我正在尝试使用 R 树实现 DBSCAN。我们可以以 R 树的形式存储数据。所以我的问题是如何在 R 树中存储实时数据以及我应该如何实现区域查询来查找点的邻域是吗？

Answer 1

首先实现 R-Tree，然后实现 DBSCAN。

对于实时性，您可能想研究数据流的专门聚类算法。

Answer 2

我不确定你所说的实时数据是什么意思。如果您涉及更改数据或流数据，您也可以从 R 树中删除过时的内容。如果您的意思是您的数据也具有时间维度，那么您可以简单地将 R 树管理的系数数量扩展到 (x,y,t) - 我假设您使用简单的双变量版本。

如果您想实现 DBSCAN，您将需要执行范围查询以计算点周围球形区域的密度。因此，您的区域查询应该能够处理球形查询区域（就此而言，我还建议您查看 Shinichi Satoh 的 SR-Tree，可能会有所帮助）。同样，如果实时数据意味着您的数据具有时间特征，您可能需要考虑使用椭圆体的查询区域（允许单独缩放空间和时间特征）。