徐紅艷 普 蓉 黃法欣 王嶸冰

（遼寧大學(xué)信息學(xué)院 沈陽 110036）

1 引言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)量的不斷膨脹，如何有效地分析這些海量數(shù)據(jù)已經(jīng)成為了目前研究的熱點(diǎn)和難點(diǎn)。聚類分析能夠有效地從海量數(shù)據(jù)中提取出有效信息［1］，DBSCAN 算法（Density-Based Spatial Clustering of Application with Noise）就是經(jīng)典的基于密度的聚類分析方法［2］。此算法能在含有噪聲的數(shù)據(jù)中識別出任意形狀的簇，能夠有效地識別出異常點(diǎn)，因而在文本分類［3］、社區(qū)發(fā)現(xiàn)［4］、垃圾郵件識別［5］等領(lǐng)域都得到廣泛的應(yīng)用。

DBSCAN算法具有很多優(yōu)點(diǎn)，但也存在著難以發(fā)現(xiàn)密度相差較大的簇的缺點(diǎn)。眾多學(xué)者對該算法進(jìn)行了深入的研究和改進(jìn)：Kai［6］等提出一種基于可變類簇的密度比聚類算法，使得當(dāng)類簇間密度差相差較大時，能夠使用單一的閾值就能夠達(dá)到比較理想的聚類效果。然而該聚類算法需要手動輸入的參數(shù)過多，輸入?yún)?shù)對聚類結(jié)果影響較大。Rodriguez［7］等提出DPC聚類算法，它是一種依據(jù)快速搜索與密度峰值共同研究發(fā)現(xiàn)的，該聚類算法能夠有效地檢測出任意一種形狀的簇，但該算法需要計(jì)算局部密度和數(shù)據(jù)點(diǎn)之間的相對距離，計(jì)算量較大。馮振華［8］等提出了一種貪心的DBSCAN改進(jìn)聚類算法名為greedy DBSCAN，采用貪心策略自適應(yīng)地尋找Eps半徑參數(shù)進(jìn)行類簇發(fā)現(xiàn)，但該算法需要手動輸入密度閾值，且聚類效率還有待提高。蔡穎琨［9］等提出了一種能夠屏蔽參數(shù)敏感性的DBSCAN改進(jìn)聚類算法，通過考察類簇間的連接信息并記錄、分析這些連接信息，從而達(dá)到屏蔽鄰域半徑參數(shù)Eps敏感的目的，不過該算法未能解決參數(shù)Eps自適應(yīng)確認(rèn)的問題。

針對上述問題，本文提出了基于網(wǎng)格和密度比的DBSCAN聚類算法，它根據(jù)網(wǎng)格和密度比來解決實(shí)際問題。此算法使用網(wǎng)格劃分的技術(shù)將數(shù)據(jù)空間進(jìn)行?；焖僬业綌?shù)據(jù)點(diǎn)密度值的“峰值”和“低谷”，以確定合適的密度閾值，以糾正由于輸入密度閾值τ不當(dāng)造成聚類結(jié)果不佳的問題；最后對?；蟮臄?shù)據(jù)空間進(jìn)行密度比聚類。

2 相關(guān)研究

2.1 DBSCAN算法

DBSCAN算法的主要思想是：給定一個未被聚類的點(diǎn)，如果它Eps鄰域內(nèi)的密度閾值不小于MinPts，則這個點(diǎn)是核心點(diǎn)。再考察它鄰域內(nèi)的其他點(diǎn)，以同樣的方式判斷其是什么點(diǎn)，一直到所有的點(diǎn)被遍歷到。由于該方法只對核心對象的鄰域密度進(jìn)行擴(kuò)展，因此對于那些形態(tài)不是很規(guī)則的簇，該算法的聚類效果較好。

盡管此算法具有能夠有效識別噪聲點(diǎn)，并且能夠識別任意形狀的簇，且聚類結(jié)果幾乎不依賴于遍歷順序的優(yōu)點(diǎn)［10］。但是它也存在較為明顯的缺點(diǎn)：難以發(fā)現(xiàn)密度相差較大的簇。由于參數(shù)Eps和MinPts是全局唯一的，所以DBSCAN算法只能發(fā)現(xiàn)密度近似的簇。此外，如果類間距離差別比較大，算法結(jié)果也會產(chǎn)生影響，容易產(chǎn)生偏差。

2.2 基于網(wǎng)格的聚類算法

這種聚類算法的工作原理是對數(shù)據(jù)空間進(jìn)行?；?，具體的操作是將數(shù)據(jù)空間進(jìn)行劃分并分割為有限個網(wǎng)格子單元，由此形成網(wǎng)格結(jié)構(gòu)，在該網(wǎng)格結(jié)構(gòu)的基礎(chǔ)上進(jìn)行數(shù)據(jù)分析［11］。該聚類算法只是和網(wǎng)格劃分出的個數(shù)有關(guān)，而與運(yùn)行時的時間復(fù)雜度和數(shù)據(jù)點(diǎn)的個數(shù)無關(guān)。STING算法［12］是一種基于網(wǎng)格的多分辨率的聚類技術(shù)，基于網(wǎng)格的聚類方法對數(shù)據(jù)輸入順序不敏感，可擴(kuò)展性也較強(qiáng)。

與其他聚類算法相比，STING算法有如下優(yōu)點(diǎn)：

1）查詢操作和基于網(wǎng)格劃分的計(jì)算是相互獨(dú)立的，因?yàn)橛?jì)算所需的信息只依賴于相互在每個單元中的統(tǒng)計(jì)信息，而不依賴于查詢。

2）STING算法在網(wǎng)格結(jié)構(gòu)上也優(yōu)于其他的聚類算法，尤其是在動態(tài)更新和處理并發(fā)進(jìn)程的方面；

3）STING算法的效率與其他聚類算法相比也有了很大程度的提高，使用該算法只需對數(shù)據(jù)庫的單元進(jìn)行一次掃描就可以通過計(jì)算得到相應(yīng)的信息，因此聚類的時間復(fù)雜度是O（n）（n為數(shù)據(jù)對象的個數(shù)）。在層次結(jié)構(gòu)建立后時間復(fù)雜度可表示為O（g）（g是最低層網(wǎng)格單元的數(shù)目，g<

此算法也存在下面的不足：

1）STING算法進(jìn)行聚類分析時使用的是多分辨率分析的方法，使用STING算法時聚類結(jié)果的質(zhì)量是由所劃分層次結(jié)構(gòu)的底層粒度來決定的。若它太細(xì)，則會使聚類的處理難度加大，采用STING算法的優(yōu)勢將無法充分發(fā)揮；若底層粒度太粗，則聚類質(zhì)量會大打折扣。

2）此算法在父親單元的構(gòu)造上忽略了其孩子單元和其相鄰單元之間的關(guān)系，會造成簇的邊界不是水平的就是豎直的，不包含斜向的分界線。

3）盡管在選取合適聚類粒度的情況下，STING算法能夠快速對數(shù)據(jù)集進(jìn)行聚類處理，但是會在一定程度上犧牲聚類的準(zhǔn)確度。

2.3 基于密度比的DBSCAN算法——Recon-DBSCAN

為了避免DBSCAN算法將低密度簇中的數(shù)據(jù)點(diǎn)錯誤地歸類為噪聲點(diǎn)，Recon-DBSCAN聚類算法［13］將密度比估計(jì)代替密度估計(jì)，其數(shù)據(jù)點(diǎn)的密度是該點(diǎn)的密度相對于鄰域平均密度進(jìn)行歸一化處理后的值。類簇實(shí)際為被低密度區(qū)域分隔開的局部高密度區(qū)域，Recon-DBSCAN算法使得高密度簇通過歸一化后變?yōu)槊芏容^低的簇，且低密度簇通過歸一化后也變?yōu)槊芏容^高的簇，歸一化后的數(shù)據(jù)能夠被全局閾值τ區(qū)分開來。

圖1（a）僅用DBSCAN單一閾值就能夠?qū)⑷齻€簇進(jìn)行區(qū)分；圖1（b）中的情形利用傳統(tǒng)的DBSCAN聚類算法使用單一閾值無法將所有類簇區(qū)分開來，若取閾值τ1則簇C3中的所有點(diǎn)都被歸為噪聲點(diǎn)；若取閾值為τ2則簇C1和C2將會歸為同一個簇；圖1（c）所示為用密度比估計(jì)替換DBSCAN算法中的密度估計(jì)，通過對數(shù)據(jù)點(diǎn)的密度進(jìn)行歸一化處理，使得可用單一的全局閾值對所有簇進(jìn)行有效區(qū)分。

Recon-DBSCAN聚類算法采用數(shù)據(jù)點(diǎn)的密度比估計(jì)替換該點(diǎn)的密度估計(jì)，然后再對數(shù)據(jù)集進(jìn)行聚類，從而使低密度集群不被DBSCAN算法錯誤地歸于噪聲點(diǎn)。但是，Recon-DBSCAN聚類算法也存在缺點(diǎn)：聚類時需要用戶手動輸入的參數(shù)過多；得到最佳聚類結(jié)果的過程是一個不斷嘗試的過程，無法自適應(yīng)地得到聚類閾值。

圖1 數(shù)據(jù)高斯分布圖

3 基于網(wǎng)格和密度比的DBSCAN聚類算法

3.1 算法思想與框架

針對上述聚類算法中存在的問題，本文使用GRDBSCAN（Grid and Density-ratio Clustering Algorithm based on DBSCAN）聚類算法來處理這些問題，此算法是依據(jù)網(wǎng)格的劃分和密度比的計(jì)算來解決實(shí)際問題。首先通過自適應(yīng)多分辨率的網(wǎng)格劃分的思想把數(shù)據(jù)劃分到多個網(wǎng)格空間中，利用所劃分的網(wǎng)格加快查找到類簇的峰值和低谷，再利用密度估計(jì)來計(jì)算密度比，從而實(shí)現(xiàn)自適應(yīng)地確定密度閾值τ和使用該全局閾值識別數(shù)據(jù)集的基于密度比聚類的目的。

GRDBSCAN算法框架如下：

本文通過劃分網(wǎng)格將數(shù)據(jù)空間進(jìn)行粒化，旨在快速找到數(shù)據(jù)點(diǎn)密度值的“山峰”和“山谷”，以確定基于密度比聚類算法中合適的密度閾值。該算法主要分為網(wǎng)格?；瘮?shù)據(jù)空間、確定閾值和網(wǎng)格單元聚類三個核心環(huán)節(jié)。

圖2 GRDBSCAN框架

3.2 網(wǎng)格?；瘮?shù)據(jù)空間

將數(shù)據(jù)空間進(jìn)行?；哪康氖菫榱藟嚎s數(shù)據(jù)，降低算法的時間復(fù)雜度。STING網(wǎng)格劃分對數(shù)據(jù)進(jìn)行?；跃W(wǎng)格單元數(shù)據(jù)的統(tǒng)計(jì)信息代替原始的數(shù)據(jù)點(diǎn)，從而達(dá)到數(shù)據(jù)壓縮的目的。數(shù)據(jù)?；乃惴?/p>

算法1：數(shù)據(jù)?；惴?/p>

輸入：數(shù)據(jù)樣本集D

算法步驟：

1）將數(shù)據(jù)樣本D歸一化到d維空間中；

2）設(shè)定頂層劃分尺度為l=，對數(shù)據(jù)空間進(jìn)行各個維度的劃分，且頂層網(wǎng)格單元與全局?jǐn)?shù)據(jù)空間的信息相一致；

3）從頂層至底層逐漸?；?，第i+1層的子單元為第i層單元的1/4，當(dāng)?shù)讓泳W(wǎng)格lk≤2ε時停止。

4）掃描整個數(shù)據(jù)集，把數(shù)據(jù)集中的每個點(diǎn)都放入網(wǎng)格劃分后的數(shù)據(jù)空間中，并記錄網(wǎng)格單元的信息（如：網(wǎng)格單元密度、最大值、最小值等），記錄網(wǎng)格單元的個數(shù)為n。

一個服從高斯分布的數(shù)據(jù)集，若存在密度極大值點(diǎn)，則越靠近聚類中心的點(diǎn)密度值越大，越是處于邊界的點(diǎn)，密度值越小，反映在網(wǎng)格密度中也存在同樣的分布規(guī)律。因此能夠?qū)澐趾蟮木W(wǎng)格子空間進(jìn)行信息的統(tǒng)計(jì)，數(shù)據(jù)壓縮等操作，選取網(wǎng)格子單元的邏輯中心點(diǎn)代表該網(wǎng)格，對數(shù)據(jù)空間進(jìn)行壓縮。壓縮后的數(shù)據(jù)點(diǎn)個數(shù)與網(wǎng)格個數(shù)相同，通過數(shù)據(jù)空間的壓縮，可以大大減小由于計(jì)算數(shù)據(jù)點(diǎn)之間的相對距離的計(jì)算量。

3.3 確定閾值

該步驟是為了在?；蟮乃芯W(wǎng)格單元中快速找出極值點(diǎn)。首先，掃描整個數(shù)據(jù)集，即將網(wǎng)格單元中數(shù)據(jù)點(diǎn)的個數(shù)作為網(wǎng)格單元的頻度；然后，利用聚類中心網(wǎng)格單元與其他聚類中心網(wǎng)格單元的距離大，而與其網(wǎng)格單元類簇中其他網(wǎng)格單元的距離小的思路，確定極大值點(diǎn)；最后，利用極小值點(diǎn)為極大值點(diǎn)連線上的密度最小點(diǎn)，得出密度閾值。算法步驟如下。

算法2：確定閾值算法

輸出：密度閾值τ

算法步驟描述：

1）計(jì)算網(wǎng)格單元的密度ρi并降序排列

2）計(jì)算網(wǎng)格單元間的相對距離距離σi，用hi為降序排列的ρi標(biāo)記，即ρh1≥ρh2≥…≥ρhn；兩網(wǎng)格單元a和b的歐氏距離定義如式（1）所示［14］：

3）將網(wǎng)格單元的局部密度和相對距離可視化，如圖3。

圖3 網(wǎng)格局部密度和相對距離可視化

4）由圖3，得出網(wǎng)格空間極大值點(diǎn)

5）極小值點(diǎn)為極大值點(diǎn)連線上的密度最小點(diǎn)，即得出極小值點(diǎn)的集合，選取極小值點(diǎn)的集合中的最大值，其密度即為密度閾值τ。

圖4 三種高斯分布組成的二維數(shù)據(jù)集估計(jì)密度分布的可視化

考慮使用一個全局密度閾值MinPts來區(qū)分所有的類簇。如圖4所示，為了將類簇集合C=｛C1，C2，C3｝區(qū)分開來，則閾值的取值 MinPts大于 p（g12）時方可將三個類簇都區(qū)分開來。然而這樣的劃分方式下，簇C3中的很多點(diǎn)都會被歸類為噪聲點(diǎn)，達(dá)不到很好的聚類效果。

更加糟糕的情形是，若g12處的局部密度p（g12）大于p3處局部密度p（p3）的情況。若取密度閾值MinPts＞p（g12），則C3中的所有數(shù)據(jù)點(diǎn)都會被歸類為噪聲數(shù)據(jù)，聚類的結(jié)果只能得到兩個類；若取密度閾值 MinPts＜p（p3），則簇 C1和 C2將會被歸為同一類，仍然只能得到兩個類。如果能夠用某種方式，能夠使得密度大的區(qū)域的密度降低一些，同時使得密度小的區(qū)域的密度更大一些，使得整個數(shù)據(jù)空間的數(shù)據(jù)對象密度分布更加均勻，減小類簇間的密度差異，使得那么密度平均化之后的是數(shù)據(jù)集能夠被一個全局閾值τ區(qū)分開來。

3.4 網(wǎng)格單元聚類

由基于密度比的DBSCAN算法的聚類過程可知，知道基于密度比的DBSCAN聚類算法需要輸入的參數(shù)包括ε，η和τ三個參數(shù)，通常為了方便衡量ε和η之間的差距，令η=λε，λ∈［1.08，1.09，…，1.16］，由此確定不同λ值對聚類效果的影響。如果能夠自適應(yīng)地確定密度比閾值τ，則只需要根據(jù)λ值確定不同的鄰域密度比與其準(zhǔn)確度之間的影響。

算法3：網(wǎng)格單元聚類算法

輸出：聚類結(jié)果C

算法步驟描述：

1）計(jì)算各網(wǎng)格單元的密度比；

2）根據(jù)算法3得到的極大值和極小值，得到它們的密度比，選取簇谷集合密度比的最大值gij為密度閾值τ；

3）根據(jù)算法1對壓縮后的網(wǎng)格單元E進(jìn)行DBSCAN聚類，根據(jù)閾值τ剔除噪聲網(wǎng)格；

4）得到最終聚類結(jié)果C。

3.5 算法復(fù)雜度分析

本文提出算法的時間開銷包括計(jì)算網(wǎng)格粒化、網(wǎng)格單元的統(tǒng)計(jì)信息、網(wǎng)格單元的相對距離和對壓縮后的數(shù)據(jù)空間進(jìn)行聚類。其中時間開銷最大的就是求網(wǎng)格單元的距離。算法的時間開銷具體如下：

1）劃分網(wǎng)格時產(chǎn)生聚類的時間復(fù)雜度為O(n)，它是通過STING掃描數(shù)據(jù)庫一次計(jì)算單元的統(tǒng)計(jì)信息而得到的，層次結(jié)構(gòu)建立后，查詢處理時間為O(R)，R為底層網(wǎng)格單元的數(shù)目；

2）查找簇峰和簇谷的過程需要求得相對距離，此過程的時間復(fù)雜度為O((n/ε)2)；

3）基于密度的DBSCAN聚類，時間復(fù)雜度為O(R2)；

總的時間復(fù)雜度如式（3）：

由于R是一個遠(yuǎn)小于n的數(shù)，所以算法的時間復(fù)雜度為O((n/ε)2)。

算法的空間復(fù)雜度只與網(wǎng)格單元的數(shù)目有關(guān)，因此算法的空間復(fù)雜度為O((n/ε)2)。

4 實(shí)驗(yàn)與分析

本文實(shí)驗(yàn)所采用的計(jì)算機(jī)硬件配置為AMD E2處理器、8GB內(nèi)存；實(shí)驗(yàn)的軟件環(huán)境為Windows8操作系統(tǒng)，采用Matlab 2014b編譯環(huán)境。為了證明本文所提算法的可行性和有效性，以UCI數(shù)據(jù)庫［15］中 4個公用數(shù)據(jù)集s1、s2、Iris、Segment為測試數(shù)據(jù)集，設(shè)計(jì)了以下實(shí)驗(yàn)進(jìn)行驗(yàn)證。

4.1 密度比值λ對算法的影響

以UCI上的一個人工數(shù)據(jù)集s1進(jìn)行實(shí)驗(yàn)，取閾值ε=0.1523，求得τ=0.8955時，以分類模型的精確率和召回率的調(diào)和平均數(shù)F值來度量本算法的精確度，得出λ和F值的關(guān)系如圖5所示。

圖5 λ與F值間關(guān)系圖

分別對另外3個數(shù)據(jù)集測試λ與F值之間的關(guān)系，得出當(dāng)λ=1.1時，算法效果最好。

4.2 聚類結(jié)果對比

數(shù)據(jù)集s2為一個包含1500個數(shù)據(jù)點(diǎn)的人造數(shù)據(jù)集，ε=0.0108時，求得τ=0.8820。聚類結(jié)果對比如圖6。

圖6 聚類結(jié)果對比

4.3 聚類運(yùn)行時間比較

以UCI數(shù)據(jù)集上的四個人工數(shù)據(jù)集Iris、Segment、s1、s2作為實(shí)驗(yàn)對象，聚類運(yùn)行時間比較如表1。

表1 算法時間復(fù)雜度對比 單位（s）

由表1可以得出，隨著數(shù)據(jù)點(diǎn)個數(shù)增多，三種算法下運(yùn)算時間都增大。由于本文算法與DPC算法都需要計(jì)算，運(yùn)算時間較傳統(tǒng)DBSCAN算法更長。但DPC算法計(jì)算更復(fù)雜、需要被計(jì)算的數(shù)據(jù)點(diǎn)更多，故運(yùn)算時間較長。

4.4 聚類準(zhǔn)確度F值比較

實(shí)驗(yàn)3以UCI數(shù)據(jù)集上的四個人工數(shù)據(jù)集Iris、Segment、s1、s2 作為實(shí)驗(yàn)對象，選取合適的參數(shù)，求得最佳的F值，與DBSCAN算法、DPC算法聚類準(zhǔn)確度F值比較如表2。

表2 F值比較

F值能夠度量一個算法性能的好壞，當(dāng)F值越大時，算法效果越好。通過以上實(shí)驗(yàn)可知，本文算法在選擇合適參數(shù)的情形下，具有較高的F值，明顯優(yōu)于DBSCAN算法，且與DPC算法相差不大。

5 結(jié)語

基于密度比的聚類算法對于密度分布不均勻的簇有較好的聚類效果，因此本文提出GRDBSCAN聚類算法，它依據(jù)網(wǎng)格和密度比的計(jì)算來提高密度分布不均勻的簇的聚類效果。同時它較比其他的聚類算法有了新的優(yōu)點(diǎn)，其一壓縮了數(shù)據(jù)空間，在此基礎(chǔ)上進(jìn)行聚類，提高了運(yùn)算效率；其二能夠自適應(yīng)地得出聚類的密度閾值，降低了因參數(shù)選取不當(dāng)造成的聚類效果不佳的問題。下一步研究如何針對海量數(shù)據(jù)進(jìn)行聚類，以及利用分布式Spark平臺進(jìn)行聚類。