决策树算法.ppt

就业工场数据中心第七章第七章决策树和决策规则决策树和决策规则本章目标本章目标??分析解决分类问题的基于逻辑的方法的特分析解决分类问题的基于逻辑的方法的特性性. . ??描述决策树和决策规则在最终分类模型中描述决策树和决策规则在最终分类模型中的表述之间的区别的表述之间的区别. . ??介绍介绍 算法算法. . ??了解采用修剪方法降低决策树和决策规则了解采用修剪方法降低决策树和决策规则的复杂度的复杂度. . 1 1就业工场数据中心??决策树和决策规则是解决实际应用中分类决策树和决策规则是解决实际应用中分类问题的数据挖掘方法。问题的数据挖掘方法。??一般来说,分类是把数据项映射到其中一一般来说,分类是把数据项映射到其中一个事先定义的类中的这样一个学习函数的个事先定义的类中的这样一个学习函数的过程。由一组输入的属性值向量过程。由一组输入的属性值向量( (也叫属性也叫属性向量向量) )和相应的类,用基于归纳学习算法得和相应的类,用基于归纳学习算法得出分类。出分类。??学习的目标是构建一个分类模型,通常也学习的目标是构建一个分类模型,通常也叫分类器。它可以根据有效的属性输入值叫分类器。它可以根据有效的属性输入值预测一些实体预测一些实体( (所给样本所给样本) )的类。是一个在样的类。是一个在样本其他属性已知的情况下预测另外一个属本其他属性已知的情况下预测另外一个属性性( (样本的类样本的类) )的模型的模型( (分类的结果分类的结果) )。。 2 2就业工场数据中心 决策树决策树??从数据中生成分类器的一个特别有效的方从数据中生成分类器的一个特别有效的方法是生成一个决策树。它是一种基于逻辑法是生成一个决策树。它是一种基于逻辑的方法,通过一组输入的方法,通过一组输入- -输出样本构建决策输出样本构建决策树的有指导学习方法。树的有指导学习方法。??决策树包含属性已被检验的节点,一个节决策树包含属性已被检验的节点,一个节点的输出分枝和该节点的所有可能的检验点的输出分枝和该节点的所有可能的检验结果相对应。结果相对应。 3 3就业工场数据中心??图图 7-2 7-2 是一个简单的决策树。该问题有两个是一个简单的决策树。该问题有两个属性属性 X,Y X,Y 。。所有属性值所有属性值 X>1 X>1 和和 Y>B Y>B 的样本属的样本属于类于类 2 2。不论属性。不论属性 Y Y的值是多少,值的值是多少,值 X <1 X <1 的的样本都属于类样本都属于类 1 1。。 4 4就业工场数据中心??对于树中的非叶节点,可以沿着分枝对于树中的非叶节点,可以沿着分枝继续分区样本,每一个节点得到它相继续分区样本,每一个节点得到它相应的样本子集。应的样本子集。??生成决策树的一个著名的算法是生成决策树的一个著名的算法是 Quinlan Quinlan 的的 ID3 ID3 算法, 算法, 是它改进版。是它改进版。 5 5就业工场数据中心?? ID3 ID3 算法的基本思路: 算法的基本思路: 1. ,选从树的根节点处的所有训练样本开始,选取一个属性来划分这些样本。对属性的每取一个属性来划分这些样本。对属性的每一个值产生一分枝。分枝属性值的相应样一个值产生一分枝。分枝属性值的相应样本子集被移到新生成的子节点上。本子集被移到新生成的子节点上。 2. ,直到这个算法递归地应用于每个子节点,直到一个节点上的所有样本都分区到某个类中。一个节点上的所有样本都分区到某个类中。 3. 。分类规则。 6 6就业工场数据中心??该算法的关键性决策是对节点属性值的选该算法的关键性决策是对节点属性值的选择。择。 ID3 ID3 和和 算法的属性选择的基础是基算法的属性选择的基础是基于使节点所含的信息熵最小化。于使节点所含的信息熵最小化。??基于信息论的方法坚持对数据库中一个样基于信息论的方法坚持对数据库中一个样本进行分类时所做检验的数量最小。本进行分类时所做检验的数量最小。 ID3 ID3 的的属性选择是根据一个假设,即:决策树的属性选择是根据一个假设,即:决策树的复杂度和所给属性值表达的信息量是密切复杂度和所给属性值表达的信息量是密切相关的。基于信息的试探法选择的是可以相关的。基于信息的试探法选择的是可以给出最高信息的属性,即这个属性是使样给出最高信息的属性,即这个属性是使样本分类的结果子树所需的信息最小。本分类的结果子树所需的信息最小。 7 7就业工场数据中心 算法:生成一个决策树算法:生成一个决策树??