基于冲突的增量式核属性更新算法  

Incremental updating algorithm of the computation of core based on the collision

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

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

出　　处：《控制与决策》2011年第7期984-990,共7页Control and Decision

基　　金：安徽省自然科学基金项目(090412054);安徽高校省级自然科学研究项目(KJ2010B137);安徽省高等学校省级优秀青年人才基金项目(2010SQRL138)

摘　　要：目前的增量式核属性更新算法大多建立在可分辨矩阵的基础上,不利于大数据集处理,而且算法的效率也不理想.为了克服上述不足,在改进的基于冲突域求核算法的基础上,提出了基于冲突的增量式核属性求解算法.该算法不需要创建可分辨矩阵,当有新对象加入时,对决策表仅需进行一次遍历便可完成核属性增量更新.算法的时间和空间复杂度分别为O(|C‖U′|)和O(|C|).理论分析和实验结果均表明,所提出的算法是可行且高效的.At present,a lot of incremental algorithms of updating the core are based on the distinguishable matrix,which are disadvantageous to the larger database,and the efficiency of algorithms is not ideal.To overcome above shortcomings,on the basis of the improved algorithm for computing the core based on the conflict region,the algorithm of incremental computing core based on the collision is proposed.The algorithm is unnecessary to create the distinguishable matrix and only needs to traverse the decision table one time,when a new object is added into the decision table.The time complexity and space complexity of the algorithm are O（｜C｜｜U＇｜）and O（｜C｜）respectively.Both of theoretical analysis and experimental results show that the algorithm is effective and efficient.

关 键 词：粗糙集 冲突域 核属性 增量计算 

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