秦福高，王文琴

(常州工學院計算機信息工程學院，江蘇 常州 213002)

0 引言

k-means算法是一種經(jīng)典的聚類分析方法，如果簇與簇之間區(qū)別明顯、簇內(nèi)部是密集的，它的聚類效果較好。但是該算法對初始聚類中心敏感，對于“噪聲”和孤立點數(shù)據(jù)敏感，容易陷入局部最優(yōu)?，F(xiàn)在許多研究人員嘗試將啟發(fā)式算法引入聚類分析，借助隨機搜索算法找到全局最優(yōu)解。

蟻群算法是一種有效的隨機搜索算法，蟻群在問題空間多點同時進行獨立的解搜索，增強了算法的全局搜索能力。Dorigo M 等［1］根據(jù)蟻群覓食原理提出了蟻群優(yōu)化算法。基于覓食行為的蟻群聚類算法中，螞蟻通過在所經(jīng)路徑移動時留下的信息素進行非直接通信。［2］基于信息素的kmeans聚類方法［3］中，初始中心點雖然不是任選樣本，但“噪聲”和孤立點仍有可能成為初始聚類中心，而且收斂速度相對較慢。如果能夠優(yōu)化初始中心點，引入精英機制及優(yōu)生優(yōu)育機制加強正反饋，則能提高聚類的準確率，加快收斂，于是本文提出了基于k-means算法的改進的蟻群聚類算法。

1 k-means算法及其缺點

1.1 k-means算法思想

k-means算法以k為參數(shù)，把n個對象分為k個簇，以使類內(nèi)具有較高的相似度，而類間的相似度最低。相似度的計算根據(jù)一個簇中對象的平均值(被看作簇的重心)來進行。收斂一般采用平方誤差準則，其中，E 是數(shù)據(jù)集中所有對象到中心點的距離平方誤差和，p是數(shù)據(jù)集中的對象，mi是簇 Ci的均值(即中心點)。［3］

1.2 k-means算法缺點

k-means算法是基于距離的經(jīng)典的聚類算法，其優(yōu)點是簡單、易懂、快速，對于密集型數(shù)據(jù)，聚類效果好，處理大數(shù)據(jù)集時，具有相對可伸縮性和高效性。但是該算法對于“噪音”和孤立點數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。如果初始中心點選擇不當，容易使算法陷入局部最優(yōu)狀態(tài)，不同的初始中心點，可能會導致不同的聚類結(jié)果。

2 一種基于信息素的k-means聚類方法

2.1 蟻群算法

螞蟻的食物源總是隨機散布于蟻巢周圍，經(jīng)過一段時間后，螞蟻總能找到一條從蟻巢到食物源的最短路徑。螞蟻運動時是通過路徑上釋放出的一種特殊的分泌物——信息素來尋找路徑。當它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，同時釋放出與路徑長度有關(guān)的信息素。螞蟻走的路徑越長，則釋放的信息量越小。當后來的螞蟻再次碰到這個路口的時候，選擇信息量較大路徑的概率相對較大，這樣便形成了一個正反饋機制。最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量卻會隨著時間的流逝而逐漸消減，最終整個蟻群會找出最優(yōu)路徑。

由于現(xiàn)實的蟻群運動過程接近于實際的聚類問題，所以近年來涌現(xiàn)出大量的蟻群聚類算法?；谝捠承袨榈南伻壕垲愃惴?，將數(shù)據(jù)視為具有不同屬性的螞蟻，聚類中心即是螞蟻所要尋找的“食物源”，數(shù)據(jù)聚類過程則被看作是螞蟻尋找食物源的過程，螞蟻通過其移動時在所經(jīng)路徑留下的信息素進行非直接通信，形成正反饋加強搜索。［2］

2.2 蟻群算法與k-means算法的結(jié)合

傳統(tǒng)k-means算法的初始中心點是任選的樣本，如果初始中心點選在“噪音”和孤立點數(shù)據(jù)周圍，即使是少量的該類數(shù)據(jù)也能夠?qū)ζ骄诞a(chǎn)生極大的影響，容易使算法陷入局部最優(yōu)狀態(tài)?；鞠伻核惴煽醋鍪且粋€分布式的多智能體系統(tǒng)，該算法在問題空間的多個點同時獨立地進行解搜索，不僅使算法具有較強的全局搜索能力，也增加了算法的可靠性。Sara Saatchi等人［3］將蟻群算法與k-means算法結(jié)合成基于信息素的k-means聚類方法，利用蟻群算法的全局搜索能力來彌補k-means算法容易陷入局部最優(yōu)的不足。

基于信息素的k-means聚類方法處理過程:開始時將所有對象隨機歸并到k個類中，然后計算出初始類中心并更新信息素，數(shù)據(jù)對象的歸屬根據(jù)轉(zhuǎn)移概率的大小來決定，在下一輪循環(huán)中，引入聚類偏差的衡量標準，更新聚類中心，計算偏差，再次判斷，直到偏差沒有變化或在一定誤差范圍內(nèi)，算法結(jié)束。

該算法的初始中心點雖然不是任選的樣本，但仍是隨機分成k類后各類樣本的重心，分類的隨機性比較大，“噪聲”和孤立點仍有可能成為初始聚類中心，陷入局部最優(yōu)，影響聚類的準確率。另外，該算法在聚類過程中只是采用基本蟻群算法中的信息素更新方式，收斂速度相對較慢。所以此算法有待進一步改進。

3 改進的聚類算法

3.1 基于距離和密度優(yōu)化初始凝聚點

通常，聚類時希望選擇數(shù)據(jù)集中、分布范圍較大的點作為凝聚點。初始凝聚點如果僅基于距離因素，往往會取到“噪聲”或孤立點。如果僅基于密度選擇初始凝聚點，選出的k個類中心中有多個距離相近同屬于一個類的可能性將非常大，這無疑會增加迭代的次數(shù)。

因此本文提出基于距離和密度優(yōu)化初始凝聚點。算法取相距最遠的k個均處于高密度區(qū)域的樣本作為聚類中心，這些中心點基本上是確定的，從而避免了初始中心選擇的隨機性，盡可能降低了“噪聲”和孤立點的干擾，保證了聚類結(jié)果較好的穩(wěn)定性，同時也能防止多個類中心同處一類導致尋優(yōu)迭代次數(shù)的增加。

首先定義樣本點x所在區(qū)域的密度:

其中，Distance(x，p)為某種距離度量，r為半徑，X代表樣本點集，p是以x為中心、以r為半徑的球體內(nèi)的樣本。式(1)表明數(shù)據(jù)對象的密度是以x為中心點、r為半徑組成的球體所包含的樣本數(shù)。半徑r的確定方法如下:首先計算兩兩數(shù)據(jù)對象間距離的平均值averdis，然后根據(jù)經(jīng)驗，給定一個常數(shù) θ，密度半徑:r=θ*averdis。

計算出每個數(shù)據(jù)對象的密度后，找到處于高密度區(qū)域的樣本組成高密度樣本集合hdsample，在hdsample中取密度最大樣本點作為第—個聚類中心center1，然后取距離center1最遠的一個高密度樣本點作為第二個聚類中心center2，接著取滿足 max(min(d(x1，center1)，d(xi，center2)))i=1，2，…，n 的樣本 xi作為 center3，以此類推，取滿足 max(min(d(x1，center1)，d(xi，center2)，…，d(xi，centerq-1)))i=1，2，…，n 的樣本 xi作為centerq。按照此方法，計算出k個初始聚類中心。

3.2 精英機制及優(yōu)生優(yōu)育機制

蟻群聚類過程中如果只是采用基本蟻群算法中的信息素更新方式，收斂速度相對較慢。因此，本文提出引入精英機制及優(yōu)生優(yōu)育機制加強正反饋進行蟻群聚類:根據(jù)信息素及螞蟻的隨機性確定每只螞蟻行走路徑，并做好相應(yīng)的標識;根據(jù)標識的類別計算各聚類中心，并計算每只螞蟻的旅程F;根據(jù)F值升序排序，前3只螞蟻作為精英，并只對這3只精英螞蟻的旅程進行變異實現(xiàn)優(yōu)生優(yōu)育，再計算F，找出父代和子代中旅程最短的精英螞蟻，保留該精英，進行后續(xù)處理。

聚類過程中采取精英保留機制，并在精英中進行變異優(yōu)生優(yōu)育，利用若干精英的信息來更新信息素。這種聚類方法不僅可以進一步避免“噪聲”和孤立點的干擾，還能夠利用信息素的正反饋作用加快收斂速度，求得最優(yōu)解。

3.3 算法的處理過程

改進的算法處理過程如下:

把基于距離和密度優(yōu)化的聚類中心作為初始中心點，依據(jù)歐氏距離進行第一次聚類;依據(jù)式(2)根據(jù)第一次聚類結(jié)果更新路徑上的信息素;依據(jù)式(3)計算轉(zhuǎn)移概率Pij，數(shù)據(jù)樣本Xi是否歸并到聚類中心Cj由轉(zhuǎn)移概率Pij決定，若Pij(t)＞P0(P0為一設(shè)定值)，則Xi歸并到Cj，否則，不歸并;根據(jù)類內(nèi)距計算適應(yīng)度值，找出前3只精英螞蟻并進行變異，從所有螞蟻中找出精英螞蟻及其路徑，更新各條路徑上的信息素，對此次最優(yōu)路徑進行正反饋;下一代螞蟻根據(jù)信息素尋找目的地;當精英螞蟻不再變化時，停止聚類，輸出結(jié)果。

其中，ρ為信息素揮發(fā)系數(shù);τij(t)為t時刻樣本Xi到聚類中心Cj路徑上的信息量;Q為信息素強度;L為當前螞蟻本次循環(huán)所走路徑的總長度;α為信息啟發(fā)式因子，反映了螞蟻在運動過程中積累的信息在螞蟻狀態(tài)轉(zhuǎn)移時所起的作用，其值越大，螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強;β為期望啟發(fā)式因子，表示能見度的相對重要性，反映螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則;ηij(t)為啟發(fā)函數(shù)，一般 ηij(t)=1/dij，dij是樣本 Xi到聚類中心Cj的距離。

4 實驗結(jié)果及分析

4.1 實驗結(jié)果

實驗環(huán)境是Matlab 7.0，實驗數(shù)據(jù)集有8個，見表1，其中Ant1和Ant2是類與類之間區(qū)別明顯的人工數(shù)據(jù)集，Iris、Glass、Blance、Image、Wine 和Zoo是來自UCI機器學習庫中的數(shù)據(jù)集。通過8個數(shù)據(jù)集測試k-means算法、基于信息素的kmeans聚類方法及本文提出的改進算法的F-measure和運行時間平均值，測試結(jié)果見表2。

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

表2 三種算法的測試結(jié)果

4.2 實驗分析

測試結(jié)果采用常用的外部評價方法F-measure來進行聚類準確率的評估。F-measure組合了信息檢索中查準率與查全率的思想，查準率即正確預測的百分比，查全率即捕捉到正確分類的百分比。

根據(jù)表2的實驗數(shù)據(jù)，在測試數(shù)據(jù)集相同的情況下，k-means算法的F-measure值最低，主要因為初始凝聚點是隨意選擇的樣本，常常受到“噪聲”或孤立點的干擾，陷入局部最優(yōu);基于信息素的 k-means聚類方法的 F-measure值比k-means算法有所提高，因為初始凝聚點是隨機分類后的樣本的重心，一定程度上可以減少“噪聲”或孤立點的干擾;本文提出的基于k-means算法的改進的蟻群聚類算法的F-measure值最高，說明基于距離和密度優(yōu)化初始凝聚點，再利用蟻群的多點同時獨立搜索這一分布式特點，可以有效避免噪聲或孤立點的影響，提高聚類準確率。

從運行時間上看，k-means算法最快，因為算法簡單，只要根據(jù)歐氏距離即可進行聚類;基于信息素的k-means聚類方法最慢，主要是為了防止陷入局部最優(yōu)，螞蟻的轉(zhuǎn)移受到隨機概率的影響;本文提出的基于k-means算法的改進的蟻群聚類算法，因為初始時對優(yōu)化的凝聚點進行了正反饋，聚類過程中又采取了精英保留機制和優(yōu)生優(yōu)育策略加強正反饋，所以加快了收斂，能更快地找到最優(yōu)解。

5 結(jié)語

本文提出了一種基于k-means算法的改進的蟻群聚類算法，從實驗結(jié)果看，較好地解決了“噪聲”或孤立點的干擾，在實現(xiàn)全局搜索提高聚類準確率的同時，加快了收斂速度，該算法是可行的、有效的。

［1］Dorigo M，Di Caro G.The ant colony optimization meta-heuristic［C］//Corne D，Dorigo M，Glover F.New Ideas in Optimization.London:McGraw-Hill，1999:11-32.

［2］李士勇，陳永強，李妍.蟻群算法及其應(yīng)用［M］.哈爾濱:哈爾濱工業(yè)大學出版社，2004:14-18.

［3］Saatchi S，Hung C C.Hybridization of the Ant Colony Optimization with the K-Means Algorithm for Clustering［C］//Kalviainen H，Parkkinen J，Kaarna A.SCIA 2005.Berlin:Springer-Verlag，2005:511-520.