DBSCAN演算法在出行行為中的應用例項及程式碼解析（1）

將物理或抽象物件的集合分成由類似的物件組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組資料物件的集合，這些物件與同一個簇中的物件彼此相似，與其他簇中的物件相異。常用的聚類演算法包括原型聚類、密度聚類和層次聚類三大類。

其中密度聚類演算法（density-based clustering）假設聚類結構能透過樣本分佈的緊密程度確定。通常情況下，密度聚類演算法從樣本密度角度考察樣本之間的可連線性，並基於可連線性不斷擴充套件聚類簇以獲得最終的聚類效果。

DBSCAN

（Density-Based Spatial Clustering of Applications with Noise）是一種典型的密度聚類演算法。其在交通領域的資料處理中有著廣泛的應用和獨特的優勢。下面科研Lab將從演算法優勢、概念原理、案例講解（附程式碼）三部分講解DBSCAN。

1. 演算法優勢

作為密度聚類的經典演算法，DBSCAN可以處理不同大小、形狀的資料集，同時聚類結果產生的簇（性質相似的樣本資料組成的最大非空子集）形狀、大小、數量是任意的。以出行行為分析為例，研究之前，我們對出行鏈或站點的聚類結果是未知的，某種意義上，其聚類後的形狀、大小、數量也是任意的。

DBSCAN以高密度確定簇，同時自動將不屬於任何簇的樣本資料作為噪音捨棄，避免了噪音資料為結果產生的影響。仍以出行行為分析為例，由於罕見原因（重大活動，惡劣天氣等等）產生的出行鏈資料，其發生機率很小，在一般性的研究中使用DBSCAN去除，既不影響研究目的，也可以避免“特殊”出行鏈對結果產生的干擾。

2. 概念原理

DBSCAN演算法有兩個全域性引數：ε 和 MinPts ，在其基礎上定義鄰域，從而刻畫樣本分佈的緊密程度。給定樣本集

，定義以下概念：

ε-鄰域

：對

，其ε-鄰域包含樣本集D中與

的距離不大於

的樣本，即：

這裡的距離指的是歐氏距離

，感興趣的小夥伴可以自行了解閔可夫斯基距離。

核心點（核心元素）

：若

的ε-鄰域至少包含MinPts個樣本，即

，即

是一個

核心點

；

邊界點

：若

的ε-鄰域樣本數量少於MinPts，且

位於核心點的ε-鄰域內，則稱

為邊界點；

噪音點

：若

既不是核心點，也不是邊界點，則稱

為噪音點；

密度直達

：若

位於的ε-鄰域中，且

是核心物件，則稱

是由

密度直達

；

密度可達

：對

與

，若存在樣本序列

，其中

，

由密

度直達，則稱

由

密度可達

；

密度相連

：對

與

，若存在

使得

與

均由

密度可達，則稱

與

密度相連

。

更直觀的可以看下圖，MinPts=3，所有圓等大且半徑為ε。

紅色：核心點

黃色：邊界點

綠色：噪音點

1可由2密度直達、4可由3密度直達、2和3互相密度直達；

1可由3密度可達，4可由2密度可達；

1與4密度相連。

基於以上概念，DBSCAN將“簇”定義為：由密度可達關係匯出的最大密度相連的樣本集合。給定鄰域引數（ε和MinPts），簇是滿足

連線性

和

最大性

的

非空

樣本子集：

連線性：若

，

，則一定有

和

密度相連；

最大性：若

，

由密度可達，則

。

3. 案例講解

·

資料集構造

樣本資料集由sklearn包構造

1) 匯入包：

import

numpy

as

np

import

pandas

as

pd

import

random

from

sklearn

import

datasets

import

matplotlib。pyplot

as

plt

2) 生成資料集：

%matplotlib inline

#初始化樣本資料集

#生成樣本容量為500的樣本集合，設定噪音比。

dataset，_ = datasets。make_moons（500，noise = 0。1，random_state=1）

df = pd。DataFrame（dataset，columns = ［‘X’，‘Y’］）

#繪圖，設定透明度為0。6

df。plot。scatter（‘X’，‘Y’， s=100，alpha=0。6， title=‘dataset by make_moon’）

注：資料無量綱

樣本集視覺化得到：

演算法思路

演算法先根據給定的鄰域引數（ε和MinPts）找出所有的核心物件；在以任意核心物件為出發點，找出由其密度可達的樣本生成聚類簇，直到所有的核心物件被訪問過。

·具體實現

1) 初始化鄰域引數：

r= 0。2

minpts = 20

2) 在建立鄰域字典的基礎上，搜尋所有核心元素：

#補充樣本序號

dataset=dataset。tolist（）

i=0

while i

dataset［i］=［i+1］+dataset［i］

i+=1

#print（dataset）

#建立字典 點（鍵） 鄰域集合（值） 為方便，點以序號代替

#初始化字典

N_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_tem

#print（N_dict）

#初始化核心元素集合

U = ［］

i = 1

while i <= 500：

if len（N_dict［i］） >= minpts：

U。append（i）

i +=1

print（“the core points are ”，U）

3) 聚類：以任意核心物件為出發點，找出由其密度可達的樣本生成聚類簇，直到所有核心物件被訪問過。

#初始化 簇的集合

C = ［］

#初始化 未訪問的樣本序號集合

DS =［i for i in range（1，501）］

#建立迴圈，直到core points全部被訪問過 所有簇才被尋找到

while U ！= ［］：

DS_old = DS［：］ #標記當前未訪問過的樣本集合

print（“當前未訪問過的樣本集合：”，DS_old）

Q1 = random。sample（U，1） #不失一般性，隨機選取核心元素， #初始化 本次研究的points集

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 i not in Q1：

Q1。append（i）

DS。remove（i）

#取DS_old內，但不在DS內的元素，作為本次的簇

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）

4）

視覺化。

透過視覺化，得到下圖

其中黃色代表簇1，紅色代表簇2，藍色代表噪音點。

本期講解就到這裡啦，下期推送講講解使用sklearn庫實現DBSCAN演算法，同時介紹DBSCAN演算法的改進模型，如果你喜歡本篇文章的話，請點贊，轉發，關注，您的鼓勵與支援是我們創作的最大動力！

歡迎關注【交通科研Lab】公眾號，所有文章均在公眾號第一時間釋出！

參考文獻：［1］周志華。機器學習2016［M］。北京：清華大學出版社。2016。