一、前言
去年學聚類算法的R語言的時候,有層次聚類、系統聚類、K-means聚類、K中心聚類,最後呢,被DBSCAN聚類算法迷上了,為什麼呢,首先它可以發現任何形狀的簇,其次我認為它的理論也是比較簡單易懂的。今年在python這門語言上我打算好好弄弄DBSCAN。下面貼上它的官方解釋:
DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪聲的基于密度的聚類方法)是一種基于密度的空間聚類算法。 該算法将具有足夠密度的區域劃分為簇,并在具有噪聲的空間資料庫中發現任意形狀的簇,它将簇定義為密度相連的點的最大集合。
二、DBSCAN聚類算法
文字看不懂看下面這個圖。下面這些點是分布在樣本空間的衆多樣本,現在我們的目标是把這些在樣本空間中距離相近的聚成一類。我們發現A點附近的點密度較大,紅色的圓圈根據一定的規則在這裡滾啊滾,最終收納了A附近的5個點,标記為紅色也就是定為同一個簇。其它沒有被收納的根據一樣的規則成簇。(形象來說,我們可以認為這是系統在衆多樣本點中随機選中一個,圍繞這個被選中的樣本點畫一個圓,規定這個圓的半徑以及圓内最少包含的樣本點,如果在指定半徑内有足夠多的樣本點在内,那麼這個圓圈的圓心就轉移到這個内部樣本點,繼續去圈附近其它的樣本點,類似傳銷一樣,繼續去發展下線。等到這個滾來滾去的圈發現所圈住的樣本點數量少于預先指定的值,就停止了。那麼我們稱最開始那個點為核心點,如A,停下來的那個點為邊界點,如B、C,沒得滾的那個點為離群點,如N)。
基于密度這點有什麼好處呢,我們知道kmeans聚類算法隻能處理球形的簇,也就是一個聚成實心的團(這是因為算法本身計算平均距離的局限)。但往往現實中還會有各種形狀,比如下面兩張圖,環形和不規則形,這個時候,那些傳統的聚類算法顯然就悲劇了。于是就思考,樣本密度大的成一類呗。呐這就是DBSCAN聚類算法。
三、參數選擇
上面提到了紅色圓圈滾啊滾的過程,這個過程就包括了DBSCAN算法的兩個參數,這兩個參數比較難指定,公認的指定方法簡單說一下:
- 半徑:半徑是最難指定的 ,大了,圈住的就多了,簇的個數就少了;反之,簇的個數就多了,這對我們最後的結果是有影響的。我們這個時候K距離可以幫助我們來設定半徑r,也就是要找到突變點,比如:
以上雖然是一個可取的方式,但是有時候比較麻煩 ,大部分還是都試一試進行觀察,用k距離需要做大量實驗來觀察,很難一次性把這些值都選準。
- MinPts:這個參數就是圈住的點的個數,也相當于是一個密度,一般這個值都是偏小一些,然後進行多次嘗試
四、DBSCAN算法疊代可視化展示
國外有一個特别有意思的網站:https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
它可以把我們DBSCAN的疊代過程動态圖畫出來
設定好參數,點選GO! 就開始聚類了!
直接跳到最後看一下DBSCAN的聚類結果,如下:
如果minPoints參數設定再大一點,那麼這個笑臉可能會更好看。沒有顔色标注的就是圈不到的樣本點,也就是離群點,DBSCAN聚類算法在檢測離群點的任務上也有較好的效果。如果是傳統的Kmeans聚類,我們也來看一下效果:
是不是好醜,這完美的展現出來DBSCAN算法基于密度聚類的優勢了啊.
五、常用的評估方法:輪廓系數
這裡提一下聚類算法中最常用的評估方法——輪廓系數(Silhouette Coefficient):
ji
- 計算樣本i到同簇其它樣本到平均距離ai。ai越小,說明樣本i越應該被聚類到該簇(将ai稱為樣本i到簇内不相似度)。
- 計算樣本i到其它某簇Cj的所有樣本的平均距離bij,稱為樣本i與簇Cj的不相似度。定義為樣本i的簇間不相似度:bi=min(bi1,bi2,...,bik2)
- si接近1,則說明樣本i聚類合理
- si接近-1,則說明樣本i更應該分類到另外的簇
- 若si近似為0,則說明樣本i在兩個簇的邊界上
六、用Python實作DBSCAN聚類算法
-
import pandas as pd
-
# 導入資料
-
beer = pd.read_csv('data.txt', sep=' ')
-
print(beer)
輸出結果:
-
from sklearn.cluster import DBSCAN
-
X = beer[["calories","sodium","alcohol","cost"]]
-
# 設定半徑為10,最小樣本量為2,模組化
-
db = DBSCAN(eps=10, min_samples=2).fit(X)
-
labels = db.labels_
-
beer['cluster_db'] = labels # 在資料集最後一列加上經過DBSCAN聚類後的結果
-
beer.sort_values('cluster_db')
-
# 注:cluster列是kmeans聚成3類的結果;cluster2列是kmeans聚類成2類的結果;scaled_cluster列是kmeans聚類成3類的結果(經過了資料标準化)
-
# 檢視根據DBSCAN聚類後的分組統計結果(均值)
-
print(beer.groupby('cluster_db').mean())
-
# 畫出在不同兩個名額下樣本的分布情況
-
print(pd.scatter_matrix(X, c=colors[beer.cluster_db], figsize=(10,10), s=100))
-
# 我們可以從上面這個圖裡觀察聚類效果的好壞,但是當資料量很大,或者名額很多的時候,觀察起來就會非常麻煩。
-
from sklearn import metrics
-
# 就是下面這個函數可以計算輪廓系數(sklearn真是一個強大的包)
-
score = metrics.silhouette_score(X,beer.cluster_db)
-
print(score)