趙昶宇

（天津津航計(jì)算技術(shù)研究所，天津 300308）

粗糙集屬性約簡方法研究

趙昶宇

（天津津航計(jì)算技術(shù)研究所，天津 300308）

為了提高屬性約簡的準(zhǔn)確率和工作效率，使其能夠處理不相容和不確定關(guān)系的信息系統(tǒng)，提出了一種粗糙集屬性約簡方法。首先，將屬性的重要性度量作為啟發(fā)式信息；然后，引入遺傳算法快速找到條件屬性集合中適應(yīng)值最好的個(gè)體作為遺傳的優(yōu)化解集合；最后，使用遺傳算法生成初始信息素，利用蟻群算法的局部尋優(yōu)和正反饋機(jī)制得到粗糙集屬性約簡的最優(yōu)解。

屬性約簡；粗糙集；遺傳算法；蟻群算法

在實(shí)際應(yīng)用中，對粗糙集屬性約簡的研究有非常重要的意義——化簡冗余屬性，保留最佳決策，大大提高數(shù)據(jù)的處理效率。利用粗糙集理論和約簡方法可以實(shí)現(xiàn)知識獲取、機(jī)器學(xué)習(xí)、圖像處理、決策制訂、模型建立等應(yīng)用。高效的約簡方法是將粗糙集理論應(yīng)用于數(shù)據(jù)挖掘與知識發(fā)現(xiàn)領(lǐng)域的基礎(chǔ)。Wong S.K.M.和Ziarko在1985年已經(jīng)證明了一個(gè)信息系統(tǒng)或決策表的最小約簡是一個(gè)NP-hard問題，這是由數(shù)據(jù)組合爆炸引起的，不存在統(tǒng)一、規(guī)范的高效方法。對于大型數(shù)據(jù)庫，最小約簡事實(shí)上并不存在，得到的只是近似約簡。為了研究更有效的約簡方法，有效地獲取較優(yōu)的屬性約簡，并降低實(shí)現(xiàn)的時(shí)間復(fù)雜度，尋求快速的約簡方法是目前粗糙集理論的主要研究課題之一。

目前，最常見的粗糙集屬性約簡方法有以下幾種：①基于區(qū)分矩陣的屬性約簡算法。該算法直觀，易于理解，但是，在處理大量數(shù)據(jù)集合時(shí)，算法的時(shí)間復(fù)雜度和空間復(fù)雜度成指數(shù)增長，約簡速度非常慢。②基于屬性依賴度的約簡算法。該算法在對大量數(shù)據(jù)集合進(jìn)行約簡時(shí)，效率比較高，但是，該算法只得到了條件屬性的核，并沒有得到屬性的一個(gè)約簡，且不適合不相容系統(tǒng)的約簡。③基于屬性重要度的約簡算法。該算法與基于屬性依賴度的約簡算法相比，能夠更好地處理屬性滿足確定性關(guān)系，且有強(qiáng)烈因果關(guān)系的屬性集。但是，該算法并不能保證一定能夠找到信息系統(tǒng)的最優(yōu)解。④基于遺傳算法的屬性約簡算法。遺傳約簡算法大大提高了決策表約簡結(jié)果的準(zhǔn)確性和算法的高效性，但是，該算法不能夠處理不相容和不確定關(guān)系的信息系統(tǒng)。

為了改善粗糙集屬性約簡方法的不足之處，提高屬性約簡的準(zhǔn)確性和效率，處理不相容和不確定關(guān)系的信息系統(tǒng)，本文提出了一種粗糙集屬性約簡的方法。

1 利用遺傳算法得到條件屬性的優(yōu)化解

1.1 信息系統(tǒng)與決策表

信息系統(tǒng)是粗糙集理論中的研究對象，即I＝（U，A，V，f）.其中，U為論域，即所有研究對象的集合；A為研究對象屬性的集合；V為研究對象屬性值的集合，V＝∪a∈AVa，Va是屬性a∈A的值域；f為信息函數(shù)，f：U×A→V為單一映射，即f（x，a）∈Va，它指定U中每一對象的屬性值。對于信息系統(tǒng)I＝（U，A，V，f），如果研究對象屬性集合A由條件屬性C和決策屬性D組成，即A＝C∪D，C∩D＝Ф，則此時(shí)信息系統(tǒng)I稱為決策表。

1.2 屬性約簡和值約簡

令R為一等價(jià)關(guān)系族，且r∈R，當(dāng)ind（R）＝ind（R－{r}），稱r為R中可省略的；否則，r為R中不可省略的。當(dāng)任意一個(gè)r∈R，如果r不可省略，則稱族R為獨(dú)立的。顯然，當(dāng)R為獨(dú)立的，且PR，則P也是獨(dú)立的。P中所有不可省略關(guān)系的集合被稱為P的核，記作core（P）。

值約簡是對決策表的一種簡化，決策表中一條實(shí)例可以看作一條規(guī)則，其中可能包含冗余屬性值，因此，對實(shí)例屬性值的約簡就是對決策規(guī)則的約簡。決策規(guī)則的約簡是分別消去每個(gè)規(guī)則的不必要條件，它不是整體上的約簡屬性，而是針對每個(gè)決策規(guī)則，去掉表達(dá)該規(guī)則時(shí)的冗余屬性值，以便進(jìn)一步使規(guī)則最小化。

1.3 遺傳約簡算法

1.3.1 染色體編碼

采用長度為N的二進(jìn)制串來表示一個(gè)個(gè)體，即被選中的條件屬性表示為“l(fā)”，不被選中的條件屬性表示為“0”.

1.3.2 確定初始種群

種群的初始化是遺傳算法的關(guān)鍵，用傳統(tǒng)的遺傳算法確定初始種群時(shí)，多半采取隨機(jī)生成法形成染色體方案，以致于迭代開始就可能形成許多不可行的方案，要進(jìn)行大量的計(jì)算后才能得到優(yōu)化的方案，這在很大程度上降低了算法的運(yùn)算效率。本文改進(jìn)傳統(tǒng)遺傳算法，改進(jìn)后能夠降低隨機(jī)產(chǎn)生的種群初始值的盲目性，提高算法的效率。改進(jìn)后的初始種群的產(chǎn)生方式是：利用屬性核本身的特征，即屬性核是所有屬性約簡的交集，限制初始種群。由于每一種屬性的約簡都包括了屬性核，因此，在每個(gè)染色體中，將屬性核所在的位置上的基因強(qiáng)制取值為“1”.

1.3.3 建立適應(yīng)度函數(shù)

由屬性約簡的定義可知，個(gè)體的適應(yīng)度主要取決于2個(gè)方面，即所含條件屬性的個(gè)數(shù)（應(yīng)該盡量少）和區(qū)分能力（應(yīng)盡量強(qiáng)）。因此，定義適應(yīng)度函數(shù)為：F（v）＝|C|-Lv.其中，|C|為條件屬性集中屬性的個(gè)數(shù)；Lv是個(gè)體中所包含的條件屬性的個(gè)數(shù)。

1.3.4 判斷是否滿足終止條件

算法終止條件是，當(dāng)連續(xù)繁殖很多代的最優(yōu)條件屬性的適應(yīng)值沒有變化時(shí)，算法停止，否則轉(zhuǎn)步驟1.3.5.

1.3.5 選擇算子

由于操作簡單，傳統(tǒng)的遺傳算法大多采用“輪盤賭”選擇算子。但是，這個(gè)方法一方面容易導(dǎo)致局部最優(yōu)而無法進(jìn)化；另一方面，無法體現(xiàn)個(gè)體優(yōu)劣，導(dǎo)致搜索精度不夠。

本文對傳統(tǒng)遺傳算法的“選擇算子”進(jìn)行改進(jìn)，改進(jìn)后的選擇方式可確保適應(yīng)度比平均適應(yīng)度大的一些個(gè)體一定能夠被遺傳到下一代群體中，所以，該方法的選擇誤差比較小。具體操作如下：①設(shè)條件屬性集合的長度為N，每個(gè)屬性的適應(yīng)度為Fi（i＝1，2，…，N），計(jì)算條件屬性集合中每個(gè)屬性在下一代條件屬性集合中的期望生存數(shù)目，即②用Ni的整數(shù)部分確定各個(gè)對應(yīng)條件屬性在下一代條件屬性集合中的生存數(shù)目。其中大于Ni的最大整數(shù)，這樣可以確定下一代條件屬性集合中為各個(gè)條件屬性新的適應(yīng)度，用“輪盤賭”選擇算子，隨機(jī)確定下一代條件屬性集合中還未確定的個(gè)條件屬性。

1.3.6 交叉算子

常用的交叉方式有一點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和一致交叉等。本文對遺傳算法進(jìn)行改進(jìn)，采用多點(diǎn)位單基因交叉的方式，用父代最優(yōu)解Tmax與子代染色體池進(jìn)行交叉操作。該方法能夠避免算法過早地喪失進(jìn)化能力，具體步驟如下：①在染色體池T中選擇進(jìn)行交叉操作的條件屬性集合Ti和屬性約簡的最優(yōu)解Tmax；②隨機(jī)生成交叉片段和交叉區(qū)域；③將Ti的交叉區(qū)域加到Tmax前面，將Tmax的交叉區(qū)域加到Ti前面；④刪除與交叉區(qū)域相同的條件屬性，得到2個(gè)新的條件屬性集合。

1.3.7 變異算子

采用基本位變異算子，其具體執(zhí)行過程是：對于條件屬性的每一個(gè)基因（二進(jìn)制的0或者1），根據(jù)變異概率指定其為變異點(diǎn)。對于每一個(gè)指定的變異點(diǎn)，條件屬性核對應(yīng)的基因位不發(fā)生變異，其他則對其基因值做取反運(yùn)算，從而產(chǎn)生出一個(gè)新的條件屬性集合。

1.3.8 復(fù)制算子

在得到新一代條件屬性集合之后，如果其中最壞的屬性集合（適應(yīng)值最?。┑倪m應(yīng)值小于上一代最好的屬性集合（適應(yīng)值最大）的適應(yīng)值，則用上一代最好的屬性集合代替新一代最壞的屬性集合。該方法確保算法收斂。

2 利用蟻群算法得到粗糙集屬性約簡的最優(yōu)解

因?yàn)橄伻核惴ㄔ诔跏紩r(shí)刻比較缺乏信息素，導(dǎo)致尋優(yōu)速度不理想。因此，先使用上述遺傳算法生成初始信息素，提高初期求解的運(yùn)行速度。

遺傳算法的求解結(jié)果向蟻群算法信息素的轉(zhuǎn)化過程是：選取遺傳算法終止時(shí)條件屬性集合中適應(yīng)值最好的10%的個(gè)體作為遺傳的優(yōu)化解集合，以從剩余可選條件屬性中選擇屬性i的概率作為蟻群算法初始信息素的一部分。初始所有屬性之間的信息素的濃度τ初始為：

式（1）中：x為優(yōu)化解集合中屬性j選擇屬性i的總次數(shù)；y為優(yōu)化解集合中解的個(gè)數(shù)；ηi為屬性i對屬性j的重要性。改進(jìn)的蟻群算法描述如下：①將m個(gè)螞蟻分別置于n個(gè)屬性節(jié)點(diǎn)上，利用遺傳算法得到初始所有屬性之間的信息素，并設(shè)定最大迭代次數(shù)。②如果有螞蟻成功地將屬性i添加到屬性集合中，則為屬性節(jié)點(diǎn)間的信息素濃度賦予增量Δτi＝Ce×K；否則，如果屬性i未被添加到屬性集合中，則為屬性節(jié)點(diǎn)間的信息素濃度賦予增量Δτi＝Cp×K.其中，K為選擇屬性所用的時(shí)間開銷；Ce和Cp為相應(yīng)的獎(jiǎng)懲因子。③更新所有屬性節(jié)點(diǎn)之間的信息素τi（t），即τi（t）＝τi（t）＋Δτi，其中，i＝1，2，…，n.④在屬性約簡中，下一個(gè)屬性的選擇只能由已經(jīng)選擇的屬性來決定。設(shè)Rk為已選屬性的集合，k為迭代次數(shù)，i為已選屬性，j為待選屬性。根據(jù)各個(gè)屬性之間的信息素分布情況，計(jì)算螞蟻在Rk為已選屬性集合的情況下，從剩余可選條件屬性中選擇屬性j的概率P（j|Rk）.基于得到的最大概率值為每只螞蟻分別選取下一個(gè)屬性。⑤根據(jù)所有螞蟻選取的屬性，計(jì)算對應(yīng)的目標(biāo)函數(shù)F（v），輸出F（v）的最大值及其所對應(yīng)的屬性集合，即最小約簡。⑥如果達(dá)到最大的迭代次數(shù)，或者迭代出現(xiàn)退化現(xiàn)象，則當(dāng)前得到的最優(yōu)解即為所得的屬性集合的最小約簡；否則，清空所有螞蟻的蟻集，跳轉(zhuǎn)到步驟②。從剩余可選條件屬性中選擇屬性j的概率P（j|Rk）的公式是：式（2）中：集合U為第k次迭代后剩余可選條件屬性；τij為屬性節(jié)點(diǎn)i到屬性節(jié)點(diǎn)j的路徑信息素濃度值；ηij為屬性j對屬性i的重要性；α為2個(gè)屬性節(jié)點(diǎn)（i，j）之間的信息素濃度值的權(quán)重；β為屬性j對屬性i的重要性的權(quán)重。

3 結(jié)束語

為了提高屬性約簡的準(zhǔn)確性和效率，且能夠處理不相容和不確定關(guān)系的信息系統(tǒng)，本文提出了一種粗糙集屬性約簡的方法。

該方法將屬性的重要性度量作為啟發(fā)式信息，引入遺傳算法快速找到條件屬性集合中適應(yīng)值最好的個(gè)體作為遺傳的優(yōu)化解集合，然后使用遺傳算法生成初始信息素，利用蟻群算法的局部尋優(yōu)和正反饋機(jī)制得到粗糙集屬性約簡的最優(yōu)解。

本文提出的屬性約簡的方法在加強(qiáng)局部搜索能力的同時(shí)，保持了全局尋優(yōu)的特性，既保證了所求約簡含有比較少的屬性，又保證了分類質(zhì)量，能夠獲得最佳的搜索效果。另外，該方法縮短了屬性約簡的計(jì)算時(shí)間，并提高了決策表屬性約簡結(jié)果的準(zhǔn)確性。

［1］閆德勤，王楊.基于關(guān)聯(lián)矩陣的屬性約簡算法［J］.計(jì)算機(jī)工程與應(yīng)用，2005，41（20）：181-182.

［2］劉少輝，盛秋戩，吳斌，等.Rough集高效算法的研究［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（05）：524-529.

［3］周獻(xiàn)中，黃兵.基于粗糙集的不完備信息系統(tǒng)屬性約簡［J］.南京理工大學(xué)學(xué)報(bào)，2003，27（5）：630-635.

［4］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1999：146-254.

［5］梁云川，李德玉.基于子集類蟻群模型的屬性相對約簡算法［J］.計(jì)算機(jī)科學(xué)，2008，35（11）：147-150.

TP18

A

10.15913/j.cnki.kjycx.2017.20.013

2095－6835（2017）20－0013－03

趙昶宇（1982—），男，陜西漢中人，工學(xué)碩士，高級工程師，主要從事嵌入式系統(tǒng)軟件測試方面的研究。

〔編輯：白潔〕