DBSCAN

1. Idea
2. Algorithm
3. Advantage
4. Disadvantage
5. Reference

返回 Clustering

tags: Machine Learning, Clustering

Idea

返回 DBSCAN
返回 Clustering

透過設定的半徑(

$ϵ$)及最少資料點數(MinPts)將資料分成三類：

1. 核心點(core points)
   對於給定點P，如果以
   $ϵ$為半徑張開的圓中包含至少MinPts個資料點(包括P自己)，則稱P為核心點。
2. 邊界點(border points)
   對於給定點P，如果以
   $ϵ$為半徑張開的圓中包含小於MinPts個資料點(包括P自己)，但P包含於某個核心點張出的圓中，則稱P為邊界點。
3. 雜訊(Noise)
   對於給定點P，如果以
   $ϵ$為半徑張開的圓中包含至少MinPts個資料點(包括P自己)，且P不包含於任意核心點張出的圓中，則稱P為雜訊。

Algorithm

返回 DBSCAN
返回 Clustering

DBSCAN(D, eps, MinPts) {
	C = 0
	for each point P in dataset D {
        P is visited
            continue next point
        rk 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 Q in NeighborPts {
		if Q is not visited {
			mark Q as visited
			NeighborPts_Q = regionQuery(Q, eps)
			if sizeof(NeighborPts_Q) >= MinPts
                NeighborPts = NeighborPts joined with NeighborPts_Q
		}
		if Q is not yet member of any cluster
			add Q to cluster C
	}
}

regionQuery(P, eps)
    return all points within in the eps-neighborhood of P (including P)

翻譯成白話文就是：

# def DBSCAN(資料D、半徑epsilon、MinPts)
   # 觀察每一個資料點(P)
      # 如果P已經看過
         # 找下一個資料點
      # 把P標記成已看過
      # 找出P的鄰居
      # 如果鄰居數量<MinPts
         # 先把P當成NOISE (如是邊界點之後會有核心點來領走它)
      # 如果鄰居數量>=MinPts
         # 就把P當成一個新的群體
         # 並且找出所有屬於這個群體的點

# def 找出所有屬於群體的點(核心點P、P的鄰居、群組C、半徑epsilon、MinPts)
   # 把P加入群組C
   # 考慮P的每個鄰居(Q)
      # 如果Q還沒被看過
         # 把Q標示成看過
         # 找出Q的鄰居
         # 如果Q的鄰居數量>=MinPts (代表Q也是核心點)
            # 就把Q的鄰居也當成是P的鄰居
      # 如果Q還沒被加進任何群體(=>Q是還沒被領走的邊界點)
         # 就把Q加進群組C

# def 找出鄰居(點P、半徑epsilon)
   # 回傳所有鄰居

Advantage

返回 DBSCAN
返回 Clustering

1. 不需事先指定群數
2. 可以找出任何形狀的聚類
3. 能分辨Noise
4. 如果對資料有足夠的瞭解，可以選擇適當的參數來達到好的分類效果

Disadvantage

返回 DBSCAN
返回 Clustering

1. 不同的資料順序可能會有不同的分群結果(幸運的是，這種情況不常見)
2. 在高維度中，受到「維度災難」的影響，很難找出合適的
   $ϵ$
3. 如果資料庫裡的點有不同的密度，則無法得到好的分群結果

Reference

返回 DBSCAN
返回 Clustering

1. Wiki - DBSCAN
2. 台灣人工智慧學校 Clustering method 1