一種基于信息素和信息熵的蟻群聚類算法

王 慧， 甘 泉

（1.平頂山學(xué)院 招生就業(yè)處，河南 平頂山 467000；2.平頂山學(xué)院 計(jì)算機(jī)與科學(xué)技術(shù)學(xué)院，河南 平頂山 467000）

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

1 蟻群聚類基本原理

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

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

公式中Pp表示螞蟻拾起對(duì)象Oi的概率，Pd表示螞蟻放下對(duì)象Oi的概率，k+和k－是兩個(gè)常量。

2 基于信息素和信息熵的蟻群聚類算法（ALFBP）

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

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

在一個(gè)二維的平面網(wǎng)格中，螞蟻的短期記憶[8]和網(wǎng)格中信息素的分布決定了螞蟻從一個(gè)位置到下一個(gè)位置的空間轉(zhuǎn)移.相應(yīng)的解決方法為：讓每一個(gè)螞蟻都能夠記住近幾次所放下的數(shù)據(jù)對(duì)象和相應(yīng)的位置，如果新的數(shù)據(jù)對(duì)象被拾起，分析新對(duì)象與某個(gè)數(shù)據(jù)對(duì)象之間的關(guān)系，看是否可以歸并，如果不能，可以按照具體的數(shù)據(jù)分布來確定下一步的移動(dòng)方向[9]。假設(shè)螞蟻在平面網(wǎng)格上的具體位置為（γ，θ），在它的走過的痕跡中會(huì)留下相應(yīng)的信息素，在步長(zhǎng)時(shí)間段內(nèi)，所留下的信息為η，伴隨時(shí)間的推移，推移過后的信息就會(huì)進(jìn)行相應(yīng)的減少，設(shè)減少的衰減率為κ。那么螞蟻從k轉(zhuǎn)移到位置i的空間方面的轉(zhuǎn)移概率pik用以下公式來確定[9]：

W（si）響應(yīng)函數(shù)（response function）是關(guān)于 i的信息 素（pheromones）濃度所表示的，證明膜翅目昆蟲在關(guān)于信息素（pheromones）濃度為σi的位置i的相對(duì)出現(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)鍵因素。w（Di）為到位置i的權(quán)值因素，Di代表在時(shí)間為步長(zhǎng)的時(shí)候的位置i與位置k在方向方面的區(qū)別量，依據(jù)Di的值來對(duì)w（Di）進(jìn)行確定[10]，膜翅目昆蟲的移動(dòng)方向能夠事先看成為如圖1中的情況，因?yàn)楦鞣礁裼?個(gè)緊挨著的網(wǎng)狀式單元組成，也就有8個(gè)不同的方向進(jìn)行移動(dòng)，產(chǎn)生8個(gè)方向，各個(gè)方向之間的夾角為45°，那么膜翅目昆蟲可事先從此8個(gè)方向當(dāng)中，任意選取1個(gè)方向，則膜翅目昆蟲迅速的改變方向的概率遠(yuǎn)遠(yuǎn)小于緩慢的改變方向的概率[9]，所以，定義相異改變度數(shù)之?dāng)?shù)值與文獻(xiàn)[11]相同分別為：w（0°）=1，w（±45°）=0.5，w（±90°）=0.25，w（±135°）=0.08，w（180°）=0.05。

2.2 信息熵的計(jì)算

信息熵是一個(gè)比較抽象的數(shù)學(xué)概念，把信息熵定義為離散型隨機(jī)事件產(chǎn)生的概率。學(xué)者Shannon（香農(nóng)）對(duì)信源符號(hào)熵的界定[12]如下：假定隨機(jī)變數(shù)為X，存在取值集是x，就具有一定的可能性，在為x值的情況下，則可能性的函數(shù)就為p（x），信源符號(hào)熵E（x）的相關(guān)公式是：

針對(duì) 1 個(gè)數(shù)項(xiàng)變量之矢量 x=（x1，x2，…，xn）的信息熵的計(jì)算公式為：

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

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

2.3 算法描述

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

在ALFBP算法中，影響螞蟻運(yùn)動(dòng)狀態(tài)的因素僅有鄰域s參數(shù)，比LF算法里的設(shè)置參數(shù)不多，在各次放下對(duì)象的時(shí)候，可以不增多非大塊范圍之信源符號(hào)熵，拾起的時(shí)候，可以不減少非大塊范圍的信源符號(hào)熵，還能加快聚類過程，達(dá)到好的聚類結(jié)果。通過多次的仿真實(shí)驗(yàn)，當(dāng)形成一些較小的聚類時(shí)，負(fù)載的螞蟻會(huì)很多次尋找放下的位置，就會(huì)多次出現(xiàn)E1＜E2的情況，導(dǎo)致不能放下拾起的數(shù)據(jù).在較長(zhǎng)迭代過程中，這些螞蟻起不到聚類的作用。為了防止這種情況的產(chǎn)生，使螞蟻在放下數(shù)據(jù)的失敗次數(shù)達(dá)到一定值時(shí)（取100次），強(qiáng)行放下數(shù)據(jù)，加速了聚類的進(jìn)程。

3 仿真實(shí)驗(yàn)分析

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集表示Tab.1 Experimental data set represents

表2 實(shí)驗(yàn)參數(shù)表Tab.2 Experimental parameters table

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

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

2）正態(tài)分布測(cè)試數(shù)據(jù)集。數(shù)據(jù)集中的4組數(shù)據(jù)的屬性按照正態(tài)分布產(chǎn)生，每組200個(gè)數(shù)據(jù)，各組數(shù)據(jù)服從均值為μ，方差為s=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ù)集隨機(jī)的分布在 60×60 的網(wǎng)格上，螞蟻速度限制在1到10之間。鄰域大小為3，蟻群大小為20，分別用LF算法和ALFBP算法對(duì)生成的數(shù)據(jù)集進(jìn)行聚類，經(jīng)過16萬次的迭代得到誤差函數(shù)隨迭代次數(shù)的變化曲線圖如下：

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

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

4 結(jié) 論

文中在蟻群聚類模型中，引入了信息熵和信息素，提出了基于信息素和信息熵的蟻群聚類分析算法，并設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的蟻群聚類分析平臺(tái)，通過測(cè)試數(shù)據(jù)集對(duì)改進(jìn)的算法進(jìn)行分析，算法顯示出了較高的穩(wěn)定性和準(zhǔn)確率，證明了該改進(jìn)算法的有效性。

[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].計(jì)算機(jī)工程與應(yīng)用，2012，48（36）:33-38.SONGPei-li，QI Fei，ZHANG Peng.Hybrid ant colony colony algorithm in travel agent probl[J].Computer Engineering and Applications，2012，48（36）:33-38.

[3]侯超，侯永.一種改進(jìn)蟻群聚類算法在數(shù)據(jù)挖掘中的研究[J].微計(jì)算機(jī)信息，2011，27（12）:136-138.HOU Chao，HOU Yong.An ant colony clustering algorithm in data mining[J].Micro Computer Information，2011，27（12）:136-138.

[4]宋中山，周騰，周晶平.一種改進(jìn)的蟻群聚類算法在客戶細(xì)分中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2013，32（3）:77-81.SONG Zhong-shan，ZHOU Teng，ZHOU Jing-ping.An improved ant colony clustering algorithm in customer segmentation[J].Application Research of Computers，2013，32（3）:77-81.

[5]Lamer E，F(xiàn)ajita B.Diversity and adaptation in populations of clustering ants[C]//Cliff D，Husbands P，Meyer J，et al.From Animals to Animates 3.Proc of Third International Conference on Simulation of Adaptive Behavior.Cambridge，MA，USA:MIT Press，1994:501-508.

[6]張斌.蟻群聚類算法在WEB使用挖掘中的應(yīng)用研究[D].南寧：廣西大學(xué)，2007.

[7]許智超.基于螞蟻系統(tǒng)的基因表達(dá)數(shù)據(jù)聚類分析 [D].福州：福建農(nóng)林大學(xué)：2012.

[8]M Dorigo，L M Gambardella.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions onEvolutionary Computation，1997，1（1）:53-66.

[9]王慧.改進(jìn)的蟻群聚類分析算法的研究[D].開封：河南大學(xué)，2009.

[10]D R Chialvo，M M Millonas.How swarms build cognitive maps[C]//In:Luc Steels ed.The Biology and Technology of Intelligent Autonomous Agents， Nato ASI Series，1995:439-450.

[11]V Ramos，F(xiàn) Muge，P Pina.Self-Organized Data and Image Retrieval as a Consequence of Inter-Dynamic Synergistic Relationships in Artificial Ant Colonies[C]//Inn'：J Ruizdel-Solar， A Abraham， M koppen Eds.Hybrid Intelligent Systems， Frontiers of Artificial Intelligence and Applications， Santiago， Chile， 2002.

[12]許國(guó)志，顧基發(fā)，車宏安著.系統(tǒng)科學(xué)[M].上海：上海教育出版社，2000.