DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚類算法，是一種基于高密度連通區(qū)域的、基于密度的聚類算法，能夠?qū)⒕哂凶銐蚋呙芏鹊膮^(qū)域劃分為簇(Cluster)，并在具有噪聲的數(shù)據(jù)中發(fā)現(xiàn)任意形狀的簇。DBSCAN算法通過距離定義出一個密度函數(shù)，計算出每個樣本附近的密度，從而根據(jù)每個樣本附近的密度值來找出那些樣本相對比較集中的區(qū)域，這些區(qū)域就是我們要找的簇。

1. DBSCAN算法的基本原理

其它聚類方法大都是基于對象之間的距離進(jìn)行聚類，聚類結(jié)果是球狀的簇。DBSCAN 算法利用簇的高密度連通性，尋找被低密度區(qū)域分離的高密度區(qū)域，可以發(fā)現(xiàn)任意形狀的簇，其基本思想是:對于一個簇中的每個對象，在其給定半徑的領(lǐng)域中包含的對象不能少于某一給定的最小數(shù)目。

DBSCAN算法中有兩個重要參數(shù)：$\varepsilon$表示定義密度時的鄰域半徑，$M$ 表示定義核心點時的閾值。

考慮數(shù)據(jù)集合$X= \{x^{(1)}, x^{(2)},...,x^{(n)} \}$，引入以下概念與記號。

1. $\varepsilon$鄰域

設(shè)$x \in X$，稱

\begin{equation*}

N_{\varepsilon}(x) = \{ y \in X: d(y,x) \le \varepsilon \}

\end{equation*}

為$X$的$\varepsilon$鄰域。顯然，$x \in N_{\varepsilon}(x)$。

為了簡單起見，節(jié)點$x^{(i)}$與其下標(biāo)$i$一一對應(yīng)，引入記號

\begin{equation*}

N_{\varepsilon}(i) = \{ j: d(y^{(j)},x^{(i)}) \le \varepsilon; \; y^{(j)},x^{(i)} \in X \}

\end{equation*}

2. 密度

設(shè)$x \in X$，稱$\rho(x) = |N_{\varepsilon}(x)|$為$x$的密度。密度是一個整數(shù)，且依賴于半徑$\varepsilon$。

3. 核心點

設(shè)$x \in X$，若$\rho(x) \ge M$，則稱$x$為$X$的核心點。記由$X$中所有核心點構(gòu)成的集合為$X_c$，并記$X_{nc}=X-X_c$表示$X$中所有非核心點構(gòu)成的集合。

4. 邊界點

若$x \in X_{nc}$，且$\exists y \in X$，滿足$y \in N_{\varepsilon}(x) \bigcap X_c$，即$X$的非核心點$x$的$\varepsilon$鄰域中存在核心點，則稱$x$ 為$X$的邊界點。記由$X$中所有邊界點構(gòu)成的集合為$X_{bd}$。

此外，邊界點也可以這么定義，若$x \in X_{nc}$，且$x$落在某個核心點的$\varepsilon$鄰域內(nèi)，則稱$x$為$X$的邊界點。一個邊界點可能同時落入一個或多個核心點的$\varepsilon$ 鄰域內(nèi)。

5. 噪聲點

記$X_{noi} = X - (X_c \bigcup X_{bd})$，若$x \in X_{noi}$，則稱$x$為噪音點。

至此，我們嚴(yán)格給出了核心點、邊界點和噪音點的數(shù)學(xué)定義，且滿足$X = X_c \bigcup X_{bd} \bigcup X_{noi}$.

圖1：核心點、邊界點和噪聲點

直觀地說，核心點對應(yīng)稠密區(qū)域內(nèi)部的點，邊界點對應(yīng)稠密區(qū)域邊緣的點，而噪音點對應(yīng)稀疏區(qū)域中的點。

數(shù)據(jù)集通過聚類形成的子集是簇。核心點位于簇的內(nèi)部，它確定無誤地屬于某個特定的簇；噪音點是數(shù)據(jù)集中的干擾數(shù)據(jù)，它不屬于任何一個簇；邊界點是一類特殊的點，它位于一個或幾個簇的邊緣地帶，可能屬于一個簇，也可能屬于另外一個簇，其歸屬并不明確。

6. 直接密度可達(dá)

設(shè)$x,y \in X$. 若滿足$x \in X_c$，則稱$y$是$x$從直接密度可達(dá)的。

7. 密度可達(dá)

設(shè)$p^{(1)}, p^{(2)},..., p^{(m)} \in X$，其中$m \ge 2$。若它們滿足：$p^ {(i+1)}$ 是從$p^{(i)}$直接密度可達(dá)的，其中$i = 1,2,...,m-1$，則稱$p^ {(m)}$ 是從$p^{(1)}$ 中密度可達(dá)的。

7.1. 當(dāng)$m = 2$時，密度可達(dá)即為直接密度可達(dá)。實際上，密度可達(dá)是直接密度可達(dá)的傳遞閉包。

7.2. 密度可達(dá)關(guān)系不具有對稱性。若$p^{(m)}$是從$p^{(1)}$密度可達(dá)的，那么$p^ {(1)}$ 不一定是從$p^{(m)}$密度可達(dá)的。根據(jù)上述定義可知，$p^{(1)}, p^{(2)}, ..., p^{(m-1)}$必須為核心點，而$p^{(m)}$可以是核心點，也可以是邊界點。當(dāng)$p^ {(m)}$是邊界點時，$p^{(1)}$一定不是從$p^{(m)}$密度可達(dá)的。

8. 密度相連

設(shè)$x,y,z \in X$，若$y$和$z$均是從$x$密度可達(dá)的，則稱$y$和$z$是密度相連的。顯然，密度相連具有對稱性。

9. 簇(cluster)

非空集合$C \subset X$，如果$C$滿足：對于$x,y \in X$

若$x \in C$，且$y$是從$x$密度可達(dá)的，則$y \in C$，

若$x \in C$，$y \in C$，則$x,y$是密度相連的。

則稱$C$是$X$的一個簇。

DBSCAN 算法基于以下一個基本事實：對于任一核心點$x$，數(shù)據(jù)集$X$中所有從$x$ 密度可達(dá)的數(shù)據(jù)點可以構(gòu)成一個完整的簇$C$，且$x \in C$。其核心思想描述如下:從某個選定的核心點出發(fā)，不斷向密度可達(dá)的區(qū)域擴張，從而得到一個包含核心點和邊界點的最大化區(qū)域，區(qū)域中任意兩點密度相連。

2.?DBSCAN算法的實現(xiàn)

《數(shù)據(jù)挖掘概念與技術(shù)》給出的算法偽代碼如下:

考慮數(shù)據(jù)集合$X= \{x^{(1)}, x^{(2)},..., x^{(n)} \}$。DBSCAN算法的目標(biāo)是將數(shù)據(jù)集合$X$分成$K$個簇及噪聲點集合，其中$K$也是由算法得到，為此，引入簇的標(biāo)記數(shù)組

\begin{equation*}

m_i =

\begin{cases}

j, & \text{若}x^{(i)}\text{屬于第}j\text{個簇}; \\

-1, & \text{若}x^{(i)}\text{為噪聲點}

\end{cases}

\end{equation*}

DBSCAN算法的目標(biāo)就是生成標(biāo)記數(shù)組$m_i, \; i=1,...,n$.

為了保證可以更有效地實現(xiàn)算法1中第3句隨機選擇一個unvisited對象$p$，設(shè)計了一個數(shù)據(jù)結(jié)構(gòu)visitlist，其中包含兩個列表visitedlist和unvisitedlist，分別用于存儲已訪問的點和未訪問的點，每次從unvisitedlist 中取點可以保證每次取到的點都是未訪問過的點，實現(xiàn)代碼如下：

代碼1：visitlist數(shù)據(jù)結(jié)構(gòu)

1 #visitlist類用于記錄訪問列表

2 #unvisitedlist記錄未訪問過的點

3 #visitedlist記錄已訪問過的點

4 #unvisitednum記錄訪問過的點數(shù)量

5 classvisitlist:6 def _init_(self, count=0):7 self.unvisitedlist=[i for i inrange(count)]8 self.visitedlist=list()9 self.unvisitednum=count10

11 defvisit(self, pointId):12 self.visitedlist.append(pointId)13 self.unvisitedlist.remove(pointId)14 self.unvisitednum -= 1

DBSCAN算法實現(xiàn)代碼如下:

代碼2：DBSCAN算法實現(xiàn)

1 importnumpy as np2 importmatplotlib.pyplot as plt3 importmath4 importrandom5

6 defdist(a, b):7 #計算a,b兩個元組的歐幾里得距離

8 return math.sqrt(np.power(a-b, 2).sum())9

10 defmy_dbscanl(dataSet, eps, minPts):11 #numpy.ndarray的 shape屬性表示矩陣的行數(shù)與列數(shù)

12 nPoints =dataSet.shape[0]13 #(1)標(biāo)記所有對象為unvisited

14 #在這里用一個類vPoints進(jìn)行買現(xiàn)

15 vPoints = visitlist(count=nPoints)16 #初始化簇標(biāo)記列表C,簇標(biāo)記為 k

17 k = -1

18 C = [-1 for i inrange(nPoints)]19 while(vPoints.unvisitednum >0):20 #(3)隨機上選擇一個unvisited對象p

21 P =random.choice(vPoints.unvisitedlist)22 #(4)標(biāo)記p為visited

23 vPoints.visit(p)24 #(5)if p的$\varepsilon$-鄰域至少有MinPts個對象

25 #N是p的$\varepsilon$-鄰域點列表

26 N = [i for i in range(nPoints) if dist(dataSet[i], dataSet[p])<=eps]27 if len(N) >=minPts:28 #(6)創(chuàng)建個新簇C，并把p添加到C

29 #這里的C是一個標(biāo)記列表，直接對第p個結(jié)點進(jìn)行賦植

30 k += 1

31 C[p]=k32 #(7)令N為p的ε-鄰域中的對象的集合

33 #N是p的$\varepsilon$-鄰域點集合

34 #(8) for N中的每個點p'

35 for p1 inN:36 #(9) if p'是unvisited

37 if p1 invPoints.unvisitedlist:38 #(10)標(biāo)記p’為visited

39 vPoints.visit(p1)40 #(11) if p'的$\varepsilon$-鄰域至少有MinPts個點，把這些點添加到N

41 #找出p'的$\varepsilon$-鄰域點，并將這些點去重添加到N

42 M=[i for i in range(nPoints) ifdist(dataSet[i], \43 dataSet[p1]) <=eps]44 if len(M) >=minPts:45 for i inM:46 if i not inN:47 N.append(i)48 #(12) if p'還不是任何簇的成員，把P'添加到C

49 #C是標(biāo)記列表，直接把p'分到對應(yīng)的簇里即可

50 if C[p1] == -1:51 C[p1]=k52 #(15)else標(biāo)記p為噪聲

53 else:54 C[p]=-1

55

56 #(16)until沒有標(biāo)t己為unvisitedl內(nèi)對象

57 return C

利用sklearn生成數(shù)據(jù)集，共2500條數(shù)據(jù)，并利用matplotlib畫出散點圖，代碼如下:

代碼3：生成數(shù)據(jù)集

1 importnumpy as np2 importmatplotlib.pyplot as plt3 from sklearn importdatasets4

5 X1, Y1 = datasets.make_circles(n_samples=2000, factor=0.6, noise=0.05,6 random_state=1)7 X2, Y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.5,1.5]],8 cluster_std=[[0.1]], random_state=5)9

10 X =np.concatenate((X1, X2))11 plt.figure(figsize=(12, 9), dpi=80)12 plt.scatter(X[:,0], X[:,1], marker='.')13 plt.show()

圖2：數(shù)據(jù)集散點圖

設(shè)置參數(shù)Eps=0.1, MinPts=10，聚類結(jié)果如下圖：

圖3：聚類結(jié)果

3.?利用KD樹進(jìn)行優(yōu)化

KD樹(K-Dimensional Tree)，是一種分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，是二叉搜索樹在多維條件下的推廣。主要應(yīng)用于多維空間關(guān)鍵數(shù)據(jù)的搜索。KD樹的介紹見：https://www.jianshu.com/p/ffe52db3e12b，不贅述。

利用scipy實現(xiàn)KD樹的構(gòu)造和查詢，對代碼2的算法進(jìn)行改進(jìn)，代碼如下:

代碼4：DBSCAN算法的優(yōu)化實現(xiàn)

1 importnumpy as np2 importmatplotlib.pyplot as plt3 importmath4 importrandom5 from scipy.spatial importKDTree6

7 def my-dbscan2(dataSet, eps, minPts):8 #numpy.ndarray的 shape屬性表示矩陣的行數(shù)與列數(shù)

9 #行數(shù)即表小所有點的個數(shù)

10 nPoints =dataSet.shape[0]11 #(1) 標(biāo)記所有對象為unvisited

12 #在這里用一個類vPoints進(jìn)行實現(xiàn)

13 vPoints = visitlist(count=nPoints)14 #初始化簇標(biāo)記列表C，簇標(biāo)記為 k

15 k = -1

16 C = [-1 for i inrange(nPoints)]17 #構(gòu)建KD-Tree，并生成所有距離<=eps的點集合

18 kd =KDTree(X)19 while(vPoints.unvisitednum>0):20 #(3) 隨機選擇一個unvisited對象p

21 p =random.choice(vPoints.unvisitedlist)22 #(4) 標(biāo)t己p為visited

23 vPoints.visit(p)24 #(5) if p 的$\varepsilon$-鄰域至少有MinPts個對象

25 #N是p的$\varepsilon$-鄰域點列表

26 N =kd.query_ball_point(dataSet[p], eps)27 if len(N) >=minPts:28 #(6) 創(chuàng)建個一個新簇C，并把p添加到C

29 #這里的C是一個標(biāo)記列表，直接對第p個結(jié)點進(jìn)行賦值

30 k += 1

31 C[p] =k32 #(7) 令N為p的$\varepsilon$-鄰域中的對象的集合

33 #N是p的$\varepsilon$-鄰域點集合

34 #(8) for N中的每個點p'

35 for p1 inN:36 #(9) if p'是unvisited

37 if p1 invPoints.unvisitedlist:38 #(10) 標(biāo)記p'為visited

39 vPoints.visit(p1)40 #(11) if p'的$\varepsilon$-鄰域至少有MinPts個點，把這些點添加到N

41 #找出p'的$\varepsilon$-鄰域點，并將這些點去重新添加到N

42 M =kd.query_ball_point(dataSet[p1], eps)43 if len(M) >=minPts:44 for i inM:45 if i not inN:46 N.append(i)47 #(12) if p'還不是任何簇的成員，把p'添加到c

48 #C是標(biāo)記列表，直接把p'分到對應(yīng)的簇里即可

49 if C[p1] == -1

50 C[p1] =k51 #(15) else標(biāo)記p為噪聲

52 else:53 C[p1] = -1

54

55 #(16) until沒有標(biāo)記為unvisited的對象

56 return C

以代碼3中生成的2500條數(shù)據(jù)作為測試，比較優(yōu)化前后的算法性能

1 importtime2 start =time.time()3 C1 = my_dbscanl(X, 0.1, 10)4 end =time.time()5 print "`運行時間`:", end -start6 plt.scatter(X[:, 0], X[:, 1], c=C1, marker='.')7 plt.show()8 >>> `運行時間：`29.1249849796

圖4：優(yōu)化前算法結(jié)果

1 importtime2 start =time.time()3 C2 = my_dbscan2(X, 0.1, 10)4 end =time.time()5 print "運行時間:", end -start6 plt.scatter(X[:, 0], X[:, 1], c=C2, marker='.')7 plt.show()8 >>> 運行時間：4.72340583801

圖5：優(yōu)化后算法結(jié)果

可以看到優(yōu)化后的算法運行時間從29.12s降到了4.72s，優(yōu)化的效果非常明顯。

4.?后記

上文僅僅是對DBSCAN算法的思想與實現(xiàn)進(jìn)行了簡略摘要，是學(xué)習(xí)算法的一個過程。算法的學(xué)習(xí)還比較粗劣和淺層，在實踐應(yīng)用中上述代碼并不實用。如果需要使用DBSCAN的算法求解聚類問題，建議使用sklearn自帶的DBSCAN函數(shù)。以代碼3中生成數(shù)據(jù)為例：

1 #DBSCAN eps = 0.1, MinPts = 10

2 importtime3 from sklearn.cluster importDBSCAN4 start =time.time()5 C = DBSCAN(eps=0.1, min_pts=10).6 end =time.time()7 print "運行時間：", end -start8 plt.scatter(X[:, 0], X[:, 1], c=C, marker='.')9 plt.show()10 >>> 運行時間：0.0240921974182

總結(jié)

以上是生活随笔為你收集整理的dbscan算法python实现_挑子学习笔记：DBSCAN算法的python实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。