數據驅動下基于量子人工蜂群的K均值聚類算法優化

周湘貞,李 帥,隋 棟

(1.鄭州升達經貿管理學院 信息工程學院,河南 鄭州 451191;2.北京航空航天大學 計算機學院,北京 100191;3.北京建筑大學 電氣與信息工程學院,北京 102406)

大數據驅動多個行業深度發展,通過大數據進行有效挖掘及深度分析成為近年來研究的熱點。由于大數據具有特征量大、維度高及關聯性強等特點[1],僅靠人工統計的方式對其進行數據分析存在效率較低的問題,而聚類作為一種機器學習工具,在數據分析中應用前景廣闊。由于各行業聚類需求差異明顯,對聚類性能要求不一,聚類準確率、聚類效率及穩定性等要求彼此制約,在選擇聚類算法時,常需要結合實際需求來定。K均值聚類作為常用聚類算法,其應用場景非常廣泛。但是為了提高其在不同聚類需求中的適用度,常需要對K均值進行優化。由于隨機設置的聚類中心不容易獲得較高的聚類性能,因此常需要針對該不足進行深度優化,如用深度學習算法或者仿生算法實現自動確立中心的策略,來實現有針對性的優化。

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

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

1 K均值聚類簡介

K均值聚類首先需要根據聚類類別數設定合適的聚類中心,假設第i個中心為xi,其他樣本點與xi的距離[4]為

(1)

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

(2)

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

(3)

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

將式(3)化簡得

(4)

優化函數[6]為

minε

(5)

由以上公式知,在K均值聚類過程中,算法的復雜度與樣本點維度有極大關系,同時初始中心點的選擇也非常關鍵,常見的K均值改進主要從這兩點出發進行K均值的優化。

2 量子人工蜂群的初始聚類中心優化

在對K均值進行改進時,本文選擇了初始聚類中心優化,考慮采用量子人工蜂群進行初始聚類中心優化求解,下面給出ABC算法計算過程。

2.1 人工蜂群算法

人工蜂群(Artificial bee colony,ABC)算法旨在獲得最優適應度蜜源,通過探測蜂進行規定運動邊界的廣度搜索,確定蜜源大致位置,然后采用跟隨蜂進行細粒度搜索,獲得最優蜜源。

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

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

(6)

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

Vid=Xid+φ(Xid-Xjd)

(7)

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

當獲得新蜜源Vi(Vi=[Vi1,Vi2,…,Vid])后,調整適應度fi[8]

(8)

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

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

(9)

當運行了trial代后,探測蜂根據式(10)選擇下一步執行策略[10]

(10)

式中：Itrmax是最大迭代次數。

由于探測蜂在運動時,其精度對rand(0,1)(Ud-Ld)的依賴程度高。因此對蜜蜂位置進行量子表示,能夠實現更細粒度的搜索,從而獲得更優質量的蜜源。

2.2 量子優化

量子表示方法[11]

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

(11)

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

將上式用矩陣[12]表示

|φ〉=[α,β]T

(12)

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

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

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

(13)

采用矩陣方式對蜜蜂個體位置編碼

(14)

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

(15)

設θ是[α,β]T在|0〉=[1,0]T方向上的相位,則式(14)變為[13]

(16)

2.3 基于QABC優化的K均值聚類流程

在執行QABC+K均值聚類算法時,首先獲得待聚類的樣本并進行初始化,同時初始化聚類適應度函數。接著,隨機設置類別中心坐標,并采用QABC進行聚類中心優化,通過蜜源運動確定最優中心坐標。

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

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

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

3 實例仿真

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

表1 仿真樣本集

3.1 QABC+K均值的聚類性能

采用QABC+K均值算法對表1的六類樣本集進行聚類仿真,聚類算法共執行訓練100次,求解各種聚類性能的均值。

從表2知,QABC+K均值算法在Wine樣本集的聚類準確率最高,均值為0.957 2,在SECOM的樣本集聚類準確率最低,均值為0.863 5。對比發現,對于維數較高的樣本集,QABC+K均值算法的聚類準確率均低于維數較低樣本集。這說明樣本集的維度對QABC+K均值算法的聚類準確率影響敏感。對比最大與最小值,它們與均值的偏移程度均較小。

表2 QABC+K均值的聚類準確率

從表3得,在Silhouette性能方面,QABC+K均值算法在seeds數據集獲得了最高值0.539 1,而在SECON集獲得了最小值僅為0.397 4,主要是因為SECOM高維度引起的聚類Silhouette性能下降,這說明QABC+K均值算法的聚類Silhouette性能對樣本維度依賴程度高,在高維度樣本的聚類中,雖然通過了QABC優化,但是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均值算法對六類樣本的聚類穩定性較高。

3.2 QABC對K均值聚類的性能影響

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

從表5知,從聚類類別方面來看,QABC+K均值算法契合度最高,僅在Gistette集比實際類別少1,其他完全符合實際類別數,而ABC+K均值的聚類類別在3個樣本集出現了與實際類別數不一致的情況,K均值聚類類別在4個樣本集出現了與實際類別不一致情況。因此在聚類類別方面QABC+K均值算法優于其他兩種算法。

表5 3種算法的聚類類別

從圖2知,對于六類樣本集,三種算法的聚類準確率分層明顯,QABC+K均值算法優勢遠高于其他兩種算法,這表明經過QABC優化后,K均值算法對六類樣本的聚類準確率得到了較大提升。對于復雜度較高的多屬性樣本,三類算法的聚類準確率差異體現得更明顯,QABC+K均值的優勢更大,這表明K均值算法對維度高樣本聚類準確率性能較差,經過QABC優化后,其性能提升明顯。在聚類時間上看,K均值算法略高于其他兩種算法,但差距并不大,這是因為雖然QABC在初始聚類中心優化時消耗了一些時間,但是減少了聚類的運算時間消耗。

圖2 3種算法的聚類準確率

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

圖3 3種算法的Silhouette值

3.3 不同算法的聚類性能

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

從表6得,對于六類樣本集,采用不同算法對K均值改進后,其聚類準確率呈現出較大差別,其中QABC+K均值、BFO+K均值、GWO+K均值和PSO+K均值算法的準確率范圍分別為[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均值的優勢顯而易見,這表明QABC對K均值聚類準確率優化程度最高。橫向對比六類數據集發現,雖然經過不同算法的K均值優化,但低維度和高維度樣本的聚類準確率差距明顯,這是因為K均值算法本身對高維度樣本聚類適應度較差造成的。雖然通過不同算法對K均值優化,單優化算法僅針對K均值的初始中心類別點進行尋優,而聚類的本質運算仍是K均值算法來完成的[16],因此這四種算法的改進對解決高維度樣本的聚類性能提升不明顯。

表6 四種算法的聚類準確率

從表7得,對于六類樣本集的聚類準確率RMSE,QABC+K均值算法的RMSE最優,PSO+K均值算法最差,四種改進算法的穩定性最差和最優值在數據集的表現上不一致,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,這說明改進的K均值聚類穩定性對樣本數據維度不敏感。從統計結果得,四類算法的RMSE值在數量級上相同,這表明4類算法在穩定性方面并未拉開差距。

表7 四種算法聚類準確率RMSE

4 結束語

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