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

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

在不完备决策表中,针对近年来提出属性约简算法的时间复杂度不理想的情况,通过对已有计算容差类方法和引入的冲突域概念的研究,定义了布尔冲突矩阵并设计出该矩阵的快速属性约简算法。同时,在布尔冲突矩阵中定义了一种属性重要性度量的方法,并从理论上证明了该矩阵的属性约简与正区域的属性约简是等价的。经过对该属性约简算法的分析,其时间复杂度为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.