决策树学习相关资料

一.示例学习示例学习也称实例学习,它是一种归纳学习。示例学习是从若干实例(包括正例和反例)中归纳出一般概念或规则的学习方法。第一个拱桥的语义网络第二个拱桥的语义网络学习程序归纳出的语义网络拱桥概念的语义网络例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)即 z＝2x＋3y＋1例2假设示例空间存放有如下的三个示例：示例1：(0，2，7)示例2：(6，-1，10)示例3：(-1，-5，-10)这是三个3维向量，表示空间中的三个点。现要求求出过这三点的曲线。二.决策树学习

1．什么是决策树

决策树(decisiontree)也称判定树，它是由对象的若干属性、属性值和有关决策组成的一棵树。其中的节点为属性（一般为语言变量），分枝为相应的属性值（一般为语言值）。从同一节点出发的各个分枝之间是逻辑“或”关系；根节点为对象的某一个属性；从根节点到每一个叶子节点的所有节点和边，按顺序串连成一条分枝路径，位于同一条分枝路径上的各个“属性-值”对之间是逻辑“与”关系，叶子节点为这个与关系的对应结果，即决策。

决策树示意图

例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。。其中,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男而言,对子集集S女而言,于是,由公式式(9-1)