决策树学习ppt课件

1、一.例如学习 例如学习也称实例学习, 它是一种归纳学习。例如学习是从假设干实例(包括正例和反例)中归纳出普通概念或规那么的学习方法。 第一个拱桥的语义网络 第二个拱桥的语义网络. 学习程序归纳出的语义网络 拱桥概念的语义网络 .例 1 假设例如空间中有桥牌中同花概念的两个例如: 例如1： 花样(c1，梅花)花样(c2，梅花)花样(c3，梅花)花样(c4，梅花)同花(c1，c2，c3，c4) 例如2： 花样(c1，红桃)花样(c2，红桃)花样(c3，红桃)花样(c4，红桃)同花(c1，c2，c3，c4) 关于同花的普通性规那么: 花样(c1，x)花样(c2，x)花样(c3，x)花样(c4，x)同

2、花(c1，c2，c3，c4).对于这个问题可采用通常的曲线拟合技术，归纳出规那么： (x，y，2x+3y+1)即 z2x3y1例2 假设例如空间存放有如下的三个例如： 例如1：(0，2，7) 例如2：(6，-1，10) 例如3：(-1，-5，-10) 这是三个3维向量，表示空间中的三个点。现要求求出过这三点的曲线。.二.决策树学习 1什么是决策树 决策树(decision tree)也称断定树，它是由对象的假设干属性、属性值和有关决策组成的一棵树。其中的节点为属性普通为言语变量，分枝为相应的属性值普通为言语值。从同一节点出发的各个分枝之间是逻辑“或关系；根节点为对象的某一个属性；从根节点到每一

3、个叶子节点的一切节点和边，按顺序串连成一条分枝途径，位于同一条分枝途径上的各个“属性-值对之间是逻辑“与关系，叶子节点为这个与关系的对应结果，即决策。. 决策树表示图 .例3 以下图所示是机场指挥台关于飞机起飞的简单决策树。 .例4 以下图是一个描画“兔子概念的决策树。 .2. 怎样学习决策树 决策树学习的根本方法和步骤：首先，选取一个属性，按这个属性的不同取值对实例集进展分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进展画树。然后，调查所得的每一个子类，看其中的实例的结论能否完全一样。假设完全一样，那么以这个一样的结论作为相应分枝途径末端的叶子节点；否那么，选取一个非父节点

4、的属性，按这个属性的不同取值对该子集进展分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进展画树。如此继续，直到所分的子集全都满足：实例结论完全一样，而得到一切的叶子节点为止。 . 决策树学习举例 设表1 所示的是某保险公司的汽车驾驶保险类别划分的部分事例。我们将这张表作为一个实例集，用决策树学习来归纳该保险公司的汽车驾驶保险类别划分规那么。 .表1 汽车驾驶保险类别划分实例集 . 将实例集简记为S=(1,C), (2,C), (3,C), (4,B), (5,A), (6,A), (7,C), (8,B), (9,A), (10,A), (11,B), (12,B) 其中每个

5、元组表示一个实例，前面的数字为实例序号，后面的字母为实例的决策项保险类别。 用 “小、“中、“大 分别代表 “21、“21且25、“25 这三个年龄段。. 对于S，我们按属性“性别的不同取值将其分类。由表1 可见，这时S应被分类为两个子集：S1= (3,C), (4,B), (7,C), (8,B), (11,B), (12,B)S2=(1,C), (2,C), (5,A), (6,A), (9,A), (10,A) 于是，我们得到以性别作为根节点的部分决策树见以下图。. 决策树生成过程 . 决策树生成过程 . 决策树生成过程 .最后生成的 决策树 . 由决策树所得的规那么集： 女性且年龄在2

6、5岁以上，那么给予A类保险； 女性且年龄在21岁到25岁之间，那么给予A类保险； 女性且年龄在21岁以下，那么给予C类保险； 男性且年龄在25岁以上，那么给予B类保险； 男性且年龄在21岁到25岁之间且未婚，那么给予C类保险； 男性且年龄在21岁到25岁之间且已婚，那么给予B类保险； 男性且年龄在21岁以下且未婚，那么给予C类保险； 男性且年龄在21岁以下且已婚，那么给予B类保险。. 3. ID3算法 ID3算法是一个经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的根本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性

7、，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。.1信息熵和条件熵 设S是一个实例集(S也可以是子实例集),A为S中实例的一个属性。H(S)和H(S|A)分别称为实例集S的信息熵和条件熵, 其计算公式如下: 其中,i(i=1, 2, , n)为S中各实例一切能够的结论；lb即log2。 其中,ak(k=1, 2, , m)为属性A的取值, Sak为按属性A对实例集S进展分类时所得诸子类中与属性值ak对应的那个子类。. 2基于条件熵的属性选择.按性别划分, 实例集S被分为两个子类: S男 =(3,C), (4,B), (7,C), (8,B), (11,B), (12,B)S女 =(1,C), (2,C), (5,A), (6,A), (9,A), (10,A) 从而, 对子集S男而言,