融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法

趙燕偉,朱 芬,桂方志,任設東,謝智偉,徐 晨

1(浙江工業(yè)大學 特種裝備制造與先進加工技術(shù)教育部 浙江省重點實驗室,杭州 310014)2(浙江工業(yè)大學 計算機科學與技術(shù)學院,杭州 310014)

1 引 言

聚類是數(shù)據(jù)分析的重要手段,將數(shù)據(jù)集分為若干類,使得簇內(nèi)緊密且相似性大,簇與簇之間有明顯區(qū)別,使得相似性最小[1],在模式識別、圖像處理和風險管理等領域被廣泛應用[2-5].大數(shù)據(jù)背景下的海量和多樣數(shù)據(jù)的存在,使得聚類算法的研究對這些數(shù)據(jù)背后隱藏的模式和規(guī)律的發(fā)現(xiàn)具有重要意義.

聚類算法有劃分式、密度式,網(wǎng)格式等[6,7],其中劃分式聚類算法主要以K-means算法為代表,密度式聚類算法主要以DBSCAN[8,9]算法為代表,網(wǎng)格式主要以CLIQUE[10]算法為代表.盡管許多聚類算法被提出,但對聚類的研究仍在不斷地探索中.2014年Alex Rodriguez 和 Alessandro Laio等[11]提出了一種密度峰值聚類算法CFSFDP,憑借其能自動發(fā)現(xiàn)數(shù)據(jù)集樣本的類簇中心,實現(xiàn)任意形狀的樣本高效聚類等優(yōu)勢,引起了大量學者的關(guān)注,但是該算法存在明顯缺陷:當數(shù)據(jù)集中存在多個密度峰值或者某一個非中心樣本點分配錯誤就會出現(xiàn)連續(xù)分錯現(xiàn)象[12].對此學者提出了不同的改進方法:賈培靈等[13]針對某個類存在多個密度峰值導致聚類不理想問題,提出一種基于簇邊界劃分的DPC算法;薛小娜等[14]提出了一種結(jié)合k近鄰的改進密度峰值聚類算法,結(jié)合k鄰域思想設計了全局搜索分配策略;Wang S L等[15]提出了一種利用原始數(shù)據(jù)集中數(shù)據(jù)場的潛在熵自動提取閾值最優(yōu)值的新方法;MehmoodR等[16]提出了一種自適應選擇聚類中心的模糊CFSFDP方法,具有較好的魯棒性和有效性;謝娟英等[17]提出一種基于k近鄰的快速密度峰值搜索并高效分配樣本的聚類算法,對噪聲數(shù)據(jù)具有非常好的魯棒性;Mehmood R等[18]提出了一種通過熱擴散密度峰值算法,用于采用非參數(shù)估計給定數(shù)據(jù)集的概率分布,對截止距離的選擇和核密度估計進行校正;Zhou Y等[19]提出了一種基于密度比的方法來聚類,通過使用密度估計器計算密度比,修改基于密度的聚類算法以進行基于密度比的聚類;Du M等[20]提出了一種基于k個最近鄰點的密度峰聚類,并將主成分分析(PCA)引入到DPC-KNN模型中,進一步提出了基于PCA的方法,該方法對高維數(shù)據(jù)有更好的聚類效果;劉如輝等[21]提出半監(jiān)督約束集成的快速密度峰值聚類算法,自動選擇候選中心點提高聚類性能具有更高的聚類精度.Chen等[22]摒棄對單個初始中心點的尋找,通過用一半高密度的點生成初始聚類輪廓,完成聚類.

現(xiàn)有的研究雖取得了一定的成效,但簇心選取及未分配點分配準確率仍然不高,一方面原因是簇心質(zhì)量不佳,另一方面是由于其所采取的最近鄰原則分配策略本質(zhì)上都是基于歐式距離計算而來的密度值,并沒有從本質(zhì)上挖掘出樣本點間的相關(guān)性,造成樣本分配錯誤.因此本文提出一種融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法,引入基于平均差異度的密度度量方式,并提出一種基于可拓關(guān)聯(lián)函數(shù)和k鄰域思想的分配策略,實現(xiàn)對未分配點進行準確分類.通過對比實驗驗證,該方法具有更好的聚類效果和聚類準確率.

2 相關(guān)知識介紹

2.1 可拓關(guān)聯(lián)函數(shù)相關(guān)知識介紹

為刻畫論域中的元素具有某種性質(zhì)的程度,蔡文[23]等提出了可拓關(guān)聯(lián)函數(shù)的概念,通過建立實域上可拓集的關(guān)聯(lián)函數(shù)基本公式,定量客觀的描述元素具有某種性質(zhì)的程度及其量變與質(zhì)變的過程.該概念在分類檢索和故障預警等方面廣泛應用,趙燕偉等[24]提出一種基于可拓距的多維關(guān)聯(lián)函數(shù)產(chǎn)品低碳設計分類方法,解決了低碳設計中因需求變化所引起的分類跳躍性問題;任設東等[25]提出一種基于關(guān)聯(lián)函數(shù)多屬性相似實例檢索方法,克服了歐式距離檢索的不準確性;洪歡歡等[26]提出了一種多維關(guān)聯(lián)函數(shù)建模及其檢索應用方法,解決多維度實例檢索建模及其降維計算的問題.可見,可拓關(guān)聯(lián)函數(shù)在描述事物相似度具有較大優(yōu)勢,將其與聚類算法結(jié)合,充分發(fā)揮其優(yōu)勢是目前研究的重要方向.

在建立關(guān)聯(lián)函數(shù)前,為了描述類內(nèi)事物的區(qū)別,引入可拓距和位值等概念:

實軸上任意一點x與區(qū)間X0=之距為:

(1)

設X0=,X=,且X0?X則稱:

D(x,X0,X)=

(2)

為點x關(guān)于區(qū)間X0和X組成的區(qū)間套的位值.

設X0=,X=,且X0?X,則:

(3)

稱k(x)為點x關(guān)于區(qū)間X0和X的關(guān)聯(lián)函數(shù).通過關(guān)聯(lián)函數(shù)描述事物具有某種性質(zhì)的程度,即將“具有某性質(zhì)”的事物從定性描述擴展到“具有該性質(zhì)的程度”的定量描述.k(x)≥0表明x屬于區(qū)間X0,k(x)<0表明x不屬于區(qū)間X0.

(4)

稱K(O)為對象O的綜合關(guān)聯(lián)函數(shù),vi為對象O第i個屬性對應的值.

2.2 CFSFDP算法介紹

CFSFDP算法以其決策圖思想和一步分配策略思想,引起很多學者的關(guān)注,即提出決策圖概念自動發(fā)現(xiàn)數(shù)據(jù)集中樣本的類簇中心,并快速分配非中心點,實現(xiàn)任意形狀的高效聚類[12].

該算法認為理想的類簇中心應具備兩個基本特征:

1)該點局部密度大于圍繞它的樣本點的局部密度;

2)不同簇心間距離相對較遠.為找到滿足上述要求的點,對于每個數(shù)據(jù)i都引入了局部密度ρi和相對距離δi兩個概念:

(5)

(6)

其中dc為截斷誤差,dij是數(shù)據(jù)i和j之間的歐式距離.

(7)

可知當數(shù)據(jù)i的局部密度ρi不是最大值時,其相對距離δi為在所有的局部密度大于數(shù)據(jù)對象i的數(shù)據(jù)對象中,與數(shù)據(jù)對象i的距離最小的數(shù)據(jù)與數(shù)據(jù)i間的距離;當數(shù)據(jù)i的局部密度ρi最大時,δi為數(shù)據(jù)集中與數(shù)據(jù)i距離最大的距離.

CFSFDP算法認為簇心往往是δ異常大的樣本點,同時這些樣本點的局部密度ρ也相對較高.通過構(gòu)造樣本相對距離δ和局部密度ρ的決策圖選擇簇心;獲取簇心后,將剩余樣本點采用最近原則將其分配到更高密度的最近鄰類簇中,一步分配,快速簡潔.

但CFSFDP算法具有如下缺陷:

1)該算法采用小于截斷距離樣本的個數(shù)作為樣本點密度,對于擁有相同密度即具有相同小于截斷距離的樣本個數(shù)的節(jié)點而言,無法更加細致地區(qū)分2個節(jié)點誰更加稠密,從而對后期結(jié)合決策圖選取簇心造成一定干擾;

2)對于其高效的一步分配策略,會出現(xiàn)“多米諾骨牌效應”,即:一旦某個數(shù)據(jù)點分配錯誤,會影響剩余數(shù)據(jù)點的分配,現(xiàn)有的研究所提出的分配策略本質(zhì)上都是基于歐式距離計算而來的密度值進行最近鄰原則分配雖然取得一定的效果,但并沒有從本質(zhì)上挖掘出樣本點間的相關(guān)性,造成樣本分配錯誤,出現(xiàn)“多米諾骨牌效應”.

3 可拓關(guān)聯(lián)函數(shù)改進的密度峰值聚類算法

為有效處理CFSFDP算法中存在的兩個缺陷,本文將從密度度量方式和分配策略對其進行改進.

1)引入節(jié)點平均差異度[27]概念衡量樣本密度,對各樣本點的密度更加細致的進行區(qū)分,便于更加準確的對簇心進行選擇;

2)引入可拓關(guān)聯(lián)函數(shù)充分考慮樣本點與簇心之間相關(guān)性,用以揭示樣本點的類屬關(guān)系,提高樣本點分配的正確率,從而解決CFSFDP算法的“多米諾骨牌效應”問題.在闡述本文算法之前,需先對節(jié)點局部平均差異度、可拓關(guān)聯(lián)函數(shù)的節(jié)域和經(jīng)典域進行相關(guān)定義.

3.1 相關(guān)定義

為便于表述,首先定義樣本物元模型、簇心ζ的k距離、簇心ζ的k距離鄰域、樣本集節(jié)域和簇心ζ的k距離鄰域的經(jīng)典域等概念.對于樣本集O={O1,O2,…,On},其中Oi為m維向量(i=1,2,…,n),有如下定義:

定義1.節(jié)點局部平均差異度,即密度:

(8)

定義2.樣本物元模型:樣本Oi表示為:

(9)

其中C為樣本Oi的屬性特征,C=[c1,c2,…,cn],V為樣本Oi屬性特征所對應的值,V=[v1,v2,…,vn].

定義3.簇心ξ的k距離:

簇心點ξ的k距離是ξ到它的k最近鄰的最大距離,記為k_dist(ζ).

(10)

其中Q(ζ)為簇心點ζ到它k最近鄰樣本點的集合,k的值不能過大,影響聚類正確率,也不能過小,增加算法運行時間,一般取值為簇心個數(shù)的2～4倍.

定義4.簇心ζ的k距離鄰域:與簇心ζ距離小于k_dist(ζ)的樣本點集合,記為N(ζ)

定義5.樣本集節(jié)域:

(11)

為該樣本集O第j維屬性值的取值范圍,即為各屬性的節(jié)域.

定義6.簇心ζ的k距離鄰域的經(jīng)典域:

(12)

為第i個簇心ζi的k距離鄰域N(ζi)第j維屬性的取值范圍,即為各屬性的經(jīng)典域.

3.2 算法基本思想

本文提出的算法首先基于各節(jié)點平均局部差異度及距離繪制決策圖快速找到簇心,之后基于RDCA算法[12]中k距離鄰域思想,提出基于簇心點的k距離鄰域,得到各簇心的雛形簇心類;最后融合可拓關(guān)聯(lián)函數(shù)對各雛形簇心類不斷外擴,從而完成最終的聚類.

圖1 密度展示結(jié)構(gòu)圖Fig.1 Picture of density display

如圖1所示,以樣本點14,4,16為例,分別畫出以該點為圓心,以截斷距離dc為半徑的圓,可看出在圓內(nèi),樣本數(shù)都為4個,傳統(tǒng)的CFSFDP算法將其個數(shù)作為樣本點密度,即樣本點14,4,16密度相等,但圖中可看出,雖然樣本數(shù)相等,但各圓內(nèi)樣本與圓心的疏密程度是有所區(qū)別的,故本文提出的算法引入節(jié)點平均局部差異度概念描述樣本點的密度,對樣本點密度進行更細致的描述;進而利用決策圖找出簇心.

圖2 分配策略思想結(jié)構(gòu)圖Fig.2 Figure of distribution strategy

獲取簇心后,進行樣本的分配,本文采用的分配策略實際是在聚類算法中引入分類的思想,基于可拓關(guān)聯(lián)函數(shù)對樣本點類簇歸屬情況給出相應的分配策略如圖2所示,提高樣本點聚類的準確性,從而降低CFSFDP算法“多米諾骨牌效應”對聚類效果的不利影響.

根據(jù)改進后的決策圖選出簇心,如圖2(a)中所示,點14,16,4為決策圖選出的3個簇心,將除簇心外的其他點都標記為未分配點;根據(jù)簇心的k距離鄰域,得到各雛形簇心類,如圖2(b)中虛線圓所示,并將樣本點1,6,12,5,18,20,2,7,11標記為已分配點;如圖2(c)中,在未分配點中隨機挑出一個樣本點13分別計算樣本點13與各雛形簇心類的關(guān)聯(lián)函數(shù)值,即相關(guān)度值,根據(jù)相關(guān)度值將樣本13分配到相關(guān)度大的簇類中,并將其標記為已分配點;依次判斷剩余未分配點,如圖2(d)所示,直至完成所有未分配點的分配,即樣本點聚類完成.

3.3 算法的實施步驟

Step 1.根據(jù)公式(8)和公式(7)計算各樣本的局部平均差異度ρ和相對距離δ;

Step 2.根據(jù)ρ和δ值,繪制出樣本點的決策圖,從而確定簇心ζ;

Step 3.根據(jù)定義3中的公式(10)與定義4分別計算出各簇心ζi的k距離k_dist(ζi)及k距離鄰域N(ζi);

Step 4.將k距離領域N(ζi)默認分配到各自的對應的ζi簇心類cluster(i)中,并將其標記為已分配點,剩余點標記為未分配點;根據(jù)定義5中公式(11)計算出樣本集各屬性的節(jié)域vcj;

第三，某些選修課程設置的初期忽視了學生的呼聲和意見。某些選修課程的設置不但要圍繞某種理念進行，對學生的興趣也要加以兼顧，以利于提高學生的學習興趣。

Step 5.從簇心集ζ中隨機取出一個未被訪問的簇心ζi,并將標ζi記為已訪問點.

圖3 算法流程結(jié)構(gòu)圖Fig.3 Algorithm flowchart

Step 6.根據(jù)定義6中公式(12)計算出雛形ζi簇心類cluster(i)樣本各屬性的經(jīng)典域vq,j,并根據(jù)公式(1-3)建立未分配點各屬性的關(guān)聯(lián)函數(shù),獲得對應相關(guān)度值.

Step 7.根據(jù)信息熵[28]計算出各屬性權(quán)值,由公式(3)和公式(4)建立未分配點綜合關(guān)聯(lián)函數(shù),獲得各未分配點關(guān)于雛形ζi簇心類cluster(i)的綜合相關(guān)度值;

Step 8.若ζ中仍存在未訪問簇心點,則返回到Step 5,直至ζ中所有簇心被訪問,則進入下一步;

Step 9.將未分配點分配到綜合相關(guān)度值大的簇心類,完成未分配樣本點的聚類.

該算法流程如圖3所示.

3.4 算法復雜度分析

4 實驗驗證與分析

4.1 實驗數(shù)據(jù)集和評價指標

本文改進的算法,通過Python語言編寫,用Spyder工具對實驗結(jié)果進行顯示.為了驗證算法的有效性,本文選取4組人造數(shù)據(jù)和7組不同UCI數(shù)據(jù)庫數(shù)據(jù)集進行實驗,通過與CFSFDP算法、文獻[14]改進過的IDPCA算法、DBSCAN算法和K-means算法進行對比,以驗證本文算法的性能.各數(shù)據(jù)的特征如表1所示,其中,Aggregation、Jain和Three cluster是人造數(shù)據(jù);Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC是UCI數(shù)據(jù)庫中的真實數(shù)據(jù).

聚類效果的衡量標準,分為可視化衡量和定量衡量兩種,其中可視化衡量方法可以清晰明了的體現(xiàn)聚類結(jié)果和樣本的分布;定量衡量指標采用聚類準確率[29]指標(Accuracy,ACC)作為聚類算法性能度量標準.ACC取值范圍為[0,1],指標值越大,表明聚類質(zhì)量越高.

表1 各數(shù)據(jù)集的基本特征
Table 1 Characteristics of the data set

數(shù)據(jù)集樣本個數(shù)樣本維數(shù)分類數(shù)Aggregation78827Jain37323Three cluster60023Data1150023Iris15043Wine179133Seeds21073Ionosphere351342WDBC569302Waveform35000213CMC147393

4.2 改進的密度峰值聚類算法性能分析

4.2.1 可視化數(shù)據(jù)集實驗結(jié)果分析

實驗采用4組數(shù)據(jù)集做可視化展示:Aggregation、Jain、Three cluster和Data1,其中Aggregation數(shù)據(jù)集簇間密度相對均勻,形狀多樣且簇與簇之間有連接;Jain數(shù)據(jù)集非線性分布,密度差異較大;Three cluster數(shù)據(jù)集形狀相似,各簇樣本密度相對均勻,簇間無交集;Data1數(shù)據(jù)集線性分布,疏密差異不大.

圖4-圖7是4組數(shù)據(jù)集分別基于這5種算法聚類得到的結(jié)果:圖4,圖5分別是基于Aggregation數(shù)據(jù)集與Three cluster數(shù)據(jù)集聚類的結(jié)果,其中圖4(d)IDPCA算法聚類效果最好,其次是圖4(b)本文算法,聚類效果最差的是圖4(f)K-means算法,而在圖5中聚類效果最好的是圖5(f)K-means算法,主要原因在于K-means算法對簇型數(shù)據(jù)集且各簇間彼此不相連的數(shù)據(jù)集聚類效果較好,其次是圖5(b)本文算法聚類效,表明本文算法對簇型且各簇有相連的數(shù)據(jù)集聚類效果較好.

圖6,圖7分別是基于Jain數(shù)據(jù)集與Data1數(shù)據(jù)集聚類的結(jié)果,圖6中圖6(b)本文算法聚類效果最好,其次是圖6(d)IDPCA算法和圖6(e)DBSCAN算法,最差的是圖6(c)CFSFDP算法與圖6(f)K-means算法,原因在于CFSFDP算法對樣本疏密度較為敏感,K-means算法對非簇型聚類效果不好;圖7中圖7(d)IDPCA算法聚類效果最好,其次是圖7(b)本文算法和圖7(e)DBSCA算法,最差的是圖7(f)K-means算法,表明本文算法對不同疏密與非線性數(shù)據(jù)集具有較好的聚類效果.

圖4 Aggregation數(shù)據(jù)集聚類Fig.4 Aggregation dataset cluster

圖5 Three cluster數(shù)據(jù)集聚類Fig.5 Three cluster dataset cluster

圖6 Jain數(shù)據(jù)集聚類Fig.6 Jain dataset cluster

圖7 Data1數(shù)據(jù)集聚類Fig.7 Data1 dataset cluster

其中,圖(a)為實際聚類結(jié)果,圖(b)為本文算法聚類結(jié)果,圖(c)為CFSFDP算法聚類結(jié)果,圖(d)為IDPCA算法聚類結(jié)果,圖(e)為DBSCAN算法聚類結(jié)果,圖(f)為K-means聚類結(jié)果.

圖8是5種算法聚類準確率對比圖,從圖中可看出Aggregation和Three cluster數(shù)據(jù)集整體聚類結(jié)果偏好,聚類準確率浮動不大;從非線性和線性且密度有差異的兩組數(shù)據(jù)集Jain和Data1中可看出,本文算法對密度差異大的線性和非線性數(shù)據(jù)聚類效果更好,其次是IDPCA算法,CFSFDP算法和K-means算法聚類效果相對較差.

圖8 該5種算法聚類準確率對比圖Fig.8 Clustering accuracy ratio comparison chart

其中,x軸坐標中0:樣本真實分布;2:本文算法;4:CFSFDP算法;6:IDPCA算法;8:DBSCAN算法;10:K-means算法.

4.2.2 非可視化數(shù)據(jù)集實驗結(jié)果分析

為了進一步驗證本文算法的有效性,選取7組來自UCI數(shù)據(jù)庫的實驗數(shù)據(jù)集Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC數(shù)來測試,這7組數(shù)據(jù)都有明確的分類標簽,因此可以用來對比驗證聚類結(jié)果的好壞及算法的性能.

表2為各算法基于Iris,Wine,Seeds,Ionosphere,WDBC,waveform3和CMC 7個真實數(shù)據(jù)集聚類后的ACC評價指標值.

表2 7個數(shù)據(jù)集聚類后的ACC指標
Table 2 ACC indicator after clustering of data sets

數(shù)據(jù)集本文算法CFSFDPIDPCADBSCANKmeansIris0.9690.94—0.7930.78Wine0.9100.8830.8960.6650.7Seeds0.9470.8950.9380.7150.89Iono-sphere0.7880.6810.7690.6070.712WDBC0.9630.6130.9490.8700.928Waveform30.6980.5860.665—0.501CMC0.6750.65—0.560.35

從表2中可得出本文算法在聚類準確率上整體優(yōu)于其他4種算法,尤其對高維度的數(shù)據(jù)集Ionosphere,WDBC,Waveform3聚類優(yōu)勢更明顯.通過5種算法對UCI真實數(shù)據(jù)集的聚類準確性的對比分析可以發(fā)現(xiàn),本文提出的算法具有良好的聚類性能,優(yōu)于CFSFDP算法、IDPCA算法、DBSCAN算法和K-means算法.

5 總 結(jié)

本文針對由于CFSFDP算法聚類準確率低的問題,提出一種融合可拓關(guān)聯(lián)函數(shù)的密度峰值聚類算法.采用平均差異度作為樣本密度衡量指標,借鑒CFSFDP算法決策圖選取簇心;從簇心出發(fā)引入k鄰域及關(guān)聯(lián)函數(shù)思想對未分配點完成準確聚類.該算法在不同類型數(shù)據(jù)集上的實驗,證明了本文提出的算法對任意形狀,任意密度的數(shù)據(jù)集的聚類效果和聚類準確性均優(yōu)于經(jīng)典的CFSFDP算法、DBSCAN算法、K-means算法及改進的IDPCA算法.但本文算法中k鄰域的參數(shù)k的取值是憑經(jīng)驗選取,如何實現(xiàn)針對不同數(shù)量及不同維度的數(shù)據(jù)集自動選取最優(yōu)k值是今后研究的方向.