基于相對核的屬性約簡

王健，徐余法，陳國初

（1.華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海200237；2.上海電機學(xué)院 信息學(xué)院，上海200240）

1982年，波蘭數(shù)學(xué)家Pawlak提出了粗糙集［1］，這是一種定量分析處理不一致、不完整、不精確的信息與知識的數(shù)學(xué)工具和一種重要的信息處理技術(shù)［2-5］.粗糙集的理論是建立在分類機制的基礎(chǔ)上，將知識理解為對數(shù)據(jù)的劃分.粗糙集理論與其他處理不確定和不精確問題理論［6-7］的最顯著的區(qū)別是，它無需提供問題所需處理的數(shù)據(jù)集合之外的任何先驗信息，所以對問題的不確定性的描述或處理可以說是比較客觀的［8-9］.因此，被廣泛應(yīng)用到人工智能、模式識別和數(shù)據(jù)挖掘等方面.粗糙集理論研究課題中一個重要的內(nèi)容就是屬性約簡.一般說來，知識庫中的屬性的重要度并不是相等的，有些屬性可以刪除，從而有利于做出正確而簡潔的決策.屬性約簡可以在保持分類和決策能力不變的情況下，去除那些不相關(guān)或不重要的屬性.Wong等［10］從計算復(fù)雜性的角度證明了尋找最小約簡是NP-hard問題，通常采用啟發(fā)式的搜索算法［11-17］.本文從相對核的角度，提出了一種新的屬性約簡方法.

1 粗糙相關(guān)概念

粗糙集的關(guān)鍵點就是將知識和分類聯(lián)系起來，用等價類關(guān)系的形式表示分類［18］.

定義1 決策表 .一個決策表可以形式化定義為S＝〈U，C∪D，V，f〉.其中：有限集合U＝｛u1，u2，…，un｝為論域；C∪D是屬性有限集，C為條件屬性集，D為決策屬性集，且C∩D＝?；V為屬性集C∪D的值域；f∶U×C∪D→V為一個信息函數(shù)，表示任一個對象的屬性在V上的取值，指定了U中每一對象x的屬性值.

定義2 不可分辨關(guān)系.信息系統(tǒng)S＝〈U，C∪D，V，f〉，對于屬性子集B?A，定義一個不可分辨的二元關(guān)系.即IND（B）＝｛（x，y）∈U×U∶?a∈B，f（x，a）＝f（y，a）｝.IND（B）是一個等價關(guān)系.由這種等價關(guān)系導(dǎo)出的對U的劃分記為U／IND（B），其中包含x的等價類記為［x］IND（B）.

定義3 近似集合 .粗糙集有兩個基本概念，即上近似集和下近似集，給定X?U，R?A.

1）下近似集，即R-X＝∪｛［x］R?X｝，［x］R＝｛y｜y∈U，?a∈R，f（x，a）＝f（y，a）｝.R-X是由U上在現(xiàn)有知識R的劃分下肯定屬于X的元素組成的集合.

2）上近似集，即R-X＝∪｛［x］R∩X≠?｝.R-X是在知識R劃分下可能屬于X的元素組成集合.

定義5 相對核 .設(shè)屬性a∈C，如果POSC-a（D）＝POSC（D），那么稱屬性a相對決策屬性D是不可缺少的，所有不可缺少的屬性構(gòu)成了相對決策屬性D的相對核.

2 屬性約簡算法

2.1 算法描述

對于一個信息系統(tǒng)，S＝〈U，C∪D，V，f〉，求出條件屬性相對決策屬性的相對核，并用這些相對核屬性對論域U進行劃分 .劃分后，將可以正確辨識的部分去掉，并從條件屬性中去除這些核屬性，這樣就形成新的決策信息系統(tǒng) .然后，不斷地迭代，直到論域U完全劃分，即U＝?.假如某一次迭代的過程中不存在相對核屬性，則根據(jù)屬性重要度，選擇對劃分重要度最大的屬性，并用該屬性對當前的論域進行劃分.當U＝?時，求取每步相對核或重要度最大的屬性的并集，假設(shè)集合為P＝｛a1，a2，…，am｝，計算POSP（D）和POSP-ai（D）（i＝1，2，…，m），去除冗余信息，得到約簡集.

非核屬性的屬性重要性的判斷.文中假如某一步不存在相對核屬性，那么要從剩余的屬性中選取屬性重要度大的屬性，來對當前的論域進行劃分.設(shè)屬性a為條件屬性，那么定義屬性a的重要度為

Siga越大，則該屬性的重要度越大.

2.2 算法部分

輸入：決策信息系統(tǒng)S＝〈U，C∪D，V，f〉，A＝C∩D，C為條件屬性，D為決策屬性.輸出：決策信息系統(tǒng)的約簡 .初始化：集合P＝?.算法有如下6個主要步驟：

步驟1 求出決策信息系統(tǒng)的相對核CORED（C），記Q＝CORED（C），若CORED（C）＝?，則轉(zhuǎn)步驟4；

步驟2 用相對核對論域U進行劃分，若能將論域U完全劃分則轉(zhuǎn)步驟5；否則，會有不可辨識的部分，記為U1，U1＝U-POSQ（D），P＝P∪CORED（C），U＝U1；

步驟3 令C＝C-CORED（C），然后轉(zhuǎn)步驟1；

步驟4 利用式（1）計算剩余屬性的重要度，并排序.選取重要度最大的屬性，假設(shè)為a，P＝P∪a；然后用屬性a對當前的論域進行劃分，若能完全劃分，則轉(zhuǎn)步驟5；否則，記不可分別的部分為U2，U2＝U-POSa（D），U＝U2，C＝C-｛a｝，轉(zhuǎn)步驟1；

步驟5 對P中的每個元素，記為a，計算POSP（D）和POSP-｛a｝（D），若相等則從集合P中去除元素a，消除屬性集P中的冗余信息；

步驟6 算法結(jié)束，輸出約簡后的屬性集P.

3 實例分析

表1為天氣決策表［18］.表1中：a1，a2，a3，a4為條件屬性，分別代表天氣、溫度、濕度、風(fēng)；d是決策屬性；論域U＝｛x1，x2，…，x14｝.此外，表1中括號中數(shù)字為對應(yīng)的天氣決策表的數(shù)字表示，如a1＝｛晴，多云，雨｝＝｛1，2，3｝；a2＝｛熱，溫暖，冷｝＝｛1，2，3｝，a3＝｛高，正常｝＝｛0，1｝；a4＝｛否，真｝＝｛0，1｝，d＝｛N，P｝＝｛0，1｝.

對此決策表運用文中的方法.

表1 天氣決策表Tab.1 Weather decision table

考察ai（i＝1，2，3，4），在C中相對于D來說是否必要.為此，從C中去掉a1可得：POSC-｛a1｝（D）≠POSC（D），所以a1必要 .同理可得a2，a3不必要，a4必要，那么可得P1＝CORED（C）＝｛a1，a4｝，U／P＝｛｛1，8，9｝，｛2，11｝，｛3，13｝，｛3，5，10｝，｛6，14｝，｛7，12｝，不可分辨的集合為｛｛1，8，9｝，｛2，11｝｝.那么新的決策表為C＝｛a2，a3｝，U＝｛1，2，8，9，11｝，如表2所示 .

考察ai（i＝2，3），在C中相對于D來說是否必要.同理可得a2為不必要的，a3為必要的，那么可得P2＝CORED（C）＝｛a3｝，U／P2＝｛｛1，2，8｝，｛9，11｝｝，分辨完全.即可得P＝P1∪P2＝｛a1，a3，a4｝.則有

表2 新的決策表Tab.2 New decision table

由此可得POSP（D）≠POSP-｛a1｝，POSP（D）≠POSP-｛a3｝，POSP（D）≠POSP-｛a4｝.所以，約簡集合為｛a1，a3，a4｝.采用 UCI數(shù)據(jù)庫進行測試，結(jié)果如表3所示.

表3 試驗結(jié)果Tab.3 Test results

4 結(jié)束語

粗糙集理論目前已日趨完善，被廣泛用在許多領(lǐng)域上 .所提出的約簡算法利用相對核對論域進行劃分，從而求得屬性約簡，降低了時間和空間上的復(fù)雜度 .經(jīng)測試，該方法能夠得到合理的結(jié)果，為數(shù)據(jù)決策表的屬性約簡提供一條較為可行有效的途徑.

［1］ 王國胤，姚一豫，于洪.粗糙集理論與應(yīng)用研究綜述［J］.計算機學(xué)，2009，32（7）：1229-1246.

［2］ PAWLAK Z.Rough set［J］.International Journal of Computer and Information Sciences，1982，11（5）：341-356.

［3］ CHAN C C，GRZYMALA-BUSSE J W，ZIARKO W P.Rough sets and current trends in computing［C］∥Proceedings of the 6th International Conference on RSCTC.Akron：［s.n.］，2008.

［4］ AN A，STEFANOWSKI J，RAMANNA S，et al.Rough sets，fuzzy sets，data mining and granular computing［C］∥Proceedings of the 11th International Conference on RSFDGrC.Toronto：［s.n.］，2007.

［5］ WANG G Y，LI T R，GRZYMALA-BUSSE J W，et al.Rough sets and knowledge technology［C］∥Third International Conference on Rough Sets and Knowledge Technology.Chengdu：［s.n.］，2008.

［6］ 曾小軍，黃宜堅.利用AR模型和支持向量機的調(diào)速閥故障識別［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2011，32（1）：13-17.

［7］ 陳葉旺，于金山.一種改進的樸素貝葉斯文本分類方法［J］.華僑大學(xué)學(xué)報：自然科學(xué)版，2011，32（4）：401-404.

［8］ PAWLAK Z，GRZYMALA-BUSSE J，SLOWINSKI R，et al.Rough sets［J］.Communications of the ACM，1995，38（11）：89-95.

［9］ PAWLAK Z.Why rough sets［C］∥Proceedings of the Fifth IEEE International Conference on Fuzzy Systems.New Orleans：IEEE Press，1996：738-743.

［10］ WONG S K M，ZIARKO W.On optional decision rules in decision tables［J］.Bulletin of Polish Academy of Science，1985，33（11／12）：693-696.

［11］ HU Xiao-hua，GERCONE N.Learning in relational databases：A rough set approach［J］.International Journal of Computational Intelligence，1995，11（2）：323-338.

［12］ 葉東毅.Jelonek屬性約簡算法的一個改進［J］.電子學(xué)報，2000，28（12）：81-82.

［13］ 劉少輝，盛秋戩，史忠植.一種新的快速計算正區(qū)域的方法［J］.計算機研究與發(fā)展，2003，40（5）：637-642.

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

［15］ 胡峰，王國胤 .二維表快速排序的復(fù)雜度分析［J］.計算機學(xué)報，2007，30（6）：963-968.

［16］ 徐章艷，劉作鵬，楊炳儒，等.一個復(fù)雜度為 max（O（｜C｜｜U｜），O（｜C｜～2｜U／C｜））的快速屬性約簡算法［J］.計算機學(xué)報，2006，29（3）：391-399.

［17］ 王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計算機學(xué)報，2002，25（7）：759-766.

［18］ 瞿彬彬，盧炎生.基于粗糙集的屬性約簡算法研究［J］.華中科技大學(xué)學(xué)報：自然科學(xué)版，2005，33（8）：30-33.