DBSCAN算法（递归逻辑）

DBSCAN(D, eps, MinPts) 
    C = 0 
    for each unvisited point P in dataset D 
     mark P as visited 
     NeighborPts = regionQuery(P, eps) 
     if sizeof(NeighborPts) < MinPts 
     mark P as NOISE 
     else 
     C = next cluster 
     expandCluster(P, NeighborPts, C, eps, MinPts) 

expandCluster(P, NeighborPts, C, eps, MinPts) 
    add P to cluster C 
    for each point P' in NeighborPts 
     if P' is not visited 
     mark P' as visited 
     NeighborPts' = regionQuery(P', eps) 
     if sizeof(NeighborPts') >= MinPts 
      NeighborPts = NeighborPts joined with NeighborPts' 
     if P' is not yet member of any cluster 
     add P' to cluster C 

regionQuery(P, eps) 
    return all points within P's eps-neighborhood

以上是。如你所见，根据维基百科的DBSCAN算法。DBSCAN算法（递归逻辑）

我想问一下这个确切的部分。

 NeighborPts = NeighborPts joined with NeighborPts'

我的理解是，如果被访问从核心点的邻居的核心点，将被加入到当前检查组，对不对？但是递归如何在这里发生？因为我们已经定义的循环：加盟，所以任何额外的NeighborPts点的过程之前

for each point P' in NeighborPts

不会被expandCluster功能检查，如果新NeighborPts'实际上有一个点是另一个核心点指向同一个群集，算法如何进行？

我有“expandCluster”方法在Java中实现代码：

public void expand(Vector<Integer> region, Group c, double dist, int minPts){ 
    for(int i = 0; i < region.size(); i++){ 
     int idx = region.get(i); 
     if(labels[idx] == 0){       // check if point is visited 
      labels[idx] = 1;       // mark as visited 
      Vector<Integer> v = region(idx, dist); // check for neighboring point 
      if (v.size() >= minPts){     // check if core point 
       region.addAll(v);      // join the NeighborPts 
      } 
     } 
     if(clustered[idx] == 0){ 
      c.elements.add(patterns.get(idx)); 
      clustered[idx] = clusters.size()+1; 
     } 
    } 
}

会将数据收集region去收集数据，通过这个代码region.addAll(v);修改后要重新审视？

来源

2013-06-23 neovee

我的理解是，如果被访问从核心点的邻居的核心点，将被加入到当前检查的集群，吧？

是的，你说得对，你可以安全地删除线

如果P”是不是访问

然而，这是没有效率的。

如果点P”已被访问就没有必要计算其附近，与P.

附近加入吧

据走访意味着：它是一个噪声点，它已经在一个集群或者它是一个边界点。如果它已经在一个集群中并且它是核心点，这意味着它的邻居已经被处理了。如果是边界点，则不得连接其邻居。

但是递归怎么发生在这里呢？

在用于NeighborPts

每个点P”行

你必须考虑NeighborPts为点的动态容器。第一次输入for循环NeighborPts包含X分。如果加入Y指向NeighborPts那么for循环将访问X和Y集合。然后这将重复设置X和Y，这就是递归发生的方式。

将数据收集区域经历此代码修改数据收集之后被重新 region.addAll（ⅴ）;?

是，每次调用region.addAll(v)，region.size()增加，这证实，混淆你的递归行为的时间。

来源

2013-06-24 21:31:22

非常感谢你，我不知道'addAll（）'可以产生这种行为，它让我对递归感到困惑。 – neovee

DBSCAN算法（递归逻辑）

回答

相关问题