聚類-DBSCAN基于密度的空間聚類

1.DBSCAN介紹

密度聚類方法的指導思想是，隻要樣本點的密度大于某門檻值，則将該樣本添加到最近的簇中。

這類算法能克服基于距離的算法隻能發現“類圓形”的聚類的缺點，可發現任意形狀的聚類，且對噪聲資料不敏感。但計算密度單元的計算複雜度大，需要建立空間索引來降低計算量。

DBSCAN
密度最大值算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）是一種基于密度的空間聚類算法。該算法将具有足夠密度的區域劃分為簇，并在具有噪聲的空間資料庫中發現任意形狀的簇，它将簇定義為密度相連的點的最大集合。

基于密度這點有什麼好處呢，我們知道kmeans聚類算法隻能處理球形的簇，也就是一個聚成實心的團（這是因為算法本身計算平均距離的局限）。但往往現實中還會有各種形狀，比如下面兩張圖，環形和不規則形，這個時候，那些傳統的聚類算法顯然就悲劇了。于是就思考，樣本密度大的成一類呗。呐這就是DBSCAN聚類算法

推薦一個很形象的描述DBSCAN的網站，可視化

https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/

2.DBSCAN的重要參數

（1）eps 相當于圈的半徑，越大越小都不好，自己合适調節

（2）min_samples 相當于一個圈中最少的樣本數，不到的話，就被劃分為離散點

（3）metric

3.DBSCAN案例

1 import warnings
 2 warnings.filterwarnings(\'ignore\')
 3 import numpy as np
 4 import matplotlib.pyplot as plt
 5 %matplotlib inline
 6 
 7 from sklearn import datasets
 8 from sklearn.cluster import DBSCAN,KMeans
 9 # noise控制疊加的噪聲的大小
10 X,y = datasets.make_circles(n_samples=1000,noise = 0.1,factor = 0.3)
11 
12 # centers=[[1.5,1.5]] 坐标位置，在1.5,1.5生成
13 X3,y3 = datasets.make_blobs(n_samples=500,n_features=2,centers=[[1.5,1.5]],cluster_std=0.2)
14 
15 # 将兩個資料級聯
16 X = np.concatenate([X,X3])
17 
18 y = np.concatenate([y,y3+2])
19 
20 plt.scatter(X[:,0],X[:,1],c = y)

生成的資料：

1 # kmeans 
2 # 有缺陷
3 kmeans = KMeans(3)
4 kmeans.fit(X)
5 y_ = kmeans.predict(X)
6 plt.scatter(X[:,0],X[:,1],c = y_)

kmeans形成的：可以看出，效果很不好

1 # dbcan
2 dbscan = DBSCAN(eps = 0.15,min_samples=5)
3 dbscan.fit(X)
4 # y_ = dbscan.fit_predict(X)
5 y_ = dbscan.labels_
6 plt.scatter(X[:,0],X[:,1],c = y_)

可以看出來，使用dbscan效果明顯不錯

之後，可以再使用之前kmeans中的評測名額才評測一下

4.總結一下DBSCAN流程：

DBSCAN 從一個沒有被通路過的任意起始資料點開始。這個點的鄰域是用距離 ε（ε 距離内的所有點都是鄰域點）提取的。
如果在這個鄰域内有足夠數量的點（根據 minPoints），則聚類過程開始，并且目前資料點成為新簇的第一個點。否則，該點将會被标記為噪聲（稍後這個噪聲點可能仍會成為聚類的一部分）。在這兩種情況下，該點都被标記為「已通路」。
對于新簇中的第一個點，其 ε 距離鄰域内的點也成為該簇的一部分。這個使所有 ε 鄰域内的點都屬于同一個簇的過程将對所有剛剛添加到簇中的新點進行重複。
重複步驟 2 和 3，直到簇中所有的點都被确定，即簇的 ε 鄰域内的所有點都被通路和标記過。
一旦我們完成了目前的簇，一個新的未通路點将被檢索和處理，導緻發現另一個簇或噪聲。重複這個過程直到所有的點被标記為已通路。由于所有點都已經被通路，是以每個點都屬于某個簇或噪聲。

5.DBSCAN的優缺點

優點：

DBSCAN 與其他聚類算法相比有很多優點。首先，它根本不需要固定數量的簇。它也會将異常值識别為噪聲，而不像均值漂移，即使資料點非常不同，也會簡單地将它們分入簇中。另外，它能夠很好地找到任意大小和任意形狀的簇。

缺點：

DBSCAN 的主要缺點是當簇的密度不同時，它的表現不如其他聚類算法。這是因為當密度變化時，用于識别鄰域點的距離門檻值 ε 和 minPoints 的設定将會随着簇而變化。這個缺點也會在非常高次元的資料中出現，因為距離門檻值 ε 再次變得難以估計。

補充：

密度最大值聚類：其實就是看哪個簇的密度最大的

高局部密度點距離：換句話說，就是找比你有錢的距離你最近的人的距離

根據高局部密度點距離，可以識别簇中心：