摘要
决策树简化是决策树学习算法中的一个重要分支。文章以 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.
出处
《合肥工业大学学报（自然科学版）》
CAS
CSCD
2004年第12期1565-1569,共5页
Journal of Hefei University of Technology：Natural Science
关键词
简化决策树
先序遍历
子树比较
分支合并
simplifying of decision trees
preorder traversal
subtree comparison
merging branch
