DBSCAN - HackMD

# DBSCAN 1. [__Idea__](#Idea) 2. [__Algorithm__](#Algorithm) 3. [__Advantage__](#Advantage) 4. [__Disadvantage__](#Disadvantage) 5. [__Reference__](#Reference) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) ###### tags: `Machine Learning`, `Clustering` ## Idea [__返回 DBSCAN__](#DBSCAN) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) 透過設定的半徑($\epsilon$)及最少資料點數(MinPts)將資料分成三類： 1. __核心點(core points)__ 對於給定點P，如果以$\epsilon$為半徑張開的圓中包含至少MinPts個資料點(包括P自己)，則稱P為核心點。 2. __邊界點(border points)__ 對於給定點P，如果以$\epsilon$為半徑張開的圓中包含小於MinPts個資料點(包括P自己)，但P包含於某個核心點張出的圓中，則稱P為邊界點。 3. __雜訊(Noise)__ 對於給定點P，如果以$\epsilon$為半徑張開的圓中包含至少MinPts個資料點(包括P自己)，且P不包含於任意核心點張出的圓中，則稱P為雜訊。 ## Algorithm [__返回 DBSCAN__](#DBSCAN) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) ```(python) 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__](#DBSCAN) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) 1. 不需事先指定群數 2. 可以找出任何形狀的聚類 3. 能分辨Noise 4. 如果對資料有足夠的瞭解，可以選擇適當的參數來達到好的分類效果 ## Disadvantage [__返回 DBSCAN__](#DBSCAN) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) 1. 不同的資料順序可能會有不同的分群結果(幸運的是，這種情況不常見) 2. 在高維度中，受到「維度災難」的影響，很難找出合適的$\epsilon$ 3. 如果資料庫裡的點有不同的密度，則無法得到好的分群結果 ## Reference [__返回 DBSCAN__](#DBSCAN) [__返回 Clustering__](/_UjmWDZzQNuJO2JgQbbGNQ) 1. [__Wiki - DBSCAN__](https://zh.wikipedia.org/wiki/DBSCAN) 2. [__台灣人工智慧學校 Clustering method 1__](https://medium.com/ai-academy-taiwan/clustering-method-1-11bcbe0fb12f)