一种新的简化ID3决策树的算法  

New algorithm of simplifying the ID3 decision tree

作　　者：吴宣为[1] 史斌宁[1] 

机构地区：[1]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《合肥工业大学学报（自然科学版）》2004年第12期1565-1569,共5页Journal of Hefei University of Technology：Natural Science

摘　　要：决策树简化是决策树学习算法中的一个重要分支。文章以 ID3算法构造的决策树为基础 ,提出了一种高效的简化决策树的算法。算法先序遍历由 ID3构造出来的决策树的各个节点并对其子树进行比较 ,如果各子树的属性都相同而且存在某些相应的分支对于各子树完全相同 ,则改变决策树中相应属性的层次关系并把相同的分支分别合并起来。算法减少了决策树的深度、宽度与叶子数目 ,降低了决策树的规模。尤其对于逻辑表达式的归纳学习 ,简化之后的决策树要明显优于原决策树。Decision tree simplification is a significant branch in the study of decision-tree learning algorithms. Based on the decision tree constructed with the ID3 algorithm,a new and efficient algorithm is presented to simplify the decision tree. In the algorithm,each node of the ID3 decision tree is traversed in preorder,and then its subtrees are compared and, if the root attributes of each subtree are the same and some corresponding branches of all the subtrees are identical, the hierarchical relationship of the correlative attributes in the decision tree can be changed and the identical branches can be merged respectively. The algorithm reduces the depth and the width of the decision tree and the number of leaves and thus decreases the tree size. Especially for the inductive learning of logic expressions, the decision tree after being simplified is apparently better than the original one.

关 键 词：简化决策树 先序遍历 子树比较 分支合并 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]