基于冲突域渐减的属性约简算法  

Attribute reduction algorithm based on conflict region decreasing

作　　者：葛浩[1,2] 李龙澍[1,3] 杨传健[4] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,合肥230039 [2]滁州学院机械与电子工程学院,滁州239012 [3]安徽大学计算机科学与技术学院,合肥230039 [4]滁州学院计算机与信息工程学院,滁州239012

出　　处：《系统工程理论与实践》2013年第9期2371-2380,共10页Systems Engineering-Theory & Practice

基　　金：安徽省自然科学基金(1308085QF114);安徽高校省级自然科学研究项目(KJ2012A212;KJ2013A015);安徽省高校省级优秀青年人才基金(2011SQRL123);滁州学院科学研究项目(2011KJ003Z)

摘　　要：针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率,首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的.然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据,研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上,设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O（｜C｜-2｜U/C｜）和O（｜U｜）.最后的实例和实验结果表明该方法是正确的,高效的.In order to resolve the errors of reduction algorithms for the existence of inconsistent objects in the decision table and enhance the efficiency of reduction algorithm, firstly, the definition of simplied decision table is proposed, and it is proved that the core and attribute reduction acquired from the method are equivalent to the core and attribute reduction of original decision table. Then, the notion and characters of the conflict region are given. The features of the core attribute and attribution importance based on the change of the number of conflict objects are studied, and the corresponding algorithms of computing core attributes and attribute importance are designed respectively. On the basis of above, an attribute reduction algorithm based on conflict region decreasing is designed, which time complexity and space complexity of the algorithm are O（｜C｜-2｜U/C｜） and O（｜U｜）. Finally, an example and the experimental results show that the algorithm is correct and efficient.

关 键 词：粗糙集 正区域 冲突域 属性约简 核属性 

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