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

上は。ご覧のとおり、Wikipedia による DBSCAN のアルゴリズム。

この正確な部分についてお聞きしたいです。

      NeighborPts = NeighborPts joined with NeighborPts'

私の理解では、コア ポイントの近隣からコア ポイントが訪問された場合、それは現在調べられているクラスターに結合されますよね? しかし、ここで再帰はどのように行われるのでしょうか? 以下のループを定義したためです。

   for each point P' in NeighborPts 

そのため、NeighborPts からの追加のポイントは expandCluster 関数によって検査されず、新しい 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