一种基于新的条件信息熵的高效知识约简算法

An Efficient Knowledge Reduction Algorithm Based on New Conditional Information Entropy

分析了在知识约简过程中现有条件信息熵的不足,给出一种新的条件信息熵,由此定义新的属性重要性.将其与基于正区域和基于现有条件信息熵的属性重要性进行比较,结果表明新的属性重要性是一种更准确、更全面的启发信息.以新的属性重要性为启发信息设计约简算法,并给出计算新的条件信息熵的高效算法.理论分析和实验结果表明,与基于现有条件信息熵的约简算法相比,该约简算法时间复杂度较低,且在搜索最小或次优约简方面更优.

The disadvantages of the current conditional information entropy are analyzed. A new conditional information entropy is proposed. Based on this entropy the new significance of an attribute is defined and compared with two significances of this attribute based on the positive region and the current conditional information entropy respectively. The result shows that when used as heuristic information, the proposed significance of the attribute is better than the other two. Finally, a heuristic algorithm for knowledge reduction is designed and an efficient algorithm for computing conditional information entropy is proposed. Theoretical analysis and experimental results show that time complexity of this reduction algorithm is less than that of the algorithm based on the current conditional information entropy. Also, this reduction algorithm is more capable of finding the minimal or optimal reducts.