趙 軍，陳 宸

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

0 引言

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

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

1 粗糙集理論的基本知識(shí)［2］

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

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

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

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

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

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

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

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

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

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

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

3.1 算法描述

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

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

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

3.3 算法實(shí)例分析

二進(jìn)制分辨矩陣BM中，有6個(gè)條件屬性a，b，c，d，e，f;11 個(gè)項(xiàng)，如表1 所示。

表1 二進(jìn)制分辨矩陣Tab.1 Binary discernibilitymatrix

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

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

同理，對(duì)表2繼續(xù)計(jì)算RCI，可知屬性d的RCI最大，加入到REDU中，刪除d所在的列及在該列上值為1的行，得到空表，算法結(jié)束，此時(shí)REDU={d，f}。這一結(jié)果為該系統(tǒng)的最優(yōu)約簡(jiǎn)，因?yàn)槿魏螁我坏臈l件屬性均不能保持系統(tǒng)的相對(duì)正域。

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

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

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

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

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

5 結(jié)論

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

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

［2］王國(guó)胤.ROUGH理論與知識(shí)獲取［M］.西安:西安交通大學(xué)出版社，2001.

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

［3］劉清.Rough集及Rough推理［J］.計(jì)算機(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］.模式識(shí)別與人工智能，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］苗奪謙，胡桂榮.知識(shí)約簡(jiǎn)的一種啟發(fā)式算法［J］.計(jì)算機(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］王國(guó)胤，于洪，楊大春.基于條件信息熵的決策表約簡(jiǎn)［J］.計(jì)算機(jī)學(xué)報(bào)，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］吳尚智，茍平章.粗糙集和信息熵的屬性約簡(jiǎn)算法及其應(yīng)用［J］.計(jì)算機(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］吳靜，鄒海.基于屬性重要性的屬性約簡(jiǎn)算法［J］.計(jì)算機(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］劉高峰，牟廉明，張濤.基于改進(jìn)區(qū)分矩陣的決策表增量式屬性約簡(jiǎn)［J］.計(jì)算機(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集的屬性約簡(jiǎn)的改進(jìn)算法［J］.計(jì)算機(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］侯利娟，史長(zhǎng)瓊.基于分明矩陣的屬性約簡(jiǎn)啟發(fā)式算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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ìn)制可辨矩陣的屬性約簡(jiǎn)算法的改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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ìn)制可分辨矩陣的最小屬性約簡(jiǎn)算法［J］.計(jì)算機(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］蒙祖強(qiáng)，史忠植.一種新的基于簡(jiǎn)化二進(jìn)制可辨矩陣的相對(duì)約簡(jiǎn)算法［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］李智玲，胡彧.一種改進(jìn)的區(qū)分矩陣屬性約簡(jiǎn)算法［J］.計(jì)算機(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.

(編輯:魏琴芳)