Clustering method 1

DBSCAN（Density-Based Spatial Clustering of Application with Noise）

Published in

Taiwan AI Academy

8 min readJan 10, 2019

分群方法（Clustering method）是統計數據分析的技術，廣泛應用在許多領域，包括機器學習，資料探勘，圖像分析等等。大多分群的算法屬於非監督式學習（Unsupervised learning），像廣為人知的K-means、EM演算法，不同於大多數類神經網路的架構需要透過與Ground truth比較的訓練才能達到分群的效果。

以下將介紹另一個常用的分類方法 —— DBSCAN（Density-based spatial clustering of applications with noise）。

－基本概念－

DBSCAN主要的想法是 —— 所有屬於同一群的資料點，在給定的範圍內必須包含一定數量的資料點。也就是說，在給定的範圍內，屬同一類的集合必須超過一定的密集程度，因此，DBSCAN是一種基於密度的分群方法。然而，範圍的形狀會根據測量距離的方式決定，則表示為dist(p, q)。

此方法首先將資料點分為以下三類：

核心點（core points）：給定點展開半徑為 epsilon 的範圍內，含有超過MinPts數目的資料點，則稱該定點為核心點。（此點屬於高密度點）

設epsilon=2，MinPts = 5，則藍色點為核心點（半徑為2的範圍內包含5個以上的資料點）

邊界點（border points）：給定點展開半徑為epsilon的範圍內，資料點的數量小於MinPts，但是落在核心點的鄰近區域內，則稱該定點為邊界點。（此點在高密度點的鄰近區域）

設epsilon=2，MinPts = 5，則青色點為邊界點（以青色點為圓心，半徑為 2 的區域內僅包含 4 個資料點，但此點落在藍色核心點的鄰近區域內）

雜訊（Noise）：既不屬於核心點也不屬於邊界點則稱之雜訊。（此點屬於離群點）

設epsilon=2，MinPts = 5，則紅色點為雜訊（半徑為 2 的範圍內不包含核心點）

其中epsilon及MinPts為可調整的參數，以下為其他名詞定義：

epsilon鄰域（epsilon-neighborhood）：與給定點 p 的距離小於epsilon的所有點集合，以 N_epsilon 表示，可定義為

直接密度可達（directly density-reachable）：若點 p 在點 q 的 epsilon 鄰域內，且包含的資料點數量超過 MinPts，則稱點 p 從點 q 出發是直接密度可達的。以數學式表示，直接密度可達的點必須符合以下兩條件

密度可達（density-reachable）：若有一連串的點 p_1,…,p_n ，且起始點為點 q（p_1=q），終點為點 p（p_n=p），使得任意點從前一點出發都是直接密度可達的（ p_{i+1} is directly density-reachable from p_i ），則稱點 p 從點 q 出發是密度可達的。

藍色點作為起始點，青色點作為終點。從起始點出發至終點，任意點從前一點出發都是直接密度可達，因此青色點從藍色點出發式密度可達的

－演算法－

輸入：資料集 D，半徑 epsilon，給定點在 epsilon 鄰域內成為核心點的最小點數MinPts
輸出：目標分群集合（Clusters）

將所有資料點分別標記為核心點、邊界點及雜訊。
排除雜訊點。
將兩距離小於 epsilon 的核心點分為同一群。（直接密度可達）
將邊界點分至與鄰近核心點距離小於 epsilon 的群中。（將所有密度可達的點都分為同一類）

－算法實例－

使用Sklearn.cluster.DBSCAN套件：

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn import datasets#create datasets
X,y = datasets.make_blobs(n_samples=50, centers=3, n_features=2, random_state= 20, cluster_std = 1.5)#parameter setting
eps = 2
MinPts = 5#DBSCAN method
model = DBSCAN(eps, MinPts)
model.fit(X)
labels = model.fit_predict(X)#results visualization
plt.figure()
plt.scatter(X[:,0], X[:,1], c = labels)
plt.axis('equal')
plt.title('Prediction')plt.show()

（標示顏色僅是分群結果，沒有順序性）右圖預測的結果大部分都是分對的，但綠色點下面的紫色點被歸為雜訊（因為紫色點與分成綠色、黃色以及藍色群的點距離過遠，且密集程度不夠高）

用於影像分割

import numpy as np
import matplotlib.pyplot as plt
from skimage.transform import rescale
from sklearn.cluster import DBSCAN
import cv2#load image
img = cv2.imread('AIA.png')
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
img = rescale(img, 0.2)
rows, cols, chs= img.shape#convert image shape [rows, cols, 3] into [rows*cols, 3]
feature_img = np.reshape(img, [-1, 3])#parameter setting
eps = 0.02
MinPts = 50#DBSCAN method
db = DBSCAN(eps, MinPts)
db.fit(feature_img)
labels = db.fit_predict(feature_img)#results visualization
fig = plt.figure(figsize = (20, 12))
ax = fig.add_subplot(121)
ax1 = fig.add_subplot(122)    
    
ax.imshow(img)
ax1.imshow(np.reshape(labels, [rows, cols]))plt.show()

左圖為原圖，右圖分割的結果將邊緣的像素大多歸為雜訊（因為在影像上有解析度的問題，在邊緣時會有過渡的顏色，且此顏色與兩側的顏色都差異過大，不易分群）

完整程式：https://gitlab.aiacademy.tw/yuchi/2018November_blog.git

－ DBSCAN算法總結－

優點：

此算法與基於距離的分群法不同，可以任意形狀分群（基於距離的算法大多以類似圓形或凸形的形狀分群）。
不須指定分群的數目。
能分辨雜訊點。

缺點：

容易受給定的參數 epsilon 所影響。epsilon 較大時，會將距離較遠的資料點分為同一群，使得群的數量會較少。反之，epsilon 較小時，考慮資料點間的距離也較近，將出現大量含括資料點較少的群。
資料集的性質（包括集中密度差異大或屬高維度資料集等）會使得 epsilon 和測距的方式選取不易。

－參考資料－

原始論文： Ester, Martin, et al. “A density-based algorithm for discovering clusters in large spatial databases with noise.” Kdd. Vol. 96. №34. 1996.

DBSCAN維基百科：https://en.wikipedia.org/wiki/DBSCAN

sklearn.cluster.DBSCAN套件：https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

Clustering method 1

DBSCAN（Density-Based Spatial Clustering of Application with Noise）

Written by Yuki Liu