一種基于信息增益的蟻群聚類算法

羅聰,曹三省,2,杜懷昌

(1.中國傳媒大學信息工程學院,北京 100024;2.南京大學計算機軟件新技術國家重點實驗室,南京 210093)

1 引言

受生物進化機理的啟發(fā),科學家提出了許多用以解決復雜優(yōu)化問題的新方法,如遺傳算法、進化策略等。1991年意大利學者 Dorigo M等提出了蟻群算法。它是一種新型的優(yōu)化方法。該算法不依賴于具體問題的數(shù)學描述,具有全局優(yōu)化能力。后來其它科學家根據(jù)自然界真實螞蟻堆積尸體及分工行為,提出了基于螞蟻的聚類算法。利用簡單的智能體模仿螞蟻在給定的環(huán)境中隨意移動。這些算法的基本原理簡單,已經(jīng)應用到電路設計、文本挖掘等領域。蟻群算法作為一種模擬進化算法,具有如下的特征:(1)蟻群算法是一種自組織的算法;(2)蟻群算法是一種本質(zhì)上并行的算法;(3)蟻群算法是一種正反饋的算法;(4)蟻群算法具有較強的魯棒性;(5)蟻群算法是一種通用型隨機優(yōu)化方法;(6)蟻群算法是一種啟發(fā)式算法。

但是,蟻群聚類算法有兩個明顯的缺點:(1)由于輸入數(shù)據(jù)的所有屬性均等地參與計算,沒有突出屬性的重要程度,聚類結果可能發(fā)生較大的偏差;(2)對于大量的數(shù)據(jù),如果數(shù)據(jù)的維數(shù)過高,算法將運行很長的時間,使算法的時間效率非常低。

針對上述缺點,本文利用信息增益來衡量屬性的重要程度,選擇信息增益較大的屬性實現(xiàn)數(shù)據(jù)的降維,既解決了屬性均等重要的問題,又降低了計算量,大大縮短了算法的運行時間。

2 基本蟻群算法的原理

蟻群系統(tǒng)是最早建立的蟻群算法模型,其模型的建立來源于對螞蟻尋找食物行為的研究。在自然界中,只要仔細觀察就可以發(fā)現(xiàn),螞蟻總能找到一條從蟻巢到食物源的最短路徑。盡管單只螞蟻的能力和智力非常簡單,但蟻群卻表現(xiàn)出極其復雜的行為特征,在許多情況下能完成遠遠超過螞蟻個體能力的復雜任務。蟻群的這種能力來源于螞蟻群體中的個體協(xié)作行為,通過研究發(fā)現(xiàn),螞蟻個體之間是通過一種稱之為信息素(pheromone)的揮發(fā)性的化學物質(zhì)進行信息傳遞,從而能相互協(xié)作,完成復雜的任務。蟻群表現(xiàn)出復雜有序的行為,個體之間的信息交流與相互協(xié)作起著重要的作用。覓食的螞蟻尋找食物時,當碰到一個還沒有走過的路口時,就隨機地挑選一條路徑前行,在其走過的路徑上留下與路徑長度相關的信息素,而且能夠感知這種物質(zhì)的存在及其強度,并以此指導自己的運動方向,螞蟻傾向于信息素濃度高的方向移動。因此,由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象,即某一路徑上走過的螞蟻越多,則后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息交流機制來尋找食物,并最終沿著最短路徑行進。

3 蟻群聚類算法的設計與實現(xiàn)

本文設計的蟻群聚類算法是基于蟻堆原理的,基于蟻堆原理的聚類方法的靈感來源于自然界中螞蟻分類其尸體和幼體的方法。蟻群聚類算法設計的基本思想是將待處理的多維數(shù)據(jù)隨機的分布在一個二維平面上,然后在二維平面上引入一些人工螞蟻,人工螞蟻在二維平面上隨機移動,根據(jù)其在某地點發(fā)現(xiàn)的數(shù)據(jù)對象在局部區(qū)域的相似性而得到的概率決定該螞蟻是否拾起、放下該數(shù)據(jù)對象。經(jīng)過有限次的迭代,平面上的數(shù)據(jù)按其相似性而聚集。

在數(shù)據(jù)分析中,比較典型的情況是待處理數(shù)據(jù)對象是由有限取值的 n維屬性定義的,也就是 Rn空間中的點,此時,d(i,j)表示了這些對象間的距離,這里 d(i,j)的定義采用了歐幾里德距離,即:

假設d(Oi,Oj)為屬性空間中數(shù)據(jù)對象 Oi和 Oj間的距離,t時刻螞蟻在位置 p處,且物體 Oi就在當前位置。與物體 Oi相關的局部密度 f(Oi)定義如下:

f(Oi)是 Oi與相鄰的其它數(shù)據(jù)對象的相似性度量,稱作平均相似度函數(shù)。r是螞蟻的搜索半徑,即螞蟻在平面移動過程中可直接觀察到以當前位置 p為圓心,以 r為半徑的區(qū)域范圍內(nèi)的物體分布情況。α是差異性比例因子,利用它可以決定兩個物體是否可放置在一起。如果 α較大,則不同物體之間的區(qū)分度不明顯,導致形成的簇覆蓋過寬,同簇中物體不一定具備相近屬性。反之,如果 α過小,則會導致物體間差異度量被放大,從而使得原本相似屬性的數(shù)據(jù)不能夠聚合到一簇中。當 f(Oi)接近于 0時,Oi被拾起的概率比較大,反之 f(Oi)接近于 1時,被拾起的概率比較小。這樣就可以對螞蟻拾起或放下物體的概率選擇方式定義如下:

其中 k1,k2都是閾值常量。

算法模型基本流程設計如下:

第 1步 初始化差異性比例因子、拾起和放下概率參數(shù)、最大迭代次數(shù)等算法模型參數(shù);

第 2步 隨機投射數(shù)據(jù)對象到一個二維平面,即隨機賦給每個數(shù)據(jù)對象一對坐標(x,y);

第 3步 初始化螞蟻狀態(tài)為無負載,并將螞蟻隨機投放到二維平面內(nèi)一個被數(shù)據(jù)對象占據(jù)的位置;

第 4步 聚類開始,迭代次數(shù)加一;

第 5步 在螞蟻搜索半徑 r的范圍內(nèi),利用公式(2)計算螞蟻所選數(shù)據(jù)對象的平均相似度;

第 6步 在[0,1]區(qū)間生成一個隨機數(shù) R;

第 7步 如果螞蟻無負載,利用第 5步運算結果計算拾起概率 Ppick,并跳到第 9步;

第 8步 如果螞蟻有負載,利用第 5步運算結果計算放下概率 Pdrop,并跳到第 10步;

第 9步 比較 Ppick和 R的大小,如果 Ppick＞R,螞蟻拾起對象,并將螞蟻標注有負載,跳到第 11步;否則跳到第 12步;

第 10步 比較 Pdrop和 R的大小,如果 Pdrop＞R,螞蟻放下對象,并將螞蟻標注無負載,跳到第 12步;

第 11步 螞蟻開始負載對象移動,將一個新的未被其他數(shù)據(jù)對象占據(jù)的隨機坐標賦給螞蟻,跳到第 13步;

第 12步 螞蟻開始無負載移動,將一個新的被其他數(shù)據(jù)對象占據(jù)的隨機坐標賦給螞蟻;

第 13步 如果迭代次數(shù)小于在第 1步中設定的最大迭代次數(shù),跳轉(zhuǎn)到第 4步;否則進入第 14步;

第 14步 經(jīng)過有限次迭代和收斂,平面上的數(shù)據(jù)對象按照其相似性而聚集,其中如果某個數(shù)據(jù)對象是孤立的或其鄰域?qū)ο髠€數(shù)小于某一閾值,則標記該對象為孤立點;否則,給該數(shù)據(jù)對象分配一個聚類序列號,并將其鄰域?qū)ο髽擞洖橥恍蛄刑?

第 15步 輸出聚類結果,算法結束。

4 基于信息增益的蟻群聚類算法的實驗

4.1 實驗數(shù)據(jù)處理過程

在本文中所采用的實驗數(shù)據(jù)來自于五六四電臺的 TSW2500型短波發(fā)射機秒數(shù)據(jù)。原始實驗數(shù)據(jù)有 20個模擬量,維數(shù)過多,因此需要對數(shù)據(jù)進行預處理,使后面的處理過程可以有較高質(zhì)量的輸入數(shù)據(jù),最終得到準確的聚類結果。數(shù)據(jù)處理過程如圖1所示。

圖 1 數(shù)據(jù)處理過程

高維數(shù)據(jù)對象的特征空間中含有許多冗余特征甚至噪聲特征,這些特征一方面可能降低聚類的精度,另一方面會大大增加學習及訓練的空間及時間復雜度,所以必須對原始實驗數(shù)據(jù)進行數(shù)據(jù)降維。本文中采用計算屬性的信息增益實現(xiàn)數(shù)據(jù)降維。

4.2 信息增益定義

令 X為隨機變量,則 X的信息熵定義為:

通過觀測隨機變量 Y,隨機變量 X的信息熵變?yōu)?

其中 P(xi)代表隨機變量 X的先驗概率,P(xi|yj)代表觀測到隨機變量 Y后隨機變量 X的后驗概率。引入隨機變量 Y的信息后,隨機變量 X的信息熵 H(X|Y)≤H(X),即引入 Y后,X的不確定程度會變小或保持不變。若 Y與 X不相關,則 H(X|Y)=H(X);若 Y與 X相關,則 H(X|Y)＜H(X),而差值 H(X)-H(X|Y)越大,Y與 X的相關性越強。因此,式(7)定義信息增益 IG(X|Y)為 H(X)與 H(X|Y)的差值,反映了 Y與 X的相關程度,IG(X|Y)越大,則變量 Y與 X的相關性越強。

而且,可以證明,信息增益具有對稱性,即 IG(X|Y)=IG(Y|X)。

表 1 發(fā)射機的示例訓練樣本數(shù)據(jù)表

(續(xù)表)

(續(xù)上右側)

(續(xù)表)

4.3 基于信息增益的數(shù)據(jù)降維

表 1是發(fā)射機的示例訓練樣本數(shù)據(jù)表。首先,從表 1中選擇“狀態(tài)”屬性作為標識屬性,然后計算各屬性的信息增益。根據(jù)“狀態(tài)”屬性的取值,將該訓練樣本數(shù)據(jù)表中的元組分為 2類,分別是狀態(tài)“正?！焙蜖顟B(tài)“故障”。狀態(tài)“正?！鳖惡蜖顟B(tài)“故障”類各包含 10個元組。

為了計算每一個屬性的信息增益,首先計算“狀態(tài)”屬性的信息熵。

通過觀測“反射功率”屬性,“狀態(tài)”屬性的信息熵變?yōu)?

因此“反射功率”屬性的信息增益是:

同理:“入射功率”的信息增益等于 0.7583;“寬放電流”的信息增益等于 0.5735;“寬放電壓”的信息增益等于 0.0847;“高前陰流”的信息增益等于0.4552;“高前偏壓”的信息增益等于 0.8623;“高前簾柵壓”的信息增益等于 0.5049;“高前屏壓”的信息增益等于 0.5573;“高前燈絲電流”的信息增益等于 0.3029;“高末屏流”的信息增益等于 0.7613;“高末偏壓”的信息增益等于 0.4295;“高末簾柵壓”的信息增益等于 0.9000;“高末屏壓”的信息增益等于 0.8000;“高末燈絲電流”的信息增益等于0.5374;“高末柵流”的信息增益等于 0.2868;“高末簾柵流”的信息增益等于 0.6623;“冷凝器入水溫度”的信息增益等于 0.5623;“冷凝器出水溫度”的信息增益等于 0.2552;“實測頻率”的信息增益等于0.6623;“駐波比”的信息增益等于 0.5000。

選擇信息增益最大的 5個屬性作為聚類的屬性,即屬性“入射功率”、“高前偏壓”、“高末屏流”、“高末簾柵壓”和“高末屏壓”。

4.4 實驗結果

在處理器是 Intel(R)Core(TM)Duo CPU T2350,主頻是 1.86GHZ,內(nèi)存是 2G的 PC機上,對2700條實驗數(shù)據(jù)進行分析測試,參數(shù)設置如下:螞蟻個數(shù) =3;差異性比例因子 α=1;搜索半徑 r=4;分類半徑 R=3;最大迭代次數(shù) =300000;拾起概率因子 k1=0.45;放下概率因子 k2=0.20。蟻群聚類算法運行效果如下所示:

算法總共耗時2433秒,將 2700個數(shù)據(jù)聚合成 7類,具體信息如下:第一類數(shù)據(jù)總數(shù) 240個;第二類數(shù)據(jù)總數(shù) 1364個;第三類數(shù)據(jù)總數(shù) 809個;第四類數(shù)據(jù)總數(shù) 258個;第五類數(shù)據(jù)總數(shù) 3個;第六類數(shù)據(jù)總數(shù) 3個;第七類數(shù)據(jù)總數(shù) 2個;孤立的數(shù)據(jù)總數(shù)21個。由于第五類、第六類和第七類數(shù)據(jù)數(shù)目過少,將其歸為孤立的數(shù)據(jù)對象,所以數(shù)據(jù)集中分布在前四類中,分析結果也可以從圖 4中直觀地獲得。前四類中的數(shù)據(jù)是發(fā)射機正常工作時的數(shù)據(jù),而后三類數(shù)據(jù)和孤立的數(shù)據(jù)很可能就是故障數(shù)據(jù),應給予重點關注。實驗結果證明該蟻群聚類算法已經(jīng)具備對大量數(shù)據(jù)進行聚類分析的能力。

5 結束語

本文首先論述了基本蟻群算法的原理,然后設計與實現(xiàn)了基于蟻堆原理的蟻群聚類算法,最后通過計算信息增益對發(fā)射機數(shù)據(jù)進行了數(shù)據(jù)降維,并對降維后的數(shù)據(jù)進行了聚類分析。通過計算屬性的信息增益實現(xiàn)數(shù)據(jù)降維,選擇較重要的屬性進行聚類分析,提高了蟻群聚類算法的抗干擾能力,使聚類結果更加準確;另外降低了算法的執(zhí)行時間,提高了時間效率。

[1] 段海濱.蟻群算法原理及其應用[M].北京:科學出版社,2006.1-117.

[2] 張建華,江賀,張憲超 .蟻群聚類算法綜述[J].計算機工程與應用,2006,42(16):171-174.

[3] 任江濤,孫婧昊,黃煥宇,印鑒 .一種基于信息增益及遺傳算法的特征選擇算法[J].計算機科學,2006,33(10):52-56.

[4] 曹三省,孟靜,杜懷昌,王陽 .蟻群聚類算法在 IPTV用戶群偏好分析中的應用[J].中國傳媒大學學報(自然科學版),2009,16(1):33-37.

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

[6] Colorni A,Dorigo M,Maniezzo V,etal.Distributed optimization by ant colonies[A].Proceeddings of the 1st European Conferences on Artificial Life[C].1991.134-142.

[7] CAO Sanxing,QIN Ying,LIU Jianbo,LU Rui.An ACO-based User Community Preference Clustering System for Customized Content Service in Broadband New Media Platforms[A].In Proc 2008 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology[C].Sydney:2008.591-595.