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

在不完备决策表中,针对近年来提出属性约简算法的时间复杂度不理想的情况,通过对已有计算容差类方法和引入的冲突域概念的研究,定义了布尔冲突矩阵并设计出该矩阵的快速属性约简算法。同时,在布尔冲突矩阵中定义了一种属性重要性度量的方法,并从理论上证明了该矩阵的属性约简与正区域的属性约简是等价的。经过对该属性约简算法的分析,其时间复杂度为max{O(|K‖C‖U|),O(|C|2|POSC(D)‖U|)}(|K|=max{|TC(x)‖x∈U}),空间复杂度为O(|C|2|POSC(D)‖U|)。最后通过实例和实验分析,说明该算法的有效性和可行性。

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