决策树学习相关资料

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一.,示例学习,示例学习也称实例学习, 它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。,第一个拱桥的语义网络,第二个拱桥的语义网络,学习程序归纳出的语义网络,拱桥概念的语义网络,例 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)同花(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 下,图所示是机场指挥台关于飞机起飞的简单决策树。,例,4,下,图是一个描述“兔子”概念的决策树。,2.,怎样学习决策树,决策树学习的基本方法和步骤：,首先，选取一个,属性,，按这个属性的不同取值对实例集进行分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进行画树。,然后，考察所得的每一个子类，看其中的实例的结论是否完全相同。如果完全相同，则以这个相同的结论作为相应分枝路径末端的叶子节点；否则，选取一个非父节点的属性，按这个属性的不同取值对该子集进行分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进行画树。,如此继续，直到所分的子集全都满足：实例结论完全相同，而得到所有的叶子节点为止。,决策树学习举例,设表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),其中每个元组表示一个实例，前面的数字为实例序号，后面的字母为实例的决策项保险类别。,用 “小”、“中”、“大”,分别代表,“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),于是，我们得到以性别作为根节点的部分决策树（见下图）。,决策树生成过程,决策树生成过程,决策树生成过程,最后生成的,决策树,由决策树所得的规则集,：, 女性且年龄在25岁以上，则给予A类保险；, 女性且年龄在21岁到25岁之间，则给予A类保险；, 女性且年龄在21岁以下，则给予C类保险；, 男性且年龄在25岁以上，则给予B类保险；, 男性且年龄在21岁到25岁之间且未婚，则给予C类保险；, 男性且年龄在21岁到25岁之间且已婚，则给予B类保险；, 男性且年龄在21岁以下且未婚，则给予C类保险；, 男性且年龄在21岁以下且已婚，则给予B类保险。,3.,ID3算法,ID3算法是一个经典的决策树学习算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。,（1）,信息熵和条件熵,设,S,是一个实例集(,S,也可以是子实例集),A,为,S,中实例的一个属性。,H,(,S,)和,H,(,S,|,A,)分别称为实例集,S,的信息熵和条件熵, 其计算公式如下,:,其中,i,(,i,=1, 2, ,n,)为S中各实例所有可能的结论；lb即log2。,其中,a,k,(,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,男,而言,对子集,S,女,而言,于是,由公式,(9-1),有,:,又,将以上,3,式代入公式,(9-2),得,:,用同样的方法可求得,:,可见, 条件熵,H,(,S,|性别)为最小,所以,应取“性别”这一属性对实例集进行分类, 即以“性别”作为决策树的根节点。,