基于網(wǎng)格篩選的大規(guī)模密度峰值聚類算法

徐 曉 丁世飛 孫統(tǒng)風(fēng) 廖紅梅

(中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇徐州 221116) (xu_xiao@cumt.edu.cn)

信息技術(shù)的飛速發(fā)展以及互聯(lián)網(wǎng)的普及，使得數(shù)據(jù)更新速度快、數(shù)據(jù)源多樣、數(shù)據(jù)量以空前的速度增長(zhǎng).面對(duì)大規(guī)模數(shù)據(jù)存儲(chǔ)難、計(jì)算復(fù)雜度高等一系列的問題，如何對(duì)大規(guī)模數(shù)據(jù)集進(jìn)行有效的數(shù)據(jù)挖掘、快速獲取有價(jià)值的信息，已經(jīng)成為人們研究的焦點(diǎn)[1].聚類學(xué)習(xí)是一種重要的數(shù)據(jù)分析技術(shù)，能從復(fù)雜的數(shù)據(jù)中發(fā)現(xiàn)有用的信息[2-3].可以先對(duì)數(shù)據(jù)進(jìn)行聚類,根據(jù)數(shù)據(jù)對(duì)象的相關(guān)特征,將相似的對(duì)象歸到同一類中,而差別較大的對(duì)象劃分到不同類中,找到數(shù)據(jù)之間的內(nèi)在聯(lián)系,為決策提供支持.聚類分析在市場(chǎng)分析、模式識(shí)別、基因研究、圖像處理等領(lǐng)域具有一定的應(yīng)用價(jià)值[4].

2014年Rodríguez和Laio[5]提出了一種新的密度峰值聚類算法(density peaks clustering algorithm, DPC).聚類中心具有2大特點(diǎn)：1)聚類中心本身的密度較大，即被密度均不超過它的鄰居包圍；2)聚類中心與其他密度更大的數(shù)據(jù)點(diǎn)之間的“距離”相對(duì)更大.DPC利用上述2大特點(diǎn)繪制決策圖，找到聚類中心，然后對(duì)剩余的點(diǎn)進(jìn)行高效分配[6].由于聚類中心是密度和距離2個(gè)屬性值均較大的點(diǎn)，所以稱之為密度峰值，該算法稱為密度峰值聚類算法.密度峰值聚類算法可以用于不同形狀數(shù)據(jù)的聚類分析，不需要預(yù)先設(shè)定類簇?cái)?shù)，通過決策圖快速發(fā)現(xiàn)密度峰值，得到比較滿意的聚類結(jié)果.

盡管密度峰值聚類算法在規(guī)模較小的數(shù)據(jù)集上表現(xiàn)很好，但是它依舊存在多方面不足：1)在計(jì)算局部密度時(shí)沒有采用統(tǒng)一的密度度量標(biāo)準(zhǔn)，參數(shù)dc的選取對(duì)聚類結(jié)果影響較大.2)如果數(shù)據(jù)點(diǎn)的個(gè)數(shù)n很大，密度峰值聚類算法將會(huì)把所有點(diǎn)都作為選取聚類中心的候選數(shù)據(jù)點(diǎn).計(jì)算n個(gè)點(diǎn)的局部密度和距離屬性都依賴于點(diǎn)與點(diǎn)之間的相似度矩陣，需要的時(shí)間復(fù)雜度為O(n2)，時(shí)間開銷會(huì)嚴(yán)重降低聚類的處理效率.同時(shí)，存儲(chǔ)相似度矩陣需要的空間復(fù)雜度也是O(n2)，因此，對(duì)于密度峰值聚類算法而言，可供使用的內(nèi)存空間將是其處理數(shù)據(jù)規(guī)模的上限.對(duì)于通常的計(jì)算設(shè)備來說，內(nèi)存空間畢竟有限，這將使得密度峰值聚類算法失去處理較大規(guī)模數(shù)據(jù)的能力.

當(dāng)前，在密度峰值聚類算法研究領(lǐng)域，針對(duì)第1個(gè)弊端的研究居多.Du等人[7]提出DPC-KNN聚類算法，其將KNN的概念引入到密度峰值聚類算法中，dc的選取不局限于局部，使局部密度的計(jì)算有另一選擇.Xie等人[8]利用樣本點(diǎn)的KNN信息定義樣本局部密度，搜索和發(fā)現(xiàn)樣本的密度峰值，以峰值點(diǎn)作為初始類簇中心來改進(jìn)密度峰值聚類算法.Zhou等人[9]提出一種名為3DC的聚類算法，是密度峰值聚類算法的改進(jìn)版本.3DC算法由分治策略和DBSCAN框架中密度可達(dá)性概念驅(qū)動(dòng)，考慮數(shù)據(jù)的全局分布，遞歸地找到正確的簇?cái)?shù).但是對(duì)于第2個(gè)弊端的研究甚少.僅在2015年鞏樹鳳和張巖峰[10]提出一種高效的分布式密度中心聚類算法(EDDPC)，它利用Voronoi分割與合理的數(shù)據(jù)復(fù)制及過濾，避免了大量無用的距離計(jì)算開銷和數(shù)據(jù)傳輸開銷.Zhang等人[11]提出一種在MapReduce上聚類大數(shù)據(jù)集的高效分布式密度峰值聚類算法，利用局部敏感Hash進(jìn)行分區(qū)數(shù)據(jù)的近似算法，執(zhí)行本地計(jì)算，并聚合局部結(jié)果近似最終結(jié)果.然而，采用分布式雖然在一定程度上解決了大規(guī)模高維數(shù)據(jù)的計(jì)算復(fù)雜度問題，但在每次迭代過程中，節(jié)點(diǎn)間傳送大量的數(shù)據(jù)帶來巨大的通信代價(jià)，其遠(yuǎn)遠(yuǎn)大于計(jì)算代價(jià)，總體效率較低[12].同時(shí)，分布式計(jì)算涉及多臺(tái)計(jì)算機(jī)，而且都依賴網(wǎng)絡(luò)通信，因此1臺(tái)或者多臺(tái)計(jì)算機(jī)，1條或者多條網(wǎng)絡(luò)出現(xiàn)故障都將影響分布式系統(tǒng)，而且一旦出現(xiàn)問題不易排除[13-14].對(duì)于大規(guī)模數(shù)據(jù)的處理任務(wù)，抽樣的策略是通常的選擇，然而隨機(jī)抽樣往往會(huì)產(chǎn)生糟糕的聚類結(jié)果，同時(shí)抽樣的規(guī)模多大才能覆蓋原數(shù)據(jù)集的所有自然簇等問題難以解決[15].SVM通過挑選位于分類超平面附近的訓(xùn)練樣本作為最終的訓(xùn)練集，從而在確保分類器準(zhǔn)確率的情況下實(shí)現(xiàn)訓(xùn)練過程加速，本文受此啟發(fā)[16]，設(shè)計(jì)一種新穎的基于網(wǎng)格篩選的方法.先利用網(wǎng)格化方法篩選去除密度稀疏的點(diǎn)，然后計(jì)算剩余點(diǎn)的局部密度和距離屬性尋找聚類中心.由于密度稀疏與聚類中心局部密度大的特點(diǎn)違背，去除的點(diǎn)一定不會(huì)是聚類中心，不會(huì)影響聚類中心的選取.然后在篩選后的數(shù)據(jù)集上繪制決策圖選取聚類中心，有效降低聚類的計(jì)算復(fù)雜度.基于此，提出一種基于網(wǎng)格篩選的密度峰值聚類算法(density peaks clustering algorithm based on grid screening, SDPC)，并從理論上證明該算法可以有效提高密度峰值聚類算法的運(yùn)行效率，獲得令人滿意的聚類結(jié)果.

1 密度峰值聚類算法原理

密度峰值聚類算法是一種新提出的聚類算法，該算法可以創(chuàng)建任意形狀的集群，而不考慮它們被嵌入的空間維度并且有效地排除異常值，應(yīng)用前景廣泛[17-18].算法中心思想基于這樣一個(gè)假設(shè)：對(duì)于一個(gè)數(shù)據(jù)集，聚類中心被一些低局部密度的數(shù)據(jù)點(diǎn)包圍，而且這些低局部密度的點(diǎn)距離其他高密度的點(diǎn)的距離都比較大.算法首先對(duì)每一個(gè)數(shù)據(jù)點(diǎn)i賦予2個(gè)屬性：點(diǎn)的局部密度ρi和該點(diǎn)到具有更高局部密度的點(diǎn)的距離δi,局部密度ρi定義為

(1)

其中，di j表示數(shù)據(jù)點(diǎn)xi和xj的距離.dc表示截?cái)嗑嚯x，是密度峰值聚類算法的唯一輸入?yún)?shù)，在作者的代碼中定義為

dc=dNd×2%,

(2)

其中Nd屬于每2個(gè)點(diǎn)之間的所有距離的集合，其以升序排序.因此，ρi等于與點(diǎn)i的距離小于dc的點(diǎn)的個(gè)數(shù)，其也被定義為所呈現(xiàn)的代碼中的高斯核函數(shù):

(3)

數(shù)據(jù)點(diǎn)i的δi是點(diǎn)到任何比其密度大的點(diǎn)的距離的最小值,即:

(4)

對(duì)于密度最大的點(diǎn)，我們可以得到：

(5)

DPC算法選擇ρi和δi均大的值作為聚類中心.例如圖1(a)表示嵌入二維空間中的28個(gè)數(shù)據(jù)的分布，數(shù)據(jù)點(diǎn)按照密度遞減的方式排列;圖1(b)是密度峰值聚類算法根據(jù)圖1(a)中數(shù)據(jù)繪制的決策圖.根據(jù)圖1(b),我們把密度和距離都較大的點(diǎn)1和點(diǎn)10作為聚類中心.

Fig. 1 Decision graph of the density peaks clustering algorithm圖1 密度峰值聚類算法決策圖

DPC算法具體步驟如算法1所示：

算法1. DPC聚類算法.

輸入:數(shù)據(jù)集X={x1,x2,…,xn}、參數(shù)dc；

輸出:聚類結(jié)果Y.

Step1. 計(jì)算所有點(diǎn)與點(diǎn)之間的距離di j，構(gòu)建相似度矩陣；

Step2. 基于Step1構(gòu)建的矩陣和用戶輸入的參數(shù)dc，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度ρi和高密度距離δi；

Step3. 依據(jù)Step2計(jì)算的數(shù)據(jù)點(diǎn)屬性繪制決策圖，并根據(jù)γi=ρi×δi選擇2個(gè)屬性都大的點(diǎn)作為聚類中心；

Step4. 剩下的點(diǎn)按照“最近鄰”算法，將“當(dāng)前點(diǎn)”歸于密度等于或者高于“當(dāng)前點(diǎn)”的最近點(diǎn)一類；

Step5. 去除當(dāng)前類別中小于邊界閾值的噪聲孤立點(diǎn)；

Step6. 返回結(jié)果矩陣Y.

注意到，密度峰值聚類算法最大的優(yōu)勢(shì)在于根據(jù)聚類中心的兩大特點(diǎn)繪制決策圖，選擇聚類中心[19].但是聚類中心的選擇依靠局部密度ρi和距離δi，而這2個(gè)值都取決于數(shù)據(jù)點(diǎn)間的距離di j，當(dāng)數(shù)據(jù)集規(guī)模較大時(shí)，計(jì)算量非常大，以樣本數(shù)的二次冪規(guī)模增長(zhǎng)，內(nèi)存需求極大.一種可行的解決方法是通過網(wǎng)格篩選，先去除密度稀疏不可能成為聚類中心的點(diǎn)，然后利用剩余的點(diǎn)進(jìn)行決策圖繪制.雖然會(huì)損失一部分?jǐn)?shù)據(jù)信息，但由于篩選的點(diǎn)均為密度稀疏的點(diǎn)，不影響聚類中心的選取，在保證聚類準(zhǔn)確率的基礎(chǔ)上極大地降低了計(jì)算復(fù)雜度.

2 基于網(wǎng)格篩選的密度峰值聚類算法

2.1 算法描述

一種改進(jìn)的基于網(wǎng)格篩選的密度峰值聚類算法(SDPC)的提出目的是降低原DPC算法的計(jì)算復(fù)雜度，使該算法不受數(shù)據(jù)集大小的限制.本文算法基本思想：引入稀疏網(wǎng)格篩選的方法，去除一部分密度稀疏即不可能成為聚類中心的點(diǎn)，只保留稠密網(wǎng)格單元中的點(diǎn)作為候選集進(jìn)行聚類中心的選取.雖然引入網(wǎng)格篩選的方法會(huì)損失部分?jǐn)?shù)據(jù)信息，但由于密度稀疏網(wǎng)格中的數(shù)據(jù)點(diǎn)局部密度均較小，與聚類中心局部密度較大的特點(diǎn)矛盾，因此篩選的點(diǎn)不會(huì)成為聚類中心，去除并不影響聚類中心的選擇.例如，假設(shè)對(duì)數(shù)據(jù)規(guī)模為n的數(shù)據(jù)集X={x1,x2,…,xn}進(jìn)行網(wǎng)格劃分，并篩選去除“稀疏”網(wǎng)格，只對(duì)“稠密”網(wǎng)格包含的m(m?n)個(gè)元素進(jìn)行聚類，則新數(shù)據(jù)集A={a1,a2,…,am},ai∈X的聚類中心和數(shù)據(jù)集X的聚類中心基本相近，從而保證了聚類的準(zhǔn)確性.

SDPC算法首先以網(wǎng)格來劃分?jǐn)?shù)據(jù)空間，將數(shù)據(jù)集映射到網(wǎng)格單元；然后利用數(shù)據(jù)在網(wǎng)格中分布的不均勻性，選出“稀疏”網(wǎng)格和“稠密”網(wǎng)格，通過設(shè)定篩選比例，把“稀疏”的網(wǎng)格單元去除；集中精力考慮剩余網(wǎng)格中的數(shù)據(jù)點(diǎn)，使用DPC算法中繪制決策圖的方法確定聚類中心；最后將剩余的點(diǎn)歸到密度大于它的最近類中.該算法有效降低了時(shí)間復(fù)雜度和內(nèi)存需求，具體步驟見算法2.

定義1. 網(wǎng)絡(luò)邊長(zhǎng).假設(shè)存在一個(gè)d維數(shù)據(jù)集，第i維上的值在區(qū)間[li,hi)中，i=1,2,…,d，則S=[l1,h1)×[l2,h2)×…×[ld,hd)就是d維數(shù)據(jù)空間.對(duì)數(shù)據(jù)空間的每一個(gè)維度進(jìn)行劃分，將其劃分成邊長(zhǎng)相等且互不相交的網(wǎng)格單元，為了提高計(jì)算效率和聚類效果，本文進(jìn)行幾何平均數(shù)的求解，定義網(wǎng)格的邊長(zhǎng)ξ:

(6)

其中，a為比例系數(shù)，用來調(diào)整控制網(wǎng)格邊長(zhǎng)大小.本文實(shí)驗(yàn)數(shù)據(jù)表明：當(dāng)a∈[0.5,1.5]時(shí)，網(wǎng)格能得到合適的劃分進(jìn)行篩選，并且能夠獲得較好的聚類效果.

定義2. 單元格密度.假設(shè)將數(shù)據(jù)集X={x1,x2,…,xn}映射到對(duì)應(yīng)的網(wǎng)格單元中，按照定義1中ξ將數(shù)據(jù)空間劃分為{u1,u2,…,un}網(wǎng)格單元，則單元格ui的密度為

ρui=count(Gui),

(7)

其中,count(Gui)表示統(tǒng)計(jì)網(wǎng)格編號(hào)為Gui的單元格中點(diǎn)數(shù).

算法2. SDPC聚類算法.

輸入:數(shù)據(jù)集X={x1,x2,…,xn}、篩選比例a；

輸出:聚類結(jié)果Y.

Step1. 按照定義1劃分?jǐn)?shù)據(jù)空間，將數(shù)據(jù)點(diǎn)X={x1,x2,…,xn}映射到對(duì)應(yīng)的網(wǎng)格單元；

Step2. 根據(jù)式(7)計(jì)算每個(gè)網(wǎng)格密度，并按照網(wǎng)格密度進(jìn)行從大到小排序；

Step3. 按比例a篩選去除“稀疏”網(wǎng)格，只保留可能成為聚類中心的樣本點(diǎn)，形成新的數(shù)據(jù)集A={a1,a2,…,am}；

Step4. 計(jì)算數(shù)據(jù)集A中兩兩樣本間距離；

Step5. 根據(jù)式(3)和式(4)計(jì)算A中每個(gè)樣本的ρi和δi值；

Step6. 從由ρi，δi構(gòu)成的決策圖中選擇k個(gè)聚類中心；

Step7. 使用算法1中分配策略將數(shù)據(jù)集A中的其余數(shù)據(jù)點(diǎn)歸于密度等于或者高于“當(dāng)前點(diǎn)”的最近點(diǎn)一類；

Step8. 將Step3篩選出的n-m個(gè)數(shù)據(jù)點(diǎn)，按照“最近鄰”原則歸到最近中心點(diǎn)一類；

Step9. 返回結(jié)果矩陣Y.

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

密度峰值聚類算法的核心思想是根據(jù)聚類中心的兩大特點(diǎn)繪制決策圖尋找聚類中心，本文算法保留了此選擇聚類中心的方法，但本文算法卻只需要在篩選過的m個(gè)點(diǎn)中尋找聚類中心，計(jì)算復(fù)雜度遠(yuǎn)遠(yuǎn)小于原密度聚類算法，尤其當(dāng)n特別大的時(shí)候.

對(duì)樣本規(guī)模為n的數(shù)據(jù)集，原密度峰值聚類算法存儲(chǔ)兩兩之間距離矩陣的空間復(fù)雜度為O(n2)，也是該算法空間復(fù)雜度的主要來源.本文算法只需對(duì)篩選剩下的m個(gè)點(diǎn)存儲(chǔ)相似度矩陣，空間復(fù)雜度O(m2)?O(n2).同時(shí)，本文算法比原密度峰值聚類算法增加了篩選去除的每個(gè)樣本到每個(gè)聚類中心的距離，但增加的空間復(fù)雜度不超過O(|CL|(n-m))，而且表示類簇?cái)?shù)的|CL|通常較小，因此，本文算法的空間復(fù)雜度一定比原密度峰值的空間復(fù)雜度小.

與原密度峰值聚類算法相比，本文引入網(wǎng)格篩選的概念，需事先利用網(wǎng)格劃分去除部分密度稀疏一定不是聚類中心的點(diǎn)，但此事件的時(shí)間復(fù)雜度幾乎可以忽略.另外，獲得聚類中心后，本文算法需對(duì)開始篩選去除的n-m個(gè)點(diǎn)進(jìn)行分配，這些點(diǎn)在原密度峰值聚類算法中需要O((n-m)2)的時(shí)間復(fù)雜度計(jì)算其ρi和δi屬性，本文算法只需要計(jì)算其與聚類中心的距離，時(shí)間復(fù)雜度一定小于O((n-m)2)，為節(jié)省時(shí)間做出貢獻(xiàn).假設(shè)n表示數(shù)據(jù)集中樣本點(diǎn)的個(gè)數(shù)，本文算法的時(shí)間復(fù)雜度由以下4部分決定:1)用O(n)的時(shí)間劃分?jǐn)?shù)據(jù)空間，將數(shù)據(jù)映射到網(wǎng)格單元中；2)使用快速排序的方法，O(ulgu)的時(shí)間按比例篩選稀疏的網(wǎng)格單元,u(u?n)表示非空網(wǎng)格單元個(gè)數(shù)；3)對(duì)篩選過后剩下的m(m?n)個(gè)點(diǎn)進(jìn)行密度峰值聚類，時(shí)間復(fù)雜度為O(m2)；4)分配篩選去除的點(diǎn)到k個(gè)聚類中心的距離，時(shí)間復(fù)雜度不超過O((n-m)2).所以本文算法時(shí)間復(fù)雜度不超過O(n)+O(ulgu)+O(m2)+O((n-m)2)，由于m?n且u?n，其總的時(shí)間復(fù)雜度一定小于DPC算法.

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了證明SDPC算法的聚類性能，實(shí)驗(yàn)采用經(jīng)典人工數(shù)據(jù)集和UCI數(shù)據(jù)集對(duì)本文算法進(jìn)行測(cè)試和評(píng)價(jià).我們將通過合成數(shù)據(jù)集的可視化來比較SDPC算法與DPC算法的精度以及運(yùn)行效率.除了DPC之外，SDPC在UCI數(shù)據(jù)集的性能還與在高維數(shù)據(jù)集上效果較好的標(biāo)準(zhǔn)譜聚類(NJW-SC)[20]、基于Nystrom的低秩近似譜聚類(Nystrom-SC)[21]以及2種改進(jìn)的DPC-KNN算法[7]和FKNN-DPC算法[8]進(jìn)行比較.本文使用聚類精度(Acc)來測(cè)量聚類結(jié)果的質(zhì)量.對(duì)于N個(gè)不同樣本集xi，yi，zi是xi,yi和zi的固有類別標(biāo)簽和預(yù)測(cè)類別標(biāo)簽，Acc計(jì)算為

(8)

其中,map()通過Hungarian算法將每個(gè)簇標(biāo)簽映射到類別標(biāo)簽，并且該映射是最優(yōu)的.Acc的值越高，聚類性能就越好.在實(shí)驗(yàn)中，DPC和SDPC算法參數(shù)dc的選擇參考文獻(xiàn)[5]取1%～2%，DPC代碼由文獻(xiàn)[5]的作者提供.該文中算法均通過10次試驗(yàn)嘗試獲取最優(yōu)參數(shù)，并且實(shí)驗(yàn)展示的結(jié)果都是其平均結(jié)果.

仿真實(shí)驗(yàn)在Inter core i5、雙核CPU、內(nèi)存4 GB、Windows7的操作系統(tǒng)和MATLAB 2010的環(huán)境下進(jìn)行.

3.2 實(shí)驗(yàn)結(jié)果分析

3.2.1 人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

本節(jié)對(duì)6組人工數(shù)據(jù)集進(jìn)行算法測(cè)試，實(shí)驗(yàn)數(shù)據(jù)特征如表1所示.數(shù)據(jù)集A2和A3分別包含7 500個(gè)和5 250個(gè)數(shù)據(jù)點(diǎn)，具有變化數(shù)量簇(M=50,35)的2維集合.S2數(shù)據(jù)集包含15類、5 000個(gè)數(shù)據(jù)點(diǎn)，呈復(fù)雜性空間分布.Five Cluster數(shù)據(jù)集共有4 000個(gè)數(shù)據(jù)點(diǎn)，5個(gè)類分別具有不同的大小和形狀.Twenty和Forty分別是有20和40類的數(shù)據(jù)集，均勻分布在數(shù)據(jù)空間.

Table 1 Characteristic of Artificial Datasets表1 人工實(shí)驗(yàn)數(shù)據(jù)特征

實(shí)驗(yàn)首先將數(shù)據(jù)集按照不同的數(shù)據(jù)分布，映射到不相交的網(wǎng)格單元中；然后計(jì)算網(wǎng)格單元的密度，篩選去除密度稀疏網(wǎng)格中數(shù)據(jù)點(diǎn).這里由于數(shù)據(jù)集規(guī)模較大和數(shù)據(jù)分布較緊密，所以篩選比例直接取70%，留下30%的“稠密”網(wǎng)格；然后用DPC算法在留下的數(shù)據(jù)集上選取正確的聚類中心；最后分配剩余點(diǎn)以及篩選去除的點(diǎn).SDPC算法的聚類結(jié)果如圖2～7所示.

Fig. 2 Clustering results of A2 by SDPC圖2 SDPC對(duì)A2數(shù)據(jù)集的聚類結(jié)果

Fig. 3 Clustering results of A3 by SDPC圖3 SDPC對(duì)A3數(shù)據(jù)集的聚類結(jié)果

Fig. 4 Clustering results of S2 by SDPC圖4 SDPC對(duì)S2數(shù)據(jù)集的聚類結(jié)果

Fig. 5 Clustering results of Five Cluster by SDPC圖5 SDPC對(duì)Five Cluster數(shù)據(jù)集的聚類結(jié)果

Fig. 6 Clustering results of Forty by SDPC圖6 SDPC對(duì)Forty數(shù)據(jù)集的聚類結(jié)果

Fig. 7 Clustering results of Twenty by SDPC圖7 SDPC對(duì)Twenty數(shù)據(jù)集的聚類結(jié)果

圖2(a)～圖7(a)表示DPC和SDPC在各個(gè)數(shù)據(jù)集上的聚類中心圖，“☆”表示DPC的聚類中心，“○”表示SDPC的聚類中心.從圖2(a)～圖7(a)中看出，2個(gè)算法的聚類中心很接近，因此可以說明篩選去除密度稀疏網(wǎng)格單元中的數(shù)據(jù)并不影響聚類中心的選取.圖2(b)～圖7(b)分別是SDPC在這6組數(shù)據(jù)集上的決策圖.進(jìn)一步可以證明SDPC保留了DPC選取密度峰值的方法，可以準(zhǔn)確找出聚類中心.圖2(c)～圖7(c)是SDPC的聚類結(jié)果圖，可以看出SDPC均有令人滿意的聚類結(jié)果.雖然DPC在這6組數(shù)據(jù)集上也表現(xiàn)出良好的聚類性能，但隨著數(shù)據(jù)規(guī)模的增大，其時(shí)間消耗呈指數(shù)上升，如表2所示.

從表2中可以看出，SDPC在這6個(gè)數(shù)據(jù)集上運(yùn)行時(shí)間明顯低于DPC.DPC依靠計(jì)算所有點(diǎn)的局部密度和距離屬性尋找聚類中心，計(jì)算復(fù)雜度較高.而本文SDPC算法采用網(wǎng)格篩選的方法，只考慮從高密度數(shù)據(jù)集中選取聚類中心，計(jì)算復(fù)雜度將大幅度下降.隨著數(shù)據(jù)規(guī)模的增大，SDPC的優(yōu)越性越明顯，如圖8所示.從圖8可以看出，數(shù)據(jù)集越大，SDPC比DPC快得越明顯.這在一定程度上說明SDPC算法能夠較好地處理大規(guī)模數(shù)據(jù)集，在保證聚類準(zhǔn)確率的同時(shí)有效降低了時(shí)間復(fù)雜度，提高了DPC的運(yùn)行效率.

Table 2 Clustering Time of SDPC and DPC on Different Datasets

3.2.2 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果分析

本節(jié)分別采用表3中6組UCI數(shù)據(jù)集驗(yàn)證本文SDPC算法的聚類性能.Iris是最常見的數(shù)據(jù)集，包含150個(gè)樣本點(diǎn)、3類.Seeds包含3類小麥種子，每個(gè)樣本有種子的7個(gè)屬性描述.Waveform包含3類波形,每類各占33%.Ring Norm數(shù)據(jù)集中2類樣本分別呈現(xiàn)有部分重疊的不同正態(tài)分布.Pen Digits和Gamma是2個(gè)包含10 000個(gè)以上樣本的大規(guī)模數(shù)據(jù)集.

由于高維數(shù)據(jù)在數(shù)據(jù)空間中分布稀疏，這里進(jìn)行SDPC算法測(cè)試時(shí)，根據(jù)數(shù)據(jù)集大小的不同，隨機(jī)選取不同的比例進(jìn)行篩選，然后進(jìn)行聚類中心的查找.分別計(jì)算在各情況下SDPC算法的準(zhǔn)確率以及運(yùn)行時(shí)間，與DPC以及Nystrom-SC，NJW-SC，DPC-KNN，F(xiàn)KNN-DPC進(jìn)行對(duì)比.Nystrom-SC算法在大規(guī)模數(shù)據(jù)集上均取50%的樣本點(diǎn)，并取最好的實(shí)驗(yàn)結(jié)果.SDPC以及各對(duì)比算法的聚類準(zhǔn)確率和運(yùn)行時(shí)間分別如表4和表5所示(“-”表示內(nèi)存不足，無法進(jìn)行實(shí)驗(yàn)).

Table 3 Characteristic of UCI Datasets表3 UCI實(shí)驗(yàn)數(shù)據(jù)特征

從表4中可以看出,本文SDPC算法由于保留了DPC算法選取聚類中心的方法，所以聚類的準(zhǔn)確率同其他5種算法相比還算令人滿意.DPC以及其他對(duì)比算法在較小規(guī)模的數(shù)據(jù)集上可以正常運(yùn)行，但當(dāng)處理Pen Digits等大規(guī)模數(shù)據(jù)集時(shí)，會(huì)提示內(nèi)存不足而無法聚類.因?yàn)镈PC需要所有數(shù)據(jù)點(diǎn)之間的相似度，空間復(fù)雜度為O(n2)，當(dāng)數(shù)據(jù)量很大時(shí)，存儲(chǔ)數(shù)據(jù)點(diǎn)的局部密度和距離屬性需要很大的內(nèi)存空間.而本文算法采用網(wǎng)格篩選的方法，只需要計(jì)算部分?jǐn)?shù)據(jù)之間的相似度，空間復(fù)雜度大幅度降低，所以可以在有限的內(nèi)存里進(jìn)行大規(guī)模數(shù)據(jù)集的聚類.從表4中可以看出，大部分情況下，隨著篩選比例的減少，即保留數(shù)據(jù)集的增大，SDPC的準(zhǔn)確率會(huì)逐漸增加，這是由于保留的數(shù)據(jù)集越多，聚類中心的選擇越準(zhǔn)確.

表5中，在小規(guī)模數(shù)據(jù)集上，SDPC算法和DPC算法的運(yùn)行效率相當(dāng)；但隨著數(shù)據(jù)規(guī)模的增大，SDPC算法明顯優(yōu)于DPC算法，當(dāng)數(shù)據(jù)規(guī)模達(dá)到上萬時(shí)，本文算法仍然保持著良好的性能.因?yàn)镾DCP只計(jì)算了部分?jǐn)?shù)據(jù)之間的相似度尋找聚類中心；而DPC計(jì)算了所有數(shù)據(jù)之間的相似度，時(shí)間復(fù)雜度很高.隨著篩選比例的增加，SDPC的速度越來越快.而Nystrom-SC和NJW-SC以及改進(jìn)的DPC算法雖然在小數(shù)據(jù)集上有著不錯(cuò)的聚類效果，但在大規(guī)模數(shù)據(jù)集上，消耗時(shí)間太長(zhǎng)，影響聚類效率.綜合考慮聚類準(zhǔn)確率以及運(yùn)行時(shí)間，本文SDPC算法在大規(guī)模數(shù)據(jù)集上更有優(yōu)勢(shì)，適合大數(shù)據(jù)環(huán)境下的數(shù)據(jù)挖掘.

Fig. 8 Clustering time of DPC and SDPC on different datasets圖8 DPC和SDPC算法在不同數(shù)據(jù)集上的聚類時(shí)間

DatasetsSDPCScreening RatioAccuracySDPCDPCDPC-KNNFKNN-DPCNystrom-SCNJW-SC0.30.9400Iris0.20.94000.94000.96000.97300.88000.88670.10.94000.30.8762Seeds0.20.87620.85240.91430.92400.89520.93810.10.87620.70.6072Waveform0.50.62180.58080.58400.70300.61800.61860.30.61000.70.5104Ring Norm0.50.52310.50850.50820.51000.50570.94690.30.62090.70.4200Pen Digits0.50.42000.30.42050.70.5110Gamma0.60.51100.50.5248

Table 5 Clustering Time of Different Algorithms on Different Datasets表5 各算法在不同數(shù)據(jù)集上的聚類時(shí)間

4 結(jié)束語

求解密度峰值聚類算法將所有樣本點(diǎn)作為聚類中心的候選數(shù)據(jù)集，依賴于計(jì)算所有數(shù)據(jù)點(diǎn)的局部密度和距離屬性，時(shí)間復(fù)雜度和空間復(fù)雜度均為O(n2)，無法處理大規(guī)模數(shù)據(jù)集.本文算法引入網(wǎng)格篩選的方法，通過將數(shù)據(jù)點(diǎn)映射到對(duì)應(yīng)的網(wǎng)格中，根據(jù)數(shù)據(jù)分布去除局部密度較小的點(diǎn)，只保留有效數(shù)據(jù)集繪制決策圖尋找聚類中心，很大程度上降低了時(shí)間開銷以及空間開銷.本文從理論上證明了網(wǎng)格篩選可以有效降低計(jì)算復(fù)雜度.經(jīng)典人工數(shù)據(jù)集和UCI真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明：本文算法優(yōu)于傳統(tǒng)的密度峰值聚類算法，既保持了原有算法尋找聚類中心的準(zhǔn)確性，又降低了計(jì)算復(fù)雜度，能較好地處理大規(guī)模數(shù)據(jù)集.

無論是原密度峰值聚類算法還是結(jié)合了網(wǎng)格篩選方法的密度峰值聚類算法，在選擇聚類中心時(shí)，依然需要依靠用戶的經(jīng)驗(yàn)，進(jìn)一步探索是否可以使選擇更加可靠簡(jiǎn)單.