江平平 曾慶鵬

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

0 引 言

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

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

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

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

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

1 DPC算法

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

定義1局部密度：一個數據點一定半徑內其他點的個數。點xi的局部密度ρi為：

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

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

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

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

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

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

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

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

(1) 初始化參數dc；

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

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

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

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

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

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

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

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

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

2.1 網格劃分

定義4網格邊長：假定存在一個d維數據集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維數據空間。將數據空間各個維度劃分成均等且不相交的網格單元[25-26]。網格邊長side計算公式為：

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

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

圖1 Birch3的數據分布

圖2 網格劃分后的數據分布

2.2 數據聚類

2.2.1自動選擇聚類中心

網格j中點的集合為P={p1,p2,…,plj},lj為該網格j內數據點的總個數。則該網格的代表點為:

定義6代表點局部密度值：網格代表點Pj的局部密度是網格j內數據點的個數，網格j中點的個數為:

式中：

則網格代表點Pj的局部密度為ρj=lj。

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

式中：Dkj是網格代表點Pk與網格代表點Pj的距離。

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

圖3 DPC算法決策圖

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

ρCi-μ(ρi)≥0

(12)

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

(13)

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

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

2.2.2數據點歸類

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

2.3 邊界點與噪聲點的處理

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

2.4 算法實現

G-DPC算法實現的具體步驟如下：

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

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

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

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

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

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

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

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

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

2.5 高維數據降維方法

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

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

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

mintr(YTLY) s.t.YTDY=1

(15)

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

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

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

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

Ly=λDy

(16)

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

L=D-W

(18)

2.6 聚類效果評價指標

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

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

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

3 實驗仿真

3.1 數據測試

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

本實驗選取兩組數據集進行測試。

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

表1 低維數據集算法效果對比

續(xù)表1

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

圖4 低維數據集的算法運行時間對比

圖5 低維數據集的精確度對比

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

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

圖6 Birch3數據集聚類結果

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

表2 高維數據集信息

圖7 高維數據集精確度對比圖

圖8 高維數據集的算法運行時間對比

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

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

3.2 算法分析

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

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

(14)

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

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

4 結 語

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