基于數(shù)據(jù)空間網(wǎng)格化的密度峰值聚類算法

【摘要】密度峰值聚類方法能夠?qū)?shù)據(jù)進(jìn)行聚類，且適用于任意形狀數(shù)據(jù)集的聚類。但當(dāng)數(shù)據(jù)量增大時(shí)，算法的時(shí)間復(fù)雜度和存儲(chǔ)開(kāi)銷也會(huì)大幅增加。針對(duì)此問(wèn)題，提出一種基于數(shù)據(jù)空間網(wǎng)格化的密度峰值聚類方法，將數(shù)據(jù)每個(gè)維度的對(duì)應(yīng)值域等分為若干區(qū)間，即將數(shù)據(jù)空間分成若干網(wǎng)格，在計(jì)算局部密度和距離時(shí)，僅需利用相鄰網(wǎng)格的點(diǎn)。實(shí)驗(yàn)表明，該方法在保證聚類質(zhì)量的前提下能極大地減少計(jì)算時(shí)間和占用內(nèi)存，具有較高的可靠性和有效性。

【關(guān)鍵詞】密度峰值;網(wǎng)格化;聚類;數(shù)據(jù)空間

〔中圖分類號(hào)〕TP183 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕1674-3229（2021）04-0019-05

0 引言

聚類算法是根據(jù)數(shù)據(jù)的相似性，把相同或者具有相似特征的數(shù)據(jù)劃分成同一組進(jìn)行特征分析，用于數(shù)據(jù)的進(jìn)一步挖掘。目前，聚類算法被廣泛應(yīng)用于電子商務(wù)、社區(qū)檢測(cè)以及圖像分割等方面[1]。但大多數(shù)聚類算法都存在著聚類中心確定困難、聚類精度低、數(shù)據(jù)集自適應(yīng)性不高，導(dǎo)致聚類效率低下和參數(shù)依賴性等問(wèn)題。針對(duì)這些問(wèn)題，2014年，A.Rodriguez等[2]首次提出了密度峰值聚類（DensityPeak Clustering，DPC）算法，該算法結(jié)合密度和距離兩個(gè)維度選擇出聚類中心，且不需要任何迭代。此后，學(xué)者們對(duì)DPC方法進(jìn)行了一些改進(jìn)，如R.Mehmood等提出了一種模糊CFSFDP方法[3]，可有效而自適應(yīng)地選擇聚類中心;其他學(xué)者根據(jù)高斯分布的3B原則[4]，每個(gè)點(diǎn)的影響半徑為3σ（其中σ是數(shù)據(jù)點(diǎn)的標(biāo)準(zhǔn)差），使用數(shù)據(jù)的潛在嫡自動(dòng)計(jì)算截?cái)嗑嚯xdc，提高聚類效果[5-6];高詩(shī)瑩等[7]通過(guò)計(jì)算數(shù)據(jù)樣本中的密度比，減少密度較小類簇的遺漏，提高聚類精度;Shuliang Wang等[8]使用多變量的核密度估計(jì)方法自動(dòng)選擇截?cái)嗑嚯xdc;Rashid Mehmood等[9]基于熱方程，使用另一個(gè)非參數(shù)密度估計(jì)器進(jìn)行密度估計(jì);Z.Yan等[10]提出基于點(diǎn)與第k個(gè)最近鄰點(diǎn)之間的距離（稱為半徑）來(lái)估計(jì)每個(gè)點(diǎn)的局部密度，同時(shí)利用兩個(gè)點(diǎn)的k個(gè)最近鄰點(diǎn)的交點(diǎn)較小，分配不同的聚類特性，改進(jìn)了DPC算法的分配策略：在KNN核密度估計(jì)（NKD）[11]的啟發(fā)下，Geng YA等[12]利用相對(duì)k最近鄰核密度（RNKD）來(lái)估計(jì)點(diǎn)的密度，解決了NKD在類密度不均勻的情況下聚類性能不佳的問(wèn)題，設(shè)計(jì)了RECOME算法。

DPC在聚類過(guò)程中，需要計(jì)算每個(gè)數(shù)據(jù)點(diǎn)的局部密度和每個(gè)數(shù)據(jù)點(diǎn)與其他較高局部密度點(diǎn)之間的最短距離，其時(shí)間復(fù)雜度為O（N2），存儲(chǔ)開(kāi)銷為O（1/2N2）。對(duì)于大規(guī)模數(shù)據(jù)集，為提高效率，ShichaoCheng[13]等提出了FDP算法，使用k-dtree建立指標(biāo)索引，只計(jì)算當(dāng)前點(diǎn)的k個(gè)最近鄰。王飛等[14]提出了基于網(wǎng)格的密度峰值聚類算法（GDPCA）。該算法根據(jù)數(shù)據(jù)集的分布，按照一定的規(guī)則自適應(yīng)地劃分網(wǎng)格，并將數(shù)據(jù)按照規(guī)則映射到網(wǎng)格空間中，然后對(duì)每個(gè)網(wǎng)格空間的數(shù)據(jù)使用密度峰值聚類算法進(jìn)行聚類分析，接著根據(jù)邊界點(diǎn)的分布進(jìn)行相鄰網(wǎng)格聚類結(jié)果的合并，其不足之處在于沒(méi)有利用距離這個(gè)維度，在一些數(shù)據(jù)集上無(wú)法達(dá)到令人滿意的效果。Courjault-rad等在2016年提出IDPC算法[15]，通過(guò)使用縮小窗口（ICMDW）迭代封面圖來(lái)構(gòu)建密度圖，從而減少維度，但當(dāng)局部密度較高時(shí)，迭代次數(shù)會(huì)急劇增加。

本文提出的基于數(shù)據(jù)空間網(wǎng)格化的密度峰值聚類（LSDPC）算法利用相鄰網(wǎng)格所在的點(diǎn)計(jì)算密度，而不必基于所有全局?jǐn)?shù)據(jù)點(diǎn)兩兩之間的距離來(lái)計(jì)算密度;最后得到的決策圖是全局?jǐn)?shù)據(jù)點(diǎn)的決策圖，而不必像文獻(xiàn)[14]再進(jìn)行各個(gè)網(wǎng)格聚類結(jié)果的合并;在保證聚類質(zhì)量的前提下，極大地減少了計(jì)算時(shí)間和內(nèi)存的開(kāi)銷。

1 密度峰值聚類（DPC）算法

密度峰值聚類算法中，聚類中心的確定需要給出樣本點(diǎn)的局部密度ρ和兩個(gè)樣本點(diǎn)之間的距離δ。假設(shè)待聚類的數(shù)據(jù)集s={xi}i=1N，數(shù)據(jù)點(diǎn)xi和xj之間的距離可以表示為dij=dist（Xi，Xj）。定義S中任意數(shù)據(jù)點(diǎn)xi的兩個(gè)參數(shù)為ρi和δi，ρi表示當(dāng)前點(diǎn)的局部密度，δi表示密度大于當(dāng)前點(diǎn)且離當(dāng)前點(diǎn)最近的距離。使用截?cái)嗪撕瘮?shù)來(lái)定義數(shù)據(jù)點(diǎn)Xi的局部密度ρi，其表達(dá)式如下：其中參數(shù)dc為截?cái)嗑嚯x（Cut-off distance）。定義Xi與Xj之間的最小距離δi為：

在計(jì)算δi的時(shí)候同時(shí)記錄ρ值更大的數(shù)據(jù)點(diǎn)中與第i點(diǎn)距離最近的點(diǎn)的編號(hào)j，記做L（i）。

計(jì)算綜合考慮ρ值和δ值的聚類決策值γi，用來(lái)確定一個(gè)聚類中心，如式（3）

γi=ρiδi，i∈IS（3）

DPC算法的具體步驟如下：

DPC算法的瓶頸在于計(jì)算數(shù)據(jù)點(diǎn)的密度時(shí)，要利用所有數(shù)據(jù)點(diǎn)間的距離進(jìn)行密度值的計(jì)算。一種做法是引入一個(gè)（對(duì)稱的）距離矩陣，用來(lái)存儲(chǔ)數(shù)據(jù)集中的任意兩個(gè)點(diǎn)之間的距離，但是這種方法的時(shí)間復(fù)雜度為O（N2），且需要O（1/2N2）的存儲(chǔ)開(kāi)銷。

對(duì)于樣本點(diǎn)的局部密度ρi的計(jì)算，需要求出Xi和其他樣本點(diǎn)之間的所有距離dij{j=1…N，j≠i}。因此，ρ的計(jì)算復(fù)雜度為O（N2）。

對(duì)于兩個(gè)樣本點(diǎn)之間的距離δi，需要對(duì)所有的ρ進(jìn)行排序，并查找比較大于ρi的所有點(diǎn)的距離。因此，δ的計(jì)算復(fù)雜度為O（1/2N2）。

2 基于數(shù)據(jù)空間網(wǎng)格化的密度峰值聚類算法

2.1 問(wèn)題分析

用DPC算法計(jì)算局部密度ρi耗時(shí)較長(zhǎng)，當(dāng)數(shù)據(jù)量增大時(shí)，這個(gè)問(wèn)題尤為突出。有效計(jì)算局部密度ρi的瓶頸在于要求出Xi和其他樣本點(diǎn)之間的所有距離dij{j=1…N，j≠i}。實(shí)際上，隨著樣本點(diǎn)的距離越近，它對(duì)局部密度ρi的貢獻(xiàn)越大，而其他點(diǎn)對(duì)密度的貢獻(xiàn)隨著到目標(biāo)點(diǎn)的距離增大而呈指數(shù)衰減。據(jù)此，本文將樣本在n維空間進(jìn)行劃分，對(duì)每一個(gè)維度等量劃分，將全空間劃分為互不相交的網(wǎng)格單元。如圖1所示，在二維數(shù)據(jù)的情況下，對(duì)于圓點(diǎn)所在的編號(hào)14的網(wǎng)格，本文只需要將上下左右以及斜線上的8個(gè)相鄰網(wǎng)格以及自身網(wǎng)格（編號(hào)為8，9，10，13，14，15，18，19，20）中點(diǎn)集合做密度計(jì)算，求近似值即可。只需搜索相鄰網(wǎng)格的局部點(diǎn)來(lái)近似計(jì)算局部密度，不用對(duì)所有數(shù)據(jù)點(diǎn)間的距離進(jìn)行排序，避免樣本點(diǎn)對(duì)上的重復(fù)計(jì)算。

圖1 二維空間網(wǎng)格化

同樣，對(duì)于兩個(gè)樣本點(diǎn)之間的距離s，只考慮相鄰網(wǎng)格的點(diǎn)即可。因?yàn)榫嚯x最近的點(diǎn)一定在相鄰的網(wǎng)格中，只需查找這些網(wǎng)格中密度ρj比它大的點(diǎn)即可。如果不存在密度比它大的點(diǎn)，說(shuō)明該點(diǎn)是局部密度最大，可以參加第二次的全局密度比較。

該相鄰網(wǎng)格計(jì)算法顯著降低了原始DPC算法中密度計(jì)算成本，卻獲得了幾乎相等的聚類效果。圖2第一列展示了數(shù)據(jù)集flame上，DPC算法截?cái)嗑嚯xdc=4%的情況下以及LSDPC算法截?cái)嗑嚯xdc=8%、網(wǎng)格數(shù)為5×5情況下的聚類結(jié)果和決策圖。圖2第二列展示了數(shù)據(jù)集S2上，DPC算法截?cái)嗑嚯xdc=4%的情況下以及LSDPC算法截?cái)嗑嚯xdc=8%、網(wǎng)格數(shù)為88×88情況下的聚類結(jié)果。

圖2 Flame和S2數(shù)據(jù)集上DPC和LSDPC的聚類結(jié)果比較

2.2 算法步驟

LSDPC算法步驟如下：

2.3 計(jì)算復(fù)雜度分析

假設(shè)樣本數(shù)為N，則ρ的計(jì)算復(fù)雜度為O（N2），δ的計(jì)算復(fù)雜度為O（1/2N2）。分成m個(gè)網(wǎng)格后，則每個(gè)網(wǎng)格平均有N/m個(gè)點(diǎn)，對(duì)每個(gè)網(wǎng)格來(lái)說(shuō)，有k個(gè)鄰居，ρ的計(jì)算復(fù)雜度為（kN/m）2，全部的計(jì)算復(fù)雜度為m*（kN/m）2=k2*N/m*N。根據(jù)歸納總結(jié)則計(jì)算復(fù)雜度為O（kN）。

同樣可以求得δ的計(jì)算復(fù)雜度為O（kN）。

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

3.1 評(píng)價(jià)指標(biāo)

為了驗(yàn)證本文算法的性能，使用了6個(gè)模擬數(shù)據(jù)集，每個(gè)數(shù)據(jù)集的屬性數(shù)量和類數(shù)如表1所示。

表1 6個(gè)數(shù)據(jù)集的屬性和類數(shù)

為了客觀評(píng)價(jià)比較聚類算法，本文從三個(gè)方面來(lái)評(píng)估：內(nèi)部評(píng)價(jià)指標(biāo)、外部評(píng)價(jià)指標(biāo)和運(yùn)行時(shí)間[16]。內(nèi)部評(píng)價(jià)指標(biāo)使用戴維森堡丁指數(shù)（Da-vies-Bouldin Index），DB越小意味著類內(nèi)距離越小，同時(shí)類間距離越大，聚類效果越好。外部評(píng)價(jià)指標(biāo)使用調(diào)整蘭德指數(shù)（Adjusted Rand index ARI），ARI考慮到同一個(gè)聚類和不同聚類中存在的實(shí)例數(shù)。ARI取值范圍為[0，1]，值越大意味著聚類結(jié)果與真實(shí)情況越吻合。值為1的時(shí)候代表所有的樣本都被正確地聚類，每個(gè)聚類只包含本類樣本。從廣義的角度來(lái)講，ARI衡量的是兩個(gè)數(shù)據(jù)分布的吻合程度。

3.2 實(shí)驗(yàn)結(jié)果比較

為了驗(yàn)證算法的有效性，首先在隨機(jī)生成的包含三類的高斯數(shù)據(jù)集及隨機(jī)生成的包含二類的均勻分布的數(shù)據(jù)集上進(jìn)行比較。圖3分別展示了高斯數(shù)據(jù)集和均勻數(shù)據(jù)集的聚類效果?？梢?jiàn)兩者算法都能達(dá)到較好的聚類效果，并且都能從決策圖上識(shí)別出聚類中心。

圖3 隨機(jī)高斯數(shù)據(jù)集和均勻數(shù)據(jù)集上DPC和LSDPC的聚類結(jié)果及決策圖比較

表2展示了DPC、FDPC[13]、LSDPC在6個(gè)數(shù)據(jù)集上的DB、ARI指標(biāo)結(jié)果。對(duì)于每個(gè)聚類算法，每個(gè)度量的最佳值都以粗體顯示。而“-”代表無(wú)法度量，內(nèi)存溢出。

從表2可以看出LSDPC算法與DPC、FDPC聚類算法相比，LSDPC算法在6個(gè)數(shù)據(jù)集上，基于所有外部度量提供了最佳的聚類輸出。

表2 3種聚類算法的指標(biāo)比較

圖4算法運(yùn)行時(shí)間比較

圖4顯示了三種聚類算法的運(yùn)行時(shí)間比較結(jié)果。當(dāng)N=104時(shí)，LSDPC使用的時(shí)間與FDPC相差不大;相比于DPC，LSDPC節(jié)省了1個(gè)數(shù)量級(jí)。當(dāng)N=106時(shí)，LSDPC使用的時(shí)間相比于FDPC節(jié)省了一個(gè)數(shù)量級(jí);對(duì)比DPC，LSDPC節(jié)省的時(shí)間將達(dá)到3個(gè)數(shù)量級(jí)。結(jié)合表2可以看出，LSDPC在聚類指標(biāo)（ARI、DB）上十分接近DPC，而且隨著數(shù)據(jù)量的增大，指標(biāo)值更為接近。雖然LSDPC在聚類指標(biāo)ARI上略低于DPC，但可以極大地減少運(yùn)行時(shí)間。

4 結(jié)論

本文針對(duì)在大規(guī)模數(shù)據(jù)聚類時(shí)，DPC算法所需時(shí)空代價(jià)急劇增大的問(wèn)題，提出了數(shù)據(jù)空間網(wǎng)格化的密度聚類方法。LSDPC算法將數(shù)據(jù)每個(gè)維度對(duì)應(yīng)值域等分為若干區(qū)間，將數(shù)據(jù)空間分成若干網(wǎng)格，同時(shí)僅利用相鄰網(wǎng)格所在的點(diǎn)計(jì)算局部密度和距離。文中將LSDPC在6個(gè)數(shù)據(jù)集上作了實(shí)驗(yàn)，并從ARI、DB、運(yùn)行時(shí)間三個(gè)方面對(duì)LSDPC結(jié)果進(jìn)行分析比較。當(dāng)數(shù)據(jù)量增大時(shí)，該方法對(duì)比DPC來(lái)說(shuō)，極大地降低了算法的時(shí)間和內(nèi)存消耗。例如，當(dāng)原始數(shù)據(jù)樣本點(diǎn)數(shù)大小超過(guò)100，000時(shí)，所提算法仍能在可承受的時(shí)間和內(nèi)存中執(zhí)行。但本文實(shí)驗(yàn)中的網(wǎng)格數(shù)目采用經(jīng)驗(yàn)方法來(lái)確定，今后可根據(jù)不同的數(shù)據(jù)集來(lái)確定網(wǎng)格數(shù)目，改進(jìn)算法，以提高聚類算法的準(zhǔn)確性。

[參考文獻(xiàn)]

[1]Olfa Nasraoui，Chiheb-Eddine Ben N'Cir.Clustering Meth-ods for Big Data Analytics[M].Switzerland：Springer，Cham，2019.

[2]Rodriguez A，Laio A.Machine learning.Clustering by fastsearch and find of density peaks[J].Science，2014，344（6191）：1492.

[3]Mehmood R，Bie R，Dawood H，et al.Fuzzy Clustering byFast Search and Find of Density Peaks[J].Personal&Ubiq-uitous Computing，2016，20（5）：785-793.

[4]Barany I，Vu V H.Central limit theorems for Gaussian poly-topes[J].Annals of Probability，2006，35（4）：1593-1621.

[5]Ji C，Lei Y.Parallel clustering by fast search and find ofdensity peaks [A].2016 International Conference on Au-dio，Language and Image Processing（ICALIP）[C].NewYork：IEEE Xplore，2017：563-567.

[6]Wang S，Wang D，Caoyuan L 1，et al.Clustering by FastSearch and Find of Density Peaks with Data Field[J].Chi-nese Journal of Electronics，2016，25（3）：397-402.

[7]高詩(shī)瑩，周曉鋒，李帥.基于密度比例的密度峰值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（16）：10-17.

[8]WANG Shuliang，WANG Dakui，LI Caoyuan，et al.Cluster-ing by Fast Search and Find of Density Peaks with DataField[J].Chinese Journal of Electronics，2016，25（3）：397-402.

[9]Mehmood R，Zhang G，Bie R，et al.Clustering by fastsearch and find of density peaks via heat diffusion[J].Neu-rocomputing，2016（208）：210-217.

[10]Yan Z，Loo W，Bu C，et al.Clustering spatial data by theneighbors intersection and the density difference[A].2016 IEEE/ACM 3rd International Conference on Big DataComputing Applications and Technologies（BDCAT）[C].New York：IEEE Xplore，2016：217-226.

[11]Tran T N，Wehrens R，Buydens L M C.KNN-kerneldensity-based clustering for high-dimensional multivari-ate data[J].Computational Statistics&Data Analysis，2006，51（2）：513-525.

[12]Geng Y A，Li Q，Zheng R，et al.BECOME：a New Densi-ty-Based Clustering Algorithm Using Relative KNN Ker-nel Density[J].Information Sciences，2018：13-30.

[13]Shichao Cheng，Yuzhuo Duan，Xin Fan，et al.Review ofFast Density-Peaks Clustering and Its Application to Pedi-atric White Matter Tracts[J].Medical Image Understand-ing and Analysis，2017：436-447.

[14]王飛，王國(guó)胤，李智星，等.一種基于網(wǎng)格的密度峰值聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2017，38（5）：1034-1038.

[15]Vincent Courjault-Radé，Ludovic D'Estampes，St6phane Pu-echmorel.Improved density peak clustering for large datasets[EB/OL].https：//hal.archives-ouvertes.fr/hal-01353574，2016-12-12.

[16]Zhang Y，Cheny S，Yu G.Efficient Distributed DensityPeaks for Clustering Large Data Sets in MapReduce[A].2017 IEEE 33rd International Conference on Data Engi-neering（ICDE）[C].New York：IEEE Xplore，2017：67-68.

[收稿日期]2021-07-28

[基金項(xiàng)目]莆田學(xué)院科研項(xiàng)目“基于張量數(shù)據(jù)的顯著性檢測(cè)算法研究”（2016041）

[作者簡(jiǎn)介]張萍（1982-），女，碩士，莆田學(xué)院機(jī)電與信息工程學(xué)院講師，研究方向：計(jì)算機(jī)視覺(jué)、機(jī)器學(xué)習(xí)。