文档介绍：河北大学
硕士学位论文
前向决策树算法的研究与改进
姓名:张悦
申请学位级别:硕士
专业:计算机应用技术
指导教师:翟俊海;王熙照
20100501
摘要
摘要
决策树学****是应用最广泛的归纳推理算法之一。目前存在的决策树归纳算法大多数
是基于自顶向下的贪婪算法,它在每个结点都执行一个局部最优决策。然而,在大多数
情况下,贪婪算法构造的树不是全局最优的。对于贪婪算法的改进,前向搜索是一种众
所周知的技术。大多数人认为,前向决策树算法产生的决策树优于贪婪算法,并且搜索
深度越深其效果越好。然而,在实际中前向决策树算法得到的结果并非如此,许多文献
通过实验指出在决策树归纳过程中前向搜索往往会伤害决策树的质量。
本文以 ID3 算法为基础,研究了前向决策树算法,并与贪婪算法的建树过程进行了
对比。通过实例将前向决策树算法与经典的 ID3 算法进行了比较,结果表明针对某些特
定的问题前者在保证分类精度不降低的同时也简化了决策树。本文还重点分析了前向决
策树算法存在的缺点,正是由于算法本身存在的这些缺陷使得产生的决策树没有质量上
的提高。为了改进前向决策树算法,本文提出了一种基于属性约简的建树方法——受限
制的前向决策树算法。改进后的算法限制了前向决策树算法的搜索空间,首先使用属性
约简方法选择出一个属性子集,然后在预先选定的属性子集中使用前向搜索方法寻找最
优分裂属性进行决策树的建造。通过在部分 UCI 数据集上做实验,可以看出本文提出
的方法能减小决策树的规模,提高预测精度。
关键词决策树贪婪算法前向搜索属性约简
I
Abstract
Abstract
Decision tree learning is one of the most widely used practical methods for inductive
inference. The existing majority of the decision tree inductions are based on a top-down
greedy algorithm, which make a locally optimal decision at each node. However, in most
cases, the tree constructed by greedy algorithm is not optimal globally. Lookahead search is a
well-known technique for improving greedy algorithms. Most people believe that the
decision tree produced by lookahead search is better than greedy algorithms, and the deeper
search, the better result. But, the result obtained by lookahead search is not the case in
practice. Many literatures pointed out that lookahead would be harmful in decision tree
learning through experiments.
The decision tree algorithm based on lookahead is studied in this thesis pared
with the process of constructing tree by greedy algorithm. Compared with the classical ID3
algorithm through an example, the former can reduce the decision tree at the same time of
making sure of improving classification accuracy in some certain problem. The ings
of decision tree algorithm based on lookahead are analyzed in this paper. Due to these defects
in algorithm itself, the deci