《以ID算法为例探讨数据挖掘中决策树算法的应用.ppt》由会员分享，可在线阅读，更多相关《以ID算法为例探讨数据挖掘中决策树算法的应用.ppt（32页珍藏版）》请在三一文库上搜索。
1、以ID3算法为例探讨数据挖掘中决策树算法的应用,主讲：郭佳 2013.11.28,决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的数据处理。最有影响和最早的决策树方法是由Quinlan在1986年提出的著名的基于信息熵的ID3算法。接下来主要介绍ID3算法。,决策树算法的概念,由ID3算法得到的决策树,决策树分类是一种从无次序、无规则的训练样本集中推理出决策树表示形式的分类规则的方法。它采用自顶向下的方法，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结
2、点得到结论。所以从根结点到任一个叶结点所形成的一条路径就构成了一条分类规则，叶结点所标记的类别就构成了规则的结论内容。,决策树算法的概念,数据挖掘是由可以获取的数据驱动的，其成功在很大程度上取决于数据的数量和质量。我们应从大量的企业客户数据中找到与分析问题有关的样本数据子集。这样可以减少处理的数据量，但必须保证其样本子集具有典型的代表性。然后，进行数据预处理、分析，尽可能的对问题解决的要求进一步明确化、量化。按问题要求对数据进行增删或组合生成新的变量，以体现对问题状态的有效描述。,用于分类的训练数据源组,将具体的客户年龄概化为50三个年龄段，分别代表青年、中年和老年客户，将产品价格分为高、中、
3、低三档等，具体见表1，有4个属性：客户年龄段、文化程度、销售地区、产品档次，类别是销售业绩，分为好和差两类。,以某类产品的销售记录数据为例,表1训练样本集合,ID3算法是一种根据熵减（Entropy Deduce）理论选择最优的描述属性的方法。该算法从树的根节点处的所含训练样本开始，选取一个属性来区分这些样本。对属性的每一个值产生一个分支。分支属性的相应样本子集被移到新生成的子节点上。这个算法递归地应用于每个子节点，直到一个节点上的所有样本都分区到某个类中。算法中属性选择的基础是基于使节点所含的信息熵最小化。,ID3算法原理,具体方法如下： 设S为一个包含s个数据样本的集合，类别属性可以取m个
4、不同的值，对应于m个不同的类别 ， 。 假设 为类别 中的样本个数，若要对一个给定数据对象进行分类，决策树的构造过程如下： (1)计算初始熵 其中 是任意一个数据对象属于类别 的概率，可以按 计算。,ID3算法原理,(2)属性的选择 设一个属性A取v个不同的值 。可以用属性A将集合S划分为v个子集 ，其中 包含了集合S中属性A取 值的数据样本。若属性A被选为测试属性，设 为子集 中属于 类别的样本数。则利用属性A划分当前样本集合所需要的信息（熵）可以计算如下：,ID3算法原理,其中 被当作第j个子集的权值，它是由子集中属性A取aj值的样本数之和除以S集合中的样本总数，E(A)的值越小，表示子集
5、划分结果越好。 I 是对于一个给定子集 的信息熵，计算方法为：,这样利用属性A对当前分支节点进行相应样本集合划分所获得的信息增益为： Gain(A)= -E(A) 换言之，Gain(A)被认为是根据属性 A 取值进行样本集合划分所获得的信息熵的减少量，也可以说是由于知道属性A的值而导致的熵的期望压缩。,ID3算法原理,ID3 算法计算每个属性的信息增益，并从中选择出信息增益最大的属性作为给定集合的测试属性并由此产生相应的分支节点。所产生的节点被标记为相应的属性，并根据这一属性的不同取值分别产生相应决策树分支，每个分支代表一个被划分的样本子集。,ID3算法原理,由表1可知：类标号属性有两个不同的
6、值，因此有两个不同的类（即m=2）设类C1对应于good，类C2对应于bad。类good有18个样本，类bad有8个样本。 为了计算每个属性的信息增益，先使用 计算初始信息熵为： I(s1,s2) = I(18,8)= -,ID3算法分类模型的建立,下一步，需要计算每个属性的熵，即客户年龄age、文化程度education、产品档次level和销售区域area。先看age属性，观察age的每个样本值的good、bad分布，对每个分布分别计算信息熵： 当age=50：s13=1 s23=2时，I(s13,s23)= - 如果样本按age划分，对一个给定的样本分类所需的信息熵为： E(age)=
7、=0.8192,类似的，可以得到： E(education)= =0.7669 E(level)= =0.853 E(area)=,利用上述属性对当前分支节点进行相应样本集合划分所获得的信息增益分别为： Gain(age) = I(s1,s2)- E(age) =0.895-0.8192=0.0758 Gain(education) = I(s1,s2)- E(education) =0.895-0.7769=0.1181 Gain(level) = I(s1,s2)- E(production) =0.895-0.853=0.042 Gain(area) = I(s1,s2)- E(area
8、) =0.895-0.783=0.112 由上述结果可知，属性education具有最高信息增益，因此成为决策树根节点的测试属性。如图所示：,在样本中对属性education的3个取值进行分支，3个分支对应3个子集，分别为： P11,2,3,4,15,16,17,18,19； P28,9,10,11,12,13,14,22,23,24,25,26； P3=5,6,7,20,21 其中P3的样本都为good类，因此对应分支标记为good，P1和P2的样本类别不定，因此需要对P1子集和P2子集分别递归调用ID3算法。,在P1中可求出余下的三个属性:age、level、area的信息增益。,因为ar
9、ea属性的信息增益最大，所以以它为该分支的节点，再向下分支，类似方法处理P2，最后得到的决策树如下所示：,输入：训练样本samples, 表示有离散值属性,候选属性 的集合attribute_list 输出：一棵决策树 算法： 1.创建节点N； 2.if samples都在同一个类C then 3.返回N作为叶节点，以类C标记 4.if attribute_list为空then 5.返回N作为叶节点，标记为samples中最普遍的类,ID3算法描述,6.选择attribute_list中具有最高信息增益的属性 branch_attribute 7.标记节点N为branch_attribute
10、8.for each branch_attribute中已知的值ai 9.由节点N长出一个条件为branch_attribute=ai 的分支 10.设si是samples中branch_attribute=ai的样本集合 11.如果si为空 then 12.加上一个树叶，标记为samples中最普遍的类 13.else 加上一个由 generate_decision(si,attribute_list-branch_attribute)返回的节点,ID3算法描述,首先确定所要生成的决策树的相关分类 C，如“销售业绩good”，销售业绩bad”。 1.树以代表训练样本的单个节点开始。 2.若样
11、本都属于 C，则该节点成为叶，并标记该节点概率权值为1。 3.否则，算法使用称为“信息增益”的基于熵的度量作为启发信息，选择能够最好的将样本分类的属性。该属性成为节点的“测试”或“分支”属性。 4.对于测试属性的每个已知值，创建一个分支，并根据此划分样本。,ID3算法说明,5.算法使用同样的过程，递归的形成每个划分上的样本决策树。一旦一个属性出现在一个节点上，就不会在该分支再次出现。 6.递归划分步骤当且仅当下列条件之一成立时停止： (1)给定节点的所有样本都属于 C 或者都不属于 C。此时当前节点成为叶子节点，并标记该节点的概率权值为1或0。 (2)没有剩余属性可用来进一步划分样本。此时当前
12、节点成为叶子节点，并标记该节点的概率权值为C类样本在样本中所占比例。 (3)分支 test_attributeai 没有样本。在这种情况下，以samples中的多数类创建一个树叶。,ID3算法说明,决策树很容易转换成分类规则，并以 IFTHEN 形式的分类规则表示。对从根到树叶的每条路径创建一个规则。IFTHEN 规则易于理解，特别是当给定的树比较大的时候。我们用IF-THEN形式的分类规则提取决策树中表示的知识，企业可以从中发现销售规律，以便制定未来更有效的营销策略。,由决策树提取分类规则,1.IF education= “H” AND area= “I” OR(area= “”) AND
13、age= “=50” OR(age= “31-50” AND area= “”) THEN achievement= “bad”,分类规则,前三条分类规则说明该企业的高档产品对于本地区受过高等教育的年轻客户的吸引力较大，低档产品对该类客户的吸引力较小；该企业的各档次产品对于本地受过高等教育的中年客户吸引力均较大。,分类规则说明,后两条规则说明企业的高档产品对于受过中等教育的年轻客户或者本地的中年客户吸引力较大；高档产品在受过中等教育的老年客户或者外地区的中年客户中不很受欢迎。因此该企业可以加大高档产品在年轻客户中的宣传以及各档次产品在本地受过高等教育的中年客户中的宣传，他们是该企业的一个重点客
14、户群。在外地区针对受过中、高等教育的中年及老年客户的销售业绩还有待提高。该企业的产品对于教育程度较低的客户群销售业绩比较平稳。,分类规则说明,ID3 算法的理论清晰，方法简单，学习能力较强，但是 ID3 算法也有其不足之处，主要有以下几点： ID3 算法利用信息增益作为分类评价函数来选取最优属性，而这种选择标准容易倾向于选择取值较多的属性，但取值较多的属性并不都是最重要的属性。 ID3算法只能处理具有离散值的属性，不适合处理连续值属性。 ID3 算法是非增量式算法。对于增量式学习任务来说，由于 ID3 不能增量地接受训练实例，每增加一次实例都必须抛弃原有决策树，重新构造新的决策树，造成较大开销。 ID3算法没有考虑训练集中的缺值问题。,ID3算法优缺点,