基于改進差別矩陣的增量式屬性約簡算法

馮少榮，張東站

廈門大學信息科學與技術學院，福建廈門361005

知識約簡是粗糙集理論［1］的核心內容之一.在粗糙集理論中，知識約簡分為屬性約簡和屬性值約簡.隨著數據庫系統中數據的不斷增加，屬性約簡相對屬性值約簡更加有效.它大大簡化了數據庫結構的復雜度，提高了人們對隱含在數據庫龐大數據量下的各種信息的認識程度.因此，屬性約簡成為目前粗糙集的研究熱點之一［2-5］.決策表的屬性約簡通常是不唯一的，人們希望能找到具有最少屬性的最佳約簡.然而，找到最佳約簡是一個NP-hard問題，導致NP-hard的主因是屬性的組合爆炸，解決該問題通常采用啟發式搜索方法，求出最佳或次最佳約簡［6-8］.現有的屬性約簡大體上可分為，基于差別矩陣或基于差別矩陣的改進的屬性約簡算法、基于正區域的屬性約簡算法及啟發式的屬性約簡算法，其共同特點是:①利用屬性的重要性作為啟發式信息，但并不完備［9］;②這些算法大都針對靜態的信息系統或決策表，不適合信息系統或決策表動態變化的情況.現有的有關屬性約簡的增量式算法不多，已有的動態增量屬性約簡算法，其時間和空間復雜度都較高.很多屬性約簡是從求屬性核開始的，所以求核是粗糙集理論的關鍵之一，求解屬性核也面臨同樣問題.

本研究圍繞粗糙集中的求屬性核和屬性約簡問題，分析現有的求核算法和屬性約簡算法［10-11］時間和空間復雜度高的原因，基于差別矩陣對稱性，通過改進差別矩陣定義，改進增量式求屬性核算法及高效的屬性約簡完備算法.理論分析和實驗驗證都表明，本研究提出的算法有效可行，可明顯降低時間和空間復雜度.

1 改進的差別矩陣定義及求核算法

1.1 改進的差別矩陣定義

按照文獻 ［11］差別矩陣定義，U1為論域，xi和xj是論域U1中的元素，mij和mji是差別矩陣M中的元素項，在計算差別矩陣時，當xi∈U1，xj∈U1時，mij=mji，文獻 ［11］ 同時計算了mij及mji.由于差別矩陣是對稱的，因此只需計算mij就能正確求核.當較大時，可顯著降低計算量，特別是當決策表一致時，減少的不必要計算量是求核實際所需計算量的1/2.

故當xi∈U1，xj∈U1時，通過限定i＞j，只計算mij，而不需計算與其對稱且相等的mji.因此，本研究對給定信息系統 (information system，IS)，將文獻 ［11］的差別矩陣M={mij}重新定義為

1.2 改進的求核算法

針對動態增加的情況，文獻［11］中算法2(optimization for incremental updating algorithm of a core，OIUAC)的時間復雜度為時間復雜度較低.該算法的空間復雜度為 O，由于該算法在計算核時使用了差別矩陣，導致空間復雜度較高，特別當決策一致時，U1=U，U'2=0，U為論域，空間復雜度為，不能有效處理大數據集.為此，本研究通過改進文獻［11］中的算法2，由于差別矩陣是對稱矩陣，只存儲差別矩陣下三角部分，降低空間復雜度.

基于本研究重新定義的差別矩陣，新的求屬性核的算法流程如圖1.其中，C為條件屬性集合;f為屬性集到值域集的映射;count(≥1)為mij在差別矩陣M中出現的次數;DMSC(C)為C的核.

2 改進的核增量式算法

2.1 算法原理

在只存儲差別矩陣下三角部分情況下，針對文獻［11］的3種情況，本研究分別做如下處理:

①當x與(U1∪U'2)一致時，計算x與U1∪U'2間的mij，并按如圖2的處理過程，將 mij增至DMSC(C)，U1=U1∪ {x}.

②當x與U1不一致時，在U1中找出與x不一致的 y，計算 y與 U1∪ U'2之間的 mij，并把DMSC(C)中相應的mij依據圖2處理過程刪除;令U'2=U'2∪{y}，U1=U1－{y}，并計算y與U1之間的mij，按圖2處理過程，將mij增至DMSC(C).

③當x與U'2不一致時，DMSC(C)保持不變.

改進的核增量式算法 (improved optimization for incremental updating algorithm of a core，IOIUAC)流程圖如圖2.其中，core(C)表示最終得到的條件屬性集C的核.

圖1 改進的求核算法Fig.1 Improved algorithm of the computation of a core

2.2 算法分析

①當x與(U1∪U'2)一致時，將x加入U1，文獻［11］對差別矩陣增加了1行1列，由于mij=mji，當xi∈U1，xj∈U1時，增加的列對于核計算來說是多余的，所以IOIUAC只需計算相應的行;此時計算量為.判斷x與(U1∪U'2)是否一致，所需計算量為故在此情況下，IOIUAC的總時間復雜度為

②當x與U1不一致時，計算U1中與x不一致的對象y，并刪除DMSC(C)中y所在行的單個屬性，其計算量為然后，y作為U'2中的對象計算相應的DMSC(C)，其計算量為判斷一致性的時間為，所以，x與U1不一致時總的時間為故IOIUAC的時間復雜度為，小于文獻［11］中算法2的時間復雜度

③當x與U'2不一致時，文獻［11］算法2空間復雜度為，而算法IOIUAC空間復雜度為為條件屬性數.由于，故 IOIUAC較文獻［11］中算法2的空間復雜度有顯著改善.

2.3 實驗

在內存為1 024 MB，CPU為PⅣ 2.9 GHz，操作系統為Windows XP的聯想PC上，Eclipse下Java實現文獻［11］中算法 OIUAC及本研究提出的IOIUAC.利用UCI提供的蘑菇數據庫 (mushroom)進行實驗，該數據庫有8 124個對象.將蘑菇數據庫看作決策表，并進行2個實驗.

實驗1 從8 124個對象中選擇7 000個對象作為基準決策表 (基準決策表即該表生成的差別矩陣作為OIUAC和IOIUAC的輸入)，從剩下1 124個對象中依次選擇200、500、800和1 124個對象作為增量，執行OIUAC和IOIUAC，運行結果如圖3.

實驗2 由蘑菇數據庫生成8 000個對象，其中有1 000個不一致對象，從生成的8 000個對象中選擇7 500條作為基準決策表，從剩下的500個對象中依次選擇100、200、300和500個對象作為增量，執行OIUAC和IOIUAC，運行結果如圖4.

2.4 實驗分析

實驗1 8 124個對象為一致性對象.OIUAC計算及遍歷差別矩陣相應的行和列，而IOIUAC只需計算1行，又因我們優化了核屬性計算算法，所以IOIUAC的計算時間比較少.

實驗2 當x與U1不一致時，OIUAC首先遍歷差別矩陣中與x相應的行和列，刪除DMSC(C)中相關的核屬性，然后把該對象插入U2，計算U2中x相應的差別矩陣，把核屬性插入DMSC(C).此時，IOIUAC的計算量明顯少于OIUAC的計算量.

對實驗過程的監測結果顯示，OIUAC因為存儲差別矩陣，隨著對象數從7 200個增至8 124個，內存使用量從225 Mbit增至285 Mbit;而IOIUAC內存使用量一直保持小幅增加，增幅僅約20 M.所以，IOIUAC較OIUAC的另一重要優勢為前者可應對大數據集的挑戰.

圖2 改進的核增量式算法Fig.2 Improved optimization for incremental updating algorithm of a core

圖3 第1組實驗算法的執行時間Fig.3 Algorithm running time in first group experiment

圖4 第2組實驗算法的執行時間Fig.4 Algorithm running time in second group experiment

3 改進的屬性約簡完備算法及其分析

文獻［12］的增量式屬性約簡算法多次調用求核過程，其時間復雜度為，這是引起時間復雜度高的一個重要原因;又因該算法存儲了差別矩陣，求核遍歷差別矩陣的時間復雜度為，故文獻［12］使用差別矩陣是引起時間空間復雜度高的另一重要原因.當決策表一致時，有U1=U，文獻［12］屬性約簡算法的時間和空間復雜度至少為O

徐章艷［13］給出的屬性約簡算法RedueBaseSig，其時間復雜度為，由于該算法未從求核出發，在某些情況下，獲得并非屬性的約簡，其中會包含冗余屬性.

文獻［14］對RedueBaseSig進行了改進，提出一種基于分布計數的基數排序方法的等價類劃分算法.對決策表采用分布計數的基數排序，按屬性集C對決策表S排序，該算法的時間復雜度也為O，空間復雜度為

3.1 改進的屬性約簡完備算法

改進的增量式屬性約簡算法 (improved incremental updating algorithm of attribute reduction for inserting，IIUAARI)分2種情況:① 新增對象x，若x與U'2一致或x與U'2中的某個對象不一致或x與U1中的對象是P一致的，則P是一個屬性約簡;②其他情況，由增量式核算法IOIUAC計算得到的核開始重新計算屬性約簡.

IIUAARI流程如圖5.其中，POSC(D)表示D的C正域，POSS(D)表示D的S正域，NEGS(D)表示D的S負域.

3.2 時間復雜度分析

運行IIUAARI算法時各中間步驟的時間復雜度分別為:更新 DMSC(C)為判斷一致性為由DMSC(C)得到核為判斷P不一致性為計算POSC(D)、POSS(D)和 NEGS(D)時，3個公式的復雜度都為 O;POSC(D)≠POSS(D)的循環處理為綜上可知，算法IIUAARI總時間復雜度為

圖5 改進的增量式屬性約簡算法Fig.5 Improved incremental updating algorithm of attribute reduction

由于IIUAARI算法沒有存儲差別矩陣，所以它的時間復雜度較文獻［12，15］的有顯著降低，并與文獻［14］的時空復雜度相當.但文獻［14］的求核算法只能用于求一致性決策表的核;而IIUAARI算法充分利用已有的核，能減少計算量，適用于一致性、不一致性決策表的屬性增量式約簡;同時當新增對象x，x與U2中的某個對象不一致或x與U1中的對象是P一致時，IIUAARI的時間復雜度為能高效求得屬性約簡.

3.3 示例說明

表1是一張有5個對象和5個屬性二值數據表，其中，C={C1，C2，C3，C4}為條件屬性集;D 為決策屬性.

表1 二值數據表Table 1 Two-value data table

由表1可知，U1={x3，x4，x5}，U2={x1，x2}，U'2={x1}，由文獻［11］定義可得差別矩陣M為

由文獻［11］可得，該表中核為{C2}.由文獻［1］可知，{C1，C2}和{C2，C3，C4}為其2個屬性約簡.

為進一步說明算法IIUAARI，以下通過新增對象x說明插入對象后屬性約簡更新情況.

① 若 x={1，0，1，0，3}，則 x與 x1不一致，由IIUAARI可知，核和屬性約簡不變.

② 若 x={1，1，1，0，1}，則 x與 x3不一致;當IIUAARI通過IOIUAC更新DMSC(C)，且x與U1中的對象不一致時，由DMSC(C)=?及S=?，可得 SGF(C1，S，D)=2/6， SGF(C2，S，D)=0，SGF(C3，S，D)=1/6，SGF(C4，S，D)=1/6;在C中選擇 C1，使得 SGF(ai，S，D)取值最大，則 S={C1}，由于POSC(D)=POSS(D)，故S={C1}為一屬性約簡.

③ 若 x={0，1，0，0，3}，則 x與 x4不一致;當IIUAARI通過IOIUAC更新DMSC(C)，且x與U1中的對象不一致時，由 DMSC(C)={C2}及 S={C2}，可得SGF(C1，S，D)=1/6，SGF(C3，S，D)=0，SGF(C4，S，D)=1/6;(U-POSS(D))/{C1}=2，將C1加入 S，得 S={C1，C2};重新計算可得SGF(C3，S，D)=1/6， SGF(C4，S， D)=1/6;(U-POSS(D))/{C1}=2，將 C3加入 S，S={C1，C2，C3}，此時 POSC(D)=POSS(D)，故 S={C1，C2，C3}為一屬性約簡.

④ 若 x={1，1，0，1，3}，則 x 與原決策表中的對象P一致，由算法IIUAARI可知，核和屬性約簡不改變.

⑤ 若 x={0，1，0，1，3}，則 x 與原決策表中的對象一致;IIUAARI通過IOIUAC更新DMSC(C);由 DMSC(C)={C2，C3，C4}，S={C2，C3，C4}，POSC(D)=POSS(D)，可得 S={C2，C3，C4}為一屬性約簡.

可見算法IIUAARI在各種情況下得到的約簡與文獻［12］算法相同，本文示例取自文獻［12］.

結 語

本研究基于已有增量式求核算法，提出不存儲差別矩陣的改進增量式求核算法，由于差別矩陣是對稱矩陣，本研究中的求核算法，通過只存儲差別矩陣下三角部分，有效降低了空間復雜度.故能有效地處理大數據集.由于本文的IIUAARI算法沒有存儲差別矩陣，充分利用已有的核，顯著減少計算量，降低了屬性約簡的復雜度，較已有的屬性約簡增量式算法［12-18］更高效，而且它適用于一致性、不一致性決策表的屬性增量式約簡.故可以用于快速處理大數據集，能高效的求得屬性約簡.

下一步我們將繼續完善屬性約簡算法，著重考慮對象刪除情況下核增量式算法及屬性約簡的更新問題.

/References:

［1］ Pawlak Z.Rough sets［J］.International Journal of Information and Computer Science，1982，11(5):341-356.

［2］ QIAN Yu-hua，LIANG Ji-ye，Pedrycz Witold，et al.Positive approximation:an accelerator for attribute reduction in rough set theory ［J］.Artificial Intelligence，2010，174(9/10):597-618.

［3］ HE Qiang，WU Cong-xin，CHEN De-gang，et al.Fuzzy rough set based attribute reduction for information systems with fuzzy decisions ［J］.Knowledge-Based Systems，2011，24(5):689-696.

［4］ QIAN Yu-hua，LIANG Ji-ye，Pedrycz Witold，et al.An efficient accelerator for attribute reduction from incomplete data in rough set framework ［J］.Pattern Recognition，2011，44(8):1658-1670.

［5］ XU Wei-hua，LI Yuan，LIAO Xiu-wu.Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems ［J］.Knowledge-Based Systems，2012，27:78-91.

［6］ Wong S K M，Ziarko W.On optimal decision rules in decision tables［J］.Bulletin of Polish Academy of Sciences，1985，33(11/12):663-676.

［7］ Hu X H，Cercone N.Mining knowledge rules from databases:a rough set approach［C］//Proceedings of the 12th International Conference on Data Engineering.New Orleans(USA):IEEE Press，1996:96-105.

［8］ Hu X H，Nick Cercone.Learning in relational databases:a rough set approach ［J］.International Journal of Computational Intelligence，1995，11(2):323-338.

［9］ WANG Guo-yin，YU Hong，YANG Da-chun.Decision table reduction based on conditional information entropy［J］.Chinese Journal of Computers，2002，25(7):759-766.(in Chinese)王國胤，于 洪，楊大春.基于條件信息熵的決策表約簡 ［J］.計算機學報，2002，25(7):759-766.

［10］ YE Dong-yi，CHEN Zhao-jiong.A new discernibility matrix and the computation of a core［J］.ACTA Electronica Sinica，2002，30(7):1086-1088.(in Chinese)葉東毅，陳昭炯.一個新的差別矩陣及其求核方法［J］.電子學報，2002，30(7):1086-1088.

［11］ YANG Ming.An incremental updating algorithm of the computation of a core based on the improved discernibility matrix ［J］.Chinese Journal of Computers，2006，29(3):407-413.(in Chinese)楊 明.一種基于改進差別矩陣的核增量式更新算法［J］.計算機學報，2006，29(3):407-413.

［12］ YANG Ming.An incremental updating algorithm for attribute reduction based on improved discernibility matrix［J］.Chinese Journal of Computers，2007，30(5):815-822.(in Chinese)楊 明.一種基于改進差別矩陣的屬性約簡增量式更新算法 ［J］.計算機學報，2007，30(5):815-822.

［13］ XU Zhang-yan，YANG Bin-ru.Quickly attribution reduction algorithm based on decision table［J］.Journal of Chinese Computer Systems，2006，25(5):858-861.(in Chinese)徐章艷，楊炳儒.一個基于決策表的快速屬性約簡算法 ［J］.小型微型計算機系統，2006，25(5):858-861.

［14］ GE Hao，LI Long-shu，YANG Chuan-jian.Improvement to quick attribution reduction algorithm ［J］.Journal of Chinese Computer Systems，2009，30(2):308-312.(in Chinese)葛 浩，李龍澍，楊傳健.改進的快速屬性約簡算法［J］.小型微型計算機系統，2009，30(2):308-312.

［15］ LIU Yang，FENG Bo-qin，ZHOU Jiang-wei.Complete algorithm of increment for attribute reduction based on discernibility matrix［J］.Journal of Xi'an Jiaotong University，2007，41(2):158-161.(in Chinese)劉 洋，馮博琴，周江衛.基于差別矩陣的增量式屬性約簡完備算法 ［J］.西安交通大學學報，2007，41(2):158-161.

［16］ QIAN Jin，YE Fei-Yue，LU Ping.An incremental attribute reduction algorithm in decision table［C］//Proceedings of the Seventh International Conference on Fuzzy Systems and Knowledge Discovery(FSKD).Yantai(China):IEEE Press，2010，4:1848-1852.

［17］ XU Yi-tian，WANG Lai-sheng，ZHANG Rui-yan.A dynamic attribute reduction algorithm based on 0-1 integer programming ［J］.Knowledge-Based Systems，2011，24(8):1341-1347.

［18］ ZHANG Jun-bo，LI Tian-rui，RUAN Da.Rough sets based incremental rule acquisition in set-valued information systems［J］.Autonomous Systems:Developments and Trends，2012，391:135-146.