適合多密度的DBSCAN改進算法*

侯思祖, 韓思雨, 韓利釗, 錢雪忠

(1.華北電力大學 電子與通信工程系,河北 保定 071003；2 江南大學 物聯網技術應用教育部工程研究中心,江蘇 無錫 214122)

0 引 言

作為數據挖掘的重要手段之一,聚類分析已經應用到很多領域。如文獻[1]提出了基于聚類分析的SAR圖像變化檢測,應用到圖像處理中；文獻[2]將模糊C均值聚類方法應用于火災預警。具有噪聲的基于密度的空間聚類(density-based spatial clustering of application with noise,DBSCAN)[3]算法,存在2方面問題：1)DBSCAN算法需要用戶在無先驗知識的情況下輸入2個參數Eps和MinPts,對聚類結果影響很大,特別是在密度分布不均勻的多密度數據中,聚類效果不理想。2)DBSCAN時間復雜度為O(N2),限制了其處理大規(guī)模數據的能力。一些研究人員提出了將傳統(tǒng)網格劃分算法[4～6]的思想用于DBSCAN算法中。

本文提出了一種適合多密度的DBSCAN聚類算法,實驗驗證了算法能有效地實現多密度、任意形狀的數據分類。

1 DBSCAN算法

1.1 DBSCAN算法的相關理論

DBSCAN算法的基本思想是：計算每個數據對象以Eps為半徑的鄰域內數據的個數,如果達到密度閾值MinPts，歸為一類,用密度可達將高密度區(qū)域連通形成簇。給定一個包含n個數據的d維數據集D,給定Eps和MinPts,DBSCAN算法中的相關定義如下：

定義1 數據對象?p∈D的Eps鄰域NEps(p)定義為以p為核心,Eps為半徑的d維超球體區(qū)域內包含的點的集合,即NEps(p)={q∈D|dist(p,q)≤Eps},dist(p,q)為D中數據p和q之間的距離。

定義2 對于數據對象p,如果p的Eps鄰域內包含的對象個數滿足|NEps(p)|≥MinPts,稱p為核心對象。

定義3 對于數據對象p,q∈D,滿足q∈NEps(p)且|NEps(p)|≥MinPts,稱q從p關于Eps,MinPts直接密度可達。直接密度可達不滿足對稱性,如圖1(a)所示。

定義4 對于數據對象q,p∈D,如果存在對象序列p1,p2,…,pn∈D,其中,p1=q,pn=p,且pi+1為從pi直接密度可達,則稱p為從q關于Eps,MinPts。密度可達如圖1(b)所示,p3為從p1關于Eps,MinPts密度可達。密度可達不滿足對稱性。

定義5 對于數據對象q,p∈D,如果存在一個數據o使得p和q均從o密度可達,則稱p和q關于Eps,MinPts密度相連。因此,密度相連滿足對稱性。如圖1(c)所示。

圖1 DBSCAN相關概念

1.2 DBSCAN算法步驟

當給定Eps和MinPts時,DBSCAN算法的核心思想為尋找密度相連的最大集合。具體步驟如下：

輸入：數據集D,參數Eps和MinPts。

輸出：帶有類標簽的聚類結果。

1)從數據集D中隨機取出一個未處理的數據p,掃描數據集D,查看p的鄰域數據的個數。

2)如果|NEps(p)|≥MinPts,查找密度相連所有數據,作類標簽并標記已處理；否則，標記已處理過,不標記類標簽,下次取數據時不再考慮,等待其他數據進行密度可達或者密度相連時處理。

3)重復步驟(1)、步驟(2),直到所有數據均標記已處理,對于未類標記的數據作為噪聲處理,聚類結束。

可以看出數據共分為3種：在其鄰域內的數據達到密度閾值MinPts；邊界點,其鄰域內的數據未達到密度閾值,但為某一個核心對象的直接密度可達點；噪聲點,其鄰域內數據達不到密度閾值,且不在任何一個核心對象的鄰域內。

2 適合多密度的DBSCAN改進算法

首先根據核心點鄰域內密度的大小對數據集進行排序,然后自適應的選取適合本鄰域的密度閾值MinPts進行聚類。一方面能夠使DBSCAN算法處理多密度數據；另一方面,可以避免數據的輸入順序對聚類結果的影響。

2.1 數據預處理

輸入數據集D,給定半徑參數Eps,掃描數據集依次計算每個數據對象與其他數據對象的距離并以此給數據集D加屬性A,A所記錄的內容為：當前數據對象在半徑Eps鄰域內的對象個數。以屬性A為標準,對數據集D降序排序。排序后數據集設為D1,作為DBSCAN算法的輸入,數據對象輸入順序基本上代表了該對象所在簇密度的高低。

2.2 自適應獲取密度閾值

定義6 初始核心對象：每一個簇聚類開始時第一個核心對象。

首先根據高密度簇(即數據集D1的第一個數據所在的簇)獲取一個初始的密度閾值MinPts,該參數僅用于對第一個簇進行聚類,聚類結束后,從未被聚類的數據對象中選取屬性A最大的對象作為核心對象,自適應地獲取密度閾值MinPts

(1)

式中NEps(A)為當前數據對屬性A的值；NEps(maxA)為數據集D1第一個數據對象屬性A的值。每聚類一次,密度閾值隨著初始核心對象鄰域的密度值改變。

根據不同密度使用不同的密度閾值,使DBSCAN算法對數據分布的適應性更強。

2.3 算法具體描述

對數據集進行預處理,根據輸入的參數Eps和MinPts以第一個數據對象作為初始核心對象,進行聚類；在未被處理的數據中選取屬性A的值最大的對象作為初始核心對象；依次進行下去,直到剩余未處理的數據無法形成一個類為止(剩余任何對象中在其Eps鄰域范圍內的數據個數小于4)。

當給定Eps和MinPts時,適合多密度的DBSCAN算法的具體步驟如下：

輸入：數據集D,參數Eps和MinPts。

輸出：帶有類標簽的聚類結果。

1)根據參數Eps對數據進行預處理,生成含有屬性A的數據集D1；

2)選取D1中第一個數據作為初始核心對象,用參數Eps和MinPts進行DBSCAN擴展聚類,并對已經聚類的數據做已處理標記,直到該簇聚類結束；

3)從未被聚類的數據中按D1的順序選取初始聚類核心對象,利用獲得的密度閾值和半徑參數Eps進行DBSCAN擴展聚類；

4)重復步聚(3),剩余的對象不存在核心對象時,聚類結束。

2.4 時間復雜度分析

設聚類結果最終生成K個簇K?N,N為數據對象個數,相較于DBSCAN算法,該算法在時間上只多了2部分：數據預處理的時間,時間復雜度為O(n2)；計算密度閾值時間,在聚類過程中共計算K-1次,時間可以忽略不計。綜上,本文提出的算法時間復雜度依然為O(N2)。

3 實驗結果與分析

本文所提算法通過MATLAB工具實現并處理實驗結果。實驗環(huán)境是：CPU為Intel i3 3.7 GHz；內存為4 GB；OS為Windows7。對比了經典的DBSCAN算法和文獻[7]提出的針對多密度的DBSCAN改進算法。

實驗所有結果中的“×”為噪聲點；相同顏色和形狀的為一個簇；設MP為密度閾值。

實驗1 數據集DS1共含有1 927個數據,4個密度不相同的簇,且含有臨界點干擾。聚類結果如圖2所示。

圖2 DS1聚類結果

圖2(a)、圖2(b)本文算法中右下角的簇密度最大,左上角的簇密度較小,且相距較近。圖2(a)中僅有高密度區(qū)域可以形成簇,低密度區(qū)域當作噪聲；圖2(b)中增加聚類半徑,但仍未識別出密度較小的簇,如果再繼續(xù)增加聚類半徑，左上角2個簇被合并成一個簇；圖2(c)中自適應地找到適合本密度的聚類半徑,但左上角2個簇相聚較近,被合并成了一個簇；圖2(d)中每個簇會根據初始聚類核心對象鄰域內數據個數自適應的生成密度閾值,準確識別出了4個簇。

實驗2 數據集DS2共8 000個數據,8個簇,包括多個不同的密度和不同形狀，實驗結果如圖3所示。

實驗2中的聚類結果與實驗1結果類似,由圖3(a)、圖3(b)可以看出，在保證相鄰高密度簇不被合并的情況下,就要損失低密度區(qū)域。圖3(c)與實驗1情況相同。圖3(d)準確識別出了8個簇。

圖3 DS2聚類結果

實驗3 數據集DS3來源于文獻[9]的真實數據集Chameleon,共8 000個數據,6個類簇,實驗對比了經典的DBSCAN算法與2016年馮振華等人提出的針對多密度聚類的DBSCAN改進算法,實驗結果如圖4所示。

圖4 DS3聚類結果

圖4(a)中僅識別出4個簇,造成大量簇信息丟失；圖4(b)中試圖增加半徑參數,識別圖4(a)中未識別的簇,效果較好,識別出5個簇。圖4(c)中識別出了6個簇,且簇與簇之間的連接處的“橫線”干擾數據進行了準確識別,但邊界處吸收量較多的噪聲。圖4(d)識別出了6個簇,且邊界數據處理較好,中間“橫線”的識別稍有瑕疵。

4 結束語

經過理論分析和實驗證明,本文提出的適合多密度的DBSCAN聚類算法,可以在一定程度上弱化參數對聚類結果的影響,對數據分布的適應能力更強,聚類效果更優(yōu)。但在效率上與原算法大致相同,不太適合大規(guī)模數據的聚類。