甘　泉, 王　慧

(1.平頂山學(xué)院 計算機與科學(xué)技術(shù)學(xué)院,河南 平頂山,467000;

2.平頂山學(xué)院 招生就業(yè)處,河南 平頂山,467000)

?

一種改進的蟻群聚類分析算法

甘泉1, 王慧2

(1.平頂山學(xué)院 計算機與科學(xué)技術(shù)學(xué)院,河南 平頂山,467000;

2.平頂山學(xué)院 招生就業(yè)處,河南 平頂山,467000)

摘要：提出了一種改進的蟻群聚類分析算法。該算法改進了經(jīng)典的LF算法。利用短期記憶和網(wǎng)格信息素的局部分布控制螞蟻的隨機移動,利用信息熵作為螞蟻運動狀態(tài)轉(zhuǎn)換規(guī)則,通過對信息熵的計算與比較,更改了數(shù)據(jù)對象拾起和放下的判斷規(guī)則。設(shè)置的參數(shù)減少了,不僅每次放下對象時能夠減少小塊區(qū)域的信息熵,拾起時能夠增加小塊區(qū)域的信息熵,還能加快聚類過程,達(dá)到好的聚類結(jié)果。結(jié)果表明,該算法顯示出了較高的穩(wěn)定性和準(zhǔn)確率。

關(guān)鍵詞：聚類; 蟻群聚類; 信息素; 信息熵

1引言

數(shù)據(jù)挖掘技術(shù)領(lǐng)域中的數(shù)據(jù)聚類的存在,是對事物進行了解的重要步驟。20世紀(jì)90年代,Dario M等人提出了蟻群算法[1],最早被用于解決旅游商問題,還用于二度調(diào)度問題[2]。隨著蟻群算法的廣泛應(yīng)用[3],人們發(fā)現(xiàn)蟻群模型在某些方面更接近實際的聚類問題。在與其他聚類分析模型進行比較時,基于蟻群的聚類分析模型有較多的優(yōu)點:這種模型一般是獨自需要解決相關(guān)難題,會自動根據(jù)數(shù)據(jù)對象的特征產(chǎn)生聚類的數(shù)量,會更好地處理噪聲和異常值[4],會處理不同維度的數(shù)據(jù)集,能較容易完成數(shù)據(jù)的可視化。

2蟻群聚類基本原理

Lumer和Faieta[5]對基本模型進行了擴展,在數(shù)據(jù)分析領(lǐng)域廣泛應(yīng)用,提出了LF算法。該算法先將數(shù)據(jù)任意散放在單獨網(wǎng)格里,在地點螞蟻能有效的感受到周圍的狀況。對象Oj在地點r與附近事物的相似度由下面公式計算[6]:

(1)

式中:f(Oi)表示對象Oi和其鄰域內(nèi)的對象Oj之間的相似度的度量[7]。參數(shù)α代表了相差異的度量,利用它來確定兩個數(shù)據(jù)對象能否放置在一起。Neighs×s是指以地點r為中心的s×s的區(qū)域。 在LF算法中螞蟻拾起或者放下一個對象Oi的概率分別按照以下公式計算:

(2)

(3)

式中:Pp表示螞蟻拾起對象Oi的概率,Pd表示螞蟻放下對象Oi的概率,k+和k-是兩個常量。

3改進的蟻群聚類分析算法(ALFBP)

在LF算法中,基本模型被擴展到了數(shù)據(jù)分析范疇,而且有很大的進展,由于這種算法的參數(shù)設(shè)置繁瑣,并且敏感,同時對于運動的區(qū)域進行了限制,即二維網(wǎng)格的圈定,對于某些網(wǎng)格的存在失去了意義,例如沒有數(shù)據(jù)的網(wǎng)格。所以,這種“物以類聚”統(tǒng)計分析情況并不盡如人意。改進算法思想為:首先將有需要的數(shù)據(jù)對象分布于二維網(wǎng)格,然后具體的具有螞蟻真實的群體行為進行聚類剖析。采用信息素和短期記憶的思想對控制螞蟻的隨意移動進行控制,把信息熵作為螞蟻運動狀態(tài)的轉(zhuǎn)換規(guī)則,信息熵的計算與比較來替代LF算法中的群體相似度計算和概率轉(zhuǎn)換函數(shù),對拾起和放下數(shù)據(jù)對象的判斷規(guī)則進行修改。實驗結(jié)果顯示證明了改進算法是有效的,算法取得了較好的聚類結(jié)果。

3.1螞蟻空間轉(zhuǎn)移策略

在一個二維的平面網(wǎng)格中,螞蟻的短期記憶和網(wǎng)格中信息素的分布決定了螞蟻從一個位置到下一個位置的空間轉(zhuǎn)移.相應(yīng)的解決方法為:讓每一個螞蟻都能夠記住近幾次所放下的數(shù)據(jù)對象和相應(yīng)的位置,如果新的數(shù)據(jù)對象被拾起,分析新對象與某個數(shù)據(jù)對象之間的關(guān)系,看是否可以歸并,如果不能,可以按照具體的數(shù)據(jù)分布來確定下一步的移動方向。

假設(shè)螞蟻在平面網(wǎng)格上的具體位置為(γ,θ),在它的走過的痕跡中會留下相應(yīng)的信息素,在步長時間段內(nèi),所留下的信息為η,伴隨時間的推移,推移過后的信息就會進行相應(yīng)的減少,設(shè)減少的衰減率為κ。那么螞蟻從k轉(zhuǎn)移到位置k的空間方面的轉(zhuǎn)移概率pik用以下公式來確定:

(4)

(5)

W(σi)響應(yīng)函數(shù)(response function)是關(guān)于i的信息素(pheromones)濃度所表示的,證明膜翅目昆蟲在關(guān)于信息素(pheromones)濃度為σi的位置i的相對出現(xiàn)率,較高的β取值使膜翅目昆蟲順著信息素的有關(guān)方向位移,其中β是決定膜翅目昆蟲所有情況的抗噪比相關(guān)的參數(shù)數(shù)據(jù),1/δ證明膜翅目昆蟲在具有信息素(pheromones)范圍內(nèi)所能捕捉到信息素改變之能力,j/k表示在k鄰域內(nèi)所有網(wǎng)格單元j的和,集合中的參數(shù)β與1/δ二者是形成了信息素(pheromones)痕跡的關(guān)鍵因素。ω(Δi)為到位置i的權(quán)值因素,Δi代表在時間為步長的時候的位置i與位置K在方向方面的區(qū)別量,依據(jù)Δi的值來對ω(Δi)進行確定[8],因為各方格有八個緊挨著的網(wǎng)狀式單元組成,也就有8個不同的方向進行移動,產(chǎn)生八個方向,各個方向之間的夾角為45度,那么膜翅目昆蟲可事先從此八個方向當(dāng)中,任意選取1個方向,則膜翅目昆蟲迅速的改變方向的概率遠(yuǎn)遠(yuǎn)小于緩慢的改變方向的概率,所以,定義相異改變度數(shù)之?dāng)?shù)值與文獻[8]相同,分別為:ω(0o)=1,ω(±45o)=0.5,ω(±90o)=0.25,ω(±135o)=0.08,ω(180o)=0.05。

3.2信息熵的計算

信息熵是一個比較抽象的數(shù)學(xué)概念,我們把信息熵定義為離散型隨機事件產(chǎn)生的概率。學(xué)者Shannon(香農(nóng))對信源符號熵的界定如下:假定隨機變數(shù)為X,存在取值集是x,就具有一定的可能性,在為x值的情況下,則可能性的函數(shù)就為p(x),信源符號熵E(x)的相關(guān)公式是:

(6)

針對1個數(shù)項變量之矢量x=(x1,x2,…,xn)的信息熵的計算公式為:

(7)

式中:p(x1,x2,…,xn)是多變量可能分布函數(shù),X1,X2,…Xn是相應(yīng)向量項的可能取值集合。

通過借用信息熵中包含聚類的子空間的信息熵比不包含聚類的信息熵小的特征,在 LF算法中引入信息熵,對數(shù)據(jù)對象拾起和放下的判斷規(guī)則進行更改,設(shè)置的參數(shù)變少了,取得了較好的聚類質(zhì)量。該策略描述為:單個負(fù)重對象oi的膜翅目昆蟲位移至網(wǎng)絡(luò)中空白區(qū),計算附近s×s范圍里的對象信源符號熵,試想未放下對象oi前的信源符號熵在與該區(qū)域的信源符號熵進行比對時,前者略大于后者,則放下該對象oi單個并未負(fù)重的膜翅目昆蟲移至對象oi處,計算附近s×s區(qū)域中的對象信息熵,試想oi未拾起對象前的信源符號熵與該對象后該范圍的信源符號熵,在做出對比時,前者大于后者時,不小于拾起則拾起對象oi。假定所有“數(shù)據(jù)對象”(Data Object )包含n個屬性,且它們之間是獨立的關(guān)系,A1,A2,…,An,每個屬性之取值集為X1,X2,…Xn,就有極大的可能性s×s區(qū)域中的對象信息熵E(S2)為:

(8)

3.3算法描述

據(jù)上面對基于信息素和信息熵的蟻群聚類算法的討論,ALFBP算法的過程如圖1所示。

在ALFBP算法中,影響螞蟻運動狀態(tài)的因素僅有鄰域s參數(shù),比LF算法里的設(shè)置參數(shù)不多,在各次放下對象的時候,可以不增多非大塊范圍之信源符號熵,拾起的時候,可以不減少非大塊范圍的信源符號熵,還能加快聚類過程,達(dá)到好的聚類結(jié)果。通過多次的仿真實驗,當(dāng)形成一些較小的聚類時,負(fù)載的螞蟻會很多次尋找放下的位置,就會多次出現(xiàn)E1

4改進的蟻群聚類算法分析

(1) 為了測試ALFBP算法的聚類質(zhì)量和改進算法的有效性,我們分別進行了兩組各十次實驗,比較了最終聚類結(jié)果與LF算法的聚類結(jié)果。算法采用JAVA來實現(xiàn)。實驗使用UCI公共數(shù)據(jù)庫所提供的兩個數(shù)據(jù)集見表1,這兩個數(shù)據(jù)集都有自己的分類表,能夠評價最終的聚類性能,設(shè)置算法的參數(shù)參見表2。聚類性能評價通過計算F一measure 的值,最大迭代次數(shù)都設(shè)置為106。

表1　實驗數(shù)據(jù)集表示

第一組實驗中,使用Iris數(shù)據(jù)集來測試算法的聚類質(zhì)量。在20次實驗中,ALFBP算法的F一measure 值有18次超過了LF算法的F一measure 值。就平均F一measure值而言,ALFBP算法達(dá)到了0.945,LF算法為0.889。由此可知,聚類質(zhì)量ALFBP算法要優(yōu)于LF算法。而且,對比LF算法,ALFBP算法避免產(chǎn)生小塊的聚類。

圖1　ALFBP算法流程圖Fig.1　ALFBP algorithm flow chart

表2　實驗參數(shù)表

第二組20次實驗中,采用了數(shù)據(jù)集Zoo來測試算法的聚類質(zhì)量。在20次實驗中,ALFBP算法的F一measure值全都超過了LF算法的F一measure值。ALFBP算法平均F一measure 值為0.856,能夠保持比較滿意的聚類效果,但是LF算法之平均數(shù)值約是0.688,聚類之效果并不明顯。由此可見ALFBP算法更適合于高緯數(shù)據(jù)的處理。

(2) 正態(tài)分布測試數(shù)據(jù)集。數(shù)據(jù)集中的四組數(shù)據(jù)的屬性按照正態(tài)分布產(chǎn)生,每組200個數(shù)據(jù),各組數(shù)據(jù)服從均值為μ,方差為σ=2的正態(tài)分布。

具體為:類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]}。數(shù)據(jù)集隨機的分布在60×60的網(wǎng)格上,螞蟻速度限制在1到10之間。鄰域大小為3,蟻群大小為20,分別用LF算法和ALFBP算法對生成的數(shù)據(jù)集進行聚類,經(jīng)過16萬次的迭代得到誤差函數(shù)隨迭代次數(shù)的變化曲線圖如圖2所示。

圖2　兩種算法誤差比較Fig.2　Comparison of the two algorithms error

在圖2中,橫坐標(biāo)表示為迭代次數(shù)×104,縱坐標(biāo)表示為誤差平方和×102。從圖2我們可以看出ALFBP算法有較好的收斂性能,而且能夠加快聚類,這是因為ALFBP算法設(shè)置的參數(shù)減少了,使用ILFBP算法中定義的螞蟻信息素和短期記憶方式校正其隨機移動,利用信息熵作為螞蟻運動狀態(tài)轉(zhuǎn)換規(guī)則,每次對于數(shù)據(jù)的拾起和放下都會對區(qū)域的信息熵有減少或者增加的影響。還能加快聚類過程,使相似度大的數(shù)據(jù)對象能夠較快地聚集在一起能夠加快聚類。另外,兩種算法經(jīng)過16萬次迭代后的F-measure 值為LF為0.2344,ALFBP算法為0.9822,這些結(jié)果都表明該算法可行。

5結(jié)束語

本文提出了改進的蟻群聚類分析算法,利用短期記憶和網(wǎng)格信息素的局部分布控制螞蟻的隨機移動,通過使用當(dāng)前數(shù)據(jù)對象位置局部區(qū)域信息熵的計算和比較作為螞蟻運動狀態(tài)轉(zhuǎn)換的策略,來減少設(shè)置參數(shù)的個數(shù)。實驗結(jié)果顯示改進的算法收斂速度快,效果更高,算法的穩(wěn)定性高。另外,本文各種方法采用的實驗數(shù)據(jù),均為國內(nèi)相關(guān)文獻選用的實驗數(shù)據(jù),這便于本文方法與相關(guān)方法實驗結(jié)果的比較。在未來的研究工作中,應(yīng)將本文各方法應(yīng)用于實際數(shù)據(jù)處理問題,將其不斷完善。

參考文獻:

[1]Dorigo M,Bonabeau E,Theraulaz G.Ant algorithms and stigmergy[J].Future Generation Computer Systems.2000,16(8):851-871.

[2]宋佩莉,祁飛,張鵬.混合蟻群蜂群算法在旅行Agent問題中的應(yīng)用[J].計算機工程與應(yīng)用,2012,48(36):33-38.

SONG Peili,QI Fei,ZHANG Peng.Application of hybrid ant colony and bee colony algorithm in traveling Agent problem[J].Computer Engineering and Applications,2012,48(36):34-38.

[3]侯超.侯永.一種改進蟻群聚類算法在數(shù)據(jù)挖掘中的研究[J].微計算機信息,2011,27(12):136-138.

HOU Chao,HOU yong.An Improved Ant Colony Clustering Algorithm in Data Mining[J].Micro Computer Information.2011,27(12):136-138.

[4]周國娟.基于蟻群算法的文本聚類處理的研究[J].通信技術(shù).2010,43(11):74-77.

ZHOU Guojuan.Text Clustering Research based on Ant Colony Algorithm[J].Communications Technology.2010,43(11):74-77.

[5]Lamer E,Fajita B.Diversity and adaptation in populations of clustering ants[C].Proc.of Third International Conference on Simulation of Adaptive Behavior.Cambridge,MA,USA:MIT Press.1994:501-508.

[6]DM Dorigo,L M Gambardella.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66

[7]D R Chialvo,M M Millonas.How swarms build cognitive maps[C].The Biology and Technology of Intelligent Autonomous Agents,Nato ASI Series.1995:(144):439-450.

[8]V Ramos,F Muge,P Pina.Self-Organized Data and Image Retrieval as a Consequence of Inter-Dynamic Synergistic Relationships in Artificial Ant Colonies[C]Hybrid Intelligent Systems,Frontiers of Artificial Intelligence and Applications,Santiago,Chile,2002,12.

甘泉男(1980-),安徽靈璧縣人,講師,研究方向為算法分析等。

王慧女(1982-),河南平頂山人,講師,研究方向為數(shù)據(jù)挖掘。

An Improved Ant Clustering Analysis AlgorithmGANQuan1,WANGHui2

(1.College of Computer Science and Technology,Pingdingshan University,Pingdingshan 467000,China;

2.Department of Admission and Employmentl Pingdingshan University,Pingdingshan 467000,China)

Abstract：An improved ant colony clustering algorithm is developed.This algorithm improved classic LF algorithm by employing short-term memory and local distribution grid to control ant pheromone random movement,information entropy state of motion to act as ants’ conversion rules.The judgment rule of picking up and dropping data is changed based on calculating and comparing the information entropy.This reduces the set parameters.Not only the entropy of small area which putting down the object reduces,but also the entropy of small area which picking up the object increases.The method speeds up of process of clustering and achieves good clustering results.These results prove that the algorithm has high stability and accuracy.

Key words：clustering; ant colony clustering; pheromone; information entropy

基金項目：河南省科技廳攻關(guān)項目(KJT142102210226)

中圖分類號：TP 391

文獻標(biāo)識碼：A