基于冲突域渐减的属性约简算法

针对因决策表中存在不一致对象造成的约简求解错误,同时为了进一步提高约简算法求解效率, 首先,给出简化决策表的定义,并证明了简化决策表的核属性和属性约简与原始决策表的核属性和属性约简是等价的. 然后,提出冲突域的概念,分析冲突域的性质,以冲突域中冲突对象个数的变化为度量依据, 研究核属性和属性重要性的性质,同时设计相应的核属性和属性重要性求解算法;在此基础上, 设计基于冲突域渐减式属性约简算法,算法的时间和空间复杂度分别为O(|C|²|U/C|)和O(|U|). 最后的实例和实验结果表明该方法是正确的,高效的.

Attribute reduction algorithm based on conflict region decreasing

In order to resolve the errors of reduction algorithms for the existence of inconsistent objects in the decision table and enhance the efficiency of reduction algorithm, firstly, the definition of simplied decision table is proposed, and it is proved that the core and attribute reduction acquired from the method are equivalent to the core and attribute reduction of original decision table. Then, the notion and characters of the conflict region are given. The features of the core attribute and attribution importance based on the change of the number of conflict objects are studied, and the corresponding algorithms of computing core attributes and attribute importance are designed respectively. On the basis of above, an attribute reduction algorithm based on conflict region decreasing is designed, which time complexity and space complexity of the algorithm are O(|C|²|U/C|) and O(|U|). Finally, an example and the experimental results show that the algorithm is correct and efficient.