文档介绍：决策树的学****如果学****的任务是对一个大的例子集作分类概念的归纳定义,而这些例子又都是用一些无结构的属性值对来表示,则可以采用示例学****方法的一个变种──决策树学****其代表性的算法是昆兰( , 1986 )提出的 ID3 。?决策树(Decision Tree) 一种描述概念空间的有效的归纳推理办法。基于决策树的学****方法可以进行不相关的多概念学****具有简单快捷的优势,已经在各个领域取得广泛应用。?决策树学****是以实例为基础的归纳学****从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。?概念分类学****算法:来源于– Hunt,Marin 和 Stone 于 1966 年研制的 CLS 学****系统,用于学****单个概念。– 1979 年, . Quinlan 给出 ID3 算法,并在 1983 年和 1986 年对 ID3 进行了总结和简化,使其成为决策树学****算法的典型。– Schlimmer 和 Fisher 于 1986 年对 ID3 进行改造,在每个可能的决策树节点创建缓冲区,使决策树可以递增式生成,得到 ID4 算法。– 1988 年, Utgoff 在 ID4 基础上提出了 ID5 学****算法,进一步提高了效率。– 1993 年, Quinlan 进一步发展了 ID3 算法,改进成算法。–另一类决策树算法为 CART ,与不同的是, CART 的决策树由二元逻辑问题生成,每个树节点只有两个分枝,分别包括学****实例的正例与反例。?其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶节点中的实例都属于同一类。?决策树学****采用的是自顶向下的递归方法。?决策树的每一层节点依照某一属性值向下分为子节点,待分类的实例在每一节点处与该节点相关的属性值进行比较,根据不同的比较结果向相应的子节点扩展,这一过程在到达决策树的叶节点时结束,此时得到结论。?从根节点到叶节点的每一条路经都对应着一条合理的规则, 规则间各个部分(各个层的条件)的关系是合取关系。整个决策树就对应着一组析取的规则。?决策树学****算法的最大优点是,它可以自学****在学****的过程中,不需要使用者了解过多背景知识,只需要对训练例子进行较好的标注,就能够进行学****如果在应用中发现不符合规则的实例,程序会询问用户该实例的正确分类,从而生成新的分枝和叶子,并添加到树中。?树是由节点和分枝组成的层次数据结构。节点用于存贮信息或知识,分枝用于连接各个节点。树是图的一个特例,图是更一般的数学结构, 如贝叶斯网络。?决策树是描述分类过程的一种数据结构,从上端的根节点开始,各种分类原则被引用进来,并依这些分类原则将根节点的数据集划分为子集,这一划分过程直到某种约束条件满足而结束。根结点个子大可能是松鼠可能是老鼠可能是大象在水里会吱吱叫鼻子长脖子长个子小不会吱吱叫鼻子短脖子短可能是长颈鹿在陆地上可能是犀牛可能是河马?可以看到,一个决策树的内部结点包含学****的实例,每层分枝代表了实例的一个属性的可能取值,叶节点是最终划分成的类。如果判定是二元的,那么构造的将是一棵二叉树,在树中每回答一个问题就降到树的下一层,这类树一般称为 CART ( Classification And Regression Tree )。?判定结构可以机械的转变成产生式规则。可以通过对结构进行广度优先搜索,并在每个节点生成“ IF… THEN ”规则来实现。如图 6-13 的决策树可以转换成下规则: IF “个子大” THEN IF “脖子短” THEN IF “鼻子长” THEN 可能是大象形式化表示成可能是大象鼻子长脖子短个子大????构造一棵决策树要解决四个问题: –收集待分类的数据,这些数据的所有属性应该是完全标注的。–设计分类原则,即数据的哪些属性可以被用来分类,以及如何将该属性量化。–分类原则的选择,即在众多分类准则中,每一步选择哪一准则使最终的树更令人满意。–设计分类停止条件,实际应用中数据的属性很多,真正有分类意义的属性往往是有限几个,因此在必要的时候应该停止数据集分裂: ?该节点包含的数据太少不足以分裂, ?继续分裂数据集对树生成的目标(例如 ID3 中的熵下降准则)没有贡献, ?树的深度过大不宜再分。?通用的决策树分裂目标是整棵树的熵总量最小,每一步分裂时,选择使熵减小最大的准则,这种方案使最具有分类潜力的准则最先被提取出来?证据由属性值对表示–证据由固定的的属性和其值表示,如属性(温度),值(热)最简单的学****情况时每个属性拥有少量的不相关的值。?目标函数有离散输出值–决策树分配一个二值的树,很容易扩展成为多于两个的输出值。?需要不相关