王 慧， 甘 泉

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

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

1 蟻群聚類基本原理

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

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

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

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

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

2.1 螞蟻空間轉移策略

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

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

2.2 信息熵的計算

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

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

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

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

2.3 算法描述

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

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

3 仿真實驗分析

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

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

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

表2 實驗參數(shù)表Tab.2 Experimental parameters table

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

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

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

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

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

4 結 論

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

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

[2]宋佩莉，祁飛，張鵬.混合蟻群蜂群算法在旅行Agent問題中的應用[J].計算機工程與應用，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]侯超，侯永.一種改進蟻群聚類算法在數(shù)據(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].計算機應用研究，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使用挖掘中的應用研究[D].南寧：廣西大學，2007.

[7]許智超.基于螞蟻系統(tǒng)的基因表達數(shù)據(jù)聚類分析 [D].福州：福建農(nóng)林大學：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]王慧.改進的蟻群聚類分析算法的研究[D].開封：河南大學，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]許國志，顧基發(fā)，車宏安著.系統(tǒng)科學[M].上海：上海教育出版社，2000.