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的算法根据维基百科。
我想问一下这个确切的部分。
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.addAll(v);
修改数据收集后,是否会重新访问数据收集region
?
我的理解是,如果一个核心点来自核心的邻居 访问点,它将加入当前检查的集群, 右?
是的,你是对的,你可以安全地删除这条线
如果未访问 P'
但是,这效率不高。
如果已访问点 P',则无需计算其邻域并将其与 P 邻域连接。
它被访问意味着:它是一个噪音点,它已经在集群中,或者它是一个边界点。如果它已经在集群中,并且它是一个核心点,这意味着它的邻居已经被处理了。如果它是边界点,则不得连接其相邻点。
但是递归是如何在这里发生的呢?
在行中
对于相邻点中的每个点 P'
您必须将NeighborPts
视为点的动态容器。第一次进入 for 循环时NeighborPts
包含 X
个点。如果连接将 Y
个点添加到NeighborPts
则 for 循环将访问X
和Y
集。然后,这将对集合重复此操作 X
和 Y
这就是递归发生的方式。
数据收集区域是否会在 通过此代码修改数据收集 region.addAll(v(;?
是的,每次您调用region.addAll(v)
时,region.size()
都会增加,这证实了使您感到困惑的递归行为。