基于冲突域的高效属性约简算法  

An Efficient Attribute Reduction Algorithm Based on Conflict Region

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

机构地区：[1]滁州学院机械与电子工程学院,安徽滁州239012 [2]安徽大学计算机科学与技术学院,合肥230039 [3]滁州学院计算机与信息工程学院,安徽滁州239012

出　　处：《计算机学报》2012年第2期342-350,共9页Chinese Journal of Computers

基　　金：安徽省自然科学基金(050420204;090412054);安徽高等学校省级自然科学研究项目基金(KJ2011Z276);安徽省高等学校省级优秀青年人才基金(2011SQRL123);滁州学院自然科学研究项目基金(2010kj014B;2011kj003Z)资助~~

摘　　要：引入冲突域的概念,研究冲突域的性质.以冲突域中冲突对象数目的变化为度量标准,给出核属性和属性重要性的计算方法,并设计了快速求解核属性和属性重要性的算法.在此基础上,给出高效属性约简算法,该算法以核属性为初始约简集,以属性重要性为启发式信息.在最坏情况下,算法的时间复杂度为O(|C|2|U|),空间复杂度为O(|U|);实验结果表明,该算法是正确的、高效的.The notion of the conflict region is given, and natures of the conflict region are researched. The features of the core attributes and attribution importance, which are based on the change of the number of conflict objects, are studied. The algorithms for computing core attrib- utes and attribute significance are designed. Based on these conditions, using core attributes as the initial reduction sets and the significance of attribute as heuristic information, an efficient attribute reduction algorithm is proposed. In the worst case, the time complexity and space complexity of the algorithm are O（ ｜ C ｜2 ｜ U ｜ ） and O（ ｜U ｜ ） respectively. The experimental results show that the algorithm is correct and efficient.

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

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