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

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

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

1 引言

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

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

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

2 基本蟻群算法的原理

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

3 蟻群聚類算法的設計與實現

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

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

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

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

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

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

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

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

第 3步 初始化螞蟻狀態為無負載,并將螞蟻隨機投放到二維平面內一個被數據對象占據的位置;

第 4步 聚類開始,迭代次數加一;

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

第 6步 在[0,1]區間生成一個隨機數 R;

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

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

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

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

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

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

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

第 14步 經過有限次迭代和收斂,平面上的數據對象按照其相似性而聚集,其中如果某個數據對象是孤立的或其鄰域對象個數小于某一閾值,則標記該對象為孤立點;否則,給該數據對象分配一個聚類序列號,并將其鄰域對象標記為同一序列號;

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

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

4.1 實驗數據處理過程

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

圖 1 數據處理過程

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

4.2 信息增益定義

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

通過觀測隨機變量 Y,隨機變量 X的信息熵變為:

其中 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 發射機的示例訓練樣本數據表

(續表)

(續上右側)

(續表)

4.3 基于信息增益的數據降維

表 1是發射機的示例訓練樣本數據表。首先,從表 1中選擇“狀態”屬性作為標識屬性,然后計算各屬性的信息增益。根據“狀態”屬性的取值,將該訓練樣本數據表中的元組分為 2類,分別是狀態“正常”和狀態“故障”。狀態“正常”類和狀態“故障”類各包含 10個元組。

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

通過觀測“反射功率”屬性,“狀態”屬性的信息熵變為:

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

同理:“入射功率”的信息增益等于 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,內存是 2G的 PC機上,對2700條實驗數據進行分析測試,參數設置如下:螞蟻個數 =3;差異性比例因子 α=1;搜索半徑 r=4;分類半徑 R=3;最大迭代次數 =300000;拾起概率因子 k1=0.45;放下概率因子 k2=0.20。蟻群聚類算法運行效果如下所示:

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

5 結束語

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

[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.