1.算法簡介
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一種基于密度的聚類算法，簇集的劃定完全由樣本的聚集程度決定。聚集程度不足以構(gòu)成簇落的那些樣本視為噪聲點，因此DBSCAN聚類的方式也可以用于異常點的檢測。
2.算法原理
2.1 基本原理
算法的關(guān)鍵在于樣本的‘聚集程度’，這個程度的刻畫可以由聚集半徑和最小聚集數(shù)兩個參數(shù)來描述。如果一個樣本聚集半徑領(lǐng)域內(nèi)的樣本數(shù)達到了最小聚集數(shù)，那么它所在區(qū)域就是密集的，就可以圍繞該樣本生成簇落，這樣的樣本被稱為核心點。如果一個樣本在某個核心點的聚集半徑領(lǐng)域內(nèi)，但其本身又不是核心點，則被稱為邊界點；既不是核心點也不是邊界點的樣本即為噪聲點。其中，最小聚集數(shù)通常由經(jīng)驗指定，一般是數(shù)據(jù)維數(shù)+1或者數(shù)據(jù)維數(shù)的2倍。
通俗地講，核心點就是構(gòu)成一個簇落的核心成員；邊界點就是構(gòu)成一個簇落的非核心成員，它們分布于簇落的邊界區(qū)域；噪聲點是無法歸屬在任何一個簇集的游離的異常樣本。如圖所示。
對于聚成的簇集，這里有三個相關(guān)的概念：密度直達，密度可達，密度相連。
- 密度直達：對一個核心點p，它的聚集半徑領(lǐng)域內(nèi)的有點q，那么稱p到q密度直達。密度直達不具有對稱性。
- 密度可達： 有核心點p1,p2,…,pn，非核心點q，如果pi到pi+1（i=1,2,…,n-1）是密度直達的，pn到q是密度直達的，那么稱核心點pi(i=1,2,…,n)到其他的點是密度可達的。密度可達不具有對稱性。
- 密度相連：如果有核心點P，到兩個點A和B都密度可達，那么稱A和B密度相連。密度相連具有對稱性。
簡單地講，核心點到其半徑鄰域內(nèi)的點是密度直達的；核心點到其同簇集內(nèi)的點是密度可達的；同一個簇集里的成員間是密度相連的。
由定義易知，密度直達一定密度可達，密度可達一定密度相連。密度相連就是對聚成的一個簇集最直接的描述。
2.2 算法描述
輸入：樣本集D，聚集半徑r，最小聚集數(shù)MinPts；
輸出：簇集C1，C2，…,Cn，噪聲集O.
根據(jù)樣本聚集程度，傳播式地劃定聚類簇，并將不屬于任何一個簇的樣本劃入噪聲集合。
- （1）隨機搜尋一個核心點p，
- （2）在核心點p處建立簇C，將r鄰域內(nèi)所有的點加入簇C.
- （3）對鄰域內(nèi)所有未被標(biāo)記的點迭代式進行考察，擴展簇集.若一個鄰域點q為核心點，則將它領(lǐng)域內(nèi)未歸入集合的點加入簇C中.
- （4）重復(fù)以上步驟，直至所有樣本劃入了指定集合；
- （5）輸出簇集C1，C2，…，Cn和噪聲集合O。
3.優(yōu)缺點
3.1 優(yōu)勢
1.可以發(fā)現(xiàn)任意形狀的簇，適用于非凸數(shù)據(jù)集；
2.可以進行異常檢測；
3.不需要指定簇數(shù)，根據(jù)樣本的密集程度適應(yīng)性地聚集。
3.2 不足
1.當(dāng)樣本集密度不均勻，不同簇中的平均密度相差較大時，效果較差；
2.聚集半徑和最小聚集數(shù)兩個參數(shù)需人工指定。
4.示例
假設(shè)二維空間中有下列樣本，坐標(biāo)為(1,2),(1,3),(3,1),(2,2),(9,8),(8,9),(9,9),(18,18)
由DBSCAN算法完成聚類操作。
過程演算：
由經(jīng)驗指定參數(shù)聚集半徑r=2，最小聚集數(shù)MinPts=3。
- （1）隨機搜尋一個核心點，若不存在，返回噪聲集合。考察點(1,2)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共三個樣本點，達到了MinPts數(shù)，因此(1,2)為核心點。
- （2）在核心點(1,2)處建立簇C1，原始簇成員為r鄰域內(nèi)樣本：(1,2)、(1,3)、(2,2)。
- （3）對簇落C1成員迭代式進行考察，擴展簇集。先考察(1,3)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共三個樣本點，達到了MinPts數(shù)，因此(1,3)為核心點，它鄰域內(nèi)的樣本均已在簇C1中，無需進行操作。
再考察(2,2)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共四個樣本點，達到了MinPts數(shù)，因此(2,2)為核心點，將它領(lǐng)域內(nèi)尚未歸入任何一個簇落的點(3,1)加入簇C1。
再考察(3,1)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共兩個樣本點，因此(3,1)是非核心點。
考察結(jié)束，簇集C1擴展完畢。
- （4）在其余未歸簇的樣本點中搜尋一個核心點，若不存在，返回噪聲集合?？疾禳c(9,8)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共三個樣本點，達到了MinPts數(shù)，因此(9,8)為核心點。
- （5）在核心點(9,8)處建立簇C2，原始簇成員為r鄰域內(nèi)樣本：(9,8)、(8,9)、(9,9)。
- （6）對簇落C2成員迭代式進行考察，擴展簇集。先考察(8,9)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共三個樣本點，達到了MinPts數(shù)，因此(8,9)為核心點，它鄰域內(nèi)的樣本均已在簇C2中，無需進行操作。
再考察(9,9)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共三個樣本點，達到了MinPts數(shù)，因此(9,9)為核心點。它鄰域內(nèi)的樣本均已在簇C2中，無需進行操作。
考察結(jié)束，簇集C2擴展完畢。
- （7）在其余未歸簇的樣本點中搜尋一個核心點，若不存在，返回噪聲集合。其余未歸簇的樣本點集合為{(18,18)}，考察(18,18)，它到各點的距離分別為
在它的r鄰域內(nèi)，包括了自身在內(nèi)的共一個樣本點，未達到MinPts數(shù)，因此(18,18)為非核心點。其余未歸簇的樣本中不存在核心點，因此歸入噪聲集O={(18,18)}。
- （8）輸出聚類結(jié)果
簇類C1：{(1,2),(1,3),(3,1),(2,2)}
簇類C2：{(9,8),(8,9),(9,9)}
噪聲集O：{(18,18)}
5.Python代碼
'''
功能：用python實現(xiàn)DBSCAN聚類算法。
'''
from sklearn.cluster import DBSCAN
import numpy as np
import matplotlib.pyplot as plt
# 初始化數(shù)據(jù)
data = np.array([(1,2),(1,3),(3,1),(2,2),
(9,8),(8,9),(9,9),
(18,18)])
# 定義DBSCAN模型
dbscan = DBSCAN(eps=2,min_samples=3)
# 計算數(shù)據(jù)，獲取標(biāo)簽
labels = dbscan.fit_predict(data)
# 定義顏色列表
colors = ['b','r','c']
T = [colors[i] for i in labels]
# 輸出簇類
print('\n 聚類結(jié)果： \n')
ue = np.unique(labels)
for i in range(ue.size):
CLS = []
for k in range(labels.size):
if labels[k] == ue[i]:
CLS.append(tuple(data[k]))
print('簇類{}:'.format(ue[i]),CLS)
# 結(jié)果可視化
plt.figure()
plt.scatter(data[:,0],data[:,1],c=T,alpha=0.5) # 繪制數(shù)據(jù)點
plt.show()
文章來源：http://www.zghlxwxcb.cn/news/detail-846051.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-846051.html
到了這里，關(guān)于人工智能|機器學(xué)習(xí)——DBSCAN聚類算法（密度聚類）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
