基于量子蟻群優(yōu)化的近鄰傳播聚類算法研究

鄭冬花,葉麗珠,劉月紅,牛少華

(1.廣州商學院 信息技術(shù)與工程學院,廣東 廣州 511363;2.馬來西亞管理與科學大學 研究生院,雪蘭莪 莎阿南 40100;3.桂林理工大學 信息科學與工程學院,廣西 桂林 541006;4.北京理工大學 機電學院,北京 100081)

聚類作為無標簽大數(shù)據(jù)深度分析的重要手段,占據(jù)著數(shù)據(jù)分析的重要地位。通過聚類可以有效挖掘海量數(shù)據(jù)見的隱藏聯(lián)系,從而實現(xiàn)大規(guī)模數(shù)據(jù)的價值處理。由于聚類無先驗知識輔助,其在數(shù)據(jù)挖掘過程中常常因為數(shù)據(jù)維度高或數(shù)據(jù)異構(gòu)程度高而失效[1,2],無法完成數(shù)據(jù)類別劃分的任務(wù)。同時,聚類的精度也常受到樣本量、樣本均衡程度、聚類中心數(shù)量等多種因素的制約。因此要在大規(guī)模數(shù)據(jù)中獲得較好的聚類效果,必須要充分研究聚類算法,根據(jù)實際聚類需求不斷改進聚類方法。

當前,關(guān)于聚類算法的研究較多,王芙銀等[3]采用密度峰值算法完成聚類,并采用鯨魚算法進行密度峰值核心參數(shù)優(yōu)化,以增強聚類性能。姬強等[4]對常用深度學習算法聚類進行了詳細分析,解析了常用深度學習算法應(yīng)用場景并對比了其優(yōu)缺點。前者對具體聚類算法進行了性能改進,后者對機器學習的算法進行比較分析,兩者都對聚類性能提升瓶頸進行了說明,提出了聚類性能提升的改革方向。

近鄰傳播(Affinity propagation,AP)聚類算法作為一種較為新穎的聚類方法,與傳統(tǒng)聚類方法相比,無需事先給定聚類數(shù)目,且具有更好的聚類性能和效率。近期,各種量子群體智能優(yōu)化算法相繼被提出,并表現(xiàn)出更加優(yōu)秀的全局和局部尋優(yōu)能力。目前,尚沒有出現(xiàn)關(guān)于采用量子群體智能優(yōu)化算法來提升近鄰傳播聚類性能的研究。本文采用AP聚類算法進行數(shù)據(jù)聚類,為了防止因為AP聚類算法的偏向參數(shù)設(shè)置不合理而導(dǎo)致聚類性能降低,引入蟻群優(yōu)化(Ant colony optimization,ACO)策略,采用蟻群算法對偏向參數(shù)進行優(yōu)化,并采用量子比特編碼對蟻群個體位置進行編碼,以提高AP聚類的適用性。

1 近鄰傳播聚類

設(shè)兩個樣本i和j的相似程度S(i,j)計算方式為[5]

S(i,j)=-‖xi-xj‖2

(1)

式中:xi和xj分別表示樣本i和j的x維度函數(shù)。按照式(1)計算所有樣本中任意兩個樣本的距離,并以矩陣輸出,其對角線上的值稱為偏向參數(shù)P。

在樣本的相似維度函數(shù)表示中,吸引維度和隸屬維度最常用,分別用r(i,j)和a(i,j)表示,將兩者以矩陣形式表示,分別為R=[r(i,j)]N×N和A=[a(i,j)]N×N。

r(i,j)和a(i,j)更新方式[6]

(2)

(3)

式中:r(j,j)表示j的吸引度。根據(jù)式(2),左右兩邊均加上a(i,j),則

r(i,j)+a(i,j)=s(i,j)+a(i,j)-

(4)

近鄰傳播聚類算法相似度的計算一般綜合考慮r(i,j)和a(i,j),選擇r(i,j)+a(i,j)的值來衡量i和j的相似程度。

令E=[e(i,j)]N×N=[r(i,j)+a(i,j)]N×N,即E=R+A,不斷優(yōu)化求解E而獲得樣本的相似度,從而完成聚類。

為了減弱R與A更新中的振蕩效應(yīng),加入φ(φ∈[0,1))因子,那么T時刻的R與A計算方式為[7]

RT=(1-φ)RT+φRT-1

(5)

AT=(1-φ)AT+φAT-1

(6)

2 量子蟻群優(yōu)化的近鄰傳播聚類

2.1 ACO算法

蟻群算法本質(zhì)是通過螞蟻路徑選擇來尋優(yōu)。在m只螞蟻的n個節(jié)點尋優(yōu)中,通過可選節(jié)點之間的信息素來確定下個節(jié)點路徑。當螞蟻k當前處于第i個節(jié)點位置時,可選的后續(xù)節(jié)點集合為Mi,選擇下一個節(jié)點的方法為[8]

(7)

式中:τ(i,s)表示Mi中節(jié)點與點i的信息素,τ0表示初始信息素,螞蟻路徑選擇過程中的信息素計算采用概率方式[9]

(8)

式中:τ(i,j)是邊(i,j)信息素,其系數(shù)為α;η(i,j)為啟發(fā)強度,其系數(shù)為β。

螞蟻移動到下一節(jié)點后更新信息素[10]

τ(i,j)=(1-ρ)τ(i,j)+ρτ0

(9)

式中:ρ為蒸發(fā)因子。

蟻群中螞蟻全部路徑搜索完的信息素為

τ(i,j)=(1-ρ)τ(i,j)+Δτ(i,j)

(10)

2.2 量子蟻群優(yōu)化(Quantum ant colony optimi-zation,QACO)原理

量子的比特表示為[11]

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

(11)

式中:|·〉表示狄拉克符號,通常稱為疊加態(tài),α和β為非實數(shù),|α|2+|β|2=1,|α|2和|β|2分別表示量子坍縮到“0”和“1”態(tài)的概率。

將式(11)寫成矩陣方式

|φ〉=[α,β]T

(12)

令α=cos(θ),β=sin(θ),則式(12)變?yōu)?/p>

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

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

(13)

那么對蟻群所有個體位置進行編碼[12]

(14)

式中:θij=2π·Rand(),Rand()∈(0,1),i∈{1,2,…,n},j∈{1,2,…,m},n為蟻群個體總數(shù),m表示位置維度。

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

(15)

2.3 聚類流程

首先,將待聚類樣本進行相似矩陣求解,初始化偏向參數(shù),以偏向參數(shù)隨機值建立蟻群優(yōu)化算法的若干個體。然后,將螞蟻個體位置進行量子比特化處理。接著,進行蟻群優(yōu)化求解,求解適應(yīng)度最高的蟻群個體,即為最佳偏向參數(shù)。在量子蟻群優(yōu)化執(zhí)行過程中,多個弱分類器的分類結(jié)構(gòu)需要按權(quán)重投票,從而獲得強分類結(jié)果,權(quán)重的設(shè)置較為關(guān)鍵。最后,采用最佳偏向參數(shù)AP算法完成聚類。所提QACO-AP算法的具體流程如圖1所示。

圖1 基于QACO-AP的聚類流程

3 實例仿真

為了驗證基于量子蟻群優(yōu)化的近鄰傳播聚類算法,進行實例仿真,仿真數(shù)據(jù)集為公開數(shù)據(jù)集UCI,具體如表1所示。在本文的聚類性能衡量指標中,選取了常用的聚類準確度和聚類Silhouette值。仿真試驗硬件參數(shù)為:CPU Inter(R)Core(TM)i7,操作系統(tǒng)Windows 10。

表1 仿真樣本集

首先,驗證ACO-AP算法采用經(jīng)過優(yōu)化后的偏向參數(shù)進行聚類和常用偏向參數(shù)選擇方法的聚類性能差異;其次分別采用AP、ACO-AP和QACO-AP算法進行聚類性能仿真,驗證量子蟻群的優(yōu)化性能;最后采用常用聚類算法和QACO-AP算法進行聚類性能對比。

3.1 不同偏向參數(shù)的聚類性能

在AP聚類中,常用的偏向參數(shù)選擇方法為相似矩陣的中位數(shù)和最小值兩種方法,而QACO-AP的偏向參數(shù)是由QACO優(yōu)化得到的,分別采用這3種偏向參數(shù)選擇策略進行聚類仿真,其聚類類別數(shù)如表2所示。

表2 兩種算法的聚類類別數(shù)

從表2可知,當采用P為中位數(shù)的AP聚類時,其獲得聚類類別數(shù)明顯大于P為最小值的AP聚類及QACO-AP聚類,這主要是因為將P設(shè)置為中位數(shù),讓更多點獲得了成為類中心點的權(quán)利,所以在聚類過程中得到了多個類中心,從而造成類別數(shù)明顯失真;而對于P為最小值的AP聚類,其獲得的類別數(shù)也明顯多于實際類別,這表明采用常規(guī)AP聚類算法對表1中樣本進行聚類的適應(yīng)度較差,因此引入算法對AP的偏向參數(shù)進行優(yōu)化非常關(guān)鍵。

采用QACO-AP聚類算法時,其獲得的類別數(shù)和實際類別一致,具有較強的自適應(yīng)類別選擇功能,這有效解決了不同樣本類別數(shù)的聚類問題。下面將繼續(xù)對3種偏向參數(shù)設(shè)置策略對應(yīng)的AP算法的聚類準確率性能進行仿真,結(jié)果如圖2所示。

圖2 不同偏向參數(shù)設(shè)置策略對應(yīng)的Silhouette值

從圖2可以看出,采用不同偏向參數(shù)設(shè)置策略,其對應(yīng)的Silhouette值差異較大。在5類數(shù)據(jù)集中,QACO-AP算法的Silhouette明顯優(yōu)于未經(jīng)過偏向參數(shù)優(yōu)化的其他兩種算法。橫向?qū)Ρ劝l(fā)現(xiàn),3種算法分別在Iris集獲得了最高的Silhouette值。結(jié)合表2和圖3知,偏向參數(shù)的設(shè)置對AP聚類的性能影響較大,在無法手動合理設(shè)置的時候,采用算法對偏向參數(shù)進行自適應(yīng)優(yōu)化設(shè)置是較為合適的方法。

3.2 量子蟻群的優(yōu)化性能

為了進一步驗證量子蟻群算法對AP聚類的優(yōu)化性能,分別采用AP和QACO-AP算法對表1中的樣本進行聚類仿真。

從表3可知,采用AP算法所得到的聚類類別明顯大于實際類別,而QACO-AP和ACO-AP算法所獲得的聚類類別明顯和實際類別更接近。QACO-AP聚類獲得的類別和實際類別相等,而ACO-AP在Wine和Glass數(shù)據(jù)集聚類類別和實際值一樣,其他3類數(shù)據(jù)集類別與實際值不同,這表明引入ACO算法對偏向參數(shù)優(yōu)化之后,聚類得到的類別數(shù)明顯優(yōu)于傳統(tǒng)偏向參數(shù)確定方法。通過量子比特編碼,ACO的偏向參數(shù)優(yōu)化性能得到進一步提升,QACO-AP算法獲得了更準確的類別數(shù)。

表3 3種算法的聚類類別

從圖3可得,在Silhouette性能方面,QACO-AP算法均維持在0.4以上,ACO-AP算法保持在[0.3,0.36]之間,而AP算法均在0.25以下。這表明AP偏向參數(shù)經(jīng)過優(yōu)化之后,極大地提高了聚類的Silhouette性能,原因是QACO算法使數(shù)據(jù)集中不同簇類之間的分布更加合理。下面將繼續(xù)對3種算法的聚類準確率進行性能仿真。

圖3 3種算法的Silhouette值

從表4可知,對于5類樣本集,QACO-AP的聚類準確率最高,ACO-AP次之,AP算法最差,這主要是引入偏向參數(shù)優(yōu)化之后,其聚類類別更符合實際類別數(shù),根據(jù)類間距更容易獲得準確的聚類結(jié)果;從標準差角度來看,引入了QACO對AP算法進行優(yōu)化之后,聚類性能更穩(wěn)定了,這主要是因為當AP的偏向參數(shù)設(shè)置不合適時,由于類中心過多,容易造成聚類結(jié)果的振蕩。采用QACO對偏向參數(shù)優(yōu)化之后,AP聚類的類中心與實際值相同,聚類穩(wěn)定性有效增強。

表4 3種算法的聚類準確率性能

從圖4可得,3種算法的聚類準確率標準差性能QACO-AP算法明顯優(yōu)于ACO-AP和AP。從迭代次數(shù)方面來看,QACO-AP需要的迭代次數(shù)更少,ACO-AP次之,AP最多,這主要是因為在偏向參數(shù)未優(yōu)化之前,AP算法需要更多次迭代來求解最高聚類準確率,而采用QACO算法優(yōu)化后,獲得了更優(yōu)偏向參數(shù),AP聚類效率明顯提升。單從收斂曲線來看,ACO-AP和AP均有短暫陷入局部優(yōu)值的情況,而QACO-AP算法標準差一直降低直至穩(wěn)定。

圖4 3種算法的收斂性

3.3 常用算法的聚類性能

為了進一步驗證QACO-AP算法的聚類性能,將常用聚類算法決策樹(Decision tree)[14]、K-中心點(K-mediods)[15]和卷積神經(jīng)網(wǎng)絡(luò)(Convolutional neural network,CNN)聚類算法[16]與本文算法進行聚類性能對比,聚類結(jié)果如圖5所示。

圖5 4種算法的聚類準確率

從圖5可看出,對于相同的樣本集,QACO-AP算法的聚類準確率最高,CNN次之,決策樹最差,QACO-AP的聚類準確率優(yōu)勢明顯。橫向比較發(fā)現(xiàn),4種算法均是在Seeds集上聚類準確率最高,Iris集上聚類準確率普遍較差。

4 結(jié)束語

本文采用量子蟻群優(yōu)化算法對近鄰傳播聚類的偏向參數(shù)進行優(yōu)化求解,提高了近鄰傳播聚類的準確性。合理設(shè)置量子蟻群優(yōu)化的主要參數(shù),能夠獲得較好的偏向參數(shù)優(yōu)化個體,增強近鄰傳播聚類的適用度。仿真結(jié)果表明,相比多種常用聚類算法,QACO-AP算法的聚類準確率得到明顯提升,最高可達91%,較好地避免了陷入局部優(yōu)值的情況,且聚類得到的類別數(shù)明顯優(yōu)于傳統(tǒng)偏向參數(shù)確定方法。下一步研究將進一步優(yōu)化量子蟻群算法的核心參數(shù),以減少量子蟻群優(yōu)化的求解時間,從而提高QACO-AP的聚類效率,以應(yīng)對大規(guī)模樣本聚類的實時性。