一种基于决策表的属性约简增量式快速更新算法  

Quick and Incremental Updating Algorithm for Attribute Reduction in Decision Table

作　　者：钱文彬[1] 杨炳儒[1] 徐章艳[1,2] 

机构地区：[1]北京科技大学计算机与通信工程学院,北京100083 [2]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《小型微型计算机系统》2012年第2期254-258,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60875029;60963008)资助;广西教育厅科研基金项目(200807MS015)资助

摘　　要：针对实际的决策表中的对象通常是动态变化的情况,首先引入了简化的决策表,然后在动态更新核的基础上,结合简化二进制差别矩阵和位图运算的设计思想,提出了一种快速的属性约简增量式更新算法.当有新对象加入决策表时,新算法只需验证新增的对象和原决策表中的对象是否一致性,然后采用在计算二进制差别矩阵的同时对原属性约简进行动态更新,从而有效地降低算法的时空复杂度,最后用实例说明了新算法的可行性和高效性.Since the objects in the actual decision table are usually dynamically changed, on this condition, the concept of simplified de- cision table is introduced firstly in this paper. Then an efficient incremental updating algorithm for attributes reduction of decision table is designed with simplified binary discernibility matrix and bitmap operation based on dynamically computing a core. The new algorithm is only to validate the new object is consist with the objects in former decision table or not in the case of an new object is inserted, the former attribute reduction is dynamically updating when binary discernibility matrix is computing. For this reason, the time and space of the new algorithm is remarkably cut down. At last, an example is used to illustrate the efficiency and feasibility of the new algorithm.

关 键 词：属性约简 增量式更新 二进制差别矩阵 位图运算 算法复杂度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]