基于布尔冲突矩阵的不完备决策表快速属性约简算法  

FAST ATTRIBUTE REDUCTION ALGORITHM FOR INCOMPLETE DECISION TABLE BASED ON BOOLEAN CONFLICT MATRIX

作　　者：章晨光[1] 徐章艳[1] 周建华[1] 

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

出　　处：《计算机应用与软件》2014年第8期257-260,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(60963008);广西自然科学基金项目(2011GXNSFA018163)

摘　　要：在不完备决策表中,针对近年来提出属性约简算法的时间复杂度不理想的情况,通过对已有计算容差类方法和引入的冲突域概念的研究,定义了布尔冲突矩阵并设计出该矩阵的快速属性约简算法。同时,在布尔冲突矩阵中定义了一种属性重要性度量的方法,并从理论上证明了该矩阵的属性约简与正区域的属性约简是等价的。经过对该属性约简算法的分析,其时间复杂度为max{O(|K‖C‖U|),O(|C|2|POSC(D)‖U|)}(|K|=max{|TC(x)‖x∈U}),空间复杂度为O(|C|2|POSC(D)‖U|)。最后通过实例和实验分析,说明该算法的有效性和可行性。In incomplete decision table,the time complexity of attribute reduction algorithm presented in recent years is unsatisfactory.Aiming at this situation,by studying existing tolerance class calculation method and the introduced conflict domain concept,we define a Boolean conflict matrix and design the fast attribute reduction algorithm for the matrix. Meanwhile,in Boolean conflict matrix a metric method for attribute importance is defined. In succession,we prove theoretically that the attribute reduction of the matrix is equivalent to the attribute reduction of the positive region. Through analysing the attribute reduction algorithm,it is known that its time complexity is max{O（ ｜ K‖C‖U ｜）,O（ ｜ C ｜2｜ POSC（D）‖U｜）}（｜K｜ = max{｜TC（x）‖x∈U}）,and the space complexity is O（｜C｜2｜ POSC（D）‖U｜）. Finally,an example and experimental analysis are used to illustrate the effectiveness and feasibility of the algorithm.

关 键 词：不完备决策表 属性约简 容差类 冲突域 布尔冲突矩阵 

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