D0I:10.13374才.issn1001663.2013.02.017 第35卷第2期 北京科技大学学报 Vol.35 No.2 2013年2月 Journal of University of Science and Technology Beijing Feb.2013 一种快速的动态属性约简矩阵算法 钱文彬12)四，杨炳儒12)，徐章艳3)，李慧12) 1)北京科技大学计算机与通信工程学院，北京1000832)材料领域知识工程北京市重点实验室，北京100083 3)广西师范大学计算机科学与信息工程学院，桂林541004 通信作者，E-mail:qianwenbin1(027@126.com 摘要针对实际决策表中对象动态变化的情况，首先引入简化决策表概念，别除决策表中大量重复的对象，并构造了 基于正区域的简化矩阵，有效地缩小了算法的搜索空间：然后从理论上阐述了基于简化矩阵的属性约简和基于矩阵的属 性约简的一致性，并仅需扫描一遍简化矩阵便可求解出属性约简：最后在原属性约简的基础上，提出一种快速的动态属 性约简矩阵算法.通过算例分析和实验对比验证了算法的有效性和可行性. 关键词粗糙集理论：属性约简：矩阵算法；决策表 分类号TP301.6 Efficient algorithm for dynamic attribute reduction based on a matrix QIAN Wen--bim,2)凶，YANG Bing-l,2）,XU Zhang-yan.3,LlHu,2) 1)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China 2)Beijing Key Laboratory of Knowledge Engineering for Materials Science,Beijing 100083,China 3)School of Computer Science and Information Engineering,Guangxi Normal University,Guilin 541004,China Corresponding author,E-mail:gianwenbin1027@126.com ABSTRACT Objects in actual decision tables are often changed dynamically.Aiming at this problem,the concept of a simplified decision table is introduced firstly,and a large number of repeated objects are deleted.A simplified matrix based on the positive region is constructed,which can reduce the searching space.What's more,it is theoretically analyzed that the definition of attribute reduction based on the simplified matrix is equal to that based on the un- simplified matrix.The proposed method scans only once the simplified matrix and it can be effectively utilized to the old attribute reduction.On this condition,an efficient algorithm for dynamic attribute reduction based on a matrix was designed.Finally,an example and its experimental comparison were employed to illustrate the efficiency and feasibility of the proposed algorithm. KEY WORDS rough set theory;attribute reduction;matrix algorithm;decision tables 粗糙集理论)作为一种不确定性、不完全和不方法、差别矩阵方法和矩阵方法.对于前两种技术 精确数据的数学工具，已经在知识发现、数据挖掘、 目前研究较为成熟，而利用矩阵方法的研究相对较 模式分类、生物信息学等领域取得成功应用2-，'设 少.Guan等12)提出信息系统下的矩阵方法，将 计高效的属性约简是粗糙集理论研究的核心问题之 信息系统下的等价关系利用矩阵的形式进行重新描 一，近年来，许多学者根据不同的需求，设计了不同述，并在此基础上设计了约简算法：但在整个过程 的属性约简算法，算法的计算效率取得显著进步.目 中矩阵仅是一种表示形式，并不能用来参与具体的 前常见的模型主要有基于正区域的属性约简6-、 计算，尤其不能刻画和评定论域集合与对象的等价 基于差别矩阵的属性约简8-9)和基于信息熵的属 类之间的关系. 性约简10-1川.这些模型主要使用的方法是启发式 现有大多数算法都集中在静态决策表的研究， 收稿日期：2011-12-12 基金项目：国家重点基础研究发展计划资助项目(2009CB522701):国家自然科学基金资助项目(61175048)：科技部创新方法专项 项目(2010IM020900):材料领域知识工程北京市重点实验室2012年度阶梯计划项目(No.Z121101002812005)资助DOI ：10．13374／j ．issn1001－053x．2013．02．017