數(shù)據(jù)驅(qū)動(dòng)下基于量子人工蜂群的K均值聚類算法優(yōu)化

周湘貞,李 帥,隋 棟

(1.鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院 信息工程學(xué)院,河南 鄭州 451191;2.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院,北京 100191;3.北京建筑大學(xué) 電氣與信息工程學(xué)院,北京 102406)

大數(shù)據(jù)驅(qū)動(dòng)多個(gè)行業(yè)深度發(fā)展,通過(guò)大數(shù)據(jù)進(jìn)行有效挖掘及深度分析成為近年來(lái)研究的熱點(diǎn)。由于大數(shù)據(jù)具有特征量大、維度高及關(guān)聯(lián)性強(qiáng)等特點(diǎn)[1],僅靠人工統(tǒng)計(jì)的方式對(duì)其進(jìn)行數(shù)據(jù)分析存在效率較低的問(wèn)題,而聚類作為一種機(jī)器學(xué)習(xí)工具,在數(shù)據(jù)分析中應(yīng)用前景廣闊。由于各行業(yè)聚類需求差異明顯,對(duì)聚類性能要求不一,聚類準(zhǔn)確率、聚類效率及穩(wěn)定性等要求彼此制約,在選擇聚類算法時(shí),常需要結(jié)合實(shí)際需求來(lái)定。K均值聚類作為常用聚類算法,其應(yīng)用場(chǎng)景非常廣泛。但是為了提高其在不同聚類需求中的適用度,常需要對(duì)K均值進(jìn)行優(yōu)化。由于隨機(jī)設(shè)置的聚類中心不容易獲得較高的聚類性能,因此常需要針對(duì)該不足進(jìn)行深度優(yōu)化,如用深度學(xué)習(xí)算法或者仿生算法實(shí)現(xiàn)自動(dòng)確立中心的策略,來(lái)實(shí)現(xiàn)有針對(duì)性的優(yōu)化。

當(dāng)前,關(guān)于K均值算法的改進(jìn)策略研究較多,賀思云等[2]分析了粗糙K均值聚類算法的不足,并采用人工蜂群進(jìn)行聚類中心優(yōu)化,以增強(qiáng)粗糙K均值聚類的Silhouette性能。郭婧等[3]將K均值用于大數(shù)據(jù)挖掘,并采用菌群優(yōu)化(Bacterial foraging optimization,BFO)算法對(duì)聚類中心進(jìn)行優(yōu)化,有效提高了K均值的分類精度?？梢钥闯?上述兩個(gè)研究為了提高K均值算法在不同需求下的聚類適應(yīng)度,都采用仿生算法對(duì)其初始聚類中心進(jìn)行優(yōu)化,取得了較高聚類性能,但仍有較大提升空間。

近期,量子計(jì)算由于其強(qiáng)大的并行計(jì)算能力被應(yīng)用于各種算法優(yōu)化領(lǐng)域。將量子計(jì)算引入到狀態(tài)轉(zhuǎn)移概率計(jì)算中可以有效避免群體智能優(yōu)化算法易陷入局部最優(yōu)解,并同時(shí)提高收斂速度。早期被提出的量子粒子群算法用量子位的概率幅對(duì)粒子位置編碼,提高了收斂速度和尋優(yōu)精度。量子人工蜂群(Quantum artificial bee colony,QABC)作為其后續(xù)版本,均采用量子編碼思路,但是相比于前者能有效避免早熟收斂問(wèn)題。因此,本文采用人工蜂群對(duì)K均值進(jìn)行改進(jìn),并對(duì)蜂群位置進(jìn)行量子表示,以減小搜索粒度,提高了聚類中心的搜索精度,基于QABC改進(jìn)的K均值算法具有更優(yōu)的聚類性能。

1 K均值聚類簡(jiǎn)介

K均值聚類首先需要根據(jù)聚類類別數(shù)設(shè)定合適的聚類中心,假設(shè)第i個(gè)中心為xi,其他樣本點(diǎn)與xi的距離[4]為

(1)

設(shè)所有樣本點(diǎn)的維度為n,那么xi可寫成(xi1,xi2,xi3,…,xin),非中心點(diǎn)xj可寫成 (xj1,xj2,xj3,…,xjn),xi與xj的距離[5]為

(2)

采用式(2)逐個(gè)計(jì)算樣本點(diǎn)與各個(gè)中心點(diǎn)的距離,并對(duì)距離采用升序排列,根據(jù)距離最小值來(lái)判定該樣本點(diǎn)所屬類別。在實(shí)際訓(xùn)練時(shí),由于聚類中心可以不斷變化,因此一般是求解樣本點(diǎn)與所有中心點(diǎn)的距離集合,求解方法為

(3)

xj∈N(xi)表示N個(gè)樣本點(diǎn)中除了xi的其他點(diǎn),且有∑j,xj∈N(xi)Sijxj=1,Sij≥0。

將式(3)化簡(jiǎn)得

(4)

優(yōu)化函數(shù)[6]為

minε

(5)

由以上公式知,在K均值聚類過(guò)程中,算法的復(fù)雜度與樣本點(diǎn)維度有極大關(guān)系,同時(shí)初始中心點(diǎn)的選擇也非常關(guān)鍵,常見(jiàn)的K均值改進(jìn)主要從這兩點(diǎn)出發(fā)進(jìn)行K均值的優(yōu)化。

2 量子人工蜂群的初始聚類中心優(yōu)化

在對(duì)K均值進(jìn)行改進(jìn)時(shí),本文選擇了初始聚類中心優(yōu)化,考慮采用量子人工蜂群進(jìn)行初始聚類中心優(yōu)化求解,下面給出ABC算法計(jì)算過(guò)程。

2.1 人工蜂群算法

人工蜂群(Artificial bee colony,ABC)算法旨在獲得最優(yōu)適應(yīng)度蜜源,通過(guò)探測(cè)蜂進(jìn)行規(guī)定運(yùn)動(dòng)邊界的廣度搜索,確定蜜源大致位置,然后采用跟隨蜂進(jìn)行細(xì)粒度搜索,獲得最優(yōu)蜜源。

設(shè)初始蜜源i,探測(cè)蜂的d維初始位置Xid是[7]

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

(6)

式中：Ud為d維搜索邊界上限,Ld為下限,d∈{1,2,…,D},D是總維度。探測(cè)蜂從Xid處執(zhí)行蜜源搜索,其在設(shè)定范圍內(nèi)探測(cè)新蜜源Vid的方法為

Vid=Xid+φ(Xid-Xjd)

(7)

式中：j≠i,φ∈[-1,1],Xjd≠Xid且屬于[Ld,Ud]范圍內(nèi)。

當(dāng)獲得新蜜源Vi(Vi=[Vi1,Vi2,…,Vid])后,調(diào)整適應(yīng)度f(wàn)i[8]

(8)

根據(jù)fi計(jì)算值,將Vi和Xi兩者中較大的定義為新蜜源。

跟隨蜂獲得了探測(cè)蜂的信息后,在若SP個(gè)蜜源中根據(jù)pi選擇其偏好蜜源,pi計(jì)算公式[9]為

(9)

當(dāng)運(yùn)行了trial代后,探測(cè)蜂根據(jù)式(10)選擇下一步執(zhí)行策略[10]

(10)

式中：Itrmax是最大迭代次數(shù)。

由于探測(cè)蜂在運(yùn)動(dòng)時(shí),其精度對(duì)rand(0,1)(Ud-Ld)的依賴程度高。因此對(duì)蜜蜂位置進(jìn)行量子表示,能夠?qū)崿F(xiàn)更細(xì)粒度的搜索,從而獲得更優(yōu)質(zhì)量的蜜源。

2.2 量子優(yōu)化

量子表示方法[11]

|φ〉=α|0〉+β|1〉

(11)

式中：|·〉表示狄拉克符號(hào),α和β表示常量,|α|2+|β|2=1,|α|2表示量子為“0”的概率,而|β|2表示量子為“1”的概率。

將上式用矩陣[12]表示

|φ〉=[α,β]T

(12)

令α=cos(θ),β=sin(θ),則式(11)可寫為

|φ〉=cos(θ)|0〉+sin(θ)|1〉=

[cos(θ),sin(θ)]T

(13)

采用矩陣方式對(duì)蜜蜂個(gè)體位置編碼

(14)

式中：θij=2π·Rand(),Rand()∈(0,1),i∈{1,2,…,n},j∈{1,2,…,m},n是蜂群規(guī)模,m是位置維度。將式(14)化簡(jiǎn)得

(15)

設(shè)θ是[α,β]T在|0〉=[1,0]T方向上的相位,則式(14)變?yōu)閇13]

(16)

2.3 基于QABC優(yōu)化的K均值聚類流程

在執(zhí)行QABC+K均值聚類算法時(shí),首先獲得待聚類的樣本并進(jìn)行初始化,同時(shí)初始化聚類適應(yīng)度函數(shù)。接著,隨機(jī)設(shè)置類別中心坐標(biāo),并采用QABC進(jìn)行聚類中心優(yōu)化,通過(guò)蜜源運(yùn)動(dòng)確定最優(yōu)中心坐標(biāo)。

在進(jìn)行QABC對(duì)聚類中心進(jìn)行優(yōu)化時(shí),有兩個(gè)關(guān)鍵因素(蜂群規(guī)模和搜索邊界)需要考慮。在實(shí)際操作時(shí),蜂群規(guī)模和搜索邊界可以差異化設(shè)置,驗(yàn)證不同參數(shù)條件下的K均值性能,從而獲得更優(yōu)的QABC參數(shù),以進(jìn)一步提升QABC對(duì)聚類中心的優(yōu)化程度。

最后,采用QABC獲得初始聚類中心來(lái)進(jìn)行K均值聚類,輸入待聚類樣本,按照式(1)～(5)執(zhí)行聚類操作,輸出聚類類別,具體如圖1所示。

圖1 基于QABC+K均值的聚類流程

3 實(shí)例仿真

為了驗(yàn)證QABC+K均值算法聚類性能,從多種角度對(duì)其不同指標(biāo)進(jìn)行仿真,仿真對(duì)象為UCI集,充分對(duì)比QABC+K均值算法對(duì)于不同復(fù)雜程度樣本的聚類效果,選取了維度差異較大的六類樣本,具體見(jiàn)表1。首先,采用QABC+K均值算法對(duì)六類樣本集進(jìn)行聚類仿真。其次,分別采用K均值算法、ABC+K均值算法及QABC+K均值算法對(duì)表1中的六類樣本集進(jìn)行仿真。最后,采用常用K均值改進(jìn)聚類算法和QABC+K均值算法分別進(jìn)行聚類仿真,驗(yàn)證不同算法聚類性能。

表1 仿真樣本集

3.1 QABC+K均值的聚類性能

采用QABC+K均值算法對(duì)表1的六類樣本集進(jìn)行聚類仿真,聚類算法共執(zhí)行訓(xùn)練100次,求解各種聚類性能的均值。

從表2知,QABC+K均值算法在Wine樣本集的聚類準(zhǔn)確率最高,均值為0.957 2,在SECOM的樣本集聚類準(zhǔn)確率最低,均值為0.863 5。對(duì)比發(fā)現(xiàn),對(duì)于維數(shù)較高的樣本集,QABC+K均值算法的聚類準(zhǔn)確率均低于維數(shù)較低樣本集。這說(shuō)明樣本集的維度對(duì)QABC+K均值算法的聚類準(zhǔn)確率影響敏感。對(duì)比最大與最小值,它們與均值的偏移程度均較小。

表2 QABC+K均值的聚類準(zhǔn)確率

從表3得,在Silhouette性能方面,QABC+K均值算法在seeds數(shù)據(jù)集獲得了最高值0.539 1,而在SECON集獲得了最小值僅為0.397 4,主要是因?yàn)镾ECOM高維度引起的聚類Silhouette性能下降,這說(shuō)明QABC+K均值算法的聚類Silhouette性能對(duì)樣本維度依賴程度高,在高維度樣本的聚類中,雖然通過(guò)了QABC優(yōu)化,但是K均值的聚類Silhouette性能仍受到了較大影響。所提算法的均方根誤差(Root-mean-square error,RMSE)如表4所示。

表3 QABC+K均值的Silhouette值

表4 QABC+K均值的RMSE

從表4可知,QABC+K均值算法在六類樣本集的RMSE方面性能均較高,其中最低的Gisette集的聚類RMSE均值為1.407×10-3,這表明QABC+K均值算法對(duì)六類樣本的聚類穩(wěn)定性較高。

3.2 QABC對(duì)K均值聚類的性能影響

為了驗(yàn)證量子人工蜂群對(duì)K均值聚類的性能影響,采用K均值算法、ABC+K均值算法及QABC+K均值算法對(duì)表1樣本集進(jìn)行聚類仿真。

從表5知,從聚類類別方面來(lái)看,QABC+K均值算法契合度最高,僅在Gistette集比實(shí)際類別少1,其他完全符合實(shí)際類別數(shù),而ABC+K均值的聚類類別在3個(gè)樣本集出現(xiàn)了與實(shí)際類別數(shù)不一致的情況,K均值聚類類別在4個(gè)樣本集出現(xiàn)了與實(shí)際類別不一致情況。因此在聚類類別方面QABC+K均值算法優(yōu)于其他兩種算法。

表5 3種算法的聚類類別

從圖2知,對(duì)于六類樣本集,三種算法的聚類準(zhǔn)確率分層明顯,QABC+K均值算法優(yōu)勢(shì)遠(yuǎn)高于其他兩種算法,這表明經(jīng)過(guò)QABC優(yōu)化后,K均值算法對(duì)六類樣本的聚類準(zhǔn)確率得到了較大提升。對(duì)于復(fù)雜度較高的多屬性樣本,三類算法的聚類準(zhǔn)確率差異體現(xiàn)得更明顯,QABC+K均值的優(yōu)勢(shì)更大,這表明K均值算法對(duì)維度高樣本聚類準(zhǔn)確率性能較差,經(jīng)過(guò)QABC優(yōu)化后,其性能提升明顯。在聚類時(shí)間上看,K均值算法略高于其他兩種算法,但差距并不大,這是因?yàn)殡m然QABC在初始聚類中心優(yōu)化時(shí)消耗了一些時(shí)間,但是減少了聚類的運(yùn)算時(shí)間消耗。

圖2 3種算法的聚類準(zhǔn)確率

從圖3可得,在Silhouette性能方面,經(jīng)過(guò)ABC優(yōu)化后,K均值算法的Silhouette值得到了較大提升,對(duì)于六類樣本集,K均值的Silhouette值維持在0.35以下,而ABC+K均值算法和QABC+K均值算法的Silhouette值都保持在0.37以上,這說(shuō)明經(jīng)過(guò)ABC優(yōu)化后,提升了K均值的聚類結(jié)果類間分布合理性。對(duì)于seeds數(shù)據(jù)集,ABC+K均值算法和QABC+K均值算法的Silhouette值非常接近,其他5類集,QABC+K均值算法的優(yōu)勢(shì)更明顯。

圖3 3種算法的Silhouette值

3.3 不同算法的聚類性能

為了驗(yàn)證不同K均值算法優(yōu)化后的聚類性能,分別采用三種經(jīng)過(guò)優(yōu)化后的K均值聚類算法：粒子群優(yōu)化(Particle swarm optimization,PSO)K均值(PSO+K均值)[14]、灰狼優(yōu)化(Grey wolf optimization,GWO)K均值(GWO+K均值)[15]、菌群優(yōu)化K均值(BFO+K均值)[3],將三種算法與量子人工蜂群優(yōu)化K均值算法對(duì)六類樣本進(jìn)行聚類仿真。

從表6得,對(duì)于六類樣本集,采用不同算法對(duì)K均值改進(jìn)后,其聚類準(zhǔn)確率呈現(xiàn)出較大差別,其中QABC+K均值、BFO+K均值、GWO+K均值和PSO+K均值算法的準(zhǔn)確率范圍分別為[0.863 5,0.951 5]、[0.831 1,0.915 8]、[0.825 6,0.901 5]和[0.793 4,0.892 8],QABC+K均值的優(yōu)勢(shì)顯而易見(jiàn),這表明QABC對(duì)K均值聚類準(zhǔn)確率優(yōu)化程度最高。橫向?qū)Ρ攘悢?shù)據(jù)集發(fā)現(xiàn),雖然經(jīng)過(guò)不同算法的K均值優(yōu)化,但低維度和高維度樣本的聚類準(zhǔn)確率差距明顯,這是因?yàn)镵均值算法本身對(duì)高維度樣本聚類適應(yīng)度較差造成的。雖然通過(guò)不同算法對(duì)K均值優(yōu)化,單優(yōu)化算法僅針對(duì)K均值的初始中心類別點(diǎn)進(jìn)行尋優(yōu),而聚類的本質(zhì)運(yùn)算仍是K均值算法來(lái)完成的[16],因此這四種算法的改進(jìn)對(duì)解決高維度樣本的聚類性能提升不明顯。

表6 四種算法的聚類準(zhǔn)確率

從表7得,對(duì)于六類樣本集的聚類準(zhǔn)確率RMSE,QABC+K均值算法的RMSE最優(yōu),PSO+K均值算法最差,四種改進(jìn)算法的穩(wěn)定性最差和最優(yōu)值在數(shù)據(jù)集的表現(xiàn)上不一致,PSO+K均值算法和GWO+K均值算法均在Flowers上獲得了最差RMSE值1.932×10-3和1.721×10-3,而BFO+K均值算法和QABC+K均值算法均在Gisette上獲得了最差RMSE值1.532×10-3和1.407×10-3,這說(shuō)明改進(jìn)的K均值聚類穩(wěn)定性對(duì)樣本數(shù)據(jù)維度不敏感。從統(tǒng)計(jì)結(jié)果得,四類算法的RMSE值在數(shù)量級(jí)上相同,這表明4類算法在穩(wěn)定性方面并未拉開差距。

表7 四種算法聚類準(zhǔn)確率RMSE

4 結(jié)束語(yǔ)

采用量子人工蜂群的K均值聚類,通過(guò)量子人工蜂群的高精度搜索,以及量子化的細(xì)粒度尋優(yōu),提高了聚類精度。本文采用QABC的尋優(yōu)中,其主要參數(shù)均為常用設(shè)置,并未進(jìn)行差異化參數(shù)的聚類性能驗(yàn)證,后續(xù)研究將差異化微調(diào)人工蜂群算法核心參數(shù),嘗試從蜂群規(guī)模、探測(cè)蜂的搜索邊界等角度去進(jìn)行聚類性能測(cè)試,以進(jìn)一步提高本文算法的性能。