侯雄文

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

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

中圖分類號：TP31 文獻標識碼：A

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

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

1 DBSCAN算法

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

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

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

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

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

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

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

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

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

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

2 KNA-DBSCAN算法

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

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

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

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

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

2.1 KNA-DBSCAN算法的思想是

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

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

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

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

2.2 KNA-DBSCAN算法聚類步驟

步驟1：確定Mintps和Eps的值

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

步驟2：進行DBSCAN聚類

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

3結(jié)束語

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

參考文獻

[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].太原：中北大學， 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ù)自適應確定方法的研究[J].西安理工大學學報，2012，28（03）.

[5] 夏魯寧，荊繼武. SA-DBSCAN：一種自適應基于密度聚類算法[J].中國科學院研究生院學報，2009， 26（04）：530-538.endprint