《第2章 决策树学习ppt课件.pptx》由会员分享，可在线阅读，更多相关《第2章 决策树学习ppt课件.pptx（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、章 节 目 录2.1 2.1 决策树的组成及分类决策树的组成及分类2.2 2.2 决策树的构造算法决策树的构造算法CLSCLS2.3 2.3 基本的决策树算法基本的决策树算法ID3ID32.4 2.4 信息熵和信息增益及其案例信息熵和信息增益及其案例2.5 2.5 随机森林及其应用案例随机森林及其应用案例2.6 2.6 决策树和随机森林应用概述决策树和随机森林应用概述根据一些 feature 进行分类，每个节点提一个问题，通过判断，将数据分为两类，再继续提问。这些问题是根据已有数据学习出来的，再投入新数据的时候，就可以根据这棵树上的问题，将数据划分到合适的叶子上。决策树决策树 决策树是能够实现
2、分治策略的数据结构，可以通过把实例从根结点排列到某个叶子结点来对实例进行分类，可用于分类和回归。 决策树代表了实例属性值约束的合取的析取式，从树根到树叶的每一条路径都对应一组属性约束的合取，树本身对应着这些合取的析取。西瓜问题的一棵决策树西瓜问题的一棵决策树决策树学习决策树学习 单变量树变量树决策树的分类决策树的分类数据集与单变量树数据集与单变量树 多变量树多变量树决策树的分类决策树的分类数据集与数据集与线性多线性多变量树变量树 Hunt于1966年研制了一个概念学习系统(Concept Learning System, CLS)，可以学习单个概念，并能够用学到的概念分类新的实例。这是一种早期
3、的基于决策树的归纳学习系统。 在CLS决策树中，结点对应于待分类对象的属性，由某一结点引出的弧对应于这一属性可能取的值，叶结点对应于分类的结果。 CLSCLS算法算法 （1）如果TR中所有实例分类结果均为Ci，则返回Ci。 （2）从属性表中选择某一属性Ai作为检测属性。 （3）不妨假设|ValueType(Ai)|= k,根据Ai取值的不同，将TR划分为k个训练集TR1, TR2,TRk，其中： TRj=| TR且V(X,Ai)为属性Ai的第j个值 （4）从属性表中去掉已做检测的属性Ai。 （5）对每一个j(1jk)，用TRj和新的属性表递归调用CLS以生成子分支决策树DTRi。 （6）返回以
4、属性Ai为根，DTR1,DTR2,DTRk为子树的决策树。CLSCLS算法算法 大多数决策树学习算法都是核心算法的变体，都采用自顶向下的贪婪搜索(Greedy Search）方法遍历可能的决策树空间，ID3就是其中的代表。基本的决策树学习算法ID3是通过自顶向下构造决策树来进行学习的，构造过程是从“哪一个属性将在树的根结点被测试？”这个问题开始的。ID3ID3算法算法 Quinlan于1983年对CLS算法进行了扩展，提出了ID3算法。该算法不仅能方便地表示概念属性-值信息的结构，而且能从大量实例数据中有效地生成相应的决策树模型。 ID3 (Examples，Target attribute，
5、Attributes)，其中Examples即训练样例集，Target attribute是这棵树要预测的目标属性，Attributes是除目标属性外供学习的决策树要测试的属性列表。ID3ID3算法算法ID3ID3算法算法（1）创建树的Root(根)结点。（2）如果Examples都为正，那么返回label=的单结点树Root。（3）如果Examples都为反，那么返回label=的单结点树Root。（4）如果Examples为空，那么返回单结点树Root, label = Examples中最普遍 的Target_atrribute值。（5）否则： AAttributes中分类Example
6、s能力最好的属性，一般认为具有最高信息 增益(Information Gain）的属性是最好的属性。 Root的决策属性A。 对于A的每个可能值vi: a.在Root下加一个新的分支对应测试A=vi 。 b.令Examples(vi)为Examples中满足A属性值为vi 的子集。 c.如果Examples (vi)为空：在这个新分支下加一个叶子结点，结点的lable = Examples中最普遍的Target_attribute值；否则在这个新分支下加一个 子树ID3 (Examples(vi),Target_attribute,AttributesA）。（6）结束。（7）返回Root。 I
7、D3算法是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都已被使用过。 那么，在决策树生成过程当中，应该以什么样的顺序来选取实例的属性进行扩展呢？可以从第一个属性开始，然后依次取第二个属性作为决策树的下一层扩展属性，如此下去，直到某一层所有窗口仅含同一类实例为止。但是，一般来说，每一属性的重要性是不同的。那么如何选择具有最高信息增益即分类能力最好的属性呢？ID3ID3算法算法编号编号色泽色泽根蒂根蒂敲声敲声纹理纹理脐部脐部触感触感好瓜好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑 蜷缩 沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷
8、硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是6青绿稍蜷 浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺 清脆清晰平坦软粘否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷 浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否西瓜数据集西瓜数据集2.02.0 要计算出当前属性集合色泽，根蒂，敲声，纹理，脐部，触感中每个属性的信息增益。以属性“色泽”为例，它有3个可能的取值：青绿，乌黑，浅白。若使用该属性
9、对D进行划分，则可得到3个子集，分别记为：D1（色泽青绿），D2（色泽乌黑），D3（色泽浅白）。 子集D1包含编号为1，4，6，10，13，17的6个样例，其中正例占p13/6，反例占p2=3/6；D2包含编号为2, 3, 7, 8, 9, 15的6个样例，其中正、反例分别占p14/6，p2=2/6；D3包含编号为5，11，12，14，16的5个样例，其中正、反例分别占p11/5，p24/5。 根据式 可计算出用“色泽”划分之后所获得的3个分支结点的信息熵为 根据式 可计算出属性“色泽”的信息增益为 类似的，我们可计算出其他属性的信息增益：Gain(D，根蒂）0.143；Gain(D，敲声）0
10、.141；Gain(D，纹理）0.381；Gain(D，脐部）0.289；Gain(D，触感）0.006 属性“纹理”的信息增益最大，于是它被选为划分属性。上图给出了基于“纹理”对根结点进行划分的结果，各分支结点所包含的样例子集显示在结点中 在西瓜数据集2.0上基于信息增益生成的决策树西瓜数据集2.0划分出的训练集（上部）与验证集（下部）编号编号色泽色泽根蒂根蒂敲声敲声纹理纹理脐部脐部触感触感好瓜好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑 蜷缩 沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是6青绿稍蜷 浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是10青绿硬挺 清脆清晰平坦软粘否14浅白稍蜷沉闷稍
11、糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否编号编号色泽色泽根蒂根蒂敲声敲声纹理纹理脐部脐部触感触感好瓜好瓜4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷 浊响稍糊凹陷硬滑否西瓜数据集3.0编号编号色泽色泽根蒂根蒂敲声敲声纹理纹理脐部脐部触感触感密度密度含糖率含糖率 好瓜好瓜1青绿蜷缩浊响清晰凹陷硬滑0.697 0.460是2乌黑 蜷缩 沉闷清晰凹陷硬滑0.774 0.376是3乌黑蜷缩浊响清晰凹陷硬
12、滑0.634 0.264是4青绿蜷缩沉闷清晰凹陷硬滑0.608 0.318是5浅白蜷缩浊响清晰凹陷硬滑0.556 0.215是6青绿稍蜷 浊响清晰稍凹软粘0.403 0.237是7乌黑稍蜷浊响稍糊稍凹软粘0.481 0.149是8乌黑稍蜷浊响清晰稍凹硬滑0.437 0.211是9乌黑稍蜷沉闷稍糊稍凹硬滑0.666 0.091否10青绿硬挺 清脆清晰平坦软粘0.243 0.267否11浅白硬挺清脆模糊平坦硬滑0.245 0.057否12浅白蜷缩浊响模糊平坦软粘0.343 0.099否13青绿稍蜷 浊响稍糊凹陷硬滑0.639 0.161否14浅白稍蜷沉闷稍糊凹陷硬滑0.657 0.198否15乌黑
13、稍蜷浊响清晰稍凹软粘0.360 0.370否16浅白蜷缩浊响模糊平坦硬滑0.593 0.042否17青绿蜷缩沉闷稍糊稍凹硬滑0.719 0.103否 在西瓜数据集3.0上基于信息增益生成的决策树. .随机森林的引入随机森林的引入 决策树的缺点 分类规则复杂 容易陷入局部极值 过度拟合 引入随机森林的思想 单株决策树可以按照一定精度分类，为了显著提高精度， 一种很容易理解的方法就种植一片树林，并让所有的树 参与投票，选出最流行的分类。 随机森林是一种集成算法（Ensemble Learning），它属于Bagging类型，通过组合多个弱分类器，最终结果通过投票或取均值，使得整体模型的结果具有较高
14、的精确度和泛化性能。 其可以取得不错成绩，主要归功于“随机”和“森林”，一个使它具有抗过拟合能力，一个使它更加精准。Bagging结构随机森林随机森林在源数据中随机选取数据，组成几个子集S 矩阵是源数据，有 1-N 条数据，A B C 是feature，最后一列C是类别随机森林随机森林- -基本步骤基本步骤由 S 随机生成 M 个子矩阵随机森林随机森林- -基本步骤基本步骤随机森林算法（1）从原始训练数据集中，采用bootstrap方法有放回地随机抽取 个新的等规模样本集，并在此基础上建立 棵决策树模型。研究显示bootstrap方法可以较好地提升不稳定分类器的泛化能力。（2）设数据集有n个属
15、性，则在每棵决策树的每个结点等概率随机抽取一个特征子空间，通常由 个属性组成。然后通过计算特征子空间中每个属性蕴含的信息量，从中选择一个最具有分类能力的属性来分裂结点。通过前文的定理得知，该步骤是为了控制随机森林的泛化误差。（3）每棵树不做任何剪裁，最大限度地生长。（4）将K棵决策树组成随机森林，当测试数据输入后，随机森林的预测结果根据每棵决策树的输出进行投票确定。2log ( ) 1n 随机森林的生成过程人为控制参量： 树的数量（取大数大数定律） 取mM随机森林的生成 每棵决策树是一位精通于某一个窄领域的专家，森林中众多个精通不同领域的专家，各自用不同的角度评价一个新的问题 （新的输入数据）
16、，投票结束后，取众数得到结果。随机森林过程的类比 有放回地随机选择N个样本，即每棵树的训练样本 每个节点的分类属性 随机森林的随机性体现有了两个随机的过程，避免了过拟合 随机森林需调节的参数少，一般只需两个参数。 即随机森林中决策树的棵数与每棵决策树所抽取的分裂特征数。 随机森林拥有较好的分类预测准确率， 而且可以防止过拟合现象的发生。 随机森林可以利用其袋外数据。当利用bootstrap生成新的训练样本数据时，对每一棵决策树，原始训练样本数据集中几乎有37%的数据不出现在该树的训练数据中，这些数据被称作袋外估计样本。袋外估计样本可用于估算随机森林的泛化误差，也能用于任一特征的重要性的计算。随
17、机森林的优点 选择kaggle新手赛题目泰坦尼克之灾来锻炼随机森林算法应用思路。整个流程如下： 数据预处理； 模型选择； 随机森林分类器及其参数调节。随机森林实际应用案例 首先总览数据，了解每列数据的含义,数据的格式等，下图是泰坦尼克数据集的基本内容和格式。每列数据表示乘客ID，存活情况，船票级别，乘客姓名，性别，年龄，船上的兄弟姐妹以及配偶的人数，船上的父母以及子女的人数，船票编号，船票费用，所在船舱，登船的港口。随机森林实际应用案例 数据预处理数据预处理 数据预处理主要有以下4步：（1）按照日常生活的逻辑对年龄（Age）划区间，对年龄进行分组。（2）Cabin是一个字母+一串数字的组合，我
18、们只留字母。此外，Cabin的缺失值是很多，我们把它作为新的类目，用“N”代替、（3）Fare船票费用是连续变量，同样需要分组，我们把它们四分化，分为(最小值到下四分位数)，(下四分位数到中位数)，(中位数到上四分位数)，(上四分位数到最大值)。（4）乘客的名字Name、船票编码Ticket对乘客的幸存情况所起作用不明显，会增大计算复杂度，所以我们将其删除。随机森林实际应用案例 数据预处理数据预处理 模型选择主要有以下3步：（1）根据目标函数确定学习类型,是无监督学习还是监督学习,是分类问题还是回归问题等。（2）比较各个模型的分数,然后取效果较好的模型作为基础模型。（3）我们经过多个模型的测试
19、以及模型融合测试，目前效果最好的是随机森林。随机森林实际应用案例 模型选择模型选择 利用python作为编程工具，主要步骤如下：（1）首先导入python工具包 from sklearn.ensemble import RandomForestClassifier from sklearn.model_selection import GridSearchCV from sklearn.metrics import make_scorer, accuracy_score（2）选择分类器 通过试验发现随机森林模型效果最好的，所以选择随机森林 clf = RandomForestClassifie
20、r()随机森林实际应用案例 随机森林分类器及其参数调节（3）定义随机森林参数 n_estimators: 随机森林中决策树的个数。 criterion: CART树做划分时对特征的评价标准。 max_features: 决策树划分时考虑的最大特征数。 max_depth: 决策树最大深度max_depth。 min_samples_split：内部节点再划分所需最小样本数。 min_samples_leaf： 叶子节点最少样本数。 parameters = n_estimators: 50, 100, 200, max_features: log2, sqrt, criterion: entr
21、opy, gini, max_depth: 4, 8, 16, 20, min_samples_split: 2, 4, 6, min_samples_leaf: 1,4,8 （4）定义评价标准 使用make_scorer将accuracy_score转换为评分函数 acc_scorer = make_scorer(accuracy_score)（5）自动调参 GridSearchCV用于系统地遍历多种参数组合，只要输入参数，就能给出 最优化的结果和参数。 grid_obj = GridSearchCV(clf,parameters,scoring=acc_scorer) grid_obj =
22、 grid_obj.fit(X_train,y_train)（6）设置最佳参数组合 将clf设置为参数的最佳组合 clf = grid_obj.best_estimator_（7）最佳算法参数运用于数据预测 clf.fit(X_train,y_train)我们预测的准确率为我们预测的准确率为83%，对比决策树的预测结果，对比决策树的预测结果80%，随机森林的预测效，随机森林的预测效果要优于决策树！果要优于决策树！. .决策树的应用概述决策树的应用概述 决策树学习是一种逼近离散值目标函数的方法，这种方法将从一组训练数据中学习到的函数表示为一棵决策树，它是一种常用于预测模型的算法，通过将大量数据有
23、目的的分类，从中找到一些具有价值的、潜在的信息。决策树方法以其速度快、精度高、生成的模式简单等优点，在数据挖掘中受到许多研究者和软件公司的关注。决策树的应用概述决策树的应用概述 在科学研究方面，决策树算法己被广泛应用到很多分类挖掘的实际应用中。比如：在医疗诊断过程中，通过决策树分析来指导疾病辨证分型；在图像识别领域，利用决策树算法对图像进行分类；在股票市场上对每只股票的历史数据进行分析，通过相应的技术进行预测，从而做出相对比较准确的判断；彩票的购买也可以利用数据挖掘的分类或预测技术进行分析；在金融领域中通过决策树，可以很容易地确定贷款申请者是属于高风险的还是低风险的。 除了科学研究之外，许多数据挖掘的商用软件，其中很多都采用了决策树方法。 Microsoft、SGI、SAS 等在已推出的数据挖掘系统中，首选的方法都是决策树方法。 国内南京大学的周志华教授尝试提出一种深度的树模型，称做gcForest，用文中的术语说，就是“multi-Grained Cascade forest”，多粒度级联森林。 此外，还提出了一种全新的决策树集成方法，使用级联结构让 gcForest 做表征学习，就这样采用了级联+集成的方法来实现了一个深度随机森林，为机器学习打开了另一扇窗，有兴趣的同学可以拓展学习一下。拓展：深度随机森林拓展：深度随机森林