一种高效的核属性动态更新算法  

Efficient Dynamic Updating Algorithm of the Computation of Core in Decision Table

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

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

出　　处：《计算机科学》2012年第7期210-214,共5页Computer Science

基　　金：国家重点基础研究发展计划项目(973计划)(2009CB522701);国家自然科学基金项目(60963008;60875029);科技部创新方法专项项目(2010IM020900);广西自然科学基金项目(2011GXNSFA018163)资助

摘　　要：针对决策表中对象动态删除的情况,研究了核属性的动态更新问题。首先引入了简化决策表的概念,剔除了大量重复冗余的对象,然后详细分析了当决策表删除对象时核属性的动态更新机制,并将逐层细化的方法应用到核属性的动态更新中,避免了许多不必要的重复计算。在此基础上,设计了一种无需存储差别矩阵的核属性动态更新算法。当决策表有对象删除时,该算法只需扫描一遍变化后的决策表,便可快速对核属性进行动态更新。最后,通过实例分析和实验比较验证了算法的可行性和有效性。The dynamic updating algorithm of computation of core was discussed in the decision table. Aiming at this situation, the concept of the simplified decision table was first introduced, and a large number of repeated objects in deci- sion table were deleted effectively, what＇s more, some dynamic updating mechanisms were analyzed when the objects were deleted in original decision table. At the same time, in order to avoid needless repeated computation, multi-level hi- erarchical model was applied to dynamic updating process. On this condition, an efficient dynamic updating algorithm for computing core was proposed, which does not store discernibility matrix. The algorithm only scans updated decision ta ble to compute core when the objects are dynamically deleted. At last, theoretical analysis and experimental results show that the algorithm is feasible and effective.

关 键 词：粗糙集理论 核属性 动态更新 决策表 算法复杂度 

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