基于蟻群覓食原理的聚類算法的研究及改進

張夢佳，李 秦，王菲菲

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

基于蟻群覓食原理的聚類算法的研究及改進

張夢佳，李 秦，王菲菲

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

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

蟻群聚類；兩階段；收斂速度；自適應權重

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

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

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

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

設X={Xi|i=1,2,…,N}為N個數(shù)據(jù)樣本集，其中Xi=(xi1,xi2,…,xiz) 為z維向量。基于蟻群覓食原理的聚類算法ACCA就是把X劃分為K個類M1,M2,…,MK，使聚類目標函數(shù)F最小。設mk=(mk1,mk2,…,mkz)為類Mk的聚類中心，目標函數(shù)F定義如下：

(1)

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

(2)

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

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

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

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

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

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

2 兩階段蟻群聚類算法

2.1 第一階段蟻群聚類算法

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

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

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

(3)

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

2.2 第二階段蟻群聚類算法

(4)

由于t時刻聚類中心計算公式為：

(5)

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

(6)

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

(7)

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

(8)

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

(9)

用信息素強度和加權歐氏距離指導螞蟻構造解，以降低算法僅僅依賴信息素構造解的錯誤率。

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

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

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

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

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

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

3 實驗結果與分析

本文采用人工數(shù)據(jù)集和UCI機器學習數(shù)據(jù)集中的iris、wine數(shù)據(jù)集，分別對ACCA和兩階段蟻群聚類算法進行測試。其中，人工數(shù)據(jù)集由服從以下4類高斯分布的數(shù)據(jù)構成：類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個數(shù)據(jù)。3種數(shù)據(jù)集具體描述如表1所示。

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

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

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

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

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

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

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

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

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

注：*表示無此階段

4 結 語

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

[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] 李振,賈瑞玉.基一種改進的k-means蟻群聚類算法[J].計算機技術與發(fā)展,2015,25(12):28-31.

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

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

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

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

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

[9] 林金灼,葉東毅.基于蟻群聚類算法的優(yōu)化與改進[J].計算機系統(tǒ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].北京郵電大學學報,2013(36):60-63.

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

[14] 龔燕.一種新的全局收斂的混合聚類算法[D].遼寧:大連理工大學,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

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