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

摘要

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