Vla*_*lav 4 cluster-analysis r-tree dbscan
是否有人可以向我解释dbscan算法如何与R*-Tree一起使用？我理解dbscan的工作,似乎我理解为R*-Tree有效,但我无法将它们连接在一起.
最初,我有数据 - 具有8个功能的特征向量,我不明白我如何处理构造R*-Tree.如果有人列出我必须通过的主要步骤,我将不胜感激.
如果我的问题很明显,我会道歉,但这会给我带来困难.提前致谢!
R*-Tree通过其边界框索引任意几何对象.在您的情况下,由于您只有点,因此边界框的最小值和最大值是相同的.每个R*-Tree都有类似的功能rtree.add_element(object, boundingbox).object将是数据点的索引,并将boundingbox如上所述.
连接点是DBSCAN 的regionQuery部分.regionQuery(p一个数据点的)p返回所有数据点q为哪些欧几里得距离(p,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其中:欧几里德距离(p,q)≤ε"
因此,您在R*-Tree中查询每个坐标是p ±ε 的相应坐标的点,然后计算所有匹配点与查询点p的欧氏距离.然而不同的是,这些都是检查比如果你会计算的欧几里得距离远不如点p到所有的点.因此,一个regionQuery的时间复杂度现在为O(log n*m),其中m是R*-tree返回的点数.如果你选择ε小,你的R*-tree会得到很少的匹配点,m会很小.因此,对于一个regionQuery,您的时间复杂度接近O(log n),因此对于每个数据点,一个regionQuery的O(n*log n).另一方面,如果选择ε这么大以至于它将包含大部分数据点,则m将接近n,因此,每个数据点的一个regionQuery所需的时间接近O(n*log n*n)= O (n²*log n)再次,所以与天真的方法相比,你什么也得不到.
因此,选择足够小的ε是至关重要的,这样每个点在ε的欧几里德距离内只有几个其他点.