粗糙集屬性約簡方法研究

趙昶宇

（天津津航計算技術研究所，天津 300308）

粗糙集屬性約簡方法研究

趙昶宇

（天津津航計算技術研究所，天津 300308）

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

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

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

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

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

1 利用遺傳算法得到條件屬性的優化解

1.1 信息系統與決策表

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

1.2 屬性約簡和值約簡

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

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

1.3 遺傳約簡算法

1.3.1 染色體編碼

采用長度為N的二進制串來表示一個個體，即被選中的條件屬性表示為“l”，不被選中的條件屬性表示為“0”.

1.3.2 確定初始種群

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

1.3.3 建立適應度函數

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

1.3.4 判斷是否滿足終止條件

算法終止條件是，當連續繁殖很多代的最優條件屬性的適應值沒有變化時，算法停止，否則轉步驟1.3.5.

1.3.5 選擇算子

由于操作簡單，傳統的遺傳算法大多采用“輪盤賭”選擇算子。但是，這個方法一方面容易導致局部最優而無法進化；另一方面，無法體現個體優劣，導致搜索精度不夠。

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

1.3.6 交叉算子

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

1.3.7 變異算子

采用基本位變異算子，其具體執行過程是：對于條件屬性的每一個基因（二進制的0或者1），根據變異概率指定其為變異點。對于每一個指定的變異點，條件屬性核對應的基因位不發生變異，其他則對其基因值做取反運算，從而產生出一個新的條件屬性集合。

1.3.8 復制算子

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

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

因為蟻群算法在初始時刻比較缺乏信息素，導致尋優速度不理想。因此，先使用上述遺傳算法生成初始信息素，提高初期求解的運行速度。

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

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

3 結束語

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

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

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

［1］閆德勤，王楊.基于關聯矩陣的屬性約簡算法［J］.計算機工程與應用，2005，41（20）：181-182.

［2］劉少輝，盛秋戩，吳斌，等.Rough集高效算法的研究［J］.計算機學報，2003，26（05）：524-529.

［3］周獻中，黃兵.基于粗糙集的不完備信息系統屬性約簡［J］.南京理工大學學報，2003，27（5）：630-635.

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

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

TP18

A

10.15913/j.cnki.kjycx.2017.20.013

2095－6835（2017）20－0013－03

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

〔編輯：白潔〕