葉麗珠,鄭冬花,隋 棟,吳 迪

(1.廣州商學(xué)院 信息技術(shù)與工程學(xué)院,廣東 廣州 511363;2.馬來西亞管理與科學(xué)大學(xué) 研究生院,雪蘭莪 莎阿南 40100; 3.北京建筑大學(xué) 電氣與信息工程學(xué)院,北京 102406;4.哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

大數(shù)據(jù)分析給多個領(lǐng)域發(fā)展帶來了新的機(jī)遇,通過大數(shù)據(jù)技術(shù)可實(shí)現(xiàn)對各種復(fù)雜數(shù)據(jù)的潛在價值挖掘。聚類技術(shù)作為大規(guī)模數(shù)據(jù)統(tǒng)計(jì)分析的常用方法[1],能夠有效挖掘海量異構(gòu)多維數(shù)據(jù)之間的關(guān)系,完成非標(biāo)簽的數(shù)據(jù)分類,為復(fù)雜異構(gòu)數(shù)據(jù)的各種模型分析提供數(shù)據(jù)支持。通過聚類,將數(shù)據(jù)進(jìn)行有效歸類整理,提高數(shù)據(jù)的可用性。復(fù)雜高維數(shù)據(jù)聚類由于待聚類樣本數(shù)據(jù)結(jié)構(gòu)復(fù)雜,且呈現(xiàn)樣本特征分布稀疏與特征冗余明顯等特點(diǎn)[2],完成低失真聚類的難度大幅提升,因此針對高維數(shù)據(jù)的聚類需要采取更精準(zhǔn)的聚類算法。

當(dāng)前,關(guān)于高維數(shù)據(jù)聚類的研究成果較多,武森等人[3]從樣本特征擴(kuò)展的角度去降低高維樣本的聚類復(fù)雜度,解決了高維樣本的聚類問題,但聚類效果仍有待加強(qiáng)。向志華等人[4]采用貪心選擇算法提取高維樣本的關(guān)鍵特征,并采用特征加權(quán)方法對高維特征進(jìn)行重要排序,以達(dá)到降維作用,降低高維數(shù)據(jù)復(fù)雜度,但是聚類效率受到了影響。本文采用改進(jìn)密度峰值聚類(Density peaks clustering,DPC)算法用于數(shù)據(jù)聚類,為了提高DPC應(yīng)對高維數(shù)據(jù)樣本聚類的適應(yīng)度,采用人工蜂群(Artificial bee colony,ABC)算法對DPC的距離閾值進(jìn)行優(yōu)化改進(jìn),最后采用改進(jìn)的DPC算法解決復(fù)雜高維數(shù)據(jù)聚類的問題。

1 DPC

設(shè)N個樣本集X的類別總數(shù)為k,其數(shù)學(xué)表示為C={C1,C2,…,Ck},其中k≤N,且X=C1∪C2…∪Ck,Ci∩Cj=?(i≠j)。

點(diǎn)xi和點(diǎn)xj距離值[5]

(1)

式中:n為維數(shù)。

xi在所有樣本點(diǎn)中的密度[6]

(2)

式中:rc為距離閾值,χ(x)核函數(shù)一般為

(3)

在實(shí)際密度計(jì)算時,為了考慮核函數(shù)連續(xù)可導(dǎo),常引入高斯函數(shù)代替,則式(2)變?yōu)閇7]

(4)

xi的最小距離δi為距離xi最近且密度值比xi大的點(diǎn)的距離[8]

(5)

根據(jù)計(jì)算的ρi和δi生成決策圖,兩者中值較大的點(diǎn)成為候選中心點(diǎn)。為了找出ρi和δi均較大的點(diǎn),采用求積方式[9]

γi=ρi·δi

(6)

然后選擇ρi、δi和γi均較大的點(diǎn)作為簇中心點(diǎn),具體過程見圖1。

圖1 決策圖生成過程示意圖

圖1中樣本初始分布為3個類別,選擇ρi、δi和γi均較大的點(diǎn)作為簇中心,生成以2、13和30為候選簇中心的點(diǎn)。確定中心點(diǎn),接著按照各樣本點(diǎn)至簇中心的距離判定聚類類別。

2 改進(jìn)的DPC

2.1 ABC算法

ABC算法主要根據(jù)蜜源的搜尋路徑來尋找最優(yōu)解,現(xiàn)對ABC算法進(jìn)行數(shù)學(xué)描述,設(shè)蜜源為i,引領(lǐng)探測蜂在第d維的初始隨機(jī)位置為Xid,其位置具體為[10]

Xid=Ld+rand(0,1)(Ud-Ld)

(7)

式中:Ud與Ld分別為蜜源在第d維搜索的邊界上下限范圍,d∈{1,2,…,D},D表示總維度。

探測蜂在Xid處展開蜜源搜索,新蜜源為Vid,其搜索方式為[11]

Vid=Xid+φ(Xid-Xjd)

(8)

式中:j≠i,φ取值范圍為[1,1],Xjd為搜索范圍內(nèi)第d維除了Xid外的任意位置。

當(dāng)探測蜂探測到新蜜源時,會將新舊蜜源進(jìn)行質(zhì)量對比,對比方式為計(jì)算兩者的適應(yīng)度值,新蜜源Vi=[Vi1Vi2…Vid]的適應(yīng)度fi的計(jì)算方法為[12]

(9)

若Vi的適應(yīng)度值優(yōu)于Xi,則用新蜜源替換原蜜源。探測蜂將蜜源數(shù)據(jù)傳達(dá)至跟隨蜂,而跟隨蜂選擇其偏好的蜜源概率pi為[13]

(10)

式中:SP為總蜜源數(shù)。

探測蜂搜索蜜源的策略為:當(dāng)?shù)螖?shù)trial達(dá)到最大次數(shù)Itr max時,則重新跳轉(zhuǎn)至式(7),否則繼續(xù)尋找最優(yōu)蜜源。

(11)

2.2 基于ABC的DPC

在DPC算法實(shí)現(xiàn)過程中,rc的選擇非常重要,rc既決定了DPC的聚類精度,也影響著DPC的執(zhí)行效率。DPC由于受rc的影響大,對樣本點(diǎn)分布密度不均衡的處理效果差,因此本文采取ABC算法對DPC進(jìn)行改進(jìn)。

采用ABC對DPC進(jìn)行優(yōu)化后,ABC-DPC不用再進(jìn)行DPC的rc參數(shù)選擇,而是通過蜜源搜索獲得最優(yōu)rc參數(shù)值。在獲得了待聚類的樣本之后,計(jì)算各樣本點(diǎn)兩兩之間的距離,并整理成矩陣集合。然后計(jì)算各樣本點(diǎn)的密度值及距離值,選擇兩者較大的樣本點(diǎn)作為樣本聚類的中心點(diǎn),然后計(jì)算剩余節(jié)點(diǎn)相對各中心點(diǎn)的距離值,選擇較近的中心點(diǎn)所屬類別作為各剩余節(jié)點(diǎn)的類別。具體的ABC-DPC聚類流程如圖2所示。

圖2 基于ABC-DPC的聚類流程圖

3 實(shí)例仿真

為了驗(yàn)證ABC-DPC算法的聚類性能,進(jìn)行實(shí)例仿真。仿真數(shù)據(jù)來源為某大型電商平臺,選取了4類不同商品(手機(jī)、電腦顯示器、鍵盤和鼠標(biāo))作為聚類樣本集,見表1。首先對不同維度的樣本聚類仿真, 生成DPC的決策圖并分析其性能;然后分別采用DPC和ABC-DPC進(jìn)行聚類操作,分析ABC對DPC的優(yōu)化程度。

表1 在線購物平臺樣本集參數(shù)表

3.1 不同樣本量的決策圖性能仿真

在DPC聚類過程中,核心內(nèi)容是獲得準(zhǔn)確率有效的決策圖,通過決策圖來選擇合適的聚類類別中心點(diǎn),然后根據(jù)樣本點(diǎn)離各中心點(diǎn)的距離獲得樣本類別。從表1的4種數(shù)據(jù)集中分別選擇1 000個樣本進(jìn)行ABC-DPC聚類,其中ABC-DPC算法針對4個數(shù)據(jù)集求解的決策圖如圖3所示。

由圖3可知,通過選擇不同的數(shù)據(jù)維度,得到了4幅ABC-DPC聚類決策圖。當(dāng)數(shù)據(jù)維度為26時,樣本點(diǎn)大部分分布在δ<1的范圍內(nèi),ρ軸的樣本點(diǎn)分布范圍比較廣;當(dāng)數(shù)據(jù)維度增加至34時,相比于維度為26時,1<δ<2的樣本點(diǎn)在增多;而當(dāng)維度增加至47時,δ>1的點(diǎn)相比于維度34時增加不多,但ρ值更大的樣本點(diǎn)攀升明顯;樣本數(shù)據(jù)維度為56時,相比于前3個樣本維度,樣本點(diǎn)處于δ>2且ρ>50處的點(diǎn)數(shù)增加明顯,根據(jù)DPC算法的中心點(diǎn)選擇策略,候選中心點(diǎn)數(shù)目增加,因此選擇合適中心點(diǎn)的難度在提升。

圖3 決策圖

由圖3可知,從整體上來看,當(dāng)樣本數(shù)據(jù)維度增加時,局部密度ρ最大值增大,這是因?yàn)闃颖緮?shù)據(jù)維度增加,聚類中心閾值范圍內(nèi)的節(jié)點(diǎn)數(shù)增多,因此密度值會增大。對于4個不同維度的數(shù)據(jù)集進(jìn)行ABC-DPC聚類準(zhǔn)確率仿真,統(tǒng)計(jì)結(jié)果如表2所示。

表2 ABC-DPC的聚類準(zhǔn)確率表

從表2可知,當(dāng)樣本維度從26提升至56時,平均聚類準(zhǔn)確率降低了1.097%,這可能是因?yàn)榫S度增加,在進(jìn)行ABC的距離閾值優(yōu)化時,難度提升而造成優(yōu)化效果下降,促使DPC聚類效果微降。降低效果較小,表明ABC-DPC聚類在高維數(shù)據(jù)聚類時優(yōu)勢明顯,聚類準(zhǔn)確率不隨著維度的大幅提升而明顯下降。

3.2 ABC的DPC改進(jìn)性能

為了驗(yàn)證ABC對DPC聚類算法的改進(jìn)性能,分別采用DPC和ABC-DPC算法對4個樣本集進(jìn)行聚類仿真,并求解2種算法的聚類準(zhǔn)確率。從圖4可知,經(jīng)過ABC優(yōu)化后,ABC-DPC的聚類準(zhǔn)確率明顯高于DPC算法。ABC-DPC收斂時4種樣本集聚類的平均準(zhǔn)確率約為0.95,而DPC算法在數(shù)據(jù)集1和2的聚類準(zhǔn)確率約為0.8,在數(shù)據(jù)集3和4的聚類準(zhǔn)確率約為0.7,這表明DPC算法在處理高維數(shù)據(jù)聚類時效果較差。從圖4中可觀察到,隨著樣本維度增加,DPC和ABC-DPC算法的聚類準(zhǔn)確率差值明顯擴(kuò)大,這說明引進(jìn)了ABC對DPC進(jìn)行優(yōu)化之后,對高維數(shù)據(jù)的聚類效果提升明顯。

圖4 DPC和ABC-DPC的聚類準(zhǔn)確率曲線圖

從聚類時間方面來看,穩(wěn)定時DPC算法的聚類時間和ABC-DPC算法的聚類時間相差較小,這是因?yàn)榧尤肓薃BC優(yōu)化之后,距離閾值的優(yōu)化需要消耗更多的時間。但是,從圖4中結(jié)果可得兩者差距并不大,這主要是因?yàn)橐肓薃BC優(yōu)化后,DPC算法能夠獲得更優(yōu)的距離閾值。在相同聚類準(zhǔn)確率閾值條件下,雖然ABC優(yōu)化需要消耗時間,但ABC-DPC達(dá)到收斂時能夠節(jié)省迭代次數(shù),降低聚類模型復(fù)雜度。

3.3 不同算法的聚類性能

為了驗(yàn)證不同算法的大數(shù)據(jù)聚類性能,分別采用常用聚類算法模糊聚類[14]、決策樹[15]、卷積神經(jīng)網(wǎng)絡(luò)(Convolutional neural network,CNN)[16]、非參數(shù)密度峰值聚類[17]和ABC-DPC算法對樣本進(jìn)行仿真,樣本來自于公開的UCI(University of California,Irvine)數(shù)據(jù)集,具體如表3所示。對表3的5類樣本集進(jìn)行聚類仿真,其性能結(jié)果如表4和表5所示。

表3 UCI仿真集參數(shù)表

從表4可知,5種算法對于UCI數(shù)據(jù)集4個類別樣本的聚類性能差異明顯。對于聚類準(zhǔn)確率,在4個數(shù)據(jù)集上,均表現(xiàn)出ABC-DPC算法聚類準(zhǔn)確率最高,非參數(shù)密度峰值聚類算法次之,模糊聚類算法最差的特點(diǎn)。橫向?qū)Ρ?在seeds集上4種算法表現(xiàn)出了最高聚類準(zhǔn)確率,在Gisette集上4種算法表現(xiàn)出了最低聚類準(zhǔn)確率,在seeds集上ABC-DPC算法聚類準(zhǔn)確率達(dá)到了0.867 5。

從表5得,對于聚類準(zhǔn)確率的標(biāo)準(zhǔn)差性能,ABC-DPC和非參數(shù)密度峰值聚類算法性能較好,兩者收斂時的標(biāo)準(zhǔn)差明顯優(yōu)于模糊聚類和決策樹算法,其中ABC-DPC算法在seeds集上獲得了最優(yōu)標(biāo)準(zhǔn)差0.251 3。

表4 5種算法的聚類準(zhǔn)確率表

表5 5種算法的聚類準(zhǔn)確率標(biāo)準(zhǔn)差表

4 結(jié)束語

采用ABC-DPC算法應(yīng)用于高維數(shù)據(jù)聚類,能夠獲得較高的聚類準(zhǔn)確率。通過合理設(shè)置ABC算法的探測蜂蜜源搜索范圍,優(yōu)化DPC算法的核心參數(shù)值ρ和δ,選擇兩者中值較大的點(diǎn)作為聚類中心點(diǎn)進(jìn)行聚類,與常用高維數(shù)據(jù)聚類算法對比,ABC-DPC算法能夠獲得更高的聚類準(zhǔn)確率性能,且聚類效率高,在高維聚類方面適用度高。