01.DBSCAN簡(jiǎn)述
簡(jiǎn)述
DBSCAN是一種無(wú)監(jiān)督的ML聚類算法，輸入?yún)?shù)為Eps(距離參數(shù))與MinPts(點(diǎn)個(gè)數(shù)閾值），基于密度的聚類算法可以發(fā)現(xiàn)任意形狀的聚類。在基于密度的聚類算法中，通過(guò)在數(shù)據(jù)集中尋找被低密度區(qū)域分離的高密度區(qū)域，將分離出的高密度區(qū)域作為一個(gè)獨(dú)立的類別。
根據(jù)基于中心的密度進(jìn)行點(diǎn)的分類
密度基于中心的方法我們可以將點(diǎn)分類為以下3個(gè)：
- 核心點(diǎn)：點(diǎn)的Eps范圍領(lǐng)域內(nèi)點(diǎn)個(gè)數(shù)超過(guò)MinPts閾值
- 邊界點(diǎn)：非核心點(diǎn)，但落于核心點(diǎn)鄰域內(nèi)，單個(gè)邊界點(diǎn)可能落于多個(gè)核心點(diǎn)鄰域內(nèi)
- 噪聲點(diǎn)：非核心點(diǎn)也非邊界點(diǎn)的任何點(diǎn)
優(yōu)勢(shì)與缺陷
DBSAN使用簇的基于密度的定義，因此它是相對(duì)抗噪聲的，能夠處理任意形狀和大小的簇，這一特點(diǎn)使其能夠發(fā)現(xiàn)使用K均值等其他距離聚類方式無(wú)法發(fā)現(xiàn)的簇。
在簇的密度變化過(guò)大的情況下，該聚類方式的靈敏度會(huì)大幅下降。同時(shí)在遇到高維數(shù)據(jù)時(shí)，對(duì)密度定義相對(duì)困難，需要進(jìn)行額外降維。
02.DBSCAN代碼解析（基于Python，以鳶尾花數(shù)據(jù)為例）
詳細(xì)算法
計(jì)算歐氏距離：
def find_core(j, x, eps):
N = list()
for i in range(x.shape[0]):
temp = np.sqrt(np.sum(np.square(x[j] - x[i]))) # 計(jì)算歐式距離
if temp <= eps:
N.append(i)
return set(N)具體聚類過(guò)程：
def DBSCAN(X, eps, min_Pts):
k = -1
eps_list = []
core_list = []
point = set([x for x in range(len(X))])
cluster = [-1 for _ in range(len(X))]# 進(jìn)行聚類
for i in range(len(X)):
eps_list.append(find_core(i, X, eps))
if len(eps_list[-1]) >= min_Pts:
core_list.append(i)
core_list = set(core_list)
while len(core_list) > 0:
point1 = copy.deepcopy(point)
j = random.choice(list(core_list))#隨機(jī)選取核心點(diǎn)
k = k + 1
Q = list()
Q.append(j)
point.remove(j)
while len(Q) > 0:
q = Q[0]
Q.remove(q)
if len(eps_list[q]) >= min_Pts:
delta = eps_list[q] & point
deltalist = list(delta)
for i in range(len(delta)):
Q.append(deltalist[i])
point = point - delta
ball = point1 - point
listball = list(ball)
for i in range(len(ball)):
cluster[listball[i]] = k
core_list = core_list - ball
return cluster結(jié)果展示
eps=0.5、min_Pts=9（以鳶尾花數(shù)據(jù)為例）
03.Scikit-learn中的DBSCAN的使用
Scikit-learn中集成了DBSCAN算法，具體參數(shù)如下：
def __init__(self, eps=0.5, min_samples=5, metric='euclidean',
metric_params=None, algorithm='auto', leaf_size=30, p=None,
n_jobs=1)