一種基于網(wǎng)格劃分的密度峰值聚類改進算法

江平平 曾慶鵬

(南昌大學信息工程學院 江西 南昌 330031)

0 引 言

聚類分析作為數(shù)據(jù)挖掘技術(shù)中有力的工具之一，其應用范圍普及較廣，關(guān)聯(lián)機器學習[1]、模式識別[2]、數(shù)據(jù)分析、圖像處理和市場研究[3]等多個領域。聚類分析的目是將有差異的對象集合劃分到不同的類或簇中，相似對象的集合劃為同一類，且不同類中的對象差別較大[4]。

聚類算法大體上可分為：基于劃分的方法[5-10]；基于層次的方法[11-12]；基于密度的方法如DBSCAN[13]、GDBSCAN[14]和OPTICS[15]等；基于網(wǎng)格的方法如STING[16]、WavcClustcr[17]和Clique[18]等；基于模型的方法[19]等。不同的聚類算法各有其優(yōu)缺點，如基于密度的DBSCAN算法具有處理任意形狀的簇類以及對噪音點進行過濾等長處，然而該算法需耗費大量時間和空間對距離矩陣進行計算，且對輸入?yún)?shù)較為敏感。因此，各學者提出了眾多改進方法[20-23]。文獻[20]和文獻[21]對半徑參數(shù)進行自適應改進，但領域密度閾值仍需靠經(jīng)驗方法選?。晃墨I[22]解決的參數(shù)選擇困難的缺陷，但時間開銷較大;文獻[23]提高了運行效率，但對于多維數(shù)據(jù)集的處理存在局限性。

Alex Rodriguez和Alessandro Laio于2014年在《Science》雜志上發(fā)表的基于密度峰值聚類算法DPC[24]能

夠處理任意形狀的簇、能將數(shù)據(jù)點準確歸類，并除去噪聲點。然而該算法時空復雜度高，且對一些較為復雜的數(shù)據(jù)集，難以準確地依據(jù)決策圖人工選取聚類中心。

針對DPC算法聚類時空復雜度高，無法有效處理大數(shù)據(jù)集且需人工選取聚類中心的問題。本文提出一種改良的基于網(wǎng)格的密度峰值聚類算法，先對網(wǎng)格代表點進行聚類，自動確定聚類中心；之后將非核心代表點和各網(wǎng)格中數(shù)據(jù)點進行歸類；最后對邊界的代表點和噪聲點進行處理完成聚類。

1 DPC算法

快速搜索和發(fā)現(xiàn)密度峰值聚類算法DPC的聚類中心具有兩個特征：1) 數(shù)據(jù)點自身的局部密度大；2) 局部密度大的點相對之間的間隔較遠。對于各數(shù)據(jù)點xi皆需計算其局部密度ρi以及高局部密度距離δi，通過這個兩個值來構(gòu)建決策圖[24]，人工選取ρi和δi相對大的點作為聚類中心，然后將其他數(shù)據(jù)點歸類并剔除噪聲點。

定義1局部密度：一個數(shù)據(jù)點一定半徑內(nèi)其他點的個數(shù)。點xi的局部密度ρi為：

式中:dij=dist(xi,xj)代表xi和xj的距離，dc為所有樣本點間距離的最小2%的距離中的最大距離。函數(shù)χ(x)定義如下：

當數(shù)據(jù)點為連續(xù)時，局部密度ρi為:

式中：參數(shù)dc>0,為截斷距離，需要人工指定。

定義2高密度距離：比自身局部密度高的點中，與離自身最近的那個點之間的距離。對于任一點xi的高密度距離δi為：

式中:對應指標集IS定義為:

DPC算法特征值ρi和δi畫出決策圖，人工選出這兩個數(shù)值都相對較高的數(shù)據(jù)點作為聚類中心，將剩余點按局部密度倒序排序，依次歸入局部密度更大且距離最近的數(shù)據(jù)點所在類中。

定義3邊界點：如果一個已分配的數(shù)據(jù)點與其他類中的點的距離在階段距離dc內(nèi)，則該點為邊界點。

DPC算法的最后一步是對邊界點的處理，利用密度參數(shù)dc算出類邊界點集，然后指定邊界點集中密度最高點的密度值作為劃分核心點和噪音點的閾值。DPC算法步驟：

(1) 初始化參數(shù)dc；

(2) 根據(jù)式(1)計算數(shù)據(jù)點的局部密度ρi；

(3) 按局部密度ρi倒序排序；

(4) 根據(jù)式(4)計算數(shù)據(jù)點的相對距離δi；

(5) 構(gòu)建基于ρi和δi的決策圖，并手動選取聚類中心點；

(6) 將剩余非聚類中心點歸類；

(7) 對邊界點處理，檢測噪聲點。

DPC算法具有可發(fā)現(xiàn)非球形簇，所需參數(shù)少，無需進行迭代等優(yōu)點。然而該算法同時也存在處理大規(guī)模數(shù)據(jù)集時運行時間過長，耗費內(nèi)存空間過大，人工難以準確地選取聚類中心等缺陷。

2 基于網(wǎng)格劃分的密度峰值聚類算法(G-DPC)

針對DPC算法時空復雜度高以及人工選取聚類中心易造成偏差的問題，本文提出了一種改進的基于網(wǎng)格劃分的密度峰值聚類算法G-DPC。

2.1 網(wǎng)格劃分

定義4網(wǎng)格邊長：假定存在一個d維數(shù)據(jù)集X={x1,x2,…,xn}，n∈N+，xi∈Rd。屬性(A1，A2，…，Ad)都是有界的，設第i維上的值在范圍[li，hi)中，i=1，2，…，d，則S=[[l1，h1)×[l2，h2)×…×[ld，hd)]即是d維數(shù)據(jù)空間。將數(shù)據(jù)空間各個維度劃分成均等且不相交的網(wǎng)格單元[25-26]。網(wǎng)格邊長side計算公式為：

式中:ɑ為控制參數(shù)，網(wǎng)格劃分邊長side的取值會對數(shù)據(jù)聚類的效果造成影響，太大會降低聚類精度；太小則影響處理速度。當ɑ∈(0，2]時，算法的聚類效果較好。本文實驗中選取ɑ值為1.5。

例1：圖1為Birch3[27]的原始數(shù)據(jù)集分布情況，若依照式(6)對該數(shù)據(jù)集進行網(wǎng)格劃分，劃分后如圖2所示，將網(wǎng)格單元點的統(tǒng)計信息取代原先的數(shù)據(jù)點，從而實現(xiàn)數(shù)據(jù)壓縮的效果，利于選取聚類中心。

圖1 Birch3的數(shù)據(jù)分布

圖2 網(wǎng)格劃分后的數(shù)據(jù)分布

2.2 數(shù)據(jù)聚類

2.2.1自動選擇聚類中心

網(wǎng)格j中點的集合為P={p1,p2,…,plj},lj為該網(wǎng)格j內(nèi)數(shù)據(jù)點的總個數(shù)。則該網(wǎng)格的代表點為:

定義6代表點局部密度值：網(wǎng)格代表點Pj的局部密度是網(wǎng)格j內(nèi)數(shù)據(jù)點的個數(shù)，網(wǎng)格j中點的個數(shù)為:

式中：

則網(wǎng)格代表點Pj的局部密度為ρj=lj。

定義7代表點高密度距離值：以網(wǎng)格代表點Pj更高密度代表點Pk的最近距離，作為網(wǎng)格代表點Pj的距離值，記為δj。

式中：Dkj是網(wǎng)格代表點Pk與網(wǎng)格代表點Pj的距離。

在選取聚類中心時，文獻[24]采取對決策圖進行觀察后再由人工選擇中心的方式，篩選局部密度和高密度距離值均較大的點作為聚類中心，這種方法在處理數(shù)據(jù)分布差距大的小規(guī)模數(shù)據(jù)集時較為簡單，然而在處理大規(guī)模數(shù)據(jù)集時，如圖3所示，決策圖中點的分布差距不明顯時便難以準確選擇聚類中心的數(shù)目。

圖3 DPC算法決策圖

為解決上述問題，眾多學者提出了解決方案，例如，文獻[28]中的Fuzz-CFSFDP算法使用基于上模糊規(guī)則自適應地選擇集群中心，然而該算法同樣對參數(shù)dc的取值敏感，數(shù)據(jù)集的測試精確度較低；文獻[29]中采用根據(jù)簇中心權(quán)值的變化趨勢的算法來尋找聚類中心，該方法雖能有效避免手動選取聚類中心帶來的誤差，但只適用于低維數(shù)據(jù)集分析。本文給出一種改進自適應的方法，無需人工干預選擇確切聚類中心的數(shù)量。其判定函數(shù)為:

ρCi-μ(ρi)≥0

(12)

(δCi-E(δi))/2≥σ(δi)

(13)

式中：ρCi是聚類中心網(wǎng)格代表點的密度，μ(ρi)是所有網(wǎng)格代表點密度的均值，δCi是同一個類簇中網(wǎng)格代表點距聚類中心代表點最小的距離，E(δi)是所有δi的期望。式(12)表示該網(wǎng)格代表點的局部密度值大于所有網(wǎng)格代表點局部密度的均值，這樣的判定方法滿足密度峰值算法中聚類中心往往分布在相對高密度區(qū)域這一條件；式(13)的判定方法滿足聚類中心間的相對距離較遠這個條件。

因此，當網(wǎng)格代表點對象符合以上兩個公式條件時，將該網(wǎng)格代表點選定為聚類中心。

2.2.2數(shù)據(jù)點歸類

本文采用原DPC算法中的最近鄰算法對剩余數(shù)據(jù)點進行歸類。在完成聚類中心代表點的選擇之后，將剩下的非聚類中心代表點按照ρi降序分類到距其最近且局部密度大于該點的代表點所在類中，并將原數(shù)據(jù)集中的數(shù)據(jù)點歸屬到其網(wǎng)格代表點所在類中。

2.3 邊界點與噪聲點的處理

本文G-DPC算法中，邊界點的對象是符合定義3的網(wǎng)格代表點。首先根據(jù)密度參數(shù)dc計算出當前類簇中邊界網(wǎng)格代表點的集合，在邊界點集中找出擁有最高密度的網(wǎng)格代表點，將該代表點的密度作為閾值以劃分出核心代表點和噪聲點，保留密度大于等于該密度閾值的代表點作為簇內(nèi)核心代表點；剔除當前類別中小于此密度閾值的噪聲代表點，同時將該噪聲代表點所在網(wǎng)格中的數(shù)據(jù)點也一并剔除。

2.4 算法實現(xiàn)

G-DPC算法實現(xiàn)的具體步驟如下：

(1) 將數(shù)據(jù)集標準化處理；

(2) 依據(jù)式(6)計算出網(wǎng)格劃分參數(shù)side，將數(shù)據(jù)空間劃分為均等且不相交的網(wǎng)格單元；

(3) 將數(shù)據(jù)點映射至相應的網(wǎng)格單元中，由式(7)和式(8)求出各網(wǎng)格的代表點，并統(tǒng)計每個網(wǎng)格中分別所含數(shù)據(jù)點數(shù)目；

(4) 根據(jù)式(9)和式(10)計算網(wǎng)格代表點Pi的局部密度ρi；

(5) 計算網(wǎng)格代表點之間的距離矩陣Dij，并求出密度參數(shù)dc；

(6) 將網(wǎng)格代表點按ρi進行倒序排列，由式(11)計算各網(wǎng)格代表點的高密度距離δi；

(7) 由式(12)和式(13)自適應確定聚類中心代表點，按照ρi降序分類到距其最短的且局部密度大于該點的網(wǎng)格代表點所在類中，將原數(shù)據(jù)集中所有數(shù)據(jù)點歸類到其所在網(wǎng)格代表點所屬類中；

(8) 由密度參數(shù)dc計算出當前類的邊界點集，選出邊界點集中密度最大的代表點,并將該點的密度作為劃分當前類的核心代表點和噪聲點的閾值，剔除當前類別中小于此密度閾值的代表點及代表點所在網(wǎng)格中的其他數(shù)據(jù)點；

(9) 返回最終聚類結(jié)果。

2.5 高維數(shù)據(jù)降維方法

降維是處理高維數(shù)據(jù)的一種有效方法，降維技術(shù)分為線性降維和非線性降維。線性降維方法主要有主成分分析(Principal Component Analysis，PCA)和多維尺度分析(Multi-Dimensional Scaling，MDS)[30]等；非線性流形降維方法主要有等距映射(Isomap)[31]、局部線性嵌入(Local Linear Embedding，LLE)[32-33]和拉普拉斯特征映射(Laplacian Eigenmaps，LE)[34]等。與傳統(tǒng)的線性降維方法相比，非線性降維方法能更有效地發(fā)現(xiàn)復雜高維數(shù)據(jù)內(nèi)嵌的低維結(jié)構(gòu)。

本文采用LE方法進行降維，該方法用局部的角度去構(gòu)建數(shù)據(jù)之間的關(guān)系。其主要思想是高維空間中距離近的點投影到低維空間后距離也應盡量接近。

定義對角矩陣D，對角線上(i，j)位置元素等于矩陣W的第i行之和，經(jīng)過線性代數(shù)變換，上述優(yōu)化問題可以用矩陣向量形式表示如下：

mintr(YTLY) s.t.YTDY=1

(15)

式中:矩陣L=D-W是圖拉普拉斯矩陣。限制條件YTDY=1保證優(yōu)化問題有解，并且保證映射后的數(shù)據(jù)點不會被“壓縮”到一個小于m維的子空間中。算法具體步驟如下：

(1) 使用K最近鄰方法構(gòu)建稀疏鄰接圖，若i在j的k個最近鄰之中，則i和j有邊，否則無邊；

(2) 采用直接映射方法為每條邊賦值權(quán)重。若i、j相連，則wij取值1，否則為0；

(3) 通過式(16)計算拉普拉斯矩陣L的特征向量與特征值：

Ly=λDy

(16)

式中：D是對角矩陣，滿足式(17)和式(18)，選擇最小的m個非零特征值對應的特征向量作為降維后的結(jié)果輸出。

L=D-W

(18)

2.6 聚類效果評價指標

本文通過聚類精度(Accuracy)和歸一化信息熵(Normalized Mutual Ingormation，NMI)兩種聚類評價指標來檢測G-DPC算法的聚類效果。同時，也將該算法與其他算法的運行時間對比作為聚類效率的主要評價指標。此外，還通過對算法的時間復雜度和空間復雜度進行探討以分析算法效率。

(1) Accuracy作為聚類效果的評價指標，其公式如下：

(2) NMI評價標準通過計算聚類結(jié)果與真實類別標號之間的互信息來評價聚類結(jié)果與真實類別標號的一致性[35],其公式如下：

3 實驗仿真

3.1 數(shù)據(jù)測試

本文實驗所采用的計算機硬件配置為Intel Core i7處理器(主頻3.4 GHz)、16 GB內(nèi)存；實驗的軟件環(huán)境為Windows10操作系統(tǒng)，采用MATLAB編程實現(xiàn)本文算法。

本實驗選取兩組數(shù)據(jù)集進行測試。

第一組采用六個不同數(shù)據(jù)量且維度都為2的低維人工數(shù)據(jù)集，主要用來分析隨著數(shù)據(jù)量的增加，G-DPC算法與DPCA算法、DBSCAN算法以及GRIDBSCAN算法的時間效率。其中Compound[36]、Aggregation[37]、unbalace[38]、D31[39]、t4.8k[40]為小規(guī)模數(shù)據(jù)集，Birch3[41]為較大規(guī)模數(shù)據(jù)集，共有10萬條。實驗中關(guān)涉的相似度矩陣計算均采取歐幾里得方法。各數(shù)據(jù)集的詳細信息及實驗對照結(jié)果如表1所示。

表1 低維數(shù)據(jù)集算法效果對比

續(xù)表1

為了更直觀地對比DPC算法和G-DPC算法DPCA算法、DBSCAN算法以及GRIDBSCAN算法的效率，通過表1數(shù)據(jù)給出了幾種算法的運行時間和精確率對比圖，如圖4和圖5所示。因Birch3數(shù)據(jù)集過大，DPC算法運行過程中內(nèi)存溢出而無法完成聚類，所以只對前五個數(shù)據(jù)集進行可視化。

圖4 低維數(shù)據(jù)集的算法運行時間對比

圖5 低維數(shù)據(jù)集的精確度對比

通過表1、圖4和圖5可以得出，DPC算法和DBSCAN算法隨著數(shù)據(jù)量的增加算法開銷的時間成指數(shù)型增長，而本文的G-DPC算法時間增長和數(shù)據(jù)量成線性關(guān)系，且比GRIDBSCAN算法更快。

圖6為G-DPC算法在數(shù)據(jù)集Birch3上的聚類效果圖，聚類結(jié)果基本符合圖1中的數(shù)據(jù)分布情況。因此本文中算法在處理大范圍數(shù)據(jù)集上有著明顯的優(yōu)勢，由于是基于網(wǎng)格的算法，在精確度指標上稍遜于DPC算法，但是差距很小，總體效果依然優(yōu)異。

圖6 Birch3數(shù)據(jù)集聚類結(jié)果

第二組數(shù)據(jù)采用UCI公共數(shù)據(jù)集中的Iris、seeds、wine和ring四個高維數(shù)據(jù)集對G-DPC和DPCA算法、DBSCAN算法以及GRIDBSCAN算法進行試驗，采用拉普拉斯特征映射方法降維，并對照幾種算法對高維數(shù)據(jù)的運行效率。各數(shù)據(jù)集的詳細信息如表2所示，圖7和圖8分別為各算法的運行時間對比圖以及精確率對比圖。

表2 高維數(shù)據(jù)集信息

圖7 高維數(shù)據(jù)集精確度對比圖

圖8 高維數(shù)據(jù)集的算法運行時間對比

由圖7和圖8可以看出，G-DPC算法在高維數(shù)據(jù)集上聚類精度相較于低維數(shù)據(jù)集略低，但總體來說聚類效果依然良好。在精確度指標上，G-DPC算法和DPC算法結(jié)果相差不大，聚類質(zhì)量基本持平，均遠高于DBSCAN算法和GRIDBSCAN算法。而在對高維數(shù)據(jù)集處理的時間效率上G-DPC算法遠遠優(yōu)于DPC算法。

由上述實驗可得，G-DPC算法極大地減少了內(nèi)存和計算的開銷，降低了時空復雜度，提升了運行速度。雖然該算法因為基于網(wǎng)格劃分而對噪聲點的處理較為敏感，精確率略有偏差，但并不影響總體效果。

3.2 算法分析

本文提出的G-DPC算法在時間上的開銷包括網(wǎng)格劃分、數(shù)據(jù)聚類、數(shù)據(jù)點歸類和邊界點處理共四個部分。其中：網(wǎng)格劃分包括數(shù)據(jù)點映射至相應網(wǎng)格，和對網(wǎng)格單元信息的統(tǒng)計，時間復雜度為O(n)；數(shù)據(jù)聚類的過程中耗費的最大時間代價為各網(wǎng)格代表點距離矩陣的計算，時間復雜度為O(k2)；數(shù)據(jù)點歸類是先將非核心代表點歸類到核心點，時間復雜度為O(k2)，其次將網(wǎng)格中的數(shù)據(jù)點歸入其代表點所屬類中，復雜度為O(n)；對邊界點的處理是先找到每個類中的邊界代表點集，選出其中最高密度代表點密度作為閾值劃分核心點和噪聲點，時間復雜度為O(bk),其中b表示邊界點代表點的個數(shù)。因此G-DPC算法的時間復雜度為：

Tall=2×O(n)+2×O(k2)+O(bk)

(14)

而原始的DPC算法在時間的開銷上包含數(shù)據(jù)點之間的距離矩陣的計算，尋找聚類中心和非聚類中心的歸類，所耗費的時間復雜度為O(n2)。

空間復雜度方面，G-DPC算法將數(shù)據(jù)點映射到k個網(wǎng)格單元中(假設為理想狀態(tài)，數(shù)據(jù)均勻劃分)，其空間復雜度為O(k2)，而原DPC算法中構(gòu)建距離矩陣的過程與數(shù)據(jù)總數(shù)有關(guān)，其空間復雜度為O(n2)。

4 結(jié) 語

DPC算法需人工指定聚類中心個數(shù)，對數(shù)據(jù)對象距離矩陣的計算需耗費大量的時間和空間，限制了對大規(guī)模數(shù)據(jù)集的處理。本文基于網(wǎng)格聚類的思想進行網(wǎng)格劃分，用網(wǎng)格代表點替代網(wǎng)格單元整體，從而減少計算次數(shù)。然后對各代表點進行聚類，大大降低了距離矩陣計算的時空復雜度，通過自動確定聚類中心的方法降低了人工取值帶來的誤差。在多種標準數(shù)據(jù)集的實驗結(jié)果驗證了G-DPC算法對大小規(guī)模數(shù)據(jù)集進行聚類的有效性。