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

朱元?jiǎng)P，陳 濤，陳 亮

(1.泰山職業(yè)技術(shù)學(xué)院信息工程系，山東泰安 271000;2.泰山學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東泰安 271021)

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

1 屬性兩兩間的依賴度

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

當(dāng)X只有一個(gè)元素x時(shí)，x在X中重要性(相對于Y)為

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

2 有向圖的構(gòu)造

根據(jù)1中的屬性間的依賴關(guān)系確定有向圖中各結(jié)點(diǎn)間的連接關(guān)系，其中一個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)屬性.構(gòu)造步驟如下:

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

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

(3)選取下一個(gè)結(jié)點(diǎn)j={i|max(sigX(i))∧min(sigi(x))，x∈A'

(未被選過的點(diǎn)或?qū)傩?};

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

其中，b為預(yù)先設(shè)定的量大入度數(shù);

(5)重復(fù)(3)和(4)，直到所有的結(jié)點(diǎn)都已經(jīng)選取;

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

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

3 有向圖的各結(jié)點(diǎn)的信息量初始值

在以上構(gòu)造的有向圖中選取任意一個(gè)中間結(jié)點(diǎn)Ⅰ，其信息量的初值=n1+n2，

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

其它結(jié)點(diǎn)的信息量初值類似計(jì)算.

4 確定目標(biāo)函數(shù)

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

構(gòu)造目標(biāo)函數(shù)如下:

5 算法描述

(1)設(shè)定螞蟻的總數(shù)為m，循環(huán)次數(shù)為t，各結(jié)點(diǎn)的信息量(激素)濃度由3中的方法確定，△τij=0，全部螞蟻放入結(jié)點(diǎn)S，pathk={螞蟻k經(jīng)過的結(jié)點(diǎn)}.

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

(3)計(jì)算螞蟻k從當(dāng)前結(jié)點(diǎn)i轉(zhuǎn)移到下一結(jié)點(diǎn)j，概率如公式計(jì)算，如果概率相同時(shí)選擇一個(gè)信息量最大的結(jié)點(diǎn).

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

(4)把j存入pathk，如果所有屬性全部選取或已經(jīng)達(dá)到結(jié)點(diǎn)e，轉(zhuǎn)下一步;否則轉(zhuǎn)(3).

(5)計(jì)算目標(biāo)函數(shù)，如果較前次的好，則記錄下來.

(7)如果所有螞蟻路徑已經(jīng)相同，則輸出路徑后結(jié)束;否則轉(zhuǎn)(2).

6 實(shí)例應(yīng)用

在信息系統(tǒng)中屬性算法的研究中，選取典型的一組數(shù)據(jù)組成IS信息系統(tǒng)(如表1)，分別應(yīng)用經(jīng)典的屬性約簡算法、基于蟻群算法的屬性約簡算法，實(shí)驗(yàn)過程結(jié)果如下:

表1 信息系統(tǒng)IS

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

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

7 實(shí)驗(yàn)分析

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

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

表2 三種算法的實(shí)驗(yàn)對比表

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

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

圖1是三種算法針對Eil51經(jīng)過50次測試取得約簡核的平均收斂速度曲線.從圖1易知，基于蟻群算法的屬性約簡算法收斂速度就明顯優(yōu)于另兩種算法.這是因?yàn)楸疚乃惴傔x擇較好的候選集進(jìn)行計(jì)算，使算法從開始階段的收斂速度就有明顯的提高，以致間接減少了后繼的處理計(jì)算量，較大提高了算法的收斂速度.

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

8 結(jié)束語

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

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

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

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

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

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