DBSCAN聚類演算法

1. DBSCAN演算法基本概念

DBSCAN是一種典型的基于密度的聚類演算法，基于一組鄰域 ( ? , M i n P t s ) (\epsilon, MinPts) (?,MinPts)來描述樣本集的緊密程度，其中 ? \epsilon ?描述了某一樣本的鄰域距離閾值， M i n P t s MinPts MinPts描述了某一樣本的距離為 ? \epsilon ?的鄰域中樣本個數的閾值，

在DBSCAN演算法中將資料點分為以下三類：

• 核心點：若樣本 x i x_i xi?的 ? \epsilon ?鄰域內至少包含 M i n P t s MinPts MinPts樣本，即 ∣ N ? ( x i ) ∣ ≥ M i n P t s |N_\epsilon(x_i)| \geq MinPts ∣N??(xi?)∣≥MinPts，則稱樣本點 x i x_i xi?為核心點
• 邊界點：若樣本點 x i x_i xi?的 ? \epsilon ?鄰域內包含的樣本數目小于 M i n P t s MinPts MinPts，但是它在其他核心點的鄰域內，則稱樣本點 x i x_i xi?為邊界點
• 噪音點：既不是核心點也不是邊界點的點

在DBSCAN演算法中還定義了如下概念：

• 密度直達：若樣本點 x j x_j xj?在核心點 x i x_i xi?的 ? \epsilon ?鄰域內，則稱樣本點 x j x_j xj?由 x i x_i xi?密度直達，
• 密度可達：若在樣本點 x i , 1 x_{i,1} xi,1?和樣本點 x i , n x_{i,n} xi,n?之間存在序列 x i , 2 , . . . , x i , n ? 1 x_{i,2},...,x_{i,n-1} xi,2?,...,xi,n?1?，且 x i , j + 1 x_{i,j+1} xi,j+1?由 x i , j x_{i,j} xi,j?密度直達，則稱 x i , n x_{i,n} xi,n?由 x i , 1 x_{i,1} xi,1?密度可達，由密度直達的定義可知，樣本點 x i , 1 , x i , 2 , . . . , x i , n ? 1 x_{i,1},x_{i,2},...,x_{i,n-1} xi,1?,xi,2?,...,xi,n?1?均為核心點
• 密度連接：對于樣本點 x i x_i xi?和樣本點 x j x_j xj?，若存在樣本點 x k x_k xk?，使得 x i x_i xi?和 x j x_j xj?都由 x k x_k xk?密度可達，則稱 x i x_i xi?和 x j x_j xj?密度相連

上圖 M i n P t s = 5 MinPts=5 MinPts=5，紅色的樣本都是核心點，因為其 ? \epsilon ?鄰域至少有5個樣本，黑色的樣本是非核心點，其中紅色樣本鄰域內的黑色樣本為邊界點，其他黑色樣本為噪音點，所有核心點密度直達的樣本在以紅色樣本為中心的超球體內，如果不在超球體內，則不能密度直達，圖中用綠色箭頭連起來的核心點組成了密度可達的樣本序列，在這些密度可達的樣本序列的 ? \epsilon ?鄰域內所有的樣本相互都是密度相連的，

2. DBSCAN聚類演算法流程

輸 入 ： 樣 本 集 D = { x 1 , x 2 , . . . , x n } ， 鄰 域 參 數 ( ? , M i n P t s ) ， 樣 本 距 離 度 量 方 式 輸入：樣本集D=\{x_1,x_2,...,x_n\}，鄰域引數(\epsilon,MinPts)，樣本距離度量方式 輸入：樣本集D={x1?,x2?,...,xn?}，鄰域參數(?,MinPts)，樣本距離度量方式

輸 出 ： 簇 劃 分 C = { C 1 , C 2 , . . . , C k } 輸出：簇劃分C=\{C_1,C_2,...,C_k\} 輸出：簇劃分C={C1?,C2?,...,Ck?}

1. 初始化核心點集合 Ω = ? \Omega=\varnothing Ω=?，初始化聚類簇數 k = 0 k=0 k=0，初始化為訪問集合 Γ = D \Gamma=D Γ=D，簇劃分 C = ? C=\varnothing C=?

2. 對于 i = 1 , 2 , . . . , n i=1,2,...,n i=1,2,...,n，按下面步驟找出所有的核心點：

   • 通過距離度量方式，找到樣本 x i x_i xi?的 ? \epsilon ?鄰域子樣本集 N ? ( x i ) N_\epsilon(x_i) N??(xi?)
   • 如果子樣本集樣本個數滿足 ∣ N ? ( x i ) ∣ ≥ M i n P t s |N_\epsilon(x_i)| \geq MinPts ∣N??(xi?)∣≥MinPts，將樣本 x i x_i xi?加入核心點集合： Ω = Ω ∪ { x i } \Omega=\Omega \cup \{x_i\} Ω=Ω∪{xi?}

3. 如果核心點集合 Ω = ? \Omega=\varnothing Ω=?，結束，否則轉入步驟4

4. 在核心點集合 Ω \Omega Ω中，隨機選擇一個核心點 o o o，初始化當前簇核心點佇列 Ω c u r = { o } \Omega_{cur}=\{o\} Ωcur?={o}，初始化類別序號 k = k + 1 k=k+1 k=k+1，初始化當前簇樣本集合 C k = { o } C_k=\{o\} Ck?={o}，更新為訪問樣本集合 Γ = Γ ? { o } \Gamma=\Gamma-\{o\} Γ=Γ?{o}

5. 如果當前核心點佇列 Ω c u r = ? \Omega_{cur}=\varnothing Ωcur?=?，則當前簇 C k C_k Ck?生成完畢，更新簇劃分 C = { C 1 , C 2 , . . . , C k } C=\{C_1,C_2,...,C_k\} C={C1?,C2?,...,Ck?}，更新核心點集合 Ω = Ω ? C k \Omega=\Omega-C_k Ω=Ω?Ck?，轉入步驟3，否則更新核心點集合 Ω = Ω ? C k \Omega=\Omega-C_k Ω=Ω?Ck?

6. 在當前簇核心點佇列 Ω c u r \Omega_{cur} Ωcur?中取出一個核心點 o ′ o' o′，通過鄰域閾值 ? \epsilon ?找出所有的 ? \epsilon ?鄰域子樣本集 N ? ( o ′ ) N_\epsilon(o') N??(o′)，令 Δ = N ? ( o ′ ) ∩ Γ \Delta=N_\epsilon(o') \cap \Gamma Δ=N??(o′)∩Γ，更新當前簇樣本集合 C k = C k ∪ Δ C_k=C_k \cup \Delta Ck?=Ck?∪Δ，更新為訪問樣本集合 Γ = Γ ? Δ \Gamma = \Gamma - \Delta Γ=Γ?Δ，更新 Ω c u r = Ω c u r ∪ ( Δ ∩ Ω ) ? { o ′ } \Omega_{cur}=\Omega_{cur} \cup (\Delta \cap \Omega)-\{o'\} Ωcur?=Ωcur?∪(Δ∩Ω)?{o′}，轉入步驟5

簡單來說：

1. 根據給定的鄰域引數 ? \epsilon ?和 M i n P t s MinPts MinPts確定所有的核心點
2. 對每一個核心點
3. 選擇一個未處理過的核心點，找到由其密度可達的樣本生成聚類‘簇’
4. 重復以上程序

3. 實體演示

import numpy as np 
import matplotlib.pyplot as plt 

from sklearn import cluster, datasets
from sklearn.preprocessing import StandardScaler

np.random.seed(0)

# 構建資料
n_samples = 1500
noisy_circles = datasets.make_circles(n_samples=n_samples, factor=0.5, noise=0.05)
noisy_moons = datasets.make_moons(n_samples=n_samples, noise=0.05)
blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)

data_sets = [
    (
        noisy_circles,
        {
            "eps": 0.3,
            "min_samples": 5
        }
    ),
    (
        noisy_moons,
        {
            "eps": 0.3, 
            "min_samples": 5
        }
    ), 
    (
        blobs, 
        {
            "eps": 0.3, 
            "min_samples": 5
        }
    )
]
colors = ["#377eb8", "#ff7f00", "#4daf4a"]

plt.figure(figsize=(15, 5))

for i_dataset, (dataset, algo_params) in enumerate(data_sets):
    # 模型引數
    params = algo_params

    # 資料
    X, y = dataset
    X = StandardScaler().fit_transform(X)

    # 創建DBSCAN
    dbscan = cluster.DBSCAN(eps=params["eps"], min_samples=params['min_samples'])

    # 訓練
    dbscan.fit(X)

    # 預測
    y_pred = dbscan.labels_.astype(int)

    y_pred_colors = []

    for i in y_pred:
        y_pred_colors.append(colors[i])
    
    plt.subplot(1, 3, i_dataset+1)

    plt.scatter(X[:, 0], X[:, 1], color=y_pred_colors)

plt.show()

4. DBSCAN小結

優點：

1. 可以對任意形狀的稠密資料集進行聚類，相對的，K-Means、Mean Shift之類的聚類演算法一般只適用于凸資料集
2. 可以在聚類的同時發現例外點，對資料集中的例外點不敏感，
3. 聚類結果沒有偏倚，相對的，K-Means之類的聚類演算法初始值對聚類結果有很大影響，

缺點：

1. 如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質量較差，這時用DBSCAN聚類一般不適合，
2. 如果樣本集較大時，聚類收斂時間較長，此時可以對搜索最近鄰時建立的KD樹或者球樹進行規模限制來改進，
3. 調參相對于傳統的K-Means之類的聚類演算法稍復雜，主要需要對距離閾值 ? \epsilon ?，鄰域樣本數閾值 M i n P t s MinPts MinPts聯合調參，不同的引陣列合對最后的聚類效果有較大影響，