張夢(mèng)佳，李 秦，王菲菲

(蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州730070)

基于蟻群覓食原理的聚類算法的研究及改進(jìn)

張夢(mèng)佳，李 秦，王菲菲

(蘭州交通大學(xué) 數(shù)理學(xué)院，甘肅 蘭州730070)

針對(duì)基于蟻群覓食原理的聚類算法初期收斂速度較慢的問題，以及未區(qū)分各維特征主次的缺陷，本文提出了一種兩階段蟻群聚類算法，以解決上述問題。第一階段引入各只螞蟻的實(shí)時(shí)信息素更新規(guī)則改善算法初期收斂速度較慢問題，并為第二階段提供合理的初始隸屬度矩陣；第二階段利用隸屬度矩陣自適應(yīng)地賦予各維特征不同的權(quán)重，再用信息素強(qiáng)度和加權(quán)歐氏距離共同指導(dǎo)各只螞蟻構(gòu)造解。經(jīng)過人工數(shù)據(jù)集和UCI數(shù)據(jù)集的測(cè)試，結(jié)果表明兩階段蟻群聚類算法可以加快算法初期收斂速度，同時(shí)提高聚類的準(zhǔn)確率。

蟻群聚類；兩階段；收斂速度；自適應(yīng)權(quán)重

聚類作為數(shù)據(jù)分析領(lǐng)域中人們認(rèn)識(shí)和探索事物內(nèi)在分布結(jié)構(gòu)的一種有效手段，被廣泛應(yīng)用于許多領(lǐng)域，如：信息檢索、客戶細(xì)分、機(jī)器學(xué)習(xí)、圖像壓縮、生物學(xué)等。聚類為無監(jiān)督學(xué)習(xí)，其根據(jù)數(shù)據(jù)樣本之間的相關(guān)性將數(shù)據(jù)樣本集劃分為不同的類，使得相同類內(nèi)的數(shù)據(jù)之間相似度較高，而不同類之間的相異度較高。

蟻群算法[1]是1991年由意大利學(xué)者Dorigo M提出的一種模仿螞蟻群體行為的仿生優(yōu)化算法，2004年Shelokar將蟻群算法運(yùn)用于聚類分析中，提出基于蟻群覓食原理的聚類算法[2](Ant Colony Clustering Algorithm，ACCA)?；谙伻阂捠吃淼木垲愃惴ň哂邢伻核惴ǖ碾S機(jī)搜索、自組織聚類、優(yōu)良的分布式計(jì)算等優(yōu)點(diǎn)，但是該算法初期受蟻群隨機(jī)搜索、信息素更新緩慢的影響收斂速度較慢，聚類過程中信息素的高度集中導(dǎo)致算法后期易陷入局部最優(yōu)。目前對(duì)基于蟻群覓食原理的聚類算法的改進(jìn)多是與其他算法相結(jié)合,取得了較好的聚類結(jié)果，但是還存在一些不足：文獻(xiàn)[3]使用初始化敏感的K-Means算法快速、粗略地確定蟻群聚類算法的聚類中心，聚類結(jié)果容易受初始聚類中心的影響；文獻(xiàn)[4-5]結(jié)合遺傳算法的交叉、變異操作避免蟻群聚類算法陷入局部最優(yōu)，但混合算法的運(yùn)行時(shí)間較長；文獻(xiàn)[2-5]未區(qū)分樣本各維特征的主次。為了加快算法初期收斂速度，又避免聚類結(jié)果受到初始聚類中心的影響，同時(shí)考慮樣本各維特征的貢獻(xiàn)率，本文提出一種兩階段蟻群聚類算法。

1 基于蟻群覓食原理的聚類算法

螞蟻在尋找食物源的過程中會(huì)在其走過的路徑上留下一種特殊的分泌物信息素來標(biāo)記路徑，螞蟻釋放出來的信息素的量與路徑長度成反比，而螞蟻選擇路徑的概率與信息素的量成正比，隨著時(shí)間推移該物質(zhì)也會(huì)逐漸揮發(fā)。當(dāng)一條路徑上走過的螞蟻數(shù)量越多，這條路徑被后來螞蟻選擇的概率越高，從而就增強(qiáng)了該路徑上信息素的強(qiáng)度，因此會(huì)吸引更多的螞蟻，這一過程稱為正反饋[6]。通過正反饋機(jī)制，螞蟻?zhàn)罱K可以找到從蟻穴到食物源的最短路徑。

設(shè)X={Xi|i=1,2,…,N}為N個(gè)數(shù)據(jù)樣本集，其中Xi=(xi1,xi2,…,xiz) 為z維向量?；谙伻阂捠吃淼木垲愃惴ˋCCA就是把X劃分為K個(gè)類M1,M2,…,MK，使聚類目標(biāo)函數(shù)F最小。設(shè)mk=(mk1,mk2,…,mkz)為類Mk的聚類中心，目標(biāo)函數(shù)F定義如下：

(1)

設(shè)τik(t)表示t時(shí)刻樣本Xi到聚類中心mk路徑上殘留的信息素量，該算法僅對(duì)螞蟻找到的全局最優(yōu)解路徑上的信息素更新，更新方式為：

(2)

基于螞蟻覓食原理的聚類算法如下：

步驟2：構(gòu)造每只螞蟻的解，對(duì)每只螞蟻隨機(jī)生成一個(gè)隨機(jī)數(shù)q。若q≤q0，則螞蟻根據(jù)信息素矩陣選中擁有最大信息素強(qiáng)度的類，將樣本Xi分配到類Mk中；否則，將樣本Xi隨機(jī)分配到類Mk中。

步驟3：根據(jù)螞蟻構(gòu)造的解計(jì)算式(1)目標(biāo)函數(shù)值和新的聚類中心(即類內(nèi)樣本特征的平均值)。

步驟4：若所有螞蟻均完成解的構(gòu)造，則對(duì)A個(gè)目標(biāo)函數(shù)值從小到大進(jìn)行排序，找出最小的F值記為此次迭代的最優(yōu)值；然后將此次迭代的最優(yōu)解與全局最優(yōu)解進(jìn)行比較，取二者之中目標(biāo)函數(shù)值較小者為全局最優(yōu)解，再按式(2)進(jìn)行全局信息素的更新；否則，返回步驟2。

步驟5：若滿足結(jié)束條件t>t_max，則輸出全局最優(yōu)解；否則迭代次數(shù)t=t+1，轉(zhuǎn)至步驟2。

基于蟻群覓食原理的聚類算法初期收斂速度較慢，聚類過程中未考慮各維特征的貢獻(xiàn)率，導(dǎo)致聚類結(jié)果不理想。為了改善聚類的效率和質(zhì)量，本文第一階段采用基于各只螞蟻實(shí)時(shí)信息素更新規(guī)則改進(jìn)的蟻群聚類算法進(jìn)行初始化，加快算法初期收斂速度，使蟻群盡快搜索到近似解附近，為下一階段提供合理的初始隸屬度矩陣；第二階段引入自適應(yīng)特征加權(quán)，在每次迭代中利用隸屬度矩陣自適應(yīng)賦予各維特征不同的權(quán)重，進(jìn)而由信息素強(qiáng)度和加權(quán)歐氏距離共同指導(dǎo)螞蟻構(gòu)造解，最終得到較理想的聚類。

2 兩階段蟻群聚類算法

2.1 第一階段蟻群聚類算法

基于蟻群覓食原理的聚類算法式(2)中信息素的更新僅僅增強(qiáng)了全局最優(yōu)解路徑上的信息素強(qiáng)度，其他路徑上的信息素強(qiáng)度沒有更新，這就造成了算法初期收斂速度較慢。為了改善這一問題，本階段在每只螞蟻搜索完成之后進(jìn)行全部路徑上的信息素更新，新信息素矩陣作為下一只螞蟻構(gòu)造解的依據(jù)，再結(jié)合每次迭代完成后全局最優(yōu)解路徑上信息素的更新，有效提高了算法的初期收斂速度。

第R只螞蟻實(shí)時(shí)信息素更新規(guī)則：

τik(R)=(1-ρ)τik(R-1)+Q/(dik+0.01)。

(3)

式中：Q為一個(gè)正常數(shù)，ρ為隨機(jī)揮發(fā)因子[7](當(dāng)ρ取大時(shí)有利于全局搜索，ρ取小時(shí)加快收斂速度)。

2.2 第二階段蟻群聚類算法

(4)

由于t時(shí)刻聚類中心計(jì)算公式為：

(5)

將mkj(t)帶入式(4)得：

(6)

將式(5)帶入式(6)得到不計(jì)算聚類中心點(diǎn)的各維權(quán)重系數(shù)：

(7)

上式中t時(shí)刻各維權(quán)重系數(shù)是根據(jù)t-1時(shí)刻得到的隸屬度矩陣和數(shù)據(jù)樣本計(jì)算得到。進(jìn)而能夠得到t時(shí)刻樣本Xi到聚類中心mk的加權(quán)歐氏距離：

(8)

經(jīng)過第一階段的預(yù)處理之后可以粗略地得到聚類中心，則在此階段改變螞蟻構(gòu)造解的方式為：

(9)

用信息素強(qiáng)度和加權(quán)歐氏距離指導(dǎo)螞蟻構(gòu)造解，以降低算法僅僅依賴信息素構(gòu)造解的錯(cuò)誤率。

2.3 兩階段蟻群聚類算法步驟

步驟1：初始化。設(shè)定各參數(shù)Q、L,聚類數(shù)K，螞蟻個(gè)數(shù)A，最大迭代次數(shù)t_max，第一階段迭代次數(shù)t_1，初始信息素矩陣τik(0)=C。

步驟2：迭代次數(shù)t≤t_1，則每只螞蟻按ACCA中螞蟻搜索解的方式確定各樣本所屬的類；每只螞蟻經(jīng)過所有樣本點(diǎn)后，按式(3)更新全部路徑上的信息素。

步驟3：所有螞蟻全部完成一次遍歷后,按式(2)取ρ∈rand更新全局信息素，直到滿足終止條件。

步驟4：利用隸屬度矩陣、數(shù)據(jù)樣本確定各維特征的權(quán)重系數(shù)，由信息素矩陣和按式(8)計(jì)算所得的距離矩陣確定Pik。

步驟7：若滿足結(jié)束條件t>t_max，則輸出全局最優(yōu)解；否則迭代次數(shù)t=t+1，轉(zhuǎn)至步驟4。

3 實(shí)驗(yàn)結(jié)果與分析

本文采用人工數(shù)據(jù)集和UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集中的iris、wine數(shù)據(jù)集，分別對(duì)ACCA和兩階段蟻群聚類算法進(jìn)行測(cè)試。其中，人工數(shù)據(jù)集由服從以下4類高斯分布的數(shù)據(jù)構(gòu)成：類1{x～N(0,2),y～N(0,2)}，類2{x～N(0,2),y～N(8,2)}，類3{x～N(8,2),y～N(0,2)}，類4{x～N(8,2),y～N(8,2)}，每類各50個(gè)數(shù)據(jù)。3種數(shù)據(jù)集具體描述如表1所示。

實(shí)驗(yàn)運(yùn)行環(huán)境：AMD A8-6410,2.0 GHzCPU,4 GB RAM,Matlab2010。實(shí)驗(yàn)參數(shù)設(shè)定：ρ=0.1，q0=0.9，Q=100 ,L=2,初始化τik(0)=0.01，螞蟻個(gè)數(shù)A=50。

表1 數(shù)據(jù)集

對(duì)以上3個(gè)數(shù)據(jù)集運(yùn)用ACCA和兩階段蟻群聚類算法分別運(yùn)行50次，結(jié)果如表2、表3、表4所示。從表2、表3和表4中可以看出：

(1)單用兩階段蟻群聚類算法中第一階段蟻群聚類算法比ACCA的收斂速度快，正確率也有小幅提高，說明該階段提供的隸屬度矩陣較為合理，能用于下一階段特征權(quán)重系數(shù)的計(jì)算。但是該階段僅僅依靠信息素選擇樣本所屬的類,正確率還有待提高。

(2)在人工數(shù)據(jù)集、iris數(shù)據(jù)集和wine數(shù)據(jù)集上，兩階段蟻群聚類算法的平均正確率比ACCA分別提高17.27%、7.16%、27.27%，聚類的正確率顯著提高，這是由于特征權(quán)重系數(shù)消除了數(shù)據(jù)間的冗余，使得螞蟻依靠信息素強(qiáng)度和加權(quán)歐式距離選擇樣本所屬的類更精確。

(3)相比ACCA，兩階段蟻群聚類算法的平均運(yùn)行時(shí)間有大幅提高，說明該算法有效保留了第一階段蟻群聚類算法收斂速度快的優(yōu)點(diǎn)。

表2 人工數(shù)據(jù)集聚類結(jié)果對(duì)比

表3 iris數(shù)據(jù)集聚類結(jié)果對(duì)比

表4 wine數(shù)據(jù)集聚類結(jié)果對(duì)比

注：*表示無此階段

4 結(jié) 語

本文對(duì)基于蟻群覓食原理的聚類算法進(jìn)行改進(jìn)，第一階段引入實(shí)時(shí)信息素更新規(guī)則加快算法初期收斂速度，第二階段自適應(yīng)賦予各維特征不同的權(quán)重系數(shù)，消除數(shù)據(jù)間的冗雜，使螞蟻更有效地構(gòu)造解,提高聚類的準(zhǔn)確率。經(jīng)人工數(shù)據(jù)集和UCI數(shù)據(jù)集的測(cè)試，進(jìn)一步驗(yàn)證了兩階段蟻群聚類算法的可行性及有效性。

[1] Dorigo M,Maniezzo V,Colorni A.The ant system:Optimization by a colony of cooperation agents[J].IEEE Trans on SMC,1996,26(1):28-41.

[2] Shelokar P S,Jayaraman V K,Kulkarni B D.An ant colony approach for clustering[J].Analytica Chimica Acta,2004(509):187-195.

[3] 李振,賈瑞玉.基一種改進(jìn)的k-means蟻群聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(12):28-31.

[4] 戴皇冠,石躍祥,李聘婷.基于混合交叉因子的蟻群聚類優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32:3840-3843.

[5] 王智,張自力.一種新的混合蟻群聚類算法[J].西南師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,34(3):88-92.

[6] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005:24-42.

[7] 張永強(qiáng),王曉東.基于信息素更新和揮發(fā)因子調(diào)整改進(jìn)蟻群算法[J].西安工程大學(xué)學(xué)報(bào),2016,30(3):400-404.

[8] 陳新泉.聚類算法中的優(yōu)化方法應(yīng)用[M].四川:電子科技大學(xué)出版社,2014:65-81.

[9] 林金灼,葉東毅.基于蟻群聚類算法的優(yōu)化與改進(jìn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2013,22(12):93-99.

[10] Monmarche N,Slimane M,Venturini G.On improving clustering in numerical databases with artificial ants[C].Lecture notes in Artificial Intelligence,1999,9:13-17.

[11] Huang J Z,Michael K N,Hongqiang R,et al.Automated Variable Weighting in k-Means Type Clustering[J].IEEE Transaction on pattern analysis and machine intelligence,2005,27(5):657-668.

[12] 熊文,晉耀紅.使用蟻群優(yōu)化和凝聚層次的混合聚類[J].北京郵電大學(xué)學(xué)報(bào),2013(36):60-63.

[13] 肖林云,陳秀宏,林喜蘭.特征加權(quán)和優(yōu)化劃分的模糊C均值聚類算法[J].微電子學(xué)與計(jì)算機(jī),2016,33(10):143-150.

[14] 龔燕.一種新的全局收斂的混合聚類算法[D].遼寧:大連理工大學(xué),2016:20-26.

Research and Improvement of Clustering Algorithm Based on Ant Colony Foraging Principle

ZHANG Mengjia, LI Qin, WANG Feifei

(Lanzhou Jiaotong University, Lanzhou 730070, China)

Focusing on the problem, which the clustering algorithm based on ant colony foraging principle of convergence may be slow in the initial stage, and the defects not distinguishing the various features of primary and secondary, this paper presents a two-stage ant colony clustering algorithm to solve the problems mentioned above. The first stage of algorithm which introduces the ant real-time initial pheromone update rule to improve the problem of low convergence speed in early algorithm. the second stage of algorithm, guiding the ants structural solution by the membership matrix to adaptively endow the reasonable feature weight of each dimension, as well as the pheromone intensity and weighted Euclidean distance .Through the test on artificial data set and UCI data sets, the results show that the two-stage ant colony clustering algorithm can improve the convergence speed in early algorithm, mean while, improve the accuracy of clustering.

ant colony clustering; two stages; the rate of convergence; adaptive feature weight

10.3969/j.issn.1674-5403.2017.04.014

TP301.6

A

1674-5403(2017)04-0060-05

2017-04-25

張夢(mèng)佳(1993-)，女，河南新鄉(xiāng)人，在讀碩士研究生，主要從事智能計(jì)算方面的研究.