基于互信息的并行約簡＊

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

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

0 引言

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

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

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

1 基礎(chǔ)知識

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

1．1 動態(tài)約簡

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

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

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

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

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

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

代數(shù)并行約簡是保持F中所有子表的正域不變的最小條件屬性集合，其結(jié)果可能不止一個．因為不需要求出全部子表的所有約簡，代數(shù)并行約簡省略了許多不必要的嘗試性計算，因此其算法時間復(fù)雜度是多項式級的，而且因為沒有求交運算，代數(shù)并行約簡避免了約簡結(jié)果為空的情況．

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

2 基于互信息的并行約簡

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

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

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

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

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

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

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

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

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

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

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

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

2．2 屬性重要度矩陣

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

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

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

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

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

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

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

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

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

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

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

2．3 基于互信息的并行約簡算法

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

輸入:F?P(DS)．

輸出:F的一個并行約簡．

第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 步:計算 M'(C，D，F(xiàn))．

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

第5步 輸出約簡B．

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

3 實驗

本文所有的實驗數(shù)據(jù)均來自UCI數(shù)據(jù)庫，實驗時從原決策表中隨機(jī)抽取了10個子表，第1個子表包含原決策表40%的數(shù)據(jù)，第2個子表包含原決策表46．7%的數(shù)據(jù)，依次遞增，最后一個子表包含原決策表100%的數(shù)據(jù)．實驗機(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．實驗的最終結(jié)果如表1所示．

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

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

4 結(jié)語

本文對并行約簡理論進(jìn)行了拓展，將并行約簡理論由代數(shù)觀點下拓展到了信息論意義下，提出了信息論意義下的并行約簡——基于互信息的并行約簡;探討了代數(shù)論意義下的并行約簡和信息論意義下的并行約簡的一致性和差異性;利用互信息的概念定義了信息論意義下的屬性重要度矩陣，并基于該矩陣構(gòu)造了基于互信息的并行約簡算法;最終通過實驗驗證了信息論意義下的并行約簡和代數(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］王國胤．Rough集理論代數(shù)與信息論觀點的關(guān)系研究［J］．世界科技研究與發(fā)展，2002，24(5):20-26．