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算法（遞歸邏輯）

回答

相關問題