文档介绍：决策树算法的改进摘要:决策树算法是数据挖掘中非常活跃的研究领域。通过对数据挖掘中决策树的基本思想进行阐述,讨论了决策树经典算法(ID3算法)的计算复杂度问题,并针对这一问题提出了利用统计理论知识和条件概率的思想来改进构造决策树的算法。实验表明,这种构造决策树算法的计算复杂度明显优于传统的算法,其效率也有很大的提高。关键词:决策树;算法;ID3;改进图书分类号:TP301文献标识码:A文章编号:1009-3044(2008)15-20ppp-0c TheImprovementofDecisionTreeAlgorithm ZHANNing,XUJie (XinyangVocationalandTechnicalCollege,Xinyang464000,China) Abstract:,plexityproblemofclassicDecisionTreeAlgorithm(ID3algorithm),,itsefficiencyalsoimprovedgreatly. Keywords:DecisionTree;Algorithm;ID3;Improvement 随着信息技术的飞速发展,数据量以惊人的速度增长。“丰富的数据与贫乏的知识”之间的矛盾日见突出,各个领域的人们迫切需要有一种能够从这些超大数据中寻求有用信息的工具,数据挖掘就是在这种需要下出现的。目前,决策树已成为一种重要的数据挖掘方法,是1986年有Quinlan提出的,很多专家学者对决策树和ID3算法在分类过程中有偏向于取值叫多的属性的缺点,因此人们开始怀疑ID3算法的信息熵的完美性,并对其提出了改进。 1决策树概念所谓决策树,就是在对数据进行决策分类时利用树的结构将数据记录进行分类,其中树的一个叶结点就代表符合某个条件的属性集,根据属性的不同取值建立决策树的各个分支,随后递归的构造每个子节点的子树。由于决策树结构简单便于人们认识理解以及决策树不需要额外的数据训练,因此决策树是数据挖掘中常用的一种分类方法,而现在最常用的是基于信息熵的算法。 2ID3算法(IterativeDichotomizer3) Quinlan的ID3算法是国际上公认的最早有影响的决策树算法。ID3算法是基于信息熵的决策树算法,它是根据属性集的取值分类。ID3的优缺点:ID3采用自顶向下不回溯的策略搜索全部的属性空间,它建立决策树的算法简单,深度小,分类速度快。但是ID3对于大的属性集则执行效率下降快,准确性降低,并且学****能力低下。 3改进的决策树算法(MetricBasedDecisionTree,MBDT) 对任何数量的训练集,总是能找到相应的多个线性判别函数把它分类,但是这样