基于密度的聚類之DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪聲的基于密度的聚類方法）

1.名詞解釋

給出半徑：Eps；

給出某個點的Eps鄰域内點的個數的門檻值：MinPts。

核心點（core point）：該點的給定鄰域内的點的個數≥MinPts；

邊界點（border point）：不是核心點，但落在核心點的鄰域内；

噪聲點（noise point）：除了核心點和邊界點以外的點。

Eps鄰域：與某個點的距離小于等于Eps的所有點的集合；

直接密度可達：對于樣本集合D，如果樣本點q在p的Eps領域内，并且p為核心對象，那麼對象q從對象p直接密度可達；

密度可達：對于樣本集合D，給定一串樣本點p1,p2….pn，p= p1,q= pn,假如對象pi從pi-1直接密度可達，那麼對象q從對象p密度可達。

2.DBSCAN算法流程

輸入：Eps，MinPts，樣本集合D

輸出：生成的簇

（下面的步驟來自《資料挖掘導論》[美]Pang-Ning Tan，Michael Steinbach，Vipin Kumar 著，範明，範宏建等譯）