基于集合枚舉樹的最小屬性約簡算法

成都信息工程學院 軟件工程學院，成都 610225

JIANG Yu

成都信息工程學院 軟件工程學院，成都 610225

College of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China

粗糙集理論是由波蘭學者Pawlak于1982年提出的[1-2]，是一種刻劃具有不完整性和不確定性信息的全新數(shù)學工具。其主要思想是在保證知識庫的分類能力不變的前提下，通過知識約簡導出問題的決策或分類規(guī)則。知識約簡問題是粗糙集理論的一個核心問題[3-4]。所謂知識約簡，就是在保證知識庫分類能力不變的條件下刪除其中不相關(guān)或不重要的冗余知識。

一般來講，一個決策表的屬性約簡不是唯一的，通常人們往往希望能夠找到一個冗余度最小的屬性約簡，該屬性約簡被稱為最小屬性約簡。對任一給定決策表，若屬性約簡算法能確保找到其最小屬性約簡，則該算法稱為最小屬性約簡完備算法。然而，S.K.M Wong和W.Ziarko已經(jīng)證明了找一個決策表的最小約簡是NP-hard問題[3]。導致NP-hard問題的主要原因是屬性的組合爆炸問題。目前已存在一些屬性約簡算法能夠找到?jīng)Q策表的最小屬性約簡[4-12]，但它們要么不是完備的最小屬性約簡算法，要么通過窮舉求出問題的所有約簡或所有最小約簡。

本文重新定義了屬性重要度，給出了條件屬性集上的序關(guān)系，基于該序關(guān)系構(gòu)建集合枚舉樹，提出了一種基于集合枚舉樹的最小屬性約簡算法。該算法采用至頂向下、層優(yōu)先搜索策略遍歷集合枚舉樹從而找到最小屬性約簡。為了減少搜索空間，提高算法效率，該算法采用了兩種剪枝策略剪去集合枚舉樹中冗余節(jié)點。一種剪枝方法是父集剪枝，如果一個集合的父集不是屬性約簡，則該集合一定也不是屬性約簡，該策略是通過提前停止集合枚舉樹的構(gòu)造而對樹剪枝。另一種剪枝方法是屬性核剪枝，因為所有的屬性約簡都包含核屬性，從而可以剪去集合枚舉樹中不含核屬性的節(jié)點。最后，優(yōu)化計算確保同一集合的正域只求解一次。

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

對于決策表 S=(U，C，D，V，f)，U 是論域，C是條件屬性的集合，D是決策屬性集合，V是屬性值的集合，f:U× (C∪D)→V是信息函數(shù)，U、C、D和V都是非空有限集且C ∩ D=。表1為某一決策表，且C={a，b，c，d}，D={e}。

圖1 集合{c，a，b，d}所對應的集合枚舉樹

表1 某一決策表

定義1 在決策表 S=(U，C，D，V，f)中，?R?C，決策屬性 D的 R正域 POSR(D)定義為 POSR(D)=∪{Y∈U/R: Y∈U/D}。

定義2 設(shè) S=(U，C，D，V，f)是一個決策表，P∈C，如果 POSC-{a}(D)=POSC(D)，則稱a是C中不必要的（多余的）屬性;否則，稱a是C中必要的屬性。

定義3設(shè)S=(U，C，D，V，f)是一個決策表，條件屬性集C中所有必要的屬性組成的集合，稱為屬性集C的核，記作Core(C)。

定義4 設(shè) S=(U，C，D，V，f)是一個決策表，B?C是一個屬性子集，如果滿足

則稱B是C的一個約簡。

2 屬性集上的序關(guān)系

屬性重要度標示了屬性在決策表中的重要性，粗糙集傳統(tǒng)的屬性重要度定義只區(qū)分屬性對正域變換的影響，而沒有考慮屬性對于知識粒大小的影響，因此，結(jié)合這兩方面考慮重新定義了屬性重要度。

定義5 設(shè) S=(U，C，D，V，f)是一個決策表，B?C是一個屬性子集，屬性集B的重要度為：

定理1 ?a∈C，如果Sig({a})＞1,那么a∈Core(C)。

證明根 據(jù) 定 義5可 知 ，Sig({a})=(|POSC(D)|-由于0＜|U/{a}|/||U ≤1,那么|POSC(D)|-|POSC-{a}(D)|＞0,也即是說 POSC(D)≠POSC-{a}(D)。所以，屬性a是必要屬性。

定義 6 設(shè) S=(U，C，D，V，f)是一個決策表，n=|C|?；趯傩灾匾榷x條件屬性集C上的序關(guān)系“?”，從而可獲得條件屬性集C上的一個序列：a1?a2?…?an，表示為Ordered(C)={a1，a2，…，an}， 則有 Sig({a1})≥ Sig({a2})≥… ≥Sig({an})。

3 集合枚舉樹

用圖1所示的集合枚舉樹[15]來描述條件屬性子集，通過枚舉出所有的條件屬性組合，使得求解最小屬性約簡的過程變成集合枚舉樹的搜索過程。圖1表示了表1條件屬性的集合枚舉樹，C={a，b，c，d}。樹的每個節(jié)點由兩部分組成，第一部分稱為首（head），記做h(node)，由枚舉樹中當前節(jié)點的枚舉屬性集組成；第二部分稱為尾（tail），記做t(node)，由當前節(jié)點的子節(jié)點的所有屬性除去當前節(jié)點后所包含的屬性排序而成。當前節(jié)點n的子節(jié)點nc生成方法為：h(nc)=h(n)∪{i}，i∈ t(n);t(nc)={j|j∈t(n)，i? j}。例如：對于節(jié)點 ＜{c}，{a，b，d}＞而言，有三個子節(jié)點 ＜{c，a}，{b，d}＞，＜{c，b}，j5i0abt0b＞ 和 ＜{c，d}，? ＞ 。

4 最小屬性約簡算法

為了找到?jīng)Q策表最小屬性約簡，采用簡單的至上而下、層次優(yōu)先搜索算法搜索集合枚舉樹，其搜索空間近似為條件屬性冪集。為了減少搜索空間，提高算法效率，必須采用一定的剪枝策略。

4.1 屬性核剪枝

因為所有的決策表屬性約簡必須包含屬性核，所以可以剪去集合枚舉樹中不包含屬性核的節(jié)點，如圖1中的節(jié)點 ＜{a}，{b，d}＞等，因為它沒有包含屬性核{c}。根據(jù)屬性核剪枝方法，可使集合枚舉樹的初始root節(jié)點為＜Core(C)，C-Core(C)＞，從而圖1所示集合枚舉樹可剪枝為圖2所示的集合枚舉樹。

圖2 圖1剪去不含核屬性{c}后的集合枚舉樹

4.2 父集剪枝

眾所周知，若集合B(B?C)不是決策表的屬性約簡，則其任意子集都不是決策表屬性約簡。在集合枚舉樹中，若非葉子節(jié)點的h(node)∪t(node)不是決策表的一個屬性約簡，則可從集合枚舉樹中剪去以＜h(node)，t(node)＞為根節(jié)點的子樹。

4.3 優(yōu)化計算

根據(jù)集合枚舉樹的定義可知，非葉子節(jié)點和其最左邊子樹根節(jié)點的h∪t（節(jié)點首并節(jié)點尾）是相同集合，如＜{c，a}，{b，d}＞ 和其最左邊子樹根節(jié)點 ＜{c，a，b}，j5i0abt0b＞，那么在父剪枝策略中，存在對同一個集合多次計算其正域是否等于POSC(D)。優(yōu)化計算就是確保同一集合的正域只計算一次，從而提供算法效率。

5 算法描述及其偽代碼

算法描述：函數(shù) getSubNodes（Candidate Group g，Set of Candidate Group G）的功能是，若g是一葉子節(jié)點且其首h(g)的正域等于 POSC(D)，則節(jié)點g的首h(g)是決策表一最小約簡；否則返回節(jié)點g的所有子節(jié)點。

6 實驗結(jié)果

表2展現(xiàn)了核剪枝和父集剪枝減少算法搜索空間，同時也展示了優(yōu)化計算提高算法的求解效率。該實驗是基于Microsoft Visual C++6.0開發(fā)平臺，操作系統(tǒng)Windows XP，CPU：Pentium III 1.73 MHz，內(nèi)存768 MB仿真實現(xiàn)。

7 結(jié)束語

表2 基于UCI數(shù)據(jù)庫仿真結(jié)果

本文提出了一種基于集合枚舉樹的最小屬性約簡完備算法，該算法把屬性約簡的計算問題轉(zhuǎn)化為對集合枚舉樹的搜索式問題，以直觀形象的方法展現(xiàn)了屬性約簡的過程，為屬性約簡問題的求解提供了一條新的途徑。該算法提出了核和父集剪枝策略有效地減少了算法搜索空間；同時，基于優(yōu)化計算提高了算法的運行效率。

[1]Pawlak Z.Rough sets[J].InternationalJournalofComputer and Information Science，1982，11（5）：341-356.

[2]SlowinskiR.Intelligentdecision support——handbook of applications and advances of the rough sets thorey[M].London：Kluwer Academic Publishers，1992.

[3]Wong S K M，Ziarko W.On optional decision rules in decision tables[J].Bulletin of Polish Academy of Sciences，1985，33（11/12）：693-696.

[4]Jelonek J.Rough set reduction of attributes and their domains forneuralnetworks[J].ComputationalIntelligence，1995，11（2）：339-347.

[5]Wang Jue，Miao Duoqian.Analysison attributereduction strategiesofrough set[J].JofComputSci& Technol，1998，13（2）：189-193.

[6]苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法[J].計算機研究與發(fā)展，1999，36（6）：681-684.

[7]楊明，倪魏偉，孫志揮.一種新穎的最小屬性約簡模型[J].東南大學學報：自然科學版，2004，34（5）：604-608.

[8]劉文軍，王加銀，馮艷賓，等.一種求粗糙集中最小屬性約簡的新算法[J].北京師范大學學報：自然科學版，2004，40（1）：8-12.

[9]廖建坤，葉東毅.基于免疫粒子群優(yōu)化的最小屬性約簡算法[J].計算機應用，2007，27（3）：550-552.

[10]Krysziewicz M，Lasek P.Fast discovery of minimal sets of attributes functionally determining a decision attribute[C]// InternationalConference on Rough Sets and Intelligent Systems Paradigms，2007：320-331.

[11]蔣瑜，王燮，葉振.基于差別矩陣的Rough集屬性約簡算法[J].系統(tǒng)仿真學報，2008，20（14）：3717-3720.

[12]Song Xiaoyu，Chang Chunguang，Liu Feng.Rough set theory based reduction algorithm fordecision table[C]//Proceedingsofthe 2009 InternationalConference on Machine Learning and Cybernetics，2009：2318-2323.

[13]Pawlak Z.Rough set-theoretical aspects of reasoning about data[M].Boston：Kluwer Academic Publishers，1991.

[14]張文修，吳偉志，梁吉業(yè)，等.粗糙集理論與方法[M].北京：科學出版社，2001.

[15]Rymon R.Search through systematic set enumeration[C]// Proc of 3rd Int’l Conf on Principles of Knowledge Representation and Reasoning，1992：539-550.

基于集合枚舉樹的最小屬性約簡算法

蔣 瑜

The purpose of this paper is to present an effective approach to achieve minimal attribute reduction.To achieve this goal,in this paper,it introduces a set-enumeration search tree by using total sequence over condition attribute set,and proposes a minimal attribute reduction algorithm,which uses the top-down level-first traversal to search set-enumeration search tree and guarantee that reduction discovered by it is a minimal reduction.To realize performance gains,this algorithm uses core and superset pruning to reduce search space,and uses optimal computing to guarantee that positive region of the same set only computes one time for reducing computing time.The experimental results with UCI data show that the proposed algorithm is effective.

rough set;minimal reduction;set enumeration search tree;attribute significance;pruning

為了尋找一種有效的最小屬性約簡方法，給出了條件屬性集上的屬性重要度序關(guān)系，基于此序關(guān)系構(gòu)建了屬性集上的集合枚舉樹，提出了一種快速的最小屬性約簡算法，該算法采用至上而下、層次優(yōu)先策略搜索集合枚舉樹尋找屬性最小約簡。為了提高算法性能，該算法采用核和父集剪枝策略減少搜索空間，采用優(yōu)化計算來確保同一集合的正域只計算一次?；赨CI數(shù)據(jù)的實驗結(jié)果表明，該算法是有效的。

粗糙集；最小約簡；集合枚舉樹；屬性重要度；剪枝

A

TP311

10.3778/j.issn.1002-8331.1111-0416

JIANG Yu.Minimal attribute reduction for rough set based on set enumeration search tree.Computer Engineering and Applications,2013,49（11）：101-104.

蔣瑜（1980—），男，講師，主要研究方向為粗糙集理論與數(shù)據(jù)挖掘。E-mail：jiangyu@cuit.edu.cn

2011-11-23

2012-01-10

1002-8331（2013）11-0101-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1719.034.html