cluster-analysis - 带有 R*-Tree 的 DBSCAN - 它是如何工作的

Question

是否有人可以向我解释 dbscan 算法如何与 R*-Tree 一起工作？我理解 dbscan 的工作，似乎我理解 R*-Tree 的工作原理，但我无法将它们连接在一起。

最初，我有数据 - 具有 8 个特征的特征向量，我不明白我必须如何处理它们以构建 R*-Tree。如果有人列出我必须通过的主要步骤，我将不胜感激。

如果我的问题很明显，我深表歉意，但这会给我带来困难。
提前致谢!

Answer 1

R*-Tree 通过边界框索引任意几何对象。在您的情况下，由于您只有点，因此边界框的最小值和最大值相同。每个 R*-Tree 都有一个类似 rtree.add_element(object, boundingbox) 的函数. object将是数据点的索引和 boundingbox如上所述。

连接点是regionQuery DBSCAN 的一部分。数据点 p 的 regionQuery(p) 返回所有 euclideanDistance(p,q) ≤ ε(参数 ε 的值由用户提供)的数据点 q。

天真地，您可以计算所有数据点到 p 的距离，对于一个数据点需要 O(n) 时间，因此查询所有 n 个数据点需要 o(n²) 时间。或者，您可以预先计算一个矩阵，该矩阵保存所有数据点彼此之间的欧几里德距离。然后这需要 O(n²) 的空间，而一个点的 regionQuery 只需要在该矩阵中查找。

R*-Tree 使您能够在 O(log n) 时间内查找坐标范围内的数据点。但是，R*-Tree 只允许查询以下形式

“所有点，其中:[0.3;0.5] 中的坐标 1 和 [0.8;1.0] 中的坐标 2”

并不是

“所有点 q 其中:euclideanDistance(p,q) ≤ ε”

因此，您在 R*-Tree 中查询每个坐标是 p±ε 的相应坐标的点，然后计算所有匹配点到查询点 p 的欧几里德距离。然而，不同之处在于，与计算 p 到所有点的欧几里德距离相比，这些要检查的点要少得多。因此，一个 regionQuery 的时间复杂度现在是 O(log n * m)，其中 m 是 R* 树返回的点数。如果您选择 ε 小，您将从您的 R* 树中得到很少的匹配点，并且 m 会很小。因此，一个 regionQuery 的时间复杂度接近 O(log n)，因此每个数据点的一个 regionQuery 的时间复杂度接近 O(n * log n)。在另一种极端情况下，如果您选择的 ε 大到可以包含您的大部分数据点，则 m 将接近 n，因此，每个数据点的一个 regionQuery 所需的时间接近 O(n * log n * n) = O (n² * log n ) 再次，因此与天真的方法相比，您一无所获。

因此，选择足够小的 ε 使每个点在 ε 的欧几里德距离内只有少数几个其他点，这一点至关重要。