带 R*-Tree 的 DBSCAN - 它是如何工作的
DBSCAN with R*-Tree - how it works
是否有人可以向我解释 dbscan 算法如何与 R*-Tree 一起工作？我了解 dbscan 的工作，似乎我了解 R*-Tree 的工作原理，但我无法将它们连接在一起。
最初，我有数据 - 具有 8 个特征的特征向量，但我不明白我必须如何处理它们以构建 R*-Tree。如果有人列出我必须通过的主要步骤，我将不胜感激。
如果我的问题很明显，我深表歉意，但它给我带来了困难。
提前致谢！
R* 树是一个空间索引。
它可以更快地找到邻居。
R*-Tree 通过边界框对任意几何对象进行索引。在您的情况下，由于您只有点，因此边界框的最小值和最大值相同。每个 R*-Tree 都有一个像 rtree.add_element(object, boundingbox) 这样的函数。 object 将是数据点的索引，boundingbox 将如上所述。
连接点是DBSCAN的regionQuery部分。 regionQuery(p) 一个数据点 p returns 所有数据点 q for which euclideanDistance(p,q) ≤ ε（参数ε的值由用户提供）。
天真地，您可以计算所有数据点到 p 的距离，这需要 O(n) 时间计算一个数据点，因此查询所有 n 个数据点需要 o(n²) 时间。或者，您可以预先计算一个矩阵，该矩阵保存所有数据点彼此之间的欧氏距离。这然后需要 O(n²) of space 而 regionQuery 的一个点只需要在该矩阵中查找。
R*-Tree 使您能够在 O(log n) 时间内查找坐标范围内的数据点。但是，R*-Tree 只允许
形式的查询
"All points where: Coordinate 1 in [ 0.3 ; 0.5 ] AND Coordinate 2 in [ 0.8 ; 1.0 ]"
而不是
"All points q where: euclideanDistance(p,q) ≤ ε"
因此，您在 R*-Tree 中查询每个坐标分别为 p±ε 坐标的点，然后计算所有匹配点到您的查询的欧氏距离点 p。然而，不同之处在于，与计算 p 到 all 的欧氏距离相比，这些要检查的点要少得多。因此，一个 regionQuery 的时间复杂度现在是 O(log n * m)，其中 m是您的 R* 树返回的点数。如果你选择 ε 小，你将从你的 R*-tree 中得到很少的匹配点，并且 m 会很小。因此，对于一个 regionQuery，您的时间复杂度接近 O(log n)，因此 O(n * log n) 对于每个数据点的一个区域查询。在另一个极端，如果您选择的 ε 太大以至于它将包含大部分数据点，m 将接近 n，因此，时间每个数据点需要一个区域查询接近 O(n * log n * n) = O (n² * log n ) ，因此与天真的方法相比，您一无所获。
因此，选择足够小的 ε 非常重要，这样每个点在 ε 的欧氏距离内只有少数其他点。
是否有人可以向我解释 dbscan 算法如何与 R*-Tree 一起工作？我了解 dbscan 的工作，似乎我了解 R*-Tree 的工作原理，但我无法将它们连接在一起。
最初，我有数据 - 具有 8 个特征的特征向量，但我不明白我必须如何处理它们以构建 R*-Tree。如果有人列出我必须通过的主要步骤，我将不胜感激。
如果我的问题很明显，我深表歉意，但它给我带来了困难。 提前致谢！
R* 树是一个空间索引。
它可以更快地找到邻居。
R*-Tree 通过边界框对任意几何对象进行索引。在您的情况下，由于您只有点，因此边界框的最小值和最大值相同。每个 R*-Tree 都有一个像 rtree.add_element(object, boundingbox) 这样的函数。 object 将是数据点的索引，boundingbox 将如上所述。
连接点是DBSCAN的regionQuery部分。 regionQuery(p) 一个数据点 p returns 所有数据点 q for which euclideanDistance(p,q) ≤ ε（参数ε的值由用户提供）。
天真地，您可以计算所有数据点到 p 的距离，这需要 O(n) 时间计算一个数据点，因此查询所有 n 个数据点需要 o(n²) 时间。或者，您可以预先计算一个矩阵，该矩阵保存所有数据点彼此之间的欧氏距离。这然后需要 O(n²) of space 而 regionQuery 的一个点只需要在该矩阵中查找。
R*-Tree 使您能够在 O(log n) 时间内查找坐标范围内的数据点。但是，R*-Tree 只允许
形式的查询"All points where: Coordinate 1 in [ 0.3 ; 0.5 ] AND Coordinate 2 in [ 0.8 ; 1.0 ]"
而不是
"All points q where: euclideanDistance(p,q) ≤ ε"
因此，您在 R*-Tree 中查询每个坐标分别为 p±ε 坐标的点，然后计算所有匹配点到您的查询的欧氏距离点 p。然而，不同之处在于，与计算 p 到 all 的欧氏距离相比，这些要检查的点要少得多。因此，一个 regionQuery 的时间复杂度现在是 O(log n * m)，其中 m是您的 R* 树返回的点数。如果你选择 ε 小，你将从你的 R*-tree 中得到很少的匹配点，并且 m 会很小。因此，对于一个 regionQuery，您的时间复杂度接近 O(log n)，因此 O(n * log n) 对于每个数据点的一个区域查询。在另一个极端，如果您选择的 ε 太大以至于它将包含大部分数据点，m 将接近 n，因此，时间每个数据点需要一个区域查询接近 O(n * log n * n) = O (n² * log n ) ，因此与天真的方法相比，您一无所获。
因此，选择足够小的 ε 非常重要，这样每个点在 ε 的欧氏距离内只有少数其他点。