0 
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 的算法根据 Wikipedia。

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

      NeighborPts = NeighborPts joined with NeighborPts'

我的理解是，如果访问核心点邻居的核心点，它将加入当前检查的集群，对吗？但是这里的递归是如何发生的呢？因为我们已经定义了循环：

   for each point P' in NeighborPts

在加入过程之前，因此 expandCluster 函数不会检查来自 NeighborPts' 的任何附加点，如果新的 NeighborPts' 实际上有一个点是同一集群的另一个核心点，那么算法如何进行？

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

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);？

4

1 回答 1

1

我的理解是，如果访问核心点邻居的核心点，它将加入当前检查的集群，对吗？

是的，你是对的，你可以安全地移除这条线

如果 P' 未被访问

然而，这不是有效的。

如果一个点 P' 已被访问过，则无需计算其邻域并将其与 P 的邻域连接。

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

但是这里的递归是如何发生的呢？

在行

对于 NeighborPts 中的每个点 P'

您必须将NeighborPts其视为点的动态容器。第一次进入for循环时NeighborPts包含X点。如果加入添加Y点，NeighborPts则 for 循环将访问两者X和Y集合。然后这将对集合重复，X这Y就是递归发生的方式。

通过这段代码region.addAll(v);修改数据采集后，是否会重新访问数据采集区域？

是的，每次你调用region.addAll(v)，都会region.size()增加，这证实了让你感到困惑的递归行为。

于 2013-06-24T21:31:22.850 回答