淺析DBSCAN算法中參數(shù)設(shè)置問題的研究

侯雄文

摘 要 傳統(tǒng)的DBSCAN密度聚類算法，需要人為設(shè)置鄰域閾值（Eps）和點(diǎn)數(shù)閾值（minPts）2個(gè)參數(shù)來對(duì)數(shù)據(jù)集進(jìn)行聚類，由于minPts和Eps具有全局性，使得DBSCAN算法對(duì)參數(shù)很敏感， 特別是分布不均勻的數(shù)據(jù)集。針對(duì)DBSCAN算法中這一問題，本文研究改進(jìn)的算法通過對(duì)數(shù)據(jù)點(diǎn)的k最近點(diǎn)平均距離進(jìn)行分析，根據(jù)其統(tǒng)計(jì)特性動(dòng)態(tài)地確定minPts和多個(gè)Eps值，然后根據(jù)所求得的多組（minPts， Eps）值依次對(duì)數(shù)據(jù)集進(jìn)行聚類，從而達(dá)到自適應(yīng)設(shè)置參數(shù)的目的。

關(guān)鍵詞 聚類算法 自適應(yīng) 參數(shù)

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A

聚類算法是數(shù)據(jù)挖掘、模式識(shí)別等研究中的一項(xiàng)重要技術(shù)。聚類的目的是把數(shù)據(jù)集分成若干類或簇，使得同一個(gè)類中的元素相似性較大，不同類中的元素相似性較小。其中，有多種方法來確定DBSCAN的兩個(gè)閾值參數(shù)Eps和minPts。對(duì)于minPts的確定，在數(shù)據(jù)點(diǎn)不多的情況下，minPts在二維空間中的聚類中一般取4. 另外取數(shù)據(jù)集合的1/25作為minPts的值也是一種比較有效的方法。

本文針對(duì)密度分布不均勻的數(shù)據(jù)集的minPts和Eps的取值問題，提出了一種新的改進(jìn)的基于k最近點(diǎn)平均距離的（DBSCAN based on K Nearest Average Distance， KNA-DBSCAN）聚類算法，該算法通過對(duì)數(shù)據(jù)點(diǎn)的k最近點(diǎn)平均距離的統(tǒng)計(jì)特性進(jìn)行分析，自動(dòng)的確定minPts和多個(gè)Eps參數(shù)，使其可以對(duì)密度分布不均勻的數(shù)據(jù)集進(jìn)行聚類。

1 DBSCAN算法

DBSCAN算法是基于中心的密度聚類算法，相關(guān)概念如下：

定義1 數(shù)據(jù)點(diǎn)的Eps鄰域：數(shù)據(jù)集D中任意數(shù)據(jù)點(diǎn)P，P的鄰域Eps（P）定義為以P為中心，Eps半徑的球形區(qū)域，公式表示為：

EPS（p）={q∈D|dist（p，q）≤Eps}

其中dist（p，q）表示數(shù)據(jù)點(diǎn)p和q之間的距離，這里采用歐式距離。

定義2 數(shù)據(jù)點(diǎn)的密度：數(shù)據(jù)集D中任意數(shù)據(jù)點(diǎn)P，所在的Eps鄰域內(nèi)，包含的數(shù)據(jù)點(diǎn)的數(shù)目，叫做數(shù)據(jù)點(diǎn)P的密度。

定義3 核心數(shù)據(jù)點(diǎn)：對(duì)于數(shù)據(jù)點(diǎn)P，p∈D ，如果以P為中心，以Eps為半徑，在Eps（P）內(nèi)的數(shù)據(jù)點(diǎn)的個(gè)數(shù)超過給定的minPts，則稱P為核心數(shù)據(jù)點(diǎn)。

定義4 邊界數(shù)據(jù)點(diǎn)：對(duì)于數(shù)據(jù)點(diǎn)P， p∈D，如果P不是核心數(shù)據(jù)點(diǎn)，但是P在某核心數(shù)據(jù)點(diǎn)q的鄰域Eps（q）內(nèi)，則稱數(shù)據(jù)點(diǎn)p為邊界數(shù)據(jù)點(diǎn)

定義5 噪音點(diǎn)：對(duì)于數(shù)據(jù)點(diǎn)p， p∈D，若p既不是核心數(shù)據(jù)點(diǎn)，也不是邊界數(shù)據(jù)點(diǎn)，則p為噪音點(diǎn)或離群點(diǎn)。

定義6 直接密度可達(dá)：給定數(shù)據(jù)點(diǎn)集D，若數(shù)據(jù)點(diǎn)p在數(shù)據(jù)點(diǎn)q的鄰域內(nèi)，若q為核心數(shù)據(jù)點(diǎn)，則稱從數(shù)據(jù)點(diǎn)p出發(fā)到數(shù)據(jù)點(diǎn)q是直接密度可達(dá)。

定義7 密度相連：若一個(gè)數(shù)據(jù)點(diǎn)o∈D，使得數(shù)據(jù)點(diǎn)p和數(shù)據(jù)點(diǎn)q都從點(diǎn)o在（minPts，Eps）條件下密度可達(dá)，則稱數(shù)據(jù)點(diǎn)p和數(shù)據(jù)點(diǎn)q密度相連，密度相連是對(duì)稱的。

2 KNA-DBSCAN算法

定義8：密度層次：按照數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的密度不同，將數(shù)據(jù)點(diǎn)分為不同的密度層次，密度相近的點(diǎn)簇在同一個(gè)密度層次，數(shù)據(jù)點(diǎn)分布越稠密，密度越大，密度層次也就越大。

對(duì)于分布不均勻的數(shù)據(jù)集，各個(gè)數(shù)據(jù)點(diǎn)與周圍數(shù)據(jù)的相似程度不同，本文采用數(shù)據(jù)點(diǎn)與周圍的數(shù)據(jù)點(diǎn)的距離作為衡量該點(diǎn)稠密程度的判斷標(biāo)準(zhǔn)。采用數(shù)據(jù)集D中數(shù)據(jù)點(diǎn)P的k平均最近距離作為該點(diǎn)稠密程度的評(píng)判標(biāo)準(zhǔn)，則p點(diǎn)的k最近點(diǎn)平均距離與k+1最近點(diǎn)平均距離之差則反映了p點(diǎn)密度的變化，變化越小，則p點(diǎn)當(dāng)前的（k+1）最近點(diǎn)平均距離越能反映p點(diǎn)的密度層次。我們定義密度變化如下：

定義9：密度變化：數(shù)據(jù)點(diǎn)P的k最近點(diǎn)平均距離與k+1最近點(diǎn)平均距離之差 △distak：

對(duì)于數(shù)據(jù)集中所有點(diǎn)的密度變化之和則反映了所有數(shù)據(jù)點(diǎn)的密度變化，當(dāng)密度變化之和最小時(shí)，則大部分點(diǎn)都達(dá)到了自己所在的密度層次。密度變化之和sum_incdistak的計(jì)算公式如下：

其中，pi表示第i個(gè)數(shù)據(jù)點(diǎn)，n表示數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

2.1 KNA-DBSCAN算法的思想是

（1）確定k的取值：首先計(jì)算所有數(shù)據(jù)點(diǎn)的k最近點(diǎn)平均距離，然后計(jì)算所有數(shù)據(jù)點(diǎn)的（k+1） 最近點(diǎn)平均距離，求出所有數(shù)據(jù)點(diǎn)的（k+1） 最近點(diǎn)平均距離與k最近點(diǎn)平均距離的差值即，密度變化，再將這些差值求和，即計(jì)算所有點(diǎn)的密度變化之和，找出其中密度變化之和的最小值，此時(shí)，對(duì)應(yīng)的（k+1） 最近點(diǎn)平均距離最能反映各點(diǎn)的密度層次，所以取此時(shí)的k+1的值作為k的值。

（2）確定minPts的值：k值確定后，取minPts=k。

（3）確定多個(gè)Eps的值：k值確定后，對(duì)所有點(diǎn)的k最近點(diǎn)平均距離求取對(duì)數(shù)，取對(duì)數(shù)之后不會(huì)改變數(shù)據(jù)的性質(zhì)和相關(guān)關(guān)系，但壓縮了變量的尺度，使數(shù)據(jù)變得更穩(wěn)定。這里我們將其定義為數(shù)據(jù)點(diǎn)的對(duì)數(shù)距離，數(shù)據(jù)點(diǎn)p的對(duì)數(shù)距離計(jì)算公式如下：

定義10：密度轉(zhuǎn)折點(diǎn)：若在某數(shù)據(jù)點(diǎn)Pm處，Pm+1的distak-log的值相對(duì)于Pm的distak-bg值突然增大，則稱Pm為密度轉(zhuǎn)折點(diǎn)。Pm對(duì)應(yīng)的distak值即為對(duì)應(yīng)的一個(gè)密度閾值Eps。

2.2 KNA-DBSCAN算法聚類步驟

步驟1：確定Mintps和Eps的值

根據(jù)KNA-DBSCAN算法思想對(duì)數(shù)據(jù)集進(jìn)行計(jì)算，得到minPts和Eps的值，對(duì)于密度單一的數(shù)據(jù)集，得到的Eps只有一個(gè)，對(duì)于含有多個(gè)密度層次的數(shù)據(jù)集，得到多個(gè)Eps值。

步驟2：進(jìn)行DBSCAN聚類

對(duì)數(shù)據(jù)集進(jìn)行DBSCAN聚類，按照Eps從小到大依次進(jìn)行聚類，先聚較高密度的簇，再聚較低密度的簇。將聚類成功的類標(biāo)記為Ci（i≥1），表示數(shù)據(jù)集的第i個(gè)簇。對(duì)所有的（minPts，Eps）進(jìn)行聚類后，沒有被標(biāo)記的點(diǎn)記為離群點(diǎn)或噪音點(diǎn)。

3結(jié)束語(yǔ)

本文在DBSCAN算法的基礎(chǔ)上，提出了參數(shù)自適應(yīng)的KNA-DBSCAN算法，該算法可以根據(jù)數(shù)據(jù)集的特點(diǎn)自動(dòng)地確定minPts和多個(gè)Eps參數(shù)，有效地解決了DBSCAN算法對(duì)參數(shù)敏感的問題。

參考文獻(xiàn)

[1] Chen，M.S.&J.Han.&P.S，Yu .Data mining：an overview from a database perspective [J]. Knowledge and data Engineering， IEEE Transactions on， 1996， 8（06）： 866-883.

[2] 孫凌燕.基于密度的聚類算法研究[D].太原：中北大學(xué)， 2009.

[3] Daszykowski，M.&B.Walczak&D.L.Massart.Looking for natural patterns in data： Part 1. Density-based approach[J]. Chemometrics and Intelligent Laboratory Systems，2001，56（02）： 83-92.

[4] ZHOU，H.& P.WANG.DBSCAN 算法中參數(shù)自適應(yīng)確定方法的研究[J].西安理工大學(xué)學(xué)報(bào)，2012，28（03）.

[5] 夏魯寧，荊繼武. SA-DBSCAN：一種自適應(yīng)基于密度聚類算法[J].中國(guó)科學(xué)院研究生院學(xué)報(bào)，2009， 26（04）：530-538.endprint