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);
か?