第8卷第2期 智能系统学报 Vol.8 No.2 2013年4月 CAAI Transactions on Intelligent Systems Apr.2013 D0I:10.3969/j.i8sn.1673-4785.201209056 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20130409.1436.005.html 综合属性选择和删除的属性约简方法 杨成东1，邓廷权 (1.临沂大学信息学院，山东临沂276005；2.哈尔滨工程大学理学院，黑龙江哈尔滨150001) 摘要：属性约简能有效地消除信息冗余，广泛应用于人工智能、机器学习.通过实例指出基于辨识矩阵的经典的属 性约简方法存在不能得到约简的可能性，仍具有冗余性.因此，提出了综合属性选择和删除算法的辨识矩阵属性约 简方法，并有效解决该问题.通过UCI标准数据集验证表明，新方法比经典方法进一步减少了属性的个数，凸显其实 用性和有效性。 关键词：辨识矩阵；属性约简：信息冗余；人工智能；机器学习：属性选择；属性删除 中图分类号：TP301.6文献标志码：A文章编号：16734785(2013)02018304 An approach to attribute reduction combining attribute selection and deletion YANG Chengdong,DENG Tingquan2 (1.School of Informatics,Linyi University,Linyi 276005,China;2.College of Science,Harbin Engineering University,Harbin 150001,China)） Abstract:Attribute reduction has been defined as a method for removing information redundancy effectively,which has been widely applied to artificial intelligence,and machine learning.However,an example demonstrates classi- cal attribute reduction approaches based on discernibility matrix may not get a reduction with redundancy.There- fore,an attribute reduction based on discernibility matrix combining attribute selection and deletion was proposed and thus,the problem was solved effectively.Moreover,UCI standard data sets provide further explanations on the feasibility,effectiveness,and as well as additional information on reducing the number of attributes without the classical approaches. Keywords:discernibility matrix;attribute reduction;information redundancy;artificial intelligence;machine learning;attribute selection;attribute deletion 属性约简利用粗糙集2]等理论，旨在保持信 性约简方法，存在不能得到约简的可能性，仍具有冗 息系统决策能力不变的条件下，去除冗余属性，从而 余性. 减少数据的冗余度，是机器学习和人工智能最重要 1基础知识 的研究方向之一.属性约简方法有很多，譬如基于依 赖度的属性约简方法3]、基于互信息的属性约简方 给定决策系统S=(U,C∩D,V,),其辨识矩阵 法451、基于模糊粗糙集的属性约简方法61等。 定义为 Skowron于1992年提出了辨识矩阵和辨识函数的概 M=M(x,y）, 念，利用辨识矩阵和辨识函数实现了属性约简， 式中：M(x,y)定义为 并得到了广泛的研究).然而，基于辨识矩阵的属 M(x,y）= ∫a∈Clfx,a)≠fy,a)fx,D)≠fy,D); 收稿日期：2012-09-25.网络出版日期：2013-04-09 基金项目：山东省高等学校科技计划资助项目(J12LN91):山东省信 l0,其他. 息化与工业化融合专项课题资助项目(2012E100). 显然，矩阵M中元素M(x,y)是由处于不同决策类 通信作者：杨成东，E-mail:yangchengdong@yu.edu.cm. 中的对象x和y属性值不同的属性组成
·184· 智能系统学报 第8卷 辨识函数f(M)定义为 0(1U1.因此总的时间复杂度为：0(1U11C12), f代M)= 例1给定关于大豆质量的决策系统S= A{VM(x,y)1Hx,y∈U,M(x,y)≠☑i. (U,CUD,V,f)如表1，其中C={a,b,c,d,e}是条 式中：V和∧是2个基本的二值逻辑运算：析取和合 件属性，D是决策属性. 取.辨识函数是一个布尔表达式，通过等价的逻辑计 表1决策系统 算，将其化成若干个小合取式的析取式，那么每个小 Table 1 A decision system 合取式就是一个约简.一般地，约简不是惟一的，决 U b c d e D 策系统的所有约简用REDc(D)表示. 1 MiddleMiddle Middle ferl pes1 High 辨识矩阵和辨识函数有如下性质： 2 Middle High High fer2 pes2 High 1)核是辨识矩阵中所有单个元素组成的集合： 3 High Middle Middle fer2 pes1 High 4 fer2 2)辨识函数f(M)的极小析取范式中的所有合 High High High pesl High 5 High Middle High fer2 pesl Low 取式是属性集C的所有约简. 6 High High Middle ferl pesl Low 辨识矩阵和辨识函数方法能够求出所有约简， 7 High Middle High ferl pesl Low 因此具有十分重要的理论意义，然而利用该方法求 8 HighHigh Middle ferl pesl Low 出的所有约简仍是一个NP-hard问题，特别是在大 通过计算，该信息系统有2个约简，REDc(D)= 规模数据集中几乎无法求出约简，其速度非常慢，而 {b,c}·可以验证该系统是协调决策系统，见表 实际中通常只需要一个约简。 1.而利用算法1，求得的结果是{b,d,c{,显然{b,d, 2 辨识矩阵属性约简方法及其缺点 c REDc(D),仍包含了冗余属性{d}.该例说明经 典算法不能有效计算约简，仍具有一定的冗余性.本 作为经典辨识矩阵算法，基于属性频率的辨识 文提出一种新的属性约简方法来解决该问题 矩阵快速属性约简算法利用频率作为衡量属性重要 程度的依据，具有重要的实用价值.在辨识矩阵中出 3结合属性选择和删除的属性约简方法 现频率最高的属性是较为重要的，优先选择该属性。 首先证明算法1得到的属性约简没有损失信 基于辨识矩阵属性频率的快速属性约简算法如下： 息，即其依赖度相同： 算法1基于辨识矩阵属性频率的属性约简算法： 定理1给定决策系统S=(U,CUD,V,f),经 Input:S=(U,CUD,V,f) 过算法1后，得到red,那么 Output:red Yrod(D)Yc(D). 1)compute discernibility matrix M. 证明反证法.假设yed(D)≠Yc(D),那么， 2)fM=0 Y(D)<Yc(D),因此，存在x∈Posc(D),使得x 3)return red Pos(D),那么，存在y∈[x]d,使得M(x,y)≠O. 4)end if 然而这与算法1矛盾，因为经过算法1运算后，M 5)for aeC-red 是一个空矩阵，因此假设不成立. 6)compute the attribute frequency of a 例1说明了经典算法得到的red还具有一定冗 7)end for 余性，而定理1说明了经典算法得到的red与原始 8)select ar with the largest attribute frequency,then 决策系统具有相同的分辨能力.因此，本文提出能有 red =redUx; 效避免冗余的辨识矩阵属性约简快速算法， 9)set the elements of M including a with 0. 算法2结合属性选择和删除的属性约简快速 10)ifM=0. 算法： 11)return red; Input:S=(U,CUD,V,f) 12)else Output:red 13)turn to 5); 1)compute discernibility matrix M according to red. 14)return. 2)fM=0 该算法中的时间复杂度分为关键2步：一是对 3)return red 属性进行选择有2个循环，时间复杂度为O(IC12)；4)endf 另一个是计算单个属性的频率，时间复杂度为 5)fora∈C-red
第2期 杨成东，等：综合属性选择和删除的属性约简方法 185. 6)compute the attribute frequency of a Ym(D）=Yoi-a(D), 7)end for 那么这样的属性a在14)~19)的循环中被删除了， 8)select a with the largest attribute frequency,then 即a年red. red =red Uas; 因此，假设不成立，red是独立的.所以，red是 9)set the elements of M including a:with 0. 约简 10)ifM=0, 例2继续使用例1，利用算法2，可以得到约 11)retumn red; 简red={b,c.因此，与基于辨识矩阵属性约简方法 12 else 相比，该方法能够有效地获得约简。 13)tur to 5); 14)end if 4实验与分析 15)for each a∈red, 用6个UCI标准数据集来验证本文提出的方法 16)if yrod-a(D)=Yc(D), 的实用性和有效性，如表2所示.表3对经典方法选 17)red red-a; 择的属性序列和本文提出的方法选择的属性序列进 18)end if 行了比较.利用经典方法得到的6个数据集中， 19)end for Heart、Lymph、Soybean有3个不是约简.而本文方法 20)return red 得到的都是约简，有效地解决了经典方法得不到约 算法2比算法1多了一个循环0(1U11C1),由 简的问题. 于这2个循环是并列的，那么总的时间复杂度为 表2UCI标准数据集 0(1U11C12)+0(1U11C1)=0(1U11C2),因此算 Table 2 UCI standard datasets 法2与算法1具有相同的时间复杂度，本文提出的 数据集 简称 对象个数属性个数 算法的时间复杂度不会增加. Car Evaluation Car 172 7 下面证明算法2选择的属性子集是约简，既保 Spect Heart Heart 267 23 持了信息，又有效地消除了冗余信息. Tic-Tac-Toe Tic 958 10 定理2给定决策系统S=(U,CUD,V,),经 过算法2后，得到red,那么red是约简. Lymphography Lymphography 148 19 证明类似于定理1的证明，可以得到 Soybean Large) Soybean 683 36 Yrd(D)=Yc(D). Z00 Z00 101 17 另一方面，采用反证法证明red是独立的.假设red 不是独立的，那么存在a∈red,满足 表3与经典方法的比较 Table 3 Comparison of UCI standard datasets and the classical approaches 原始 经典方法 本文提出的方法 数据集 属性个数 选择序列 选择个数 选择序列 选择个数 Car 7 {2,1,4,6,5,3 6 12,1,4,6,5,3 Heart 23 f16,22,21,20,19,1,13, 15 {16,22,21,20,19,1,13,3,5,9,14,12 12 3,8,5,9,10,14,4,12 Lymph 10 {18,14,13,12,1,15,2,10 8 {18,14,13,12,15,2,10 {6,5,7,9,16,4,10,1,22 Sovbean 19 16 {6,5,7,9,16,4,10,1,22,29,15,8} 12 29,15,28,13,21,14,8 Tic 36 {5,2,46,8,1,3,7} {5,2,4,6,8,1,3,7 8 Z00 17 16,13,4,8,3} 6 16,13,4,8,3} 6 平均属性个数18.7 9.8 8.5
·186 智能系统学报 第8卷 从选择属性个数来看，与原始数据集对比，经典 reduction based on neighborhood granulation and rough ap- 算法和本文提出的方法都大大减少平均属性个数. proximation[J].Journal of Software,2008,19(3):640- 进一步地，本文算法的平均属性个数为8.5，比经典 649. 算法减少了1.3个.因此，本文提出的方法能够获得 [7]TSANG E CC,CHEN D G,YEUNG D S,et al.Attribute 更为精简的集约数据集，进一步降低了数据集的冗 reduction using fuzzy rough sets[].IEEE Transactions on Fuzzy Systems,2008,16(5):1130-1141. 余性。 [8]张志飞，苗夺谦。基于粗糙集的文本分类特征选择算法 5结束语 [J].智能系统学报，2009,4(5)：453457 ZHANG Zhifei,MIAO Duoqian.Feature selection for text 本文提出了结合属性选择和删除的属性约简方 categorization based on rough set[J].CAAI Transactions on 法，该方法能够彻底解决经典算法产生的冗余，得到 Intelligent Systems,2009,4(5):453-457. 有效的约简，解决了经典算法不能得到约简的问题 [9]SKOWRON A,RAUSZER C.The discernibility matrices and 通过6个UCI标准数据集，实例分析表明，提出的方 functions in information systems M]//Intelligent Decision 法选择的平均属性个数比经典算法减少了1.3个， Support,Handbook of Applications and Advances of the Rough 显示了其有效性和实用性. Sets Theory.Dordrecht:Kluwer Academic Publishers,1992: 331-362. 参考文献： [10]常犁云，王国胤，吴渝.一种基于Rough Set理论的属 性约简及规则提取方法[J].软件学报，1999,10(11)： [1]张文修，吴伟志，梁吉业，等.粗糙集理论与方法[M] 1206-1211. 北京：科学出版社，2001：57. CHANG Liyun,WANG Guoyin,WU Yu.An approach for [2]PAWLAK Z.Rough sets[J].International Joumnal of Com- attribute reduction and rule generation based on rough set puter and Information Sciences,1982,11(5):341-356. theory[J].Jourmal of Software,1999,10(11):1206- 「3]蒋云良，杨章显，刘勇.不协调信息系统快速属性分布 1211. 约简方法[J].自动化学报，2012,38(3)：382388. 作者简介： JIANG Yunliang,YANG Zhangxian,LIU Yong.Quick dis- 杨成东，男，1984年生，讲师，博士， tribution reduction algorithm in inconsistent information sys- 主要研究方向为数据挖掘、粗糙集理 tem[J].Acta Automatica Sinica,2012,38(3):382-388 论、智能计算.主持山东省高等学校科 [4]XU F,MIAO D,WEI L.Fuzzy-rough attribute via mutual 技计划项目等，发表学术论文十余篇。 information with an application to cancer classification[J]. Computers and Mathematics with Applications,2009,57 (6):1010-1017. [5]BHATT R,GOPAL M.On fuzzy-rough sets approach to fea- 邓廷权，男，1965年生，教授，博士生 ture selection[J].Pattern Recognition Letters,2004,26 导师，主要研究方向为模糊信息分析、数 (7）:965-975. 学形态学与图像分析、智能识别与计算机 [6]胡清华，于达仁，谢宗霞.基于邻域粒化和粗糙逼近的 视觉.主持国家自然科学基金、中国博士 数值属性约简[J].软件学报，2008,19(3)：640-649. 后科学基金、黑龙江省博士后科学基金等 HU Qinghua,YU Daren,XIE Zongxia.Numerical attribute 多项科研项目.近年来，发表学术论文30 余篇，其中半数被SCI,EI ISPT等检索
