基于互信息的并行約簡＊

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

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

0 引言

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

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

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

1 基礎知識

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

1．1 動態約簡

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

1．2 代數意義下的并行約簡

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

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

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

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

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

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

2 基于互信息的并行約簡

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

2．1 概念與性質

定義3 給定一個決策系統DS=(U，C∪D)，P(DS)表示DS的所有子系統的集合，F是P(DS)非空子集合，稱B?C為DS的信息論意義下的F并行約簡當且僅當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中所有子表的互信息不變的最小條件屬性集合，其結果可能不止一個．從定義3可以看出，信息論并行約簡的概念是基于互信息定義的，因此也可以稱為基于互信息的并行約簡(Parallel Reducts Based on Mutual Information，簡稱PRBMI)．當條件屬性的集合B發生變化時，正域之外的元素的互信息也會相應變化，這樣只要保證約簡前后決策表的互信息保持不變，就可以避免因為沒有考慮正域之外的元素包含的信息而造成過約簡問題．

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

性質1 在一致性決策系統中，代數并行約簡和信息論并行約簡是等價的;在不一致系統中，代數并行約簡是信息論并行約簡的子集．

為證明性質1，先要引用文獻［7］中的引理1．

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

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

性質1的證明 給定一個不一致決策系統DS=(U，C∪D)，設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代數并行約簡，P是 DS信息論并行約簡，由此可知在不一致決策系統中，代數并行約簡是信息論并行約簡的子集．一致性系統中粗糙集代數觀點和信息觀點的一致性在文獻［7］中已經證明，這里不再贅述．

2．2 屬性重要度矩陣

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

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

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

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

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

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

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

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

證明 設M(C，D，F)中某一不為 0元素 σij對應的屬性為 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)矩陣中任意大于0的元素對應的屬性是其子表在信息論意義下的核屬性．命題1證畢．

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

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

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

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

輸入:F?P(DS)．

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

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

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

第3 步:計算 M'(C，D，F)．

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

第5步 輸出約簡B．

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

3 實驗

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

表1 代數并行約簡與信息論并行約簡的比較

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

4 結語

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

［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集理論代數與信息論觀點的關系研究［J］．世界科技研究與發展，2002，24(5):20-26．