一種自適應的密度峰值聚類算法

馬淑華, 尤海榮, 唐 亮, 何 平

(東北大學秦皇島分校 控制工程學院, 河北 秦皇島 066004)

隨著計算機技術的發(fā)展,數(shù)據(jù)和信息呈現(xiàn)井噴式增加,使得大數(shù)據(jù)技術日趨成熟.其中數(shù)據(jù)挖掘技術是在海量的數(shù)據(jù)中挖掘有價值的信息,使數(shù)據(jù)實現(xiàn)價值最大化,在當今時代顯得尤為重要.聚類算法是數(shù)據(jù)挖掘技術中的一個重要領域,用以描述事物之間的差異及相似性,因此對聚類算法進行研究具有十分重要的價值和意義.當前的聚類算法大致可分為以下6類:

1) 基于劃分的聚類算法.基于劃分的聚類算法原理是首先創(chuàng)建k個類別,挑選初始中心后根據(jù)啟發(fā)式算法進行更新迭代從而獲取最優(yōu)效果[1].這類算法中最常見的就是K-means算法,后續(xù)又演變出K-medoids,K-modes,K-medians,kernel K-means等算法[2-7].這類算法簡單高效,但是容易出現(xiàn)局部最優(yōu)的情況,并且對初始值和噪聲十分敏感.

2) 基于層次的聚類算法.基于層次的聚類算法分為合并和分裂兩種.前者的基本原理是從底層開始,合并相似的聚類構建上一層聚類,直到所有數(shù)據(jù)都合并成一層聚類時終止.后者恰恰相反,從一類包含所有數(shù)據(jù)的類別開始,即從頂層開始,然后從上而下進行類別分裂,直到一個數(shù)據(jù)點為一個類別結(jié)束[8].常見的此類算法有平衡迭代削減聚類(BIRCH)算法等[9].這類算法可解釋性好,但是時間復雜度十分高.

3) 基于網(wǎng)絡的聚類算法.此類算法原理比較簡單,就是將數(shù)據(jù)劃分為網(wǎng)格空間,然后判斷網(wǎng)格空間是否符合高密度的條件,如果是,將相鄰的兩個高密度單元定為一簇[10].常見的基于網(wǎng)格的聚類算法有數(shù)據(jù)信息網(wǎng)格(STING)算法、集群查詢(CLIQUE)算法等[11].此類算法速度很快,但其對參數(shù)敏感,并且不適用于不規(guī)則的數(shù)據(jù).

4) 基于模型的聚類算法.基于模型的聚類算法首先為數(shù)據(jù)假設了一個模型,然后尋找最佳擬合模型,大多采用基于概率的模型[12].這一類別常用的算法有高斯混合模型[13].此類算法對類的劃分不是十分死板,但是執(zhí)行效率不高.

5) 基于模糊的聚類算法.基于模糊的聚類算法是根據(jù)隸屬度對數(shù)據(jù)進行劃分的,克服了傳統(tǒng)聚類算法非此即彼的缺點,但是該算法依賴已有的初始聚類中心,因此還需要其他聚類算法進行配合[14].常見的此類算法有模糊C均值聚類(FCM)算法[15].

6) 基于密度的聚類算法.基于密度的聚類算法基本原理是畫圈,基于圈的半徑和圈的最小容量兩個參數(shù)進行劃分[16].此類算法中最常用的算法是帶噪聲的基于密度的應用程序空間聚類(DBSCAN)[17],最典型的基于密度的聚類算法是密度峰值聚類(density peak clustering, DPC)算法[18].此類算法可以應用于不規(guī)則形狀的聚類,并且對噪聲不敏感,但是聚類結(jié)果受參數(shù)影響比較大.

基于以上分析可以得知,基于密度的聚類算法性能最好,但是受參數(shù)影響比較大,聚類效果的好壞取決于參數(shù)選取是否精確.因此本文對密度峰值聚類算法進行了參數(shù)的自適應改進,從而進一步實現(xiàn)聚類算法的優(yōu)化.

1 DPC算法

密度峰值聚類算法是基于密度的聚類算法,其基本思想是聚類中心在其鄰域內(nèi)具有最高的密度值,并且與其他聚類中心距離較遠.該算法基于以下兩個參量:局部密度ρi和相對距離δi[18].

定義1局部密度ρi.局部密度根據(jù)數(shù)據(jù)的離散和連續(xù)分為截斷核和高斯核兩種計算方式,其中截斷核適用于離散數(shù)據(jù),計算公式為

ρi=∑j≠iχ(dij-dc) .

(1)

其中:i,j代表數(shù)據(jù)集中的兩個點;ρi代表第i個點的密度;dij代表第i個點和第j個點的歐氏距離;dc代表截斷距離.

χ(x)定義如下:

(2)

高斯核適用于連續(xù)數(shù)據(jù),計算公式為

(3)

定義2相對距離δi：

(4)

圖1 DPC算法的流程圖Fig.1 The flowchart of DPC algorithm

2 ADPC算法

傳統(tǒng)的密度峰值聚類算法對參數(shù)依賴性比較強,通常情況下密度峰值聚類算法依靠人工選定聚類中心和截斷距離dc值,比較耗費時間,并且在參數(shù)選擇不恰當時,聚類效果與預期效果大相徑庭.因此,本文對DPC算法的聚類中心的選擇和dc參數(shù)進行了自適應改進.

2.1 聚類中心的自適應選擇

首先,設計了一個綜合考慮局部密度ρi和相對距離δi的參數(shù)μi:

μi=ρilgδi.

(5)

根據(jù)DPC算法的特征,聚類中心與其他點相比具有較大的ρi和δi,本文選取對數(shù)函數(shù)來定義μi,因為聚類中心通常具有較大的局部密度ρi和相對距離δi,因此用式(5)來加大聚類中心的μi與其他點μi值的差異,得到μi之后,將μi值從大到小進行排序,然后計算μi值的下降趨勢,定義如下.

定義3下降趨勢：

(6)

其中:μi是當前的μ值;μi-1和μi+1分別代表前一時刻和后一時刻的μ值.

獲取到下降趨勢之后,取下降趨勢最大的點及前面的幾個點作為聚類中心.

2.2 dc參數(shù)的自適應選擇

DPC算法通常是經(jīng)過實驗驗證或者憑借經(jīng)驗獲得dc值,具有很大的不確定性,通常好的聚類算法劃分的同種類別的差異較小,因此選取dc值可以根據(jù)綜合衡量元素差異來獲取,本文正是采用衡量元素差距的參數(shù)——基尼系數(shù)去約束dc值,即求取基尼系數(shù)最小時的dc值.

定義4基尼系數(shù)G.傳統(tǒng)的基尼系數(shù)是用來衡量一個國家的居民收入差距的[19],本文采用該指標衡量聚類結(jié)果中每種類別內(nèi)元素的差異.定義如下:

(7)

其中:n代表數(shù)據(jù)集S中的樣本個數(shù);pi為i點的ρi×δi占所有點的比例,pi取值如下:

(8)

根據(jù)式(7)取最小值時的dc值作為最終的dc值,代替經(jīng)驗法或?qū)嶒烌炞C,從而達到自適應選取參數(shù)的效果.

2.3 ADPC算法整體流程

ADPC算法過程如表1所示.

表1 自適應密度峰值聚類算法過程Table 1 ADPC algorithm process

3 結(jié)果及評價

所有實驗均在Lenovo-Y7000P筆記本上進行,操作系統(tǒng)為Windows 10,Intel i5-9300H CPU,實驗平臺為Matlab R2018a.

3.1 數(shù)據(jù)集和評價指標

為了避免實驗結(jié)果的偶然性,本文選取了6組典型的聚類數(shù)據(jù)集進行了ADPC算法測試,包括:D31,Data1,Data2,Aggregation,Spiral,Fish數(shù)據(jù)集.重點對D31數(shù)據(jù)集聚類過程進行了詳細分析,對其數(shù)據(jù)集的聚類效果進行了展示,并且與DPC聚類算法以及最常用的K-means聚類算法進行了聚類效果對比.

本文采用常用的評估聚類效果的3項指標進行衡量,分別是調(diào)整蘭德指數(shù)ARI、標準化互信息NMI以及準確度AC.

3.2 ADPC算法聚類過程實現(xiàn)

以D31數(shù)據(jù)集為例對ADPC算法進行詳細說明及分析:

1) 首先將dc=1作為初始值,計算D31數(shù)據(jù)集的局部密度ρi和相對距離δi,并繪制決策圖,如圖2所示.

圖2 D31數(shù)據(jù)集的決策圖Fig.2 Decision graph of D31 dataset

2) 改變dc的值,并計算每個dc值對應的基尼系數(shù),繪制dc和基尼系數(shù)的關系圖,如圖3所示.

3) 根據(jù)圖3,當dc=2時,基尼系數(shù)具有最小值,因此令dc=2,重新繪制ρ-δ分布圖,新的分布圖如圖4所示,可以看出,新的分布圖具有更高的規(guī)律性,具有較大的局部密度ρi和相對距離δi的點分布比較集中.

圖3 基尼系數(shù)和dc的關系圖Fig.3 Gini coefficient and dc relationship diagram

圖4 改進后的決策圖Fig.4 Improved decision graph

4) 根據(jù)式(5)計算μi的值,并將其降序排列,繪制μi降序圖,如圖5所示.根據(jù)式(6)下降趨勢的定義,計算μi對應的下降趨勢值,并繪制下降趨勢圖如圖6所示,圖6中第31個點具有最高的下降趨勢,因此選取前31個點作為聚類中心點,聚類中心的選擇如圖7所示.

圖5 μi值的分布Fig.5 The values distribution of μi

圖6 下降趨勢圖Fig.6 The values distribution of Trend

圖7 聚類中心的選擇Fig.7 Selection of cluster centers

5) 根據(jù)已選好的聚類中心和dc值進行聚類,最終聚類結(jié)果如圖8所示,可以看出聚類效果較好.

圖8 聚類結(jié)果Fig.8 Clustering result

3.3 與DPC算法和K-means算法比較

3.3.1 聚類效果對比

本文將ADPC聚類算法與DPC算法和K-means算法進行了對比,D31,Data1,Data2,Aggregation,Spiral以及Fish數(shù)據(jù)集在3種聚類算法下的聚類結(jié)果如圖9～圖14所示.由聚類結(jié)果可以看出,Data1,Data2兩種數(shù)據(jù)集下,3種算法具有差不多的效果,聚類均比較精確,但是在Aggregation、Spiral和Fish數(shù)據(jù)集下,3種算法的聚類效果差異較大.

圖9 D31數(shù)據(jù)集Fig.9 D31 data set(a)—DPC； (b)—K-means； (c)—ADPC.

圖10 Data1數(shù)據(jù)集Fig.10 Data1 data set(a)—DPC； (b)—K-means； (c)—ADPC.

圖11 Data2數(shù)據(jù)集Fig.11 Data2 data set(a)—DPC； (b)—K-means； (c)—ADPC.

圖12 Aggregation數(shù)據(jù)集Fig.12 Aggregation data set(a)—DPC； (b)—K-means； (c)—ADPC.

圖13 Spiral數(shù)據(jù)集Fig.13 Spiral data set(a)—DPC； (b)—K-means； (c)—ADPC.

圖14 Fish數(shù)據(jù)集Fig.14 Fish data set(a)—DPC； (b)—K-means； (c)—ADPC.

Aggregation數(shù)據(jù)集的聚類效果如圖12所示,圖12a為DPC算法的聚類效果,在DPC算法下的聚類類別的區(qū)分不夠明顯,左下角黃色的類別以及右側(cè)黃色的類別沒有得到劃分.如圖12b所示，K-means算法中左下角的兩種類別被劃分很精確,但是右側(cè)的兩種類別依然沒有被劃分開.ADPC算法的聚類效果見圖12c,所有類別均被識別.

Spiral數(shù)據(jù)集在聚類數(shù)據(jù)集中比較具有代表性,與普通數(shù)據(jù)集不同的是,該數(shù)據(jù)集以環(huán)形分布,并且兩種類別的聚類比較近,不具有明顯的區(qū)別性.3種聚類算法的聚類效果見圖13,可以看出圖13a DPC算法和圖13b K-means算法的聚類效果較差,圖13c ADPC算法的聚類效果比較精確.

Fish數(shù)據(jù)集的聚類效果見圖14,可以看出K-means算法和ADPC算法的聚類效果較好.

綜上,針對一些容易區(qū)分的數(shù)據(jù)集,如Data1和Data2數(shù)據(jù)集,DPC,K-means和ADPC三種算法均有較好的聚類效果.但是對于一些不容易區(qū)分的數(shù)據(jù)集,如Aggregation,Spiral和Fish數(shù)據(jù)集,ADPC算法具有更好的聚類效果.

3.3.2 聚類效果評價

ARI指標的值在[-1,1]之間,值越大代表劃分程度越高,說明聚類效果越好.DPC,K-means以及ADPC算法在6種數(shù)據(jù)集下的ARI值如圖15所示.由圖15可以看出,ADPC相比DPC和K-means算法具有更高的ARI值.

圖15 ARI值對比Fig.15 Comparison of ARI values

NMI指標是度量兩個類別相似程度的指標,在[0,1]之間取值,指標值越大代表聚類效果越好.DPC、K-means以及ADPC算法在6種數(shù)據(jù)集下的NMI值如圖16所示,由圖16可以看出,ADPC相比于DPC和K-means算法在絕大部分情況下具有更高的NMI值.

圖16 NMI值對比Fig.16 Comparison of NMI values

AC指標是衡量聚類準確度的指標,在[0,1]之間取值,越接近1代表精確度越高.DPC、K-means以及ADPC算法在6種數(shù)據(jù)集下的AC值如圖17所示,由圖17可以看出,ADPC相比DPC和K-means算法具有更高的AC值.

圖17 AC值對比Fig.17 Comparison of AC values

綜上,對ARI，NMI和AC三個指標的值進行整理,并計算平均值,如圖18所示,結(jié)果顯示,ADPC算法與DPC算法和K-means算法相比除了在Data2數(shù)據(jù)集中的NMI值低0.02以外,其他情況下均具有更高的ARI,NMI和AC值, 并且具有更高的ARI平均值、 NMI平均值和AC平均值.因此,ADPC算法具有相對于DPC算法和K-means算法更好的聚類效果.

圖18 三項指標的平均值Fig.18 Average of three indicators

4 結(jié) 語

本文對密度峰值聚類算法做出了改進,針對其不能自動選擇聚類中心的缺點,重新定義了綜合衡量局部密度ρi和δi相對距離的參量μi,針對其不能自動確定dc的問題,通過基尼系數(shù)去衡量dc的最佳值.選取了6組具有代表性的數(shù)據(jù)集進行了算法測試,首先根據(jù)D31數(shù)據(jù)集的聚類結(jié)果對自適應的聚類算法的聚類過程進行了詳細介紹,最后將6組數(shù)據(jù)集的聚類效果與DPC聚類算法和K-means算法進行了對比,并分別分析了ARI,NMI和AC三個指標.結(jié)果表明,ADPC算法具有較好的聚類效果.