人工智能 决策树学习.pptVIP

决策树学习 什么是决策树 怎样学习决策 ID3算法 决策树示意图 例4 　下图是一个描述“兔子”概念的决策树。 2、怎样学习决策树 决策树学习举例 表1 汽车驾驶保险类别划分实例集  由决策树所得的规则集 ① 女性且年龄在25岁以上，则给予A类保险； ② 女性且年龄在21岁到25岁之间，则给予A类保险； ③ 女性且年龄在21岁以下，则给予C类保险； ④ 男性且年龄在25岁以上，则给予B类保险； ⑤ 男性且年龄在21岁到25岁之间且未婚，则给予C类保险； ⑥ 男性且年龄在21岁到25岁之间且已婚，则给予B类保险； ⑦ 男性且年龄在21岁以下且未婚，则给予C类保险； ⑧ 男性且年龄在21岁以下且已婚，则给予B类保险。 ID3算法 1）信息熵和条件熵 （2）基于条件熵的属性选择 小组成员： * * LOGO 1．什么是决策树 决策树(decision tree)也称判定树，它是由对象的若干属性、属性值和有关决策组成的一棵树。 节点:属性（一般为语言变量） 分枝:属性值（一般为语言值） 逻辑“或”关系:从同一节点出发的各个分枝； 逻辑“与”关系:位于同一条分枝路径上的各个“属性-值”对； 从根节点到每一个叶子节点的所有节点和边，按顺序串连成一条分枝路径，叶子节点为这个与关系的对应结果，即决策。 二.决策树学习 首先，选取一个属性，按这个属性的不同取值对实例集进行分类；并以该属性作为根节点，以这个属性的诸取值作为根节点的分枝，进行画树。 Title 决策树学习的基本方法和步骤 然后，考察所得的每一个子类，看其中的实例的结论是否完全相同。如果完全相同，则以这个相同的结论作为相应分枝路径末端的叶子节点；否则，选取一个非父节点的属性，按这个属性的不同取值对该子集进行分类，并以该属性作为节点，以这个属性的诸取值作为节点的分枝，继续进行画树。 如此继续，直到所分的子集全都满足：实例结论完全相同，而得到所有的叶子节点为止。 Title 设表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)} 于是，我们得到以性别作为根节点的部分决策树（见下图）。 决策树生成过程 决策树生成过程 最后生成的 决策树 ID3算法是一个经典的决策树学习算法，由Quinlan于1979年提出。 基本思想：以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变成最小的属性，以构造一棵熵值下降最快的决策树，到叶子节点处的熵值为0。此时，每个叶子节点对应的实例集中的实例属于同一类。 1）信息熵和条件熵 将实例集视为一个离散的信息系统，用信息熵表示信息量，实例的结论为随机事件，诸属性视为信息源。 H(S)和H(S|A)分别称为实例集S的信息熵和条件熵, 其计算公式如下: 其中,μi(i=1, 2, …, n)为S中各实例所有可能的结论；lb即log2。ak(k=1, 2, …, m)为属性A的取值, Sak为按属性A对实例集S进行分类时所得诸子类中与属性值ak对应的那个子类。 按性别划分, 实例集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|性别)为最小,所以,应取“性别”这一属性对实例集进行分类, 即以“性别”作为决策树的根节点 *