DBSCAN算法簡介
DBSCAN（Density-Based Spatial Clustering of Applications with Noise铅乡，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法斧拍。 該算法將具有足夠密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇旧巾，它將簇定義為密度相連的點的最大集合。
DBSCAN算法原理
DBSCAN參數(shù)
1）eps： DBSCAN算法參數(shù)暑认，即我們的??-鄰域的距離閾值嫉晶，和樣本距離超過??的樣本點不在??-鄰域內(nèi)叶洞。默認值是0.5.一般需要通過在多組值里面選擇一個合適的閾值。eps過大寸爆，則更多的點會落在核心對象的??-鄰域礁鲁，此時我們的類別數(shù)可能會減少， 本來不應(yīng)該是一類的樣本也會被劃為一類赁豆。反之則類別數(shù)可能會增大仅醇，本來是一類的樣本卻被劃分開。
2）min_samples： DBSCAN算法參數(shù)魔种，即樣本點要成為核心對象所需要的??-鄰域的樣本數(shù)閾值析二。默認值是5. 一般需要通過在多組值里面選擇一個合適的閾值。通常和eps一起調(diào)參节预。在eps一定的情況下叶摄，min_samples過大，則核心對象會過少安拟，此時簇內(nèi)部分本來是一類的樣本可能會被標為噪音點蛤吓，類別數(shù)也會變多。反之min_samples過小的話糠赦，則會產(chǎn)生大量的核心對象会傲，可能會導(dǎo)致類別數(shù)過少。
3）metric：最近鄰距離度量參數(shù)拙泽。
4）algorithm：最近鄰搜索算法參數(shù)唆铐，算法一共有三種，第一種是蠻力實現(xiàn)奔滑，第二種是KD樹實現(xiàn)艾岂，第三種是球樹實現(xiàn)。這三種方法在K近鄰法(KNN)原理小結(jié)中都有講述朋其，如果不熟悉可以去復(fù)習下王浴。對于這個參數(shù)脆炎，一共有4種可選輸入，‘brute’對應(yīng)第一種蠻力實現(xiàn)氓辣，‘kd_tree’對應(yīng)第二種KD樹實現(xiàn)秒裕，‘ball_tree’對應(yīng)第三種的球樹實現(xiàn)， ‘a(chǎn)uto’則會在上面三種算法中做權(quán)衡钞啸，選擇一個擬合最好的最優(yōu)算法几蜻。需要注意的是，如果輸入樣本特征是稀疏的時候体斩，無論我們選擇哪種算法梭稚，最后scikit-learn都會去用蠻力實現(xiàn)‘brute’。個人的經(jīng)驗絮吵，一般情況使用默認的 ‘a(chǎn)uto’就夠了弧烤。 如果數(shù)據(jù)量很大或者特征也很多，用"auto"建樹時間可能會很長蹬敲，效率不高暇昂，建議選擇KD樹實現(xiàn)‘kd_tree’，此時如果發(fā)現(xiàn)‘kd_tree’速度比較慢或者已經(jīng)知道樣本分布不是很均勻時伴嗡，可以嘗試用‘ball_tree’急波。而如果輸入樣本是稀疏的，無論你選擇哪個算法最后實際運行的都是‘brute’瘪校。
5）leaf_size：最近鄰搜索算法參數(shù)澄暮，為使用KD樹或者球樹時， 停止建子樹的葉子節(jié)點數(shù)量的閾值渣淤。這個值越小赏寇，則生成的KD樹或者球樹就越大，層數(shù)越深价认，建樹時間越長嗅定，反之，則生成的KD樹或者球樹會小用踩，層數(shù)較淺渠退，建樹時間較短。默認是30. 因為這個值一般只影響算法的運行速度和使用內(nèi)存大小脐彩，因此一般情況下可以不管它碎乃。
6） p: 最近鄰距離度量參數(shù)。只用于閔可夫斯基距離和帶權(quán)重閔可夫斯基距離中p值的選擇惠奸，p=1為曼哈頓距離梅誓， p=2為歐式距離。如果使用默認的歐式距離不需要管這個參數(shù)。
待聚類點分為三類：
1）核心點：如果一個對象在其半徑 eps 內(nèi)含有超過 MinPts 數(shù)目的點梗掰，則該對象為核心點嵌言。（如下圖點A）
2）邊界點：如果一個對象在其半徑 eps 內(nèi)含有點的數(shù)量小于 MinPts，但是該對象落在核心點的鄰域內(nèi)及穗，則該對象為邊界點摧茴。（如下圖點B、C）
3）噪音點：如果一個對象既不是核心點也不是邊界點埂陆，則該對象為噪音點苛白。（如下圖點N）
算法流程
1）DBSCAN通過檢查數(shù)據(jù)集中每個點的r鄰域來搜索簇，如果點p的r鄰域包含多于MinPts個點焚虱，則創(chuàng)建一個以p為核心對象的簇购裙；
2）DBSCAN迭代的聚集從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并著摔；
3）當沒有新的帶你添加到任何簇時缓窜，迭代過程結(jié)束定续。
DBSCAN算法python代碼實現(xiàn)
# Author:Sunshine丶天
from sklearn import datasets
import numpy as np
import random
import matplotlib.pyplot as plt
def findNeighbor(j, X, eps):
N = []
for p in range(X.shape[0]): # 找到所有領(lǐng)域內(nèi)對象
temp = np.sqrt(np.sum(np.square(X[j] - X[p]))) # 歐氏距離
if (temp <= eps):
N.append(p)
return N
def dbscan(X, eps, min_Pts):
k = -1
NeighborPts = [] # array,某點領(lǐng)域內(nèi)的對象
Ner_NeighborPts = []
fil = [] # 初始時已訪問對象列表為空
gama = [x for x in range(len(X))] # 初始時將所有點標記為未訪問
cluster = [-1 for y in range(len(X))]
while len(gama) > 0:
j = random.choice(gama)
gama.remove(j) # 未訪問列表中移除
fil.append(j) # 添加入訪問列表
NeighborPts = findNeighbor(j, X, eps)
if len(NeighborPts) < min_Pts:
cluster[j] = -1 # 標記為噪聲點
else:
k = k + 1
cluster[j] = k
for i in NeighborPts:
if i not in fil:
gama.remove(i)
fil.append(i)
Ner_NeighborPts = findNeighbor(i, X, eps)
if len(Ner_NeighborPts) >= min_Pts:
for a in Ner_NeighborPts:
if a not in NeighborPts:
NeighborPts.append(a)
if (cluster[i] == -1):
cluster[i] = k
return cluster
X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.05)
X2, y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]],
random_state=666)
X = np.concatenate((X1, X2))
eps = 0.1
min_Pts = 10
cluster = dbscan(X, eps, min_Pts)
plt.figure(figsize=(12, 9), dpi=80)
plt.scatter(X[:, 0], X[:, 1], c=cluster)
plt.show()
DBSCAN算法sklearn實現(xiàn)
from sklearn.cluster import DBSCAN
from sklearn import datasets
import numpy as np
import matplotlib.pyplot as plt
X1, y1 = datasets.make_circles(n_samples=2000, factor=.6, noise=.05)
X2, y2 = datasets.make_blobs(n_samples=500, n_features=2, centers=[[1.2, 1.2]], cluster_std=[[.1]],
random_state=666)
X = np.concatenate((X1, X2))
eps = 0.1
min_Pts = 10
y_pred = DBSCAN(eps=eps, min_samples=min_Pts, metric='euclidean', metric_params=None, algorithm='auto').fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=y_pred)
plt.show()
DBSCAN算法優(yōu)缺點
優(yōu)點：
（1）聚類速度快且能夠有效處理噪聲點和發(fā)現(xiàn)任意形狀的空間聚類谍咆；
（2）與K-MEANS比較起來，不需要輸入要劃分的聚類個數(shù)私股；
（3）聚類簇的形狀沒有偏倚摹察；
（4）可以在需要時輸入過濾噪聲的參數(shù)。
缺點：
（1）當數(shù)據(jù)量增大時倡鲸，要求較大的內(nèi)存支持I/O消耗也很大供嚎，聚類收斂時間較長，此時可以對搜索最近鄰時建立的 KD 樹或者球樹進行規(guī)模限制來進行改進峭状；
（2）當空間聚類的密度不均勻克滴、聚類間距差相差很大時，聚類質(zhì)量較差优床，因為這種情況下參數(shù)min_samples和eps選取困難劝赔；
（3）算法聚類效果依賴與距離公式選取，實際應(yīng)用中常用歐式距離胆敞，對于高維數(shù)據(jù)着帽，存在“維數(shù)災(zāi)難”。
