基于属性间交互信息的ID3算法  

An Extended Heuristic Algorithm to ID3 Based on the Mutual Information between Attributes

作　　者：谢竞博[1] 王熙照[1] 

机构地区：[1]河北大学数学与计算机学院,保定071002

出　　处：《计算机工程与应用》2004年第30期93-94,150,共3页Computer Engineering and Applications

基　　金：河北省自然科学基金资助项目(编号:603137)

摘　　要：启发式算法是决策树研究的核心。文中分析了最常见的一种决策树归纳启发式算法即ID3算法的不足,给出了一个改进版本,它在选择测试属性时不仅要求该属性带来的信息增益尽可能大,而且要求其与同一分支上已经使用过的各属性之间的交互信息尽可能小,从而避免了对冗余属性的选择,实现信息熵的真正减少。分析及实验结果表明,与ID3算法相比,该算法能构造出更优的决策树。Heuristic algorithm is the kernel in the research on decision tree.The paper analyzes the shortcomings of the most popular heuristic algorithm for generating decision tree,ie.ID3,and gives an extended version to it,which demandsthat the selected attribute can bring more information gain as well as less mutual information between it with others on its ancestor nodes.The algorithm can avoid selecting the redundant attributes and achieve the real reduce in entropy.Analysis and experiments indicate:compared with ID3,the extended heuristic algorithm can construct a better tree.

关 键 词：决策树 ID3 启发式算法 交互信息 

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