閆電勛， 鄧大勇， 金皓蘋， 陳 林

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

0 引言

為了在動(dòng)態(tài)變化或增長(zhǎng)的數(shù)據(jù)中求得一個(gè)穩(wěn)定的約簡(jiǎn)結(jié)果，Bazan［1-2］提出了動(dòng)態(tài)約簡(jiǎn)的概念．該理論的主體思想是先把要處理的決策表劃分成若干個(gè)具有強(qiáng)烈概率因素的子表，然后求出全部子表的所有約簡(jiǎn)并取其交集．通常認(rèn)為利用這種方式求得的約簡(jiǎn)結(jié)果較為穩(wěn)定．然而，動(dòng)態(tài)約簡(jiǎn)有2個(gè)缺點(diǎn):一是必須求出全部子決策表的所有約簡(jiǎn)，時(shí)間復(fù)雜度很高;二是動(dòng)態(tài)約簡(jiǎn)得到的結(jié)果有可能為空，理論本身不完備．

鄧大勇在文獻(xiàn)［3-6］中借鑒動(dòng)態(tài)約簡(jiǎn)的分表思想提出了并行約簡(jiǎn)理論．并行約簡(jiǎn)和動(dòng)態(tài)約簡(jiǎn)類似，都是將一個(gè)決策表拓展成若干個(gè)子表，然后在這些子表上求約簡(jiǎn)．和動(dòng)態(tài)約簡(jiǎn)相比，并行約簡(jiǎn)算法有2個(gè)優(yōu)點(diǎn):一是在計(jì)算過程中可以利用啟發(fā)式信息判斷條件屬性的優(yōu)劣，不需要計(jì)算子表的全部約簡(jiǎn)，所以并行約簡(jiǎn)算法的時(shí)間復(fù)雜度是多項(xiàng)式級(jí)的;二是并行約簡(jiǎn)是一個(gè)完備的理論，它在定義層面就已經(jīng)避免了約簡(jiǎn)結(jié)果為空這種情況的出現(xiàn)．

鄧大勇［5］提出的并行約簡(jiǎn)概念和相應(yīng)算法都是基于代數(shù)論知識(shí)的，因此可以稱為代數(shù)意義下的并行約簡(jiǎn)(簡(jiǎn)稱代數(shù)并行約簡(jiǎn))．本文將提出信息論意義下的并行約簡(jiǎn)(簡(jiǎn)稱信息論并行約簡(jiǎn))概念及其相應(yīng)的算法，信息論并行約簡(jiǎn)算法和代數(shù)論并行約簡(jiǎn)算法具有相同的時(shí)間復(fù)雜度，但在處理不一致數(shù)據(jù)時(shí)，信息論并行約簡(jiǎn)可以保留比代數(shù)并行約簡(jiǎn)更多的信息．

1 基礎(chǔ)知識(shí)

本文假設(shè)讀者熟悉粗糙集基本知識(shí)，因此對(duì)一些簡(jiǎn)單概念不再詳細(xì)說明，只介紹與本文密切相關(guān)的知識(shí)．

1．1 動(dòng)態(tài)約簡(jiǎn)

從定義1可以看出，如果想要求出動(dòng)態(tài)約簡(jiǎn)，就必須首先求出F中全部子表的所有約簡(jiǎn)，這已經(jīng)被證明是一個(gè)NP完全問題，其時(shí)間復(fù)雜度隨著條件屬性個(gè)數(shù)的增加呈指數(shù)級(jí)增長(zhǎng)．而且動(dòng)態(tài)約簡(jiǎn)得到的最終結(jié)果有可能是個(gè)空集，雖然Bazan等在文獻(xiàn)［2］中試圖解決動(dòng)態(tài)約簡(jiǎn)的空集問題，但是如何決定參數(shù)ε又成了一個(gè)新的問題．

1．2 代數(shù)意義下的并行約簡(jiǎn)

為了在保證約簡(jiǎn)結(jié)果穩(wěn)定性基礎(chǔ)上解決動(dòng)態(tài)約簡(jiǎn)NP難題和約簡(jiǎn)為空的問題，鄧大勇［5］提出了代數(shù)并行約簡(jiǎn)的概念及其相應(yīng)算法．代數(shù)并行約簡(jiǎn)同動(dòng)態(tài)約簡(jiǎn)類似，也是把一個(gè)決策系統(tǒng)拓展成若干個(gè)子決策表，不同的是，代數(shù)并行約簡(jiǎn)并不需要求出全部子表的所有約簡(jiǎn)，而是只要找到一個(gè)能保證所有子表正域不變的約簡(jiǎn)即可［5］．

定義2［5］給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示 DS的所有子系統(tǒng)的集合，對(duì)F?P(DS)且F≠?，稱B?C為DS的代數(shù)觀點(diǎn)下的F并行約簡(jiǎn)當(dāng)且僅當(dāng)B滿足如下2個(gè)條件:

1)對(duì)任意子表 DT∈F，POSB(DT，D)=POSC(DT，D);

2)對(duì)任意S?B，至少存在一個(gè)子表DT∈F，使得POSS(DT，D)≠POSC(DT，D)．

代數(shù)并行約簡(jiǎn)是保持F中所有子表的正域不變的最小條件屬性集合，其結(jié)果可能不止一個(gè)．因?yàn)椴恍枰蟪鋈孔颖淼乃屑s簡(jiǎn)，代數(shù)并行約簡(jiǎn)省略了許多不必要的嘗試性計(jì)算，因此其算法時(shí)間復(fù)雜度是多項(xiàng)式級(jí)的，而且因?yàn)闆]有求交運(yùn)算，代數(shù)并行約簡(jiǎn)避免了約簡(jiǎn)結(jié)果為空的情況．

從定義2可以看出，代數(shù)并行約簡(jiǎn)是基于正域不變定義的，在一致決策表中正域涵蓋了論域中所有的元素，但是在不一致決策表中論域中部分元素是在正域之外的，而在計(jì)算代數(shù)并行約簡(jiǎn)的過程中，正域之外的元素的分類信息是不被考慮的．若決策表的不一致性是由于記錄錯(cuò)誤或計(jì)算誤差而產(chǎn)生的，則不考慮正域之外的元素是合理的;但若決策表的不一致性是由于認(rèn)知不全導(dǎo)致的屬性過少而引起的，這么做就有可能造成過約簡(jiǎn)的問題．

2 基于互信息的并行約簡(jiǎn)

為了避免并行約簡(jiǎn)在處理不一致數(shù)據(jù)時(shí)可能產(chǎn)生的過約簡(jiǎn)問題，本文提出了信息論意義下的并行約簡(jiǎn)的概念．下面首先介紹其概念和性質(zhì)．

2．1 概念與性質(zhì)

定義3 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)是P(DS)非空子集合，稱B?C為DS的信息論意義下的F并行約簡(jiǎn)當(dāng)且僅當(dāng)B滿足如下2個(gè)條件:

1)對(duì)任意子表 DT∈F，I(DT，B;D)=I(DT，C;D);

2)對(duì)任意S?B，至少存在一個(gè)子表DT∈F，使得I(DT，S;D)＜I(DT，B;D)．其中，I(DT，B;D)代表決策表DT中條件屬性集B和決策屬性D的互信息．

信息論并行約簡(jiǎn)是保持F中所有子表的互信息不變的最小條件屬性集合，其結(jié)果可能不止一個(gè)．從定義3可以看出，信息論并行約簡(jiǎn)的概念是基于互信息定義的，因此也可以稱為基于互信息的并行約簡(jiǎn)(Parallel Reducts Based on Mutual Information，簡(jiǎn)稱PRBMI)．當(dāng)條件屬性的集合B發(fā)生變化時(shí)，正域之外的元素的互信息也會(huì)相應(yīng)變化，這樣只要保證約簡(jiǎn)前后決策表的互信息保持不變，就可以避免因?yàn)闆]有考慮正域之外的元素包含的信息而造成過約簡(jiǎn)問題．

定義4 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)是P(DS)非空子集合．給定PRED為F的信息論并行約簡(jiǎn)的集合，F(xiàn)的信息論并行約簡(jiǎn)的核屬性PCORE可以定義為

性質(zhì)1 在一致性決策系統(tǒng)中，代數(shù)并行約簡(jiǎn)和信息論并行約簡(jiǎn)是等價(jià)的;在不一致系統(tǒng)中，代數(shù)并行約簡(jiǎn)是信息論并行約簡(jiǎn)的子集．

為證明性質(zhì)1，先要引用文獻(xiàn)［7］中的引理1．

引理1［7］給定一個(gè)不一致決策系統(tǒng) DS=(U，C∪D)，B?C，若 H(D|B∪{a})=H(D|B)，則POSB∪{a}(D)=POSB(D)，反之則不成立．

引理1說明，一個(gè)在代數(shù)觀點(diǎn)下可以被約簡(jiǎn)的條件屬性(重要性為0)，在信息論意義下不一定是可以被約簡(jiǎn)的(重要性不一定為0);反之，一個(gè)在信息論意義下可以被約簡(jiǎn)的條件屬性(重要性為0)，在代數(shù)觀點(diǎn)下一定是可以被約簡(jiǎn)的(重要性一定為0)．利用代數(shù)并行約簡(jiǎn)對(duì)一個(gè)不一致系統(tǒng)進(jìn)行約簡(jiǎn)時(shí)，因?yàn)闆]有考慮到正域之外的元素的分類信息，就有可能約簡(jiǎn)掉一個(gè)信息論意義下不能被約簡(jiǎn)掉的屬性，從而造成過約簡(jiǎn)．

性質(zhì)1的證明 給定一個(gè)不一致決策系統(tǒng)DS=(U，C∪D)，設(shè)Q?P?C，由引理1可知可能存在這種情況:對(duì)任意 DT∈F，均有 POSC(DT，D)=POSP(DT，D)=POSQ(DT，D)且 I(DT，C;D)=I(DT，P;D)＞I(DT，Q;D);同時(shí)，對(duì)任意 Q'?Q，P'?P，至少存在一個(gè)子表 DT∈F，令 POSQ'(DT，D)≠POSQ(DT，D)，I(DT，P';D)≠I(DT，P;D)．由定義2和定義3可知，Q 是 DS代數(shù)并行約簡(jiǎn)，P是 DS信息論并行約簡(jiǎn)，由此可知在不一致決策系統(tǒng)中，代數(shù)并行約簡(jiǎn)是信息論并行約簡(jiǎn)的子集．一致性系統(tǒng)中粗糙集代數(shù)觀點(diǎn)和信息觀點(diǎn)的一致性在文獻(xiàn)［7］中已經(jīng)證明，這里不再贅述．

2．2 屬性重要度矩陣

文獻(xiàn)［5］中代數(shù)并行約簡(jiǎn)算法的屬性重要度矩陣是基于正域中元素個(gè)數(shù)的變化來定義的．下面筆者采用類似的方法定義信息論意義下基于互信息概念的并行約簡(jiǎn)的屬性重要度矩陣(簡(jiǎn)稱基于互信息的屬性重要度矩陣)．

定義5 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)?P(DS)，B?C，B關(guān)于F的相對(duì)D的屬性重要度矩陣定義為

其中:σij= σ(aj，Ui)=Ii(DTi，B;D)-Ii(DTi，B-{aj};D);Ii(DTi，B;D)代表第 i個(gè)子系統(tǒng) DTi中條件屬性集B和決策屬性D的互信息;aj∈B;(Ui，C∪D)∈F;n代表F中子決策表的個(gè)數(shù);m代表DS中條件屬性的個(gè)數(shù)．

矩陣M(B，D，F(xiàn))中的行反映了B中不同屬性在同一子表中相對(duì)于決策屬性D的分類能力;矩陣中的列反映了同一屬性在不同子表中相對(duì)于決策D的分類能力．

上面的屬性重要度矩陣是一種刪除屬性式重要度矩陣，下面介紹添加屬性式重要度矩陣．

定義6 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)?P(DS)，B?C，B關(guān)于F的相對(duì)D的屬性重要度矩陣定義為

其中:σ'ij= σ'(aj，Ui)=Ii(DTi，B∪{a};D)-Ii(DTi，B;D);aj∈B;(Ui，C∪D)∈F;n 代表 F 中子決策表的個(gè)數(shù);m代表DS中條件屬性的個(gè)數(shù)．若aj∈B，則σ'ij的值為 0．

命題1 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)?P(DS)，M(C，D，F(xiàn))矩陣中任意大于0的元素對(duì)應(yīng)的屬性是其子表在信息論意義下的核屬性．

證明 設(shè)M(C，D，F(xiàn))中某一不為 0元素 σij對(duì)應(yīng)的屬性為 p，則對(duì)子表 i有 Ii(DTi，C;D)-Ii(DTi，C-{p};D)＞0．對(duì)任意 B?C，若 p?B，則必有 Ii(DTi，C;D)＞Ii(DTi，B;D)，由定義3 可知 B 一定不是子表i的約簡(jiǎn)．由此可知，對(duì)子表i的任意約簡(jiǎn)都包含屬性p，即屬性p為子表i的核屬性．綜上所述，M(C，D，F(xiàn))矩陣中任意大于0的元素對(duì)應(yīng)的屬性是其子表在信息論意義下的核屬性．命題1證畢．

命題2 給定一個(gè)決策系統(tǒng)DS=(U，C∪D)，P(DS)表示DS的所有子系統(tǒng)的集合，F(xiàn)?P(DS)．若矩陣M(B，D，F(xiàn))中某一列元素全大于0，則該列對(duì)應(yīng)的屬性為信息論意義下F并行約簡(jiǎn)的核屬性．

命題2可由命題1和定義4簡(jiǎn)單推出，不再贅述．

2．3 基于互信息的并行約簡(jiǎn)算法

接下來介紹基于互信息的并行約簡(jiǎn)算法，該算法的主要思想是先從矩陣M(C，D，F(xiàn))中找到信息論并行約簡(jiǎn)的核，然后依次把矩陣M'(B，D，F(xiàn))中最好的屬性添加到約簡(jiǎn)中并進(jìn)行迭代，直到M'(B，D，F(xiàn))中所有的元素均為0為止．算法的具體步驟如下:

輸入:F?P(DS)．

輸出:F的一個(gè)并行約簡(jiǎn)．

第1步:建立屬性重要度矩陣M(C，D，F(xiàn))．

第2 步:B=∪mj=1{aj:?σkj(σkj∈M(C，D，F(xiàn))∧σkj≠0)}，B 是 F 中所有子表的核屬性．

第3 步:計(jì)算 M'(C，D，F(xiàn))．

第4步:重復(fù)進(jìn)行如下步驟，直到M'(C，D，F(xiàn))中全部元素都為0:

第5步 輸出約簡(jiǎn)B．

接下來評(píng)估一下這個(gè)算法的時(shí)間復(fù)雜度．可以看出，基于互信息的并行約簡(jiǎn)算法(以下簡(jiǎn)稱PRBMI算法)和文獻(xiàn)［5］中的Parallel Reducts Based on Attribute Significance算法(簡(jiǎn)稱PRBS算法)的框架和流程基本相同，只是對(duì)屬性重要性的定義方式不同．在PRBS算法中屬性重要度是利用正域個(gè)數(shù)的變化來定義的，只需要進(jìn)行一次減法運(yùn)算和除法運(yùn)算即可;而在PRBMI算法中屬性重要度是利用互信息的變化來定義的，需要進(jìn)行若干次(具體次數(shù)和劃分出來的等價(jià)類的個(gè)數(shù)有關(guān))除法運(yùn)算和對(duì)數(shù)運(yùn)算．因此從理論上來講，PRBMI算法的時(shí)間復(fù)雜度總是比PRBS算法高．在實(shí)際實(shí)驗(yàn)中，算法的大部分時(shí)間開銷都花在等價(jià)類的劃分上，計(jì)算屬性重要度的時(shí)間開銷其實(shí)非常小，可以略去不估，因此能夠認(rèn)為PRBMI和PRBS的時(shí)間復(fù)雜度是相同的，都是O(nm3|U'||log2|U'||)．其中:n代表決策子表的個(gè)數(shù);m代表?xiàng)l件屬性的個(gè)數(shù);|U'|代表最大決策子表中記錄的個(gè)數(shù)．

3 實(shí)驗(yàn)

本文所有的實(shí)驗(yàn)數(shù)據(jù)均來自UCI數(shù)據(jù)庫，實(shí)驗(yàn)時(shí)從原決策表中隨機(jī)抽取了10個(gè)子表，第1個(gè)子表包含原決策表40%的數(shù)據(jù)，第2個(gè)子表包含原決策表46．7%的數(shù)據(jù)，依次遞增，最后一個(gè)子表包含原決策表100%的數(shù)據(jù)．實(shí)驗(yàn)機(jī)器的硬件配置為:Computer Model:Lenovo Ideapad Y430;CPU:Intel Pentium(R)Dual-Core T4200@2．0 GHz;Memory:2 048 MB RAM;Hard disk:250 G;OS:Windows 7 ultimate SP1．實(shí)驗(yàn)的最終結(jié)果如表1所示．

表1 代數(shù)并行約簡(jiǎn)與信息論并行約簡(jiǎn)的比較

可以看出，PRBS算法和PRBMI算法的時(shí)間開銷基本相同，甚至對(duì)于某些數(shù)據(jù)，PRBMI算法的時(shí)間開銷比PRBS還要小，這是因?yàn)镻RBMI算法在劃分條件和決策都相同的等價(jià)類時(shí)可以利用已經(jīng)劃分出的條件等價(jià)類中的信息，而PRBS算法在劃分決策等價(jià)類時(shí)不能利用這些信息．

4 結(jié)語

本文對(duì)并行約簡(jiǎn)理論進(jìn)行了拓展，將并行約簡(jiǎn)理論由代數(shù)觀點(diǎn)下拓展到了信息論意義下，提出了信息論意義下的并行約簡(jiǎn)——基于互信息的并行約簡(jiǎn);探討了代數(shù)論意義下的并行約簡(jiǎn)和信息論意義下的并行約簡(jiǎn)的一致性和差異性;利用互信息的概念定義了信息論意義下的屬性重要度矩陣，并基于該矩陣構(gòu)造了基于互信息的并行約簡(jiǎn)算法;最終通過實(shí)驗(yàn)驗(yàn)證了信息論意義下的并行約簡(jiǎn)和代數(shù)意義下的并行約簡(jiǎn)具有相同的時(shí)間復(fù)雜度這一論斷．

［1］Bazan J G．A comparison of dynamic non-dynamic rough set methods for extracting laws from decision tables［C］//Polkowski L，Skowron A．Rough sets in knowledge discovery 1:Methodology and applications．Heidelberg:Physica-Verlag，1998:321-365．

［2］Bazan J G，Nguyen H S，Nguyen S H，et al．Rough set algorithms in classification problem［C］//Polkowski L，Tsumoto S，Lin T Y．Rough set methods and applications．Heidelberg:Physica-Verlag，2000:49-88．

［3］Deng Dayong．Parallel reducts and its properties［C］//Proceedings of 2009 IEEE International Conference on Granular Computing．Lushan:IEEE，2009:121-125．

［4］Deng Dayong，Yan Dianxun，Chen Lin．(F，ε)-parallel reducts in a series of decision subsystems［C］//The Third International Joint Conference on Computational Sciences and Optimization(CSO2010)．Huangshan:IEEE，2010:372-376．

［5］Deng Dayong，Yan Dianxun，Wang Jiyi．Parallel reducts based on attribute significance［C］//The 5th International Conference of Rough Set and Knowledge Technology(RSKT 2010)．Beijing:Springer，2010:336-343．

［6］Deng Dayong，Yan Dianxun，Wang Jiyi，et al．Parallel reducts and decision system decomposition［C］//Proceedings of the Fourth International Conference on Computational Sciences and Optimization(CSO 2011)．Kunming:IEEE，2011:799-803．

［7］王國(guó)胤．Rough集理論代數(shù)與信息論觀點(diǎn)的關(guān)系研究［J］．世界科技研究與發(fā)展，2002，24(5):20-26．