將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數據對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。常用的聚類算法包括原型聚類、密度聚類和層次聚類三大類。
其中密度聚類算法（density-based clustering）假設聚類結構能通過樣本分布的緊密程度確定。通常情況下，密度聚類算法從樣本密度角度考察樣本之間的可連接性，並基於可連接性不斷擴展聚類簇以獲得最終的聚類效果。
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一種典型的密度聚類算法。其在交通領域的數據處理中有著廣泛的應用和獨特的優勢。下面科研Lab將從算法優勢、概念原理、案例講解（附代碼）三部分講解DBSCAN。
①作為密度聚類的經典算法，DBSCAN可以處理不同大小、形狀的數據集，同時聚類結果產生的簇（性質相似的樣本數據組成的最大非空子集）形狀、大小、數量是任意的。以出行行為分析為例，研究之前，我們對出行鏈或站點的聚類結果是未知的，某種意義上，其聚類後的形狀、大小、數量也是任意的。
②DBSCAN以高密度確定簇，同時自動將不屬於任何簇的樣本數據作為噪音捨棄，避免了噪音數據為結果產生的影響。仍以出行行為分析為例，由於罕見原因（重大活動，惡劣天氣等等）產生的出行鏈數據，其發生概率很小，在一般性的研究中使用DBSCAN去除，既不影響研究目的，也可以避免「特殊」出行鏈對結果產生的幹擾。
DBSCAN算法有兩個全局參數：ε和MinPts，在其基礎上定義鄰域，從而刻畫樣本分布的緊密程度。給定樣本集D={x1, x2, … xm}，定義以下概念：
①ε-鄰域：對，其ε-鄰域包含樣本集D中與的距離不大於的樣本，即
;
這裡的距離指的是歐氏距離
，感興趣的小夥伴可以自行了解閔可夫斯基距離。
②核心點（核心元素）：若的ε-鄰域至少包含MinPts個樣本，即，即是一個核心點；
③邊界點：若的ε-鄰域樣本數量少於MinPts，且位於核心點的ε-鄰域內，則稱為邊界點；
④噪音點：若既不是核心點，也不是邊界點，則稱為噪音點；
⑤密度直達：若位於的ε-鄰域中，且是核心對象，則稱是由密度直達；
⑥密度可達：對與，若存在樣本序列，其中，由密度直達，則稱由密度可達；
⑦密度相連：對與，若存在使得與均由密度可達，則稱與密度相連。
更直觀的可以看下圖，MinPts=3，所有圓等大且半徑為ε。
1可由2密度直達、4可由3密度直達、2和3互相密度直達；
1可由3密度可達，4可由2密度可達；
1與4密度相連。
基於以上概念，DBSCAN將「簇」定義為：由密度可達關係導出的最大密度相連的樣本集合。給定鄰域參數（ε和MinPts），簇C∈D是滿足連接性和最大性的非空樣本子集：
連接性：若∈C，∈C，則一定有和密度相連；
最大性：若∈C，由密度可達，則∈C。
① 導入包：
import numpy as npimport pandas as pdimport randomfrom sklearn import datasetsimport matplotlib.pylot as plt
② 生成數據集：
%matplotlib inlinedataset,_ =datasets.make_moons(500,noise = 0.1,random_state=1)df =pd.DataFrame(dataset,columns = ['X','Y'])df.plot.scatter('X','Y',s=100,alpha=0.6, title='dataset by make_moon')註：數據無量綱
樣本集可視化得到：
算法先根據給定的鄰域參數（ε和MinPts）找出所有的核心對象；在以任意核心對象為出發點，找出由其密度可達的樣本生成聚類簇，直到所有的核心對象被訪問過。
① 初始化鄰域參數：
② 在建立鄰域字典的基礎上，搜索所有核心元素：
dataset=dataset.tolist()i=0while i<len(dataset): dataset[i]=[i+1]+dataset[i] i+=1N_dict = {}for i in dataset: n_tem = [] #臨時存儲鄰域 for j in dataset: dist=((i[1]-j[1])**2+(i[2]-j[2])**2)**0.5#距離使用歐式距離 if dist<=r: n_tem.append(j[0]) N_dict[i[0]]=n_temU = []i = 1while i <= 500: if len(N_dict[i]) >= minpts: U.append(i) i +=1print("the core points are ",U)③ 聚類：以任意核心對象為出發點，找出由其密度可達的樣本生成聚類簇，直到所有核心對象被訪問過。
C = []DS =[i for i in range(1,501)]
while U != []: DS_old = DS[:] print("當前未訪問過的樣本集合:",DS_old) Q1 = random.sample(U,1) print("隨機選取的核心元素:",Q1[0]) DS.remove(Q1[0])
Q2 = []
while Q1 != []: print("本次研究的points集:",Q1) num = Q1.pop(0) print("取出的元素:",num)
if num in U: for i in N_dict[num]: if i != num and i in DS and inot in Q1: Q1.append(i) DS.remove(i)
print("DS_old:",DS_old) print("DS",DS) for i in DS_old: if i not in DS: Q2.append(i) print("簇：",Q2) C.append(Q2)
for i in Q2: if i in U: U.remove(i)
noise = []for i in DS: if i not in C[0] and i not in C[1]: noise.append(i)print("最終簇為：",C)print("噪音為",noise)④ 可視化。
通過可視化，得到下圖
其中黃色代表簇1，紅色代表簇2，藍色代表噪音點。
參考文獻：[1]周志華.機器學習2016[M].北京：清華大學出版社.2016.
本期講解就到這裡啦，下期推送講講解使用sklearn庫實現DBSCAN算法，同時介紹DBSCAN算法的改進模型，如果你喜歡本篇文章的話，請點讚，轉發，關注！
編輯：莊楨
「交通科研Lab」：分享學習點滴，期待科研交流！
如果覺得還不錯
點這裡！👇👇👇