人工智能算法与实践-第7章 决策树

7.4算法总结7.1算法概述7.2算法原理7.3算法案例目录第七章决策树算法人工智能算法与实践—1

—

01算法概述PartTHREE—2

—

决策树（DecisionTree）是机器学习中常用的方法之一。决策树模型分为分类决策树和回归决策树。分类决策树模型是一种树形结构模型，用于描述对样本数据的分类。决策树由节点（Node）和有向边（DirectedEdge）组成。节点分为内部节点和叶节点。内部节点代表一个要素或属性，叶节点代表一个类。7.1.1算法简介—3

—

7.1.2如何生成一棵决策树—4

—

（1）学习特征变量的分枝策略。（2）根据特征变量，将数据集分割为多个子集。按照分枝策略，对样本数据进行测试，并将样本数据集分割成子集（子节点）。（3）构建子树。根据第（2）的每个数据子集，构建多棵子树。对于每个子树，重复第（1）步和第（2）步的过程，直到达到停止生长的条件。（4）对树进行剪枝。可能会形成过度拟合，需要对树进行剪枝以获得最好的泛化效果。7.1.3决策过程—5

—

在经过训练后的决策树中，每个叶节点对应一个分类器，通过对新样本数据的叶节点归属进行测试，就可以实现对新样本数据的分类预测。那么如何利用决策树进行分类？1．叶节点中哪个类别的样本多，就把叶节点归为该类别一般而言，叶节点中会包含每个分类的样本，统计叶节点中每个分类的样本数目所占的比例，并将这个叶节点的类别归入样本数目所占的比例最高的类别。2．每个叶节点对应一条规则从根节点到叶节点，形成了一条规则，且这个规则是完备的，即每个样本数据必属于其中某一条规则。规则：变量A>c1、变量B<c2且变量C>c3。3．每个叶子节点组成的规则形成一个决策树分类器在预测时，只要测试样本数据属于哪一条规则，即可得到对应的分类归属，如图所示。02算法原理PartTHREE—6

—

7.2.1信息量—7

—

信息量是指信息多少的量度。1928年，科学家“哈特莱”提出了采用事件出现概率倒数的对数作为信息的度量单位，如下式所示。信息量的大小以及信息所代表的事件发生的概率在信息中存在关联。若一信息所代表的事件是必然事件，即事件发生的概率为100%，则此信息包含的信息量为0。若一信息所代表的事件是小概率事件，即该事件发生的概率很低，则该信息包含的信息量将无限大。例1：一位同学跑过来告诉你说，明天的太阳会从东边升起。这个信息所包含的信息量就是0，因为这是一个必然事件。即使同学不告诉你，你也知道这个信息，太阳依旧会从东边升起。例2：这位同学又告诉你一个信息，他非常神秘地告诉你一串数字并且说快去买彩票，买这组数字的彩票，明天能中五百万。你买彩票之后果然中了五百万。这个信息所包含的信息量是无穷大的，因为这是一个小概率事件。7.2.2信息熵—8

—

信息熵是表示信息不确定性的一种度量。无论是热熵还是信息熵，其本质都是表明事物的混乱程度。熵越高，越混乱；熵越低，则越有序。信息量衡量由特定事件生成的信息，而熵是对结果出现之前可以生成的信息量的期望。考虑随机变量的所有可能值，即所有可能的事件带来的信息量的期望。熵是表示随机变量不确定性的度量。假设X是一个取有限个值的离散随机变量，其概率分布为：

则随机变量X的熵定义为：

其中P(Xi)代表随机事件X为Xi的概率

从信息量角度，熵可以理解为某一个随机变量的平均信息量（随机变量信息量的期望）。随机变量可能有多种取值（随机事件），每种取值发生的概率不一样，概率低的取值信息量大，概率高的取值信息量小。熵是从平均来看这个随机变量可以带来的信息量。7.2.3条件熵—9

—

当两个分类的概率值相等，即两个概率都等于0.5时，熵达到最大值。熵随概率P变化的曲线如图所示。条件熵的定义为：在给定条件X下，Y的条件概率分布的熵对X的数学期望。条件熵表示在已知随机变量X的条件下随机变量Y的不确定性。公式为：推导后得到：7.2.4信息增益—10

—

信息增益是特征选择的重要指标，表示为知道某个特征后使不确定性减少的程度。信息越多，功能的重要性就越高，对应的信息增益就越大。上面所说的信息熵代表了随机变量的复杂度，条件熵代表在某一个条件下，随机变量的复杂度，而信息增益=信息熵-条件熵，换而言之就是知道某个特征后使得不确定性减少的程度，即知道某个特征之前的熵与知道某个特征之后的熵之差。在决策树中，根据某个特征将数据分割为多个子集，分割前与分割后的样本数据熵之差就代表信息增益，信息增益越高则该特征对数据分类效果越好。7.2.4信息增益如下左图所示，每个点表示一个数据样本，蓝色的点表示属于A类，绿色的点表示属于B类。在整个数据集合中，由于A、B两类的发生概率相同，则熵为1。如下右图所示，根据x1变量的值，将样本数据分为两个子集；左侧的子集中全为蓝色的点(A类)，该子集的熵为0。同样右侧的熵也为0，分割后整体熵为0。7.2.4信息增益—12

—

用数学语言可将信息增益描述为：特征A对训练数据集D的信息增益为g(D,A)，定义为集合D经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差。（1）假设训练数据集为D，|D|则表示数据集中样本的个数。（2）假设数据D中有B个分类记作，表示类Cb的样本个数，那么。（3）假设A为数据集D中的某一个特征变量，该特征变量有n种取值。根据特征A的取值，将D划分为n个子集D1,D2...Dn，|Di|表示子集Di中的样本个数，则有。（4）子集|Di|中属于类Cb的样本集合为Dib，则|Dib|为Dib的样本个数。信息增益为：7.2.5信息增益比—13

—

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征问题，容易过度拟合，因此将引入信息增益比来解决该问题。信息增益比是特征A对数据集D的信息增益与特征A的不同取值的熵之比：反映的是特征变量A的各个可能取值的分布情况，如果不同取值的分布比较分散即不纯度很高，则越大，信息增益除以表示对其惩罚度越高。7.2.6决策树的生成—14

—

从根节点出发，根节点包括所有的训练样本。如果一个节点（包括根节点）内所有样本均属于同一类别，那么该节点就成为叶节点，并将该节点标记为样本个数最多的类别。否则采用信息增益法来选择用于对样本进行划分的特征，该特征即为测试特征，特征的每一个值都对应着从该节点产生的一个分支及被划分的一个子集。在决策树中，所有的特征均为符号值，即离散值。如果某个特征的值为连续值，则需要先将其离散化。递归上述划分子集及产生叶节点的过程，使每一个子集都会产生一个决策（子）树，直到所有节点变成叶节点。递归操作的停止条件就是：（1）一个节点中所有的样本均为同一类别，那么产生叶节点；（2）没有特征可以用来对该节点样本进行划分，这里用attribute_list=null来表示。此时也强制产生叶节点，该节点的类别为样本个数最多的类别；（3）没有样本能满足剩余特征的取值，即test_attribute=对应的样本为空。此时也强制产生叶节点，该节点的类别为样本个数最多的类别。03算法案例PartTHREE—15

—

7.3.1借贷人状态评估—16

—

随着社会的发展，在许多金融活动中存在大量的个人信用评估。贷款是当今社会一个普遍的行为，但银行要对借贷人进行评估。传统处理的方法由各专家评估打分方式实现，由此将产生过多的人为干预的因素，并且大大增加了工作量，大数据技术的发展，可避免传统方式的缺陷和弊端。申请人要满足银行的条件才可以贷款成功。下表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征：第1个特征是年龄，有3个可能值：18-25岁，26-50岁，50岁以上；第2个特征是有工作，有2个可能值：是，否；第3个特征是有房产，有2个可能值：是，否；第4个特征是信贷情况，有3个可能值：非常好，好，一般。表的最后一列是类别，表示是否同意贷款，取2个值：是，否。7.3.1借贷人状态评估—17

—

ID年龄有工作有房产信贷情况类别118-25岁否否一般否218-25岁否否好否318-25岁是否好是418-25岁是是一般是518-25岁否否一般否626-50岁否否一般否726-50岁否否好否826-50岁是是好是926-50岁否是非常好是1026-50岁否是非常好是1150岁以上否是非常好是1250岁以上否是好是1350岁以上是否好是1450岁以上是否非常好是1550岁以上否否一般否根据表中的信息可知，可以由年龄、工作、房产以及信贷情况等条件来唯一地确定是否放贷。但总结表中信息，得知有房产的申请者一般都会通过贷款，而没有房产的申请者是否通过贷款要看其他几种条件。7.3.2利用信息增益选择最优划分属性—18

—

（1）计算整个样本数据集的熵其中，为拒绝贷款的用户概率，为同意贷款的用户概率（2）计算根据为“有工作”这一特征变量对数据集分割后的熵条件有工作（总量=5）无工作（总量=10）是否同意贷款是，是，是，是，是否，否，否，否，否，否是，是，是，是(3)工作特征变量的信息增益同理也可以计算出其他几个属性的信息增益，在决策树的每一个非叶子结点划分之前，先计算每一个属性所带来的信息增益，选择最大信息增益的属性来划分。因为信息增益越大，区分样本的能力就越强，越具有代表性。7.3.2利用信息增益选择最优划分属性—19

—

利用信息增益选择最优划分属性的代码如下7.3.2利用信息增益选择最优划分属性—20

—

7.3.3递归构建决策树—21

—

通常一棵决策树包含一个根节点、若干个内部节点和若干个叶节点，叶节点对应决策结果，根节点和内部节点对应一个属性测试，每个节点包含的样本集合根据属性测试的结果划分到子节点中。对整个训练集选择的最优划分属性就是根节点。第一次划分后，数据被向下传递到树分支的下一个节点，并再次划分数据。构建决策树是一个递归的过程，而递归结束的条件是，所有属性都被遍历完，或者每个分支下的所有样本都属于同一类。7.3.3递归构建决策树—22

—

递归构建决策树的代码如下：7.3.4决策结果—23

—

最终决策结果如下图所示：04算法总结PartTHREE—24

—

7.4算法总结—25

—

优点1）简单直观，生成的决策树很直观。2）基本不需要预处理，不需要提前归一化，处理缺失值。3）既可以