Python工程应用-数据分析基础与实践课件-第6章

第一章概论西华大学机器学习第六章决策树XXX学校XXX2022目录Contents模型介绍鱼类和非鱼类判定贷款权限判定

知识引入3

本章知识图谱4模型介绍一1.1决策树概述6

决策树是一种基本的分类和回归方法。决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间和类空间上的条件概率分布。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括三个步骤：特征选择、决策树的生成和决策树的剪枝。决策树可以看作为一个条件概率模型，因此决策树的深度就代表了模型的复杂度，决策树的生成代表了寻找局部最优模型，决策树的剪枝代表了寻找全局最优模型。1.决策树定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directededge)组成。结点有两种类型：内部结点(internalnode)和叶结点(leafnode)。内部结点表示一个特征或属性(features)，叶结点表示一个类(labels)。1.1决策树概述72.决策树应用场景

游戏应用，参与游戏的一方在脑海中想某个事物，其他参与者向他提问，只允许提20个问题，问题的答案也只能用对或错回答。提问的人通过推断分解，逐步缩小待猜测事物的范围，最后得到游戏的答案。3.决策树结构1.1决策树概述8

决策树算法的学习通常是一个递归选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。构建决策树的具体过程如下：(1)构建根节点，将所有数据放在根节点，选择一个最优的特征，按照这一特征将训练数据集划分为多个子集。(2)判断，如果一个子集中的所有实例均为一类，即通过根节点所选的特征值已经能够将此部分数据正确分类，那么就构建叶节点。(3)判断，如果一个子集中的实例不能够被正确分类，那么递归地对这些子集进行选择最优特征，并进行分类，构建相应节点，不断递归下去，直到所划分的子集能够被正确分类并构建出叶子节点为止。4.决策树的构建1.1决策树概述95.决策树的剪枝后剪枝：对生成的数据进行剪枝，去掉过于细分的叶节点，使其退回到父节点，甚至更高的节点，并将父节点或更高的节点作为叶节点。预剪枝：若输入的训练数据集特征较多，也可以挑选出对数据分类影响最大的几类特征作为分类特征，从而减小决策树的复杂度。1.1决策树概述105.决策树的剪枝常用预剪枝方法：(1)定义一个高度，当决策树达到该高度时就停止决策树的生长。(2)达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这个方法对于处理数据的冲突问题比较有效。(3)定义一个阈值，当达到某个结点的实例个数小于阈值时就可以停止决策树的生长。(4)定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值大小来决定是否停止决策树的生长。1.1决策树概述115.决策树的剪枝常用后剪枝方法：(1)Reduced-ErrorPruning(REP,错误率降低剪枝)，该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点由如下步骤组成： a.删除以此结点为根的子树，使其成为叶子结点； b.

赋予该结点关联的训练数据的最常见分类； c.

当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点。1.1决策树概述125.决策树的剪枝常用后剪枝方法：(2)Pesimistic-ErrorPruning(PEP,悲观错误剪枝)。悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪，先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项式分布，并计算它的标准差。对于给定的置信区间，采用下界估计作为规则性能的度量。1.1决策树概述135.决策树的剪枝

1.1决策树概述145.决策树的剪枝常用后剪枝方法：(4)Error-BasedPruning(EBP基于错误的剪枝)。这种剪枝方法的步骤如下： a.计算叶节点的错分样本率估计的置信区间上限U。 b.计算叶节点的预测错分样本数。叶节点的预测错分样本数=到达该叶节点的样本数×该叶节点的预测错分样本率U。 c.判断是否剪枝及如何剪枝。此步骤需要分别计算三种预测错分样本数：计算子树t的所有叶节点预测错分样本数之和，记为E1。计算子树t被剪枝以叶节点代替时的预测错分样本数，记为E2。计算子树t的最大分枝的预测错分样本数，记为E3。

然后按照如下规则比较E1，E2，E3：E1最小时，不剪枝。E2最小时，进行剪枝，以一个叶节点代替t。E3最小时，采用“嫁接”(grafting)策略，即用这个最大分枝代替t。1.1决策树概述155.决策树的剪枝常用后剪枝方法：(4)Error-BasedPruning(EBP基于错误的剪枝)。这种剪枝方法的步骤如下：c.判断是否剪枝及如何剪枝。此步骤需要分别计算三种预测错分样本数：计算子树t的所有叶节点预测错分样本数之和，记为E1。计算子树t被剪枝以叶节点代替时的预测错分样本数，记为E2。计算子树t的最大分枝的预测错分样本数，记为E3。

然后按照如下规则比较E1，E2，E3：E1最小时，不剪枝。E2最小时，进行剪枝，以一个叶节点代替t。E3最小时，采用“嫁接”(grafting)策略，即用这个最大分枝代替t。1.1决策树概述166.决策树算法的特点决策树的优点：(1)其结构能方便地进行可视化，便于理解和解释。(2)能处理数值型数据和非数值型数据，对缺失值也不敏感，能处理不相关的特征，因此对预处理的要求不高，数据准备工作相对简单。(3)训练需要的数据量少，计算量小，效率相对较高。决策树的缺点：(1)适用范围有限，擅长对人、地点、事物的一系列不同特征、品质、特性进行评估，但对连续性特征较难预测，当类别太多时，错误可能增加较快。(2)容易出现过拟合。(3)忽略了属性之间的相关性，在处理特征关联性比较强的数据时表现得不是太好。1.1决策树概述177.Python中包含决策树的常用库classsklearn.tree.DecisionTreeClassifier(criterion='gini',splitter='best',max_depth=None,min_samples_split=2,min_samples_leaf=1,min_weight_fraction_leaf=0.0,max_features=None,random_state=None,max_leaf_nodes=None,min_impurity_decrease=0.0,class_weight=None,ccp_alpha=0.0)

决策树的构建可以通过sklearn库中的DecisionTreeClassifier类来构建，在最新的1.0.2版本的sklearn库中，该类的构造函数定义为：1.1决策树概述18函数参数描述参数描述criterion用于测量拆分质量的函数splitter用于在每个节点上选择拆分的策略max_depth表示树的最大深度，即树的层数，整型变量min_samples_split表示内部节点再划分所需最小样本数，整型或浮点型min_samples_leaf表示叶节点上所需要的最小样本数，整型或浮点型min_weight_fraction_leaf叶子节点最小的样本权重和，整型或浮点型max_features划分时考虑的最大特征数，默认是Nonerandom_state随机数种子，其取值可以是整型、RandomState实例或Nonemax_leaf_nodes最大叶子节点数，整型，默认是Nonemin_impurity_decrease节点划分最小不纯度减少值，浮点型class_weight类别权重，默认是None，也可以字典、字典列表或balancedccp_alpha用于最小成本-复杂性修剪的复杂度参数，非负浮点数1.2决策树数学基础

191.信息熵

香农借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”。信息熵(entropy)具有以下三个性质：(1)单调性，发生概率越高的事件，其携带的信息量越低。(2)非负性，信息熵可以看作为一种广度量，非负性是一种合理的必然。(3)累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和，这也是广度量的一种体现。1.2决策树数学基础

201.信息熵

1.2决策树数学基础

212.条件熵

1.2决策树数学基础

223.信息增益

划分数据集的大原则是将无序数据变得更加有序，在划分数据集前后信息发生的变化称为信息增益(InformationGain)。简单来说信息增益就是熵和特征条件熵的差。

1.2决策树数学基础

234.信息增益比

1.2决策树数学基础

245.基尼系数

1.3决策树算法

25三种决策树算法的应用领域及所使用的准则：1.3决策树算法

26决策树算法分类表决策树算法算法描述ID3算法其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准，来帮助确定生成每个节点时所应采用的合适属性C4.5算法C4.5决策树生成算法相对于ID3算法的重要改进是使用信息增益率来选择节点属性。该方法可以克服ID3存在的不足：ID3只适用于离散的属性，而C4.5既能处理离散的属性，也能处理连续的属性CART算法CART决策树是一种十分有效的非参数分类和回归方法，通过构建树、修剪树、评估树来构建一个二叉树。当终节点是连续变量时，该树为回归树；当终节点是离散变量时，该树为分类树1.3决策树算法

27ID3算法：

它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则根据测试属性的取值进行，测试属性有多少不同取值，就将样本集划分为多少子样本集，同时决策树上与该样本集相应的节点长出新的叶子节点。ID3算法根据信息论理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。(1)ID3算法的具体方法为：a.从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。b.由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。1.3决策树算法

28ID3算法：

1.3决策树算法

29ID3算法：

案例：鱼类和非鱼类判定二2.1案例介绍31在此案例中，需要根据以下两个特征，将动物分成两类：鱼类和非鱼类。特征一：不浮出水面是否可以生存。特征一：是否有脚蹼。数据如下表：ID不浮出水面是否可以生存是否有脚蹼是否是鱼1是是是2是是是3是否否4否是否5否是否2.2案例实现321.

生成数据集

将表6-2中“不浮出水面是否可以生存”和“是否有脚蹼”这两列数据特征中的“是”用“1”、“否”用“0”代替。类别标签“是否为鱼类”中的“是”用“yes”、“否”用“no”代替。data_set=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]

labels=['nosurfacing','flippers']2.2案例实现332.

计算给定数据集的香农熵

遍历给定数据集的最后一列数据，创建类别标签计数字典，最后依据公式计算香农熵。函数返回香农熵。创建类目计数字典香农熵计算2.2案例实现343.

划分数据集

这个函数的是作用是当我们按某个特征划分数据集时，把划分后剩下的元素抽取出来，形成一个新的子集，用于计算条件熵。

#判断axis值是否等于value

#遍历数据集，将axis上的数据和value值进行比对

ret_data_set=[]

forfeat_vecindata_set:

iffeat_vec[axis]==value:

reduce_feat_vec=feat_vec[:axis]

reduce_feat_vec.extend(feat_vec[axis+1:])

ret_data_set.append(reduce_feat_vec)

returnret_data_set

该函数通过遍历dataSet数据集,求出index对应的column列的值为value的行，然后依据index列进行分类，如果index列的数据等于value的时候，就要将index划分到创建的新数据集中。该函数的返回值为index列为value的数据集(该数据集需要排除axis列)。2.2案例实现353.

划分数据集

代码中extend和append的区别：music_media.append(object)向列表中添加一个对象objectmusic_media.extend(sequence)把一个序列seq的内容添加到列表中(跟+=在list运用类似，music_media+=sequence)1、使用append时是将object看作一个对象，整体打包添加到music_media对象中。2、使用extend时是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。ID参数名称释义1dataSet待划分的数据集2axis表示每一行的index列，特征的坐标，等于0，第0个特征为0或者13value表示index列对应的value值需要返回的特征的值2.2案例实现364.

选择最好的数据集划分方式的函数

接下来将遍历整个数据集，循环计算香农熵，找到最好的特征划分方式，并划分数据集。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。外循环（遍历特征，计算每个特征的信息增益）内循环（累加计算条件熵）比较信息增益，更新最佳信息增益值与最佳特征索引值输出最优特征索引，函数返回最优索引值2.2案例实现375.递归构建决策树

1）majorityCnt()函数筛选出现次数最多的分类标签名称创建类目计数字典倒序排序，取出出现次数最多的结果2.2案例实现385.递归构建决策树

2）创建createTree()函数，递归地创建决策树。调用函数得出最佳特征索引值从特征类别列表取出特征值，创建根节点通过循环，递归地创建子树2.2案例实现396.测试算法：使用决策树执行分类

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于决策树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。defclassify(input_tree,feat_labels,test_vec):

#获取树的第一特征属性

first_str=list(input_tree.keys())[0]

#树的分子，子集合Dict

second_dict=input_tree[first_str]

#获取决策树第一层在feat_labels中的位置

feat_index=feat_labels.index(first_str)

#测试数据,找到根节点对应的label位置,也就知道从输入数据的第几位来开始分类

forkeyinsecond_dict.keys():

iftest_vec[feat_index]==key:

#判断分支是否结束

iftype(second_dict[key]).__name__=='dict':

class_label=classify(second_dict[key],feat_labels,test_vec)

else:

class_label=second_dict[key]

returnclass_label2.2案例实现406.测试算法：使用决策树执行分类

ID参数名称释义1input_tree输入的决策树对象2feat_labels特征标签3test_vec测试的数据函数参数说明如下表：