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

An Efficient Knowledge Reduction Algorithm Based on New Conditional Information Entropy

作　　者：刘启和[1] 李凡[1] 闵帆[1] 叶茂[1] 杨国纬[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《控制与决策》2005年第8期878-882,共5页Control and Decision

基　　金：国家自然科学基金(天元)项目(A0324638)

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

关 键 词：ROUGH集理论 知识约简 条件信息熵 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]