摘要

DBSCAN（Density-Based Spatial Clustering of Applications with Noise） 為一種基于密度的聚類演算法，本文主要介紹了DBSCAN演算法的原理和引數選擇方法，并實作了一個離群值檢測案例，供讀者參考，

1. DBSCAN演算法原理

1.1 基本概念定義

DBSCAN演算法主要有兩個引數：
領域半徑：Eps；
成為核心物件的在領域半徑內的最少點數：MinPts，
以上兩個引數都會在下面的概念介紹中提到，

• Eps領域(Eps-neighborhood of a point)
  點p的Eps鄰域，記為N_Eps（p），定義為N_Eps（p）= {q∈D | dist(p,q)≤Eps}，

• 核心物件 (core points)
  如果給定物件Eps領域內的樣本點數大于等于MinPts，則稱該物件為核心物件，

• 直接密度可達(directly density-reachable)
  若：
  1） p∈ N_Eps(q)
  2）|N_Eps(q)| ≥ MinPts
  則稱物件p從核心物件q是直接密度可達的，

• 密度可達（density-reachable)
  對于物件p₁,p₂, …, p_n；
  令p₁= q, p_n = p，
  若p_i+1是從p_i直接密度可達的，則稱p是從q密度可達的，

• 密度相連(density-connected)
  對于點p和點q，若點p點q都是從點o密度可達的，則稱點p和點q密度相連，

• 簇(cluster)
  對于資料集D，若C是其中一個簇，C中的點需要滿足以下兩個條件：
  1）? p, q，如果 p∈ C且q 是從p密度可達的，則 q∈ C，
  2）? p, q ∈ C，p和q是密度相連的，

• 噪音(noise)
  不屬于任何簇的點為噪音資料，

1.2 演算法流程

• 1）給定領域半徑：Eps和成為核心物件的在領域半徑內的最少點數：MinPts，
• 2）從任意點p開始，將其標記為”visited“，檢查其是否為核心點（即p的Eps鄰域至少有MinPts個物件），如果不是核心點，則將其標記為噪聲點，否則為p創建一個新的簇C，并且把把p的Eps鄰域中的所有物件都放到候選集合N中，
• -3）迭代地把N中不屬于其它簇的物件添加至C中，在此程序中，對于N中標記為”unvisited"的物件p‘，把它標記為“visited”，并且檢查它的Eps鄰域，如果p’也為核心物件，則p’的Eps鄰域中的物件都被添加至N中，繼續添加物件至C中，直到C不能擴展，即直到N為空，此時，簇C完全生成，
• 4）從剩余的物件中隨機選擇下一個未訪問物件，重復3）的程序，直到所有物件都被訪問，

2. 引數選擇

2.1 領域半徑：Eps的選取方法（k-distance函式）

• 1）選取k值，建議取k為2*維度-1，（其中維度為特征數）
• 2） 計算并繪制k-distance圖，（計算出每個點到距其第k近的點的距離，然后將這些距離從大到小排序后進行繪圖，）
• 3）找到拐點位置的距離，即為Eps的值，
  如下圖所示：
  

2.2 MinPts的選取方法

• MinPts的取值為上述k值加1，即：

M i n P t s = k + 1 MinPts = k+1 MinPts=k+1

3. Python實作

鏈接: 參考我的另一篇博客.

4. 檢測離群值的實體

4.1 導包及設定隨機種子

import numpy as np
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN

np.random.seed(2021)

4.2 生成moon資料并繪圖

data = np.ones([1005,2])
data[:1000] = make_moons(n_samples=1000,noise=0.05,random_state=2022)[0]
data[1000:] = [[-1,-0.5],
                [-0.5,-1],
                [-1,1.5],
                [2.5,-0.5],
                [2,1.5]]
print(data.shape)
plt.scatter(data[:,0],data[:,1],color="c")
plt.show()

4.3 選擇引數

def select_MinPts(data,k):
    k_dist = []
    for i in range(data.shape[0]):
        dist = ((data[i] - data).sum(axis=1)**0.5)
        dist.sort()
        k_dist.append(dist[k])
    return np.array(k_dist)
k = 3  # 此處k取 2*2 -1 
k_dist = select_MinPts(data,k)
k_dist.sort()
plt.plot(np.arange(k_dist.shape[0]),k_dist[::-1])

有明顯拐點

# 由拐點確定鄰域半徑
eps = k_dist[::-1][15]
plt.scatter(15,eps,color="r")
plt.plot([0,15],[eps,eps],linestyle="--",color = "r")
plt.plot([15,15],[0,eps],linestyle="--",color = "r")
plt.show()

4.4 建立聚類模型

dbscan_model = DBSCAN(eps=eps,min_samples=k+1)
label = dbscan_model.fit_predict(data)
print(label)

[ 0  0  0 ... -1 -1 -1]

4.5 可視化展示

class_1 = []
class_2 = []
noise = []
for index,value in enumerate(label):
    if value == 0:
        class_1.append(index)
    elif value == 1:
        class_2.append(index)
    elif value == -1:
        noise.append(index)
plt.scatter(data[class_1,0],data[class_1,1],color="g",label="class 1")
plt.scatter(data[class_2,0],data[class_2,1],color="b",label = "class 2")
plt.scatter(data[noise,0],data[noise,1],color="r",label = "noise")
plt.legend()
plt.show()

by CyrusMay 2021 02 03

你和我背著空空的書包
逃出名為日常的監牢
忘了要長大
忘了要變老
忘了時間有腳
——————五月天（好好）——————