基于蟻群算法的屬性約簡方法

朱元凱，陳 濤，陳 亮

(1.泰山職業技術學院信息工程系，山東泰安 271000;2.泰山學院數學與系統科學學院，山東泰安 271021)

粗糙集理論是分析不完整、不精確甚至是不一致信息系統的有力工具.知識約簡是粗糙集理論研究中的核心問題，現在已經證明了粗糙集尋找最小屬性集是一個NP難問題，這是由屬性組合爆炸問題造成的.近年來，由意大利學者Dorie M等提出來的蟻群系統(Ant System)與蟻群算法(Ant Colony Algorithm)，是一種通用的啟發式算法，主要模擬自然界螞蟻覓食，通過在路徑上信息素的傳遞，最終發現一條最短路徑的過程.它的主要特征是采用正反饋機制、具有較強的魯棒性和適于并行處理.本文結合粗糙集相對核的概念和蟻群算法提出了一種新的屬性約簡方法，既能充分利用蟻群算法的并行優化處理能力，也能解決初期信息素匱乏造成的速度慢的問題.

1 屬性兩兩間的依賴度

屬性的重要性的定義及形式為:令??X?U，??Y?U，U/Y≠δ={U}，給定x∈X在X中的重要性為

當X只有一個元素x時，x在X中重要性(相對于Y)為

由于|SX(Y)|/|U|就是Y關于X的支持度，記為sptx(Y).可得結論:sptx(Y)越高，X相對于Y也就越重要，X也就越有可能屬于核.

2 有向圖的構造

根據1中的屬性間的依賴關系確定有向圖中各結點間的連接關系，其中一個結點對應一個屬性.構造步驟如下:

(1)選取第一個結點j={i|max(sigX(i))且min(sigi(x))，x∈A(所有的屬性)};

(2)作兩條有向邊＜j，i1＞和＜j，i2＞，i1和i2={i|min(sigX(i))，x∈A(所有的屬性)};

(3)選取下一個結點j={i|max(sigX(i))∧min(sigi(x))，x∈A'

(未被選過的點或屬性)};

(4)作兩條有向邊＜j，i1＞，＜j，i2＞，i1，i2={i|min(sigX(i))∧x的入度≤b，x∈A(未被選過的點)}.

其中，b為預先設定的量大入度數;

(5)重復(3)和(4)，直到所有的結點都已經選取;

(6)做起始結點s，選取入度小于2(或相對其它所有屬性依賴度較低的)結點k，作有向邊＜s，k＞，如此作兩條邊;

(7)做終點e，選取出度小于2(或其它所有屬性與之相對依賴度較低的)結點作k，作有向邊＜k，e＞，如此作兩條邊.

3 有向圖的各結點的信息量初始值

在以上構造的有向圖中選取任意一個中間結點Ⅰ，其信息量的初值=n1+n2，

其中: n1=|{j|sigx(I)＞a，a為預先設定的最小依賴度}|，n2=|{j|sigI(x)＜b，b為預先設定的最大依賴度}|，

其它結點的信息量初值類似計算.

4 確定目標函數

根據最小約簡的要求，約簡的性能主要取決于兩個方面:所含條件屬性的個數和決策屬性對其依賴度.對某一屬性子集，其含屬性個數越少，決策屬性對其依賴度越大，則最有可能成為最小約簡［2］.

構造目標函數如下:

5 算法描述

(1)設定螞蟻的總數為m，循環次數為t，各結點的信息量(激素)濃度由3中的方法確定，△τij=0，全部螞蟻放入結點S，pathk={螞蟻k經過的結點}.

(2)取新螞蟻k，path=?.

(3)計算螞蟻k從當前結點i轉移到下一結點j，概率如公式計算，如果概率相同時選擇一個信息量最大的結點.

其中:ηij=1/dij為路徑＜i，j＞的可見度:α和β分別表征信息素的跡和路線可見度的相對重要程度，α，β≥0，經過實驗α、β在區間［1，5］［5］取值效果較好.

(4)把j存入pathk，如果所有屬性全部選取或已經達到結點e，轉下一步;否則轉(3).

(5)計算目標函數，如果較前次的好，則記錄下來.

(7)如果所有螞蟻路徑已經相同，則輸出路徑后結束;否則轉(2).

6 實例應用

在信息系統中屬性算法的研究中，選取典型的一組數據組成IS信息系統(如表1)，分別應用經典的屬性約簡算法、基于蟻群算法的屬性約簡算法，實驗過程結果如下:

表1 信息系統IS

對表1采用屬性約簡的定義算法計算方法處理，得到表1的核Core(IS)={b}和一個約簡RED= {a，b}.實驗2使用基于蟻群算法的屬性約簡算法計算信息系統的核和約簡集.實驗3增加屬性，再使用基于蟻群算法的屬性約簡算法計算信息系統的核和約簡集.

實例分析:(1)實驗1與實驗2的結果約簡核和約簡集一致，經過對新增屬性的信息系統采用以上兩種算法計算(即實驗3)，約簡核和約簡集仍一致.(2)實驗2所用時間實驗有明顯提高，實驗3所用時間(即增加屬性后)比實驗2增加不明顯.

7 實驗分析

為了測試基于蟻群算法的屬性約簡算法的性能，選擇典型的測試函數對基于蟻群算法的屬性約簡算法、屬性基本定義算法和基于遺傳算法屬性約簡算法的進行測試.

三種算法參數設置相同:屬性共200個，表共20個，每表記錄數平均為1萬條.各測試函數變量維數為50，三種算法中的局部迭代次數為100，全局迭代次數為5000.當精度達到0.0001時，算法將停止迭代。測試結果如表2:

表2 三種算法的實驗對比表

由表2可知，三種算法能得到屬性的約簡核，即都是有效的.由表2可知，基于蟻群算法的屬性約簡算法在求解速度都明顯優于其他幾種算法，在性能上有一定改善，即實驗結果證明本文的算法在求解屬性約簡集時效率較高.當增加2倍屬性規模，再進行實驗。從表1的數據易知，隨著屬性規模擴大，其它兩種算法的時耗增長迅速，搜索全局最優成功率有所下降，而本文算法的時耗較低，說明其具有較高可行性.

圖1 三種算法針對Eil51的平均收斂速度曲線

圖1是三種算法針對Eil51經過50次測試取得約簡核的平均收斂速度曲線.從圖1易知，基于蟻群算法的屬性約簡算法收斂速度就明顯優于另兩種算法.這是因為本文算法總選擇較好的候選集進行計算，使算法從開始階段的收斂速度就有明顯的提高，以致間接減少了后繼的處理計算量，較大提高了算法的收斂速度.

由上分析可知，基于蟻群算法的屬性約簡算法計算屬性約簡核和約簡集是有效的、可行的，并且具有較高效率，收斂速度優于其它相關算法.

8 結束語

由上面的論述可知，粗糙集屬性約簡的算法在求最小屬性約簡理論上和實際應用中都是可行的，具有推廣應用價值.本文受蟻群的啟發，通過將條件屬性集映射到一有向圖，提出了用蟻群算法求解該問題，并通過實驗驗證了該算法的有效性.但對于該算法還存在需要研究和加以改進的地方，如有向圖的初始權值的確定和計算等問題.

［1］張修文，吳偉志，等.粗糙集理論與方法［M］.北京:高等教育出版社，2003.

［2］陶志，等.基于遺傳算法的粗糙集知識約簡方法［J］.系統工程，2003，(2):34－36.

［3］賈修一，于紹越，等.基于Rough集和蟻群算法的屬性約簡方法［J］.軟件學報，2006，(12):142－144.

［4］欒矗琛，盛建倫.基于粒子群算法的混洗蛙跳算法［J］.計算機與現代化，2009，(11):39－42.

［5］王俊峰，陸偉峰，朱慶保.知識約簡的多族蟻群算法［J］.金陵科技學院學報，2005，(3):67－69.