尚玉新

( 山東商業(yè)職業(yè)技術(shù)學(xué)院，山東 濟(jì)南 250103 )

一種改進(jìn)的基于K-Means的蟻群聚類算法

尚玉新

( 山東商業(yè)職業(yè)技術(shù)學(xué)院，山東 濟(jì)南 250103 )

聚類分析被廣泛用于數(shù)據(jù)挖掘等領(lǐng)域，基于蟻群算法的聚類算法也得以應(yīng)用。針對K-Means算法和蟻群聚類算法出現(xiàn)的缺點，利用了K-Means算法快速確定聚類中心和精英適應(yīng)保留值的策略，提出了一種改進(jìn)的基于K-Means的蟻群聚類算法。仿真實驗表明，改進(jìn)算法的性能得到有效提高。

聚類分析；K-Means算法；蟻群算法；信息素

1 引言

聚類是根據(jù)數(shù)據(jù)間的相似程度將數(shù)據(jù)進(jìn)行合理的分類，使得類間的相似性盡量小，而類內(nèi)的相似性盡量大。[1,2]聚類是一種無監(jiān)督的學(xué)習(xí)，因為它沒有關(guān)于分類的先驗知識。在實際應(yīng)用中，聚類分析的研究成果已經(jīng)廣泛應(yīng)用到數(shù)據(jù)挖掘、圖像處理、模式識別、金融投資、地理信息系統(tǒng)、衛(wèi)星圖像和信息檢索等領(lǐng)域。[3,4]蟻群算法是由意大利學(xué)者根據(jù)生物仿生學(xué)原理提出的一種智能算法，因其具有并行性、魯棒性等優(yōu)良性質(zhì)得到了廣泛的應(yīng)用。[5]蟻群聚類算法最早是由Deneubourg提出的基于螞蟻覓食行為的聚類方法[6]，Lumer 和Faieta提出改進(jìn)算法，并應(yīng)用到數(shù)據(jù)分析中[7]。但基本蟻群聚類算法參數(shù)對性能影響較大且設(shè)置有一定難度，而且需要花費較長的時間[8]，因此利用K-Means算法先在較短時間內(nèi)做出快速分類[9,10]，確定聚類中心，再利用蟻群算法根據(jù)現(xiàn)有的聚類結(jié)果來聚類，這樣可以相互彌補(bǔ)缺陷，得到更好的效果。

2 改進(jìn)的基于K-Means的蟻群聚類算法

2.1 K-means算法

K-means算法是最常用的聚類算法之一，其優(yōu)點是簡單有效，而且可以用于多種數(shù)據(jù)類型。[11]

算法描述如下：

(1)隨機(jī)選擇K個對象作為初始聚類中心；

(2)根據(jù)聚類中心將每個樣本分配給K個中心，形成相似的簇；

(3)重新計算每個簇的平均值，用均值點作為新的聚類種子。

(4)重復(fù)執(zhí)行(2)和(3)直至各個簇不再發(fā)生變化，即各個聚類中心不發(fā)生變化。

該算法對包含異常點的數(shù)據(jù)進(jìn)行聚類時，常常會收斂于局部最優(yōu)解，而不是全局最優(yōu)解。當(dāng)簇密集且區(qū)別明顯時，用此方法效果較好，區(qū)別不明顯時效果不好。

2.2 蟻群聚類算法

聚類問題的蟻群算法思路描述如下[12]：模式樣本分配給第j個聚類中心Zj(j=1,2,…，K)，螞蟻就在模式樣本i到聚類中心Zj的路徑上留下信息素τij，螞蟻選擇聚類中心Zj的轉(zhuǎn)移概率為

(1)

信息素更新方程為

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

蟻群算法存在的問題：

(1)該算法收斂過程比較緩慢，在迭代初期，由于系統(tǒng)參數(shù)改變很慢，使得整個運行過程耗時較長。為簡化操作，初始時一般都賦予相等的常數(shù)，這樣各條路徑上的信息素要明顯區(qū)別開就需要較長的時間。

(2)該算法初值的選取對聚類結(jié)果影響很大，如果選擇不當(dāng)將影響算法的執(zhí)行效率和結(jié)果。

精英蟻群聚類算法是在蟻群算法的基礎(chǔ)上引入了精英螞蟻的策略[13]，就是在每次迭代的過程中，保留固定量的具有最優(yōu)值的解進(jìn)入下一次迭代循環(huán)中，這樣可以把迭代中優(yōu)良的解保留下來加入到下一次循環(huán)中，起到提高算法性能的作用。

2.3 改進(jìn)的基于K-Means的蟻群聚類算法

通過上述內(nèi)容可知，為了實現(xiàn)優(yōu)勢互補(bǔ)，可以將K-Means算法和精英蟻群聚類算法進(jìn)行融合，做出改進(jìn)，將K-Means做過預(yù)處理的數(shù)據(jù)用精英蟻群算法進(jìn)一步聚類，從而得到理想結(jié)果。算法描述如下：

(1)任選K個初始聚類中心：Z1,Z2,Z3,…，Zk；

(2)分別將樣本集X中的各個模式樣本按照歐氏距離的平方和最小的原則分配給K個聚類中心中的某一個Zj；

(4)若Zj′≠Zj(j=1,2,…，K)且沒有快速分類到指定閾值則轉(zhuǎn)(2)；

(5)Nc←0(Nc為迭代次數(shù))，由K-Means算法的分類結(jié)果計算出聚類中心Zj(j=1,2,…，K)，計算每個樣本數(shù)據(jù)相對應(yīng)的到不同聚類中心Zj的初值τij(0)(i=1,2,…,n;=1,2,…,K)，初始化螞蟻數(shù)n，信息素?fù)]發(fā)系數(shù)ρ，精英螞蟻數(shù)r，隨機(jī)給出分配方案；

(6)對每只螞蟻按轉(zhuǎn)移概率pij選擇下一個節(jié)點，利用信息素矩陣構(gòu)造解；

(7)計算本次迭代中螞蟻找到的聚類中心和每個樣本到新的聚類中心的距離，記錄下本次迭代最優(yōu)解和全局最優(yōu)解；

(8)進(jìn)行信息素更新得到τ(t)，并保留前最優(yōu)的個解進(jìn)入下一次迭代中；

(9)若超過最大迭代次數(shù)且無退化行為，則輸出找到的最好解，計算停止，否則轉(zhuǎn)(6)。

3 數(shù)值實驗

為了驗證改進(jìn)算法的有效性，采用蝶形數(shù)據(jù)集和Iris數(shù)據(jù)集[14]利用matlab7.0編程分別對K-Means算法、蟻群聚類算法、本文改進(jìn)算法進(jìn)行比較。在實驗中，改進(jìn)算法參數(shù)設(shè)置如下：ρ=0.01，Q=100，K=3，計算蝶形數(shù)據(jù)時螞蟻個數(shù)為20，計算Iris數(shù)據(jù)集，螞蟻個數(shù)為40，Nc_max=500，每種方法進(jìn)行30次仿真，結(jié)果如表

從以上實驗數(shù)據(jù)可以看出，本文算法利用了K-Means算法快速確定聚類中心和精英適應(yīng)保留值的策略，在性能上有所改進(jìn)。3種算法中改進(jìn)算法略高于基本蟻群算法，均優(yōu)于K-Means算法。但是由于前期K-Means算法限制了聚類的個數(shù)，因而只適應(yīng)于數(shù)目確定的聚類分析問題，對于聚類數(shù)目不確定的問題沒有能很好解決，值得進(jìn)一步探索。

4 結(jié)束語

本文提出了在基于K-Means基礎(chǔ)上的改進(jìn)的蟻群聚類算法，引入了精英保留機(jī)制，將K-Means算法和精英蟻群聚類算法進(jìn)行融合。通過對兩個數(shù)據(jù)集進(jìn)行仿真實驗，發(fā)現(xiàn)新算法能有效提高算法的性能，從而為聚類問題提供了一種思路。今后還應(yīng)該著力于深入研究參數(shù)對算法的影響，以進(jìn)一步提高效率。

[1]Chen M S. Data mining :An overview from a database perspective[J].IEEE Transaction on Knowledge and Data Engineering,1996,8(6):833-866.

[2]劉念濤，劉希玉.基于改進(jìn)的啟發(fā)式蟻群算法的聚類問題的研究[J].計算機(jī)技術(shù)與發(fā)展,2007,17(8):37-39.

[3]Handl J,Knowles J,Dorigo M. On the performance of ant-based clustering[C]//Proc of the 3rd Int Conf on Hybrid Intelligent Systems. Australia: IOS Press,2003,12.

[4]王慧.改進(jìn)的蟻群聚類分析算法的研究[D].河南大學(xué)碩士學(xué)位論文，2009.

[5]Colorni A,Dorigo M,Manierzzo V,et al. Distributed optimization by ant coloies[C]//Proc of European Conf on Artificial Life. Paris, France: Elsevier Publishing,1991:134-142.

[6]Deneubourg J L,Goss S, Franks N,et al. The Dynamics of Collectivesorting:Robot-Like Ants and Ant-Like Robots[C]//Proc of the 1st Int’l Conf on Simulation of Adaptive Haviour, 1991:356-365.

[7]Lumer E,Faieta B.Diversity and Adaption in Populations of Clustering Ants[C]//Proc of the 3rd Int’l Conf on Simulation of Adaptive Behavior,1994: 501-508.

[8]Monmarche N,Slimane M,Venturini G.AntClass: discovery of clusters in numeric data by a hybridization of an ant Colony with the K means algorithm[R].Internal Report, Switzerland: [s.n.],1999.

[9]高尚,湯可宗,楊靜宇.一種新的基于混合蟻群算法的聚類方法[J].微電子學(xué)與計算機(jī),2006,23(12):38-40.

[10]韓強(qiáng),邢潔清.蟻群聚類組合方法參數(shù)M的研究[J].計算機(jī)工程應(yīng)用技術(shù),2009,5(36):10469-10470.

[11]高尚,楊靜宇,吳小俊.聚類問題的蟻群算法[J].計算機(jī)工程與應(yīng)用,2004,(8):90-91,232.

[12]邢潔清,朱慶生,郭平.蟻群聚類組合方法的研究[J].計算機(jī)工程與應(yīng)用,2009,45(18):146-148.

[13]基于最優(yōu)適值保留的蟻群文本聚類算法[J].計算機(jī)工程與科學(xué)，2010，32(5)：79-81.

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

(責(zé)任編輯：孫強(qiáng))

An Improved Ant Colony Clustering Algorithm Based on K-Means

SHANG Yu-xin

( Shandong Institute of Commerce and Technology, JiNan，ShangDong 250103, China )

Clustering analysis is mainly used for dada mining, so does the ant colony clustering algorithm. In this paper, an improved ant colony algorithm is presented based on K-Means algorithm and a mechanism of the best solution kept. It can definite culster center fastly in the beginning and make the best solution kept for the next time. The simulated results show that the improved algorithm has better performance.

clustering analysis; K-Means algorithm; ant colony algorithm; pheromone

2014-09-20

尚玉新，(1986-)，男，山東利津人，碩士，電子信息學(xué)院助教，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

TP274

A

1671-4385(2015)01-0093-03