趙 軍，陳 宸

(重慶郵電大學(xué)計算機科學(xué)與技術(shù)研究所，重慶 400065)

0 引言

粗糙集(rough set)理論［1－2］能處理不一致、不完備和不精確信息，目前已被廣泛應(yīng)用于模式識別、醫(yī)療診斷、機器學(xué)習(xí)、決策分析等各個領(lǐng)域［3－5］。決策表的屬性約簡是粗糙集信息處理模型中的一個核心內(nèi)容。所謂決策表的屬性約簡，就是要在保持條件屬性相對于決策屬性的分類能力不變的前提下，刪除其中不必要的或者不重要的條件屬性。已經(jīng)證明，最優(yōu)屬性約簡是一個NP難題［6］。于是，很多學(xué)者轉(zhuǎn)而研究更為有效的啟發(fā)式屬性約簡算法［7－13］，這些算法從信息熵、正區(qū)域或分辨矩陣等不同的角度來度量屬性的相對重要性。其中，信息熵概念依賴于樣本分布概率估算的準(zhǔn)確性，當(dāng)樣本規(guī)模較小時難以保證其約簡性能;在后兩者中，盡管基于分辨矩陣的算法時間復(fù)雜度相對略高，但這類方法卻很直觀，易于實現(xiàn)，因此在許多研究和應(yīng)用中仍然受到重視。經(jīng)典的分辨矩陣［14］以屬性集合為矩陣元素，其空間復(fù)雜高、處理效率低，于是有人將其優(yōu)化為二進制的分辨矩陣，在此基礎(chǔ)上提出了新的屬性約簡算法［15－18］，但這類算法的性能仍然有待進一步提高。

本文通過對分辨矩陣進行深入的分析，定義“加權(quán)重要度”來更好地刻畫屬性重要性。這一概念充分利用了分辨矩陣提供的信息，具有明顯的物理意義，同時也具有較強的合理性。在此基礎(chǔ)上，提出了一種基于“加權(quán)重要度”的啟發(fā)式屬性約簡算法。仿真結(jié)果表明，該算法的綜合性能優(yōu)于參考算法。

1 粗糙集理論的基本知識［2］

其中，BM((i，j)，c)表示決策表的第 i和第 j個樣本通過條件屬性c是否能區(qū)分出，若能區(qū)分出則為1，否則為0。屬性c對應(yīng)列上‘1’的個數(shù)就是c能分辨的樣本對數(shù)，它能直接描述c的分辨能力;樣本對(i，j)對應(yīng)行上‘1’的個數(shù)就是能分辨(i，j)的屬性數(shù)，其大小反過來能間接地表達相應(yīng)屬性對樣本的分辨能力。

顯然，若BM中某行上只有1個元素為‘1’，則對應(yīng)的屬性必然是核屬性。

2 基于二進制分辨矩陣的加權(quán)屬性重要度

相較于其他屬性約簡方法，分辨矩陣能充分表達屬性對樣本的分辨能力，這一概念在屬性約簡中的應(yīng)用也非常廣泛［19－22］。經(jīng)典分辨矩陣以屬性名稱來表示矩陣元素，不但存儲開銷大，而且對矩陣的處理均是符號邏輯運算，因二進制分辨矩陣更具有計算簡單、計算效率高等優(yōu)點，并受到廣泛關(guān)注。在度量候選屬性重要性時，文獻［15］提出以列方向上‘1’的總數(shù)為主，行方向上的為輔;只有當(dāng)列方向上‘1’的總數(shù)相等時，把列對應(yīng)的屬性所在的列值為1的對應(yīng)的行的“1元素”的數(shù)目相加，取和最小的屬性。統(tǒng)計多行“1元素”的總個數(shù)，而不是單獨考慮各行，這種方式過于籠統(tǒng)，必然會掩蓋那些具有特殊意義的行所表達的特征，因此這種方式本身具有一定的不合理性。文獻［16］則將矩陣行、列上的特征分開，但優(yōu)先考慮行方向，而事實上，列方向特征對屬性的描述能力更強。文獻［17］通過統(tǒng)計屬性頻率綜合利用了矩陣行、列兩個方向的信息，但對這兩者未予區(qū)分。文獻［18］以列上“1元素”的頻率作為屬性重要度的度量，而忽略了分辨矩陣行上的特征。

基于此，本文提出了一種基于二進制分辨矩陣的算法，該算法定義在二進制分辨矩陣中的列方向和行方向上同時對屬性進行度量的“加權(quán)重要度”，作為度量屬性重要度的一種方式。

定義8中，屬性的“列重要度”CI表明了屬性所能區(qū)分的項在分辨矩陣中所占的比例，該值越大，表明屬性能區(qū)分的項越多，屬性重要性就越重要，是屬性重要性的直接體現(xiàn)。

定義10中，屬性的“行重要度”RI越大，包含該屬性的最小項的長度越短，能區(qū)分相應(yīng)樣本的屬性越少，間接表明屬于該項的屬性越重要。極端情況下，當(dāng)某一行上‘1’的總數(shù)剛好為1個時，所對應(yīng)的屬性是核屬性，一定屬于約簡集合，此時，該屬性的“行重要度”為1，準(zhǔn)確反映了核屬性的特征。

定義11中，屬性的“加權(quán)重要度”RCI是對屬性的CI和RI進行加權(quán)后得到的結(jié)果，該值越大，說明屬性越重要。

通過選擇適當(dāng)?shù)募訖?quán)參數(shù)α，β，能使加權(quán)結(jié)果體現(xiàn)出不同的特性。當(dāng)α?β時，屬性的加權(quán)重要度取決于列方向上的特征;反之，當(dāng)α?β時，屬性的加權(quán)重要度取決于行方向上的特征。

分辨矩陣列方向的特征直接表明了屬性分辨樣本對的數(shù)量，而行方向特征直接表明的是能夠分辨相應(yīng)樣本對的屬性的多寡，反過來間接地表明了相應(yīng)屬性的分辨能力。因此，從描述屬性的分辨能力來看，分辨矩陣列方向上的特征更為重要，因此，在合成加權(quán)重要度時，一般取αβ。

3 基于加權(quán)屬性重要度的屬性約簡算法

3.1 算法描述

3.2 算法復(fù)雜性分析

時間復(fù)雜度方面，本文算法與相關(guān)文獻報道的基于二進制分辨矩陣的同類算法(如文獻［15－18］)相同，都為)。但由于本文算法是基于二進制分辨矩陣定義的“加權(quán)重要度”概念，將矩陣列與行兩個方向的特征通過加權(quán)求和的方式集成為一個概念，與同類算法相比，本文的方式既充分利用了矩陣信息，在選擇屬性時又不必分別對列與行2個方向的特征進行排序，只需排序一次就可選出一個屬性，減小了排序運算量，因此時間效率較同類算法更優(yōu)。

空間復(fù)雜度方面，本文算法與基于經(jīng)典分辨矩陣的屬性約簡算法相同，都為)，但由于經(jīng)典的分辨矩陣需要存儲所有的區(qū)分對象，而采用二進制形式的分辨矩陣只需存儲對稱矩陣，其存儲規(guī)模實際上比經(jīng)典分辨矩陣減小了一半，并且將極其困難的符號邏輯運算化為簡單整數(shù)運算，因此其效率比基于經(jīng)典分辨矩陣的屬性約簡算法更優(yōu)。

3.3 算法實例分析

二進制分辨矩陣BM中，有6個條件屬性a，b，c，d，e，f;11 個項，如表1 所示。

表1 二進制分辨矩陣Tab.1 Binary discernibilitymatrix

選擇使 RCI最大的屬性 f，加入約簡集合REDU，刪除f所在的列及在該列上值為1的行，得到表2的結(jié)果。

表2 刪除屬性f后的二進制分辨矩陣Tab.2 Binary discernibilitymatrix after removing the attribute f

同理，對表2繼續(xù)計算RCI，可知屬性d的RCI最大，加入到REDU中，刪除d所在的列及在該列上值為1的行，得到空表，算法結(jié)束，此時REDU={d，f}。這一結(jié)果為該系統(tǒng)的最優(yōu)約簡，因為任何單一的條件屬性均不能保持系統(tǒng)的相對正域。

而采用文獻［15］介紹的同類方法，易得到約簡集合REDU={a，b，c}，這并不是系統(tǒng)的最優(yōu)約簡。

4 算法仿真測試結(jié)果及分析

本文選用了UCI中6組數(shù)據(jù)集，在2G RAM，2.4G CPU，WIN7系統(tǒng)的計算機下，vc6.0開發(fā)環(huán)境中進行實驗。分別采用本文算法(算法1)、文獻［15］的算法(算法2)、文獻［7］中的 MIBARK 算法(算法3)和文獻［8］中的CEBARKCC算法(算法4)進行屬性約簡。其中算法1中的加權(quán)參數(shù)取α=為二進制分辨矩陣的項的總數(shù)。實驗得到了表3的結(jié)果。

表3 屬性約簡結(jié)果比較Tab.3 Attribute reduction comparison of different algorithms

從表3可以看出，實驗采用的6組數(shù)據(jù)集中，在屬性約簡結(jié)果上，算法1和算法4都得到了最優(yōu)約簡，而算法2和算法3得到的結(jié)果有部分不是最優(yōu)約簡。在運行時間上，算法1的速度較算法3和算法4有較大提高，略快于算法2。從實驗結(jié)果來看，本文提出的算法(算法1)的綜合性能是最佳的。

5 結(jié)論

本文基于二進制分辨矩陣中行和列方向上的特征，定義了“加權(quán)屬性重要度”概念來度量屬性的相對重要性。這一概念充分考慮了列及行對屬性重要性描述能力的差異，具有更好的物理意義及合理性。在此基礎(chǔ)上，提出了一種啟發(fā)式屬性約簡算法。仿真實驗結(jié)果表明，該算法是高效可行的。下一步要研究的工作就是如何進一步減少分辨矩陣的存儲空間，以降低算法的時間和空間復(fù)雜度，這對于大型數(shù)據(jù)集具有非常重要的意義。

［1］PAWLAK Z.Rough set［J］.Communications of the ACM.1995，38(11):89－95.

［2］王國胤.ROUGH理論與知識獲?。跰］.西安:西安交通大學(xué)出版社，2001.

WANG Guo－yin.Rough set theory and knowledge acquisition［M］.Xi'an:Xi'an Jiaotong University Press，2001

［3］劉清.Rough集及Rough推理［J］.計算機研究與發(fā)展，2003，7(40):969－970.

LIU Qing.Rough set and rough reasoning［J］.Journal of Computer Research and Development，2003，7(40):969－970.

［4］ZIAKOW.Rough sets;Trends，challenges，and prospects［M］//ZIARKO W，YAO Y Y.Rough Sets and Current Trends in Computing(RSCTC 2000).Berlin:Springer－Verlag，2001:1－7.

［5］王玨，苗奪謙.關(guān)于Rough Set理論與應(yīng)用的綜述［J］.模式識別與人工智能，1996，9(4):337－344.

WANG Jue，MIAO Duo－qian.Rough set theory and it'sapplication:A survey［J］.Pattern Recognition and Artific－ial Intelligence，1996，9(4):337－344.

［6］WONG SK M，ZIARKOW.On optimal decision rules in decision tables［M］.Poland:Bulletin of Polish Academy of Science，1985:693－696.

［7］苗奪謙，胡桂榮.知識約簡的一種啟發(fā)式算法［J］.計算機研究與發(fā)展，1999，6(36):681－684.

MIAO Duo－qian，HU Gui－rong.A heuristic algorithm for reduction of knowledge［J］.Journal of Computer Research and Development，1999，6(36):681－684.

［8］王國胤，于洪，楊大春.基于條件信息熵的決策表約簡［J］.計算機學(xué)報，2002，25(7):759－766.

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.

［9］吳尚智，茍平章.粗糙集和信息熵的屬性約簡算法及其應(yīng)用［J］.計算機工程，2011，7(37):56－58.

WU Shang－zhi，GOU Ping－zhang.Attribute reduction algorithm on rough set and information entropy and it's application［J］.Computer Engineering，2011，7(37):56－58

［10］吳靜，鄒海.基于屬性重要性的屬性約簡算法［J］.計算機應(yīng)用與軟件，2010，2(27):255－257.

WU Jing，ZOU Hai.Attribute reduction algorithm based on importance of attribute value［J］.Computer Applications and Software，2010，2(27):255－257.

［11］劉高峰，牟廉明，張濤.基于改進區(qū)分矩陣的決策表增量式屬性約簡［J］.計算機工程，2010，20(36):46－48.

LIU Gao－feng，MOU Lian－ming，ZHANG Tao.Incremental attributes reduction of decision table based on Imp－roved discernibilitymatrix［J］.Computer Engineering，2010，20(36):46－48.

［12］李永華，蔣蕓，王小菊.一種基于rough集的屬性約簡的改進算法［J］.計算機應(yīng)用，2008，8(28):2000－2002.

LIYong－h(huán)ua，JIANG Yun，WANG Xiao－ju.An Improved algorithm for attribute reduction based on rough sets［J］.Journal of Computer Applications，2008，8(28):2000－2002.

［13］YU Hong，YANG Da－chun.A Knowledge Reduction Algorithm Based on Conditional Entropy［J］.The Journal of China Universities of Posts and Telecommunications，2001，8(3):23－27.

［14］SKOWRON A，RAUSZER C.The Discernibility Matrices and Functions in Information Systems［M］//Intelligent Decision Support Handbook of Applications and Advances of the Rough Sets Theory.Dordrecht:Kluwer Academic Publishers，1992:331－338.

［15］侯利娟，史長瓊.基于分明矩陣的屬性約簡啟發(fā)式算法［J］.計算機工程與設(shè)計，2007，28(18):4466－4468.

HOU Li－juan，SHI Chang－qiong.Heuristic algorithm to rough set attribute reduction based on discernibilitymatrix［J］.Computer Engineering and Design，2007，28(18):4466－4468.

［16］周海巖，楊汀.基于二進制可辨矩陣的屬性約簡算法的改進［J］.計算機工程與設(shè)計，2003，12(24):35－37.

ZHOU Hai－yan，YANG Ting.A more efficient algorithm for attribute reduction based on the binary discernibility matrix ［J］.Computer Engineering and Design，2003，12(24):35－37.

［17］李龍澍，王慧萍，徐怡.二進制可分辨矩陣的最小屬性約簡算法［J］.計算機技術(shù)與發(fā)展，2010，6(20):93－96.

LILong－shu，WANG Hui－ping，XU Yi.Algorithm for the least attribute reduction of binary discernibility matrix［J］.Computer Technology and Development，2010，6(20):93－96.

［18］蒙祖強，史忠植.一種新的基于簡化二進制可辨矩陣的相對約簡算法［J］.控制與決策，2008，9(39):976－978.

MENG Zu－qiang，SHI Zhong－zhi.Algorithm for relative reduction based on simplifried binary discernibilitymatrix［J］.Control and Decision，2008，9(39):976－978.

［19］胡可云.基于概念格和粗糙集的數(shù)據(jù)挖掘方法研究［D］.北京:清華大學(xué)，2001.

HU Ke－yun.Research on concept lattice and rough set based dataminingmethods［D］.Beijing:Tsinghua University，2001.

［20］李智玲，胡彧.一種改進的區(qū)分矩陣屬性約簡算法［J］.計算機系統(tǒng)應(yīng)用，2008，17(10):51－55.

LI Zhi－ling，HU Yu.An improved algorithm for attribute reduction of discernibility matrix［J］.Computer Systems and Applications，2008，17(10):51－55.

［21］HU X H，CERCONE N.Learning in relational database:Arough set approach［J］.International Journal of Computational Intelligence，1995，11(2):323－338.

［22］NGUYEN SH，NGUYEN H S.Some efficient algorithms for rough setmethods［C］//Proceedings of the Conference on Information Processing and Management of Uncertainty in Knowledge Based Systems.Granada.Spain:［s.n.］.1996:1451－1456.

(編輯:魏琴芳)