代数约简的条件信息熵表示及其高效约简算法

Conditional Information Entropy Representation of Algebraic Reduction and its Efficient Algorithm

给出如何保持正区域不变的语义分析,提出一种修正条件信息熵计算公式,证明保持修正条件信息熵不变与保持正区域不变相互等价。在此基础上,给出代数约简概念的修正条件信息熵表示。给出反例说明修正条件信息熵不具有单调性,导致没法给出自底向上的启发式约简算法,证明了代数协调集中不可删除属性的不可逆性质,提出一种自顶向下直接删除属性的高效约简算法。它从所有条件属性集出发,逐步删除不必要的属性,只需遍历各属性一次,即可保证得到原始决策表的一个代数约简。数值算例和实验验证了该算法的正确性和高效性。

A semantic analysis on how to keep positive region unchanged was given. An improved conditional informa- tion entropy was proposed. It was proved that remaining the modified conditional information entropy unchanged and re- maining positive region unchanged are equivalent. Therefore, some main concepts of algebraic reduction were described by the revised conditional information entropy. However, a counter example illustrates that its monotonicity does not hold, which means a heuristic reduction algorithm can not be constructed based on bottom-up. Any attribute in an alge- braic consistent set is not irreversible if it is checked unsuppressible. An efficient algorithm based on top-down was pro- posed, which starts from condition attribute set, removes the unnecessary attribute step by step. It is finally guaranteed to obtain an algebraic reduction by traversing the attributes only once. Numerical example and the experimental results show that the algorithm is valid and efficient.