一種改進(jìn)的DBSCAN算法

唐亮

摘要：DBSCAN算法是基于密度的聚類算法，傳統(tǒng)的DBSCAN聚類算法在聚類過程中需要遍歷核心點(diǎn)鄰域里的點(diǎn)，這就大大增加了DBSCAN算法的運(yùn)行時(shí)間。針對DBSCAN算法時(shí)間性能低效的問題，提出一種新的改進(jìn)的DBSCAN算法。該算法在不丟失對象的基礎(chǔ)上，通過改變遍歷核心對象鄰域點(diǎn)選取方式來擴(kuò)展類，從減少每次區(qū)域查詢次數(shù)及查詢時(shí)間，提高了算法的時(shí)間性能。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的DBSCAN算法是正確和高效的。

關(guān)鍵詞：聚類；DBSCAN算法；鄰域；核心對象

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼： A 文章編號：1009-3044（2017）06-0132-02

1 概述

聚類分析[1]是數(shù)據(jù)挖掘中的重要組成部分。所謂聚類分析， 就是將一組數(shù)據(jù)集分成多個簇，在同一個簇中的數(shù)據(jù)相似度較高，而不同簇中的數(shù)據(jù)相似度較低，人們能夠通過識別不同數(shù)據(jù)密度分布的區(qū)域發(fā)現(xiàn)數(shù)據(jù)屬性之間的相互關(guān)系。在數(shù)據(jù)挖掘中，人們通過聚類對簇的特點(diǎn)進(jìn)行分析，獲取數(shù)據(jù)分布的信息。此外，人們還將聚類分析作為其他算法數(shù)據(jù)處理的步驟。到現(xiàn)在為止，已經(jīng)有許多聚類算法[2]被提出來了，比如基于劃分的方法KMeans[3]算法、基于層次的聚類算法CURE算法 、基于密度的DBSCAN[4]算法、基于網(wǎng)格的CLIQUE等算法。其中DBSCAN算法可以在數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的聚類，但由于其遍歷節(jié)點(diǎn)的次數(shù)較多，其時(shí)間性能較低。本文提出了一個DBSCAN算法的改進(jìn)方法，該方法使得DBSCAN改進(jìn)算法在時(shí)間性能上有較大提高。

2 基于密度的DBSCAN算法

2.1 基本概念

DBSCAN 算法是使用基于距離的方法對數(shù)據(jù)對象進(jìn)行聚類，聚類結(jié)果是球狀的簇。其思想是：通過檢測數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的Eps鄰域內(nèi)的數(shù)據(jù)點(diǎn)的數(shù)目來搜索簇，如果數(shù)據(jù)點(diǎn)p的鄰域內(nèi)包含的數(shù)據(jù)點(diǎn)的數(shù)目多于MinPts，則創(chuàng)建一個以p為核心對象的簇，然后，聚集直接密度可達(dá)的對象，如果不同簇之間密度可達(dá)，則將簇合并。一直到?jīng)]有新的點(diǎn)添加到簇中結(jié)束。下面給出DBSCAN聚類算法的一些定義[5] 。

定義1：鄰域

對于對象p以半徑為Eps的范圍稱為對象p的Eps鄰域，我們用表示點(diǎn)p的Eps半徑內(nèi)的點(diǎn)的集合，即：

定義2：核心對象

對于給定對象p，如果p點(diǎn)的鄰域內(nèi)包含的數(shù)據(jù)點(diǎn)數(shù)目不小于MinPts，則稱點(diǎn)p為核心對象。

定義3：邊界點(diǎn)

對于給定對象p，如果對象p點(diǎn)不是核心點(diǎn)，但是對象p在核心對象q的鄰域內(nèi)，則稱p為邊界點(diǎn)。

定義4：噪音點(diǎn)

對于給定對象p，如果對象既不是核心點(diǎn)，也不是邊界點(diǎn)，則稱對象p為噪音點(diǎn)。

定義5：直接密度可達(dá)

給定一個對象集合D，如果p在q的Eps鄰域內(nèi)，而q是一個核心對象，則稱對象p 從對象q出發(fā)時(shí)是直接密度可達(dá)的。

定義6：密度可達(dá)

如果存在一組對象，對，是從直接密度可達(dá)的，則對象p是從對象q密度可達(dá)的。

定義7：密度相連

如果存在對象，使對象p和q都是從O密度可達(dá)的，那么對象p到q是密度相連的。

2.2 DBSCAN 算法

DBSCAN 算法是一個基于密度的聚類算法，通過迭代遍歷查找所有和核心點(diǎn)直接密度可達(dá)的數(shù)據(jù)點(diǎn)， 來找到所有簇中包含的密度可達(dá)的數(shù)據(jù)對象[6]，具體的過程如下所示：

1）對于數(shù)據(jù)集D中還沒有被檢查過的數(shù)據(jù)點(diǎn)p，如果數(shù)據(jù)點(diǎn)p未被處理，則檢查該數(shù)據(jù)點(diǎn)Eps鄰域內(nèi)的數(shù)據(jù)點(diǎn)的數(shù)目，若數(shù)據(jù)點(diǎn)數(shù)不小于MinPts，則新建一個簇C，將該數(shù)據(jù)點(diǎn)Eps 鄰域內(nèi)其他所有的數(shù)據(jù)點(diǎn)添加到簇C中 。

2）對于簇C中任意一個還沒有被處理的數(shù)據(jù)點(diǎn)q，檢查它的Eps鄰域，若其鄰域里的數(shù)據(jù)點(diǎn)數(shù)不小于MinPts，則將該數(shù)據(jù)點(diǎn)的鄰域中還沒有屬于任何一個簇的數(shù)據(jù)點(diǎn)加入簇C中 。

3）重復(fù)步驟2），直到?jīng)]有新的對象加入當(dāng)前簇C 。

4）重復(fù)步驟1）?3），直到所有的數(shù)據(jù)點(diǎn)被處理。

DBSCAN算法在聚類過程中，可以發(fā)現(xiàn)數(shù)據(jù)集中任意形狀的簇，但是DBSCAN算法也有其局限性，就是需要對每個數(shù)據(jù)點(diǎn)對象都要進(jìn)行鄰域查詢，時(shí)間性能低。

3 DBSCAN改進(jìn)算法

本文對DBSCAN算法的改進(jìn)思想是：就是在核心對象進(jìn)行鄰域查詢時(shí)無需遍歷鄰域內(nèi)的所有節(jié)點(diǎn)，選擇當(dāng)前鄰域內(nèi)距離核心對象較遠(yuǎn)但未被標(biāo)記的點(diǎn)，以減小鄰域查詢次數(shù)和查詢時(shí)間。算法的聚類過程如下：

1）在數(shù)據(jù)集上隨機(jī)選取一個節(jié)點(diǎn)p 開始鄰域查詢，如果數(shù)據(jù)點(diǎn)p 是核心節(jié)點(diǎn)，則將它鄰域內(nèi)的所有數(shù)據(jù)點(diǎn)點(diǎn)用C進(jìn)行類別標(biāo)記。

2）選擇里核心點(diǎn)p較遠(yuǎn)的點(diǎn)q進(jìn)行鄰域查詢，如果它是核心點(diǎn)，則將q點(diǎn)鄰域里的不在簇C里的點(diǎn)加入到簇C里，如果不是核心點(diǎn)，則繼續(xù)進(jìn)行遍歷，知道將p鄰域里較遠(yuǎn)的數(shù)據(jù)點(diǎn)全部遍歷完為止。

3）重復(fù)以上過程，直到所有節(jié)點(diǎn)都被標(biāo)記。

4 實(shí)驗(yàn)

本文所涉及的算法均是用matlab語言編寫的，并在win7系統(tǒng)環(huán)境下運(yùn)行。

4.1 改進(jìn)算法的對比實(shí)驗(yàn)

為了驗(yàn)證DBSCAN改進(jìn)算法正確性，采用了三個二維數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)驗(yàn)證，如圖1所示：

其中，data1自然聚成6類，data2自然聚成5類，data3自然聚成9類。

本文采用相同的參數(shù)驗(yàn)證DBSCAN算法和改進(jìn)算法，所得到的聚類結(jié)果完全相同，如下圖2所示：

通過對比實(shí)驗(yàn)，我們發(fā)現(xiàn)，DBSCAN算法和其改進(jìn)算法在data1、data2和data3上的運(yùn)行結(jié)果完全一樣，由此可以看出DBSCAN改進(jìn)算法與DBSCAN算法的相同的聚類功效，改進(jìn)算法的正確性得以保證。

4.2 執(zhí)行時(shí)間的對比實(shí)驗(yàn)

測試改進(jìn)算法的時(shí)間對比實(shí)驗(yàn)仍然采用上面的3個數(shù)據(jù)集，期執(zhí)行時(shí)間如表1所示：

從表中可以看出改進(jìn)算法的執(zhí)行時(shí)間總是比DBSCAN算法執(zhí)行時(shí)間少，由此可見，改進(jìn)算法與DBSCAN算法比，其時(shí)間性能高效。

5 結(jié)束語

雖然改進(jìn)算法和DBSCAN算法具有相同的時(shí)間復(fù)雜度，但是DBSCAN需要遍歷每一個核心節(jié)點(diǎn)并計(jì)算其鄰域，而改進(jìn)算法只遍歷距離核心點(diǎn)較遠(yuǎn)的點(diǎn)，降低了計(jì)算量，從而減少了時(shí)間，提高了時(shí)間性能。

參考文獻(xiàn)：

[1] HAN Jia Wei，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟曉峰，譯.北京：機(jī)械工業(yè)出版社，2001.

[2] 楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究[D].杭州：浙江大學(xué)，2005.

[3] KAUFANL， RPUSSEEUW P J.Finding groups in data：Anintroduction to cluster analysis[M] .New York：JohnWiley& Sons，1990.

[4] 陳剛，劉秉權(quán)，吳巖.一種基于高斯分布的自適應(yīng)DBSCAN 算法[J].微電子學(xué)與計(jì)算機(jī)，2013（3）：27-30，34.

[5] 周水庚，周傲英，曹晶，等.一種基于密度的快速聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2000，37（11）：1287-1292.

[6] NANNI M，PEDRESCHI D.Time-focused clustering of trajectories of moving objects[J].Journal of Intelligent Information Systems，2006，27（3）：267-289.