现代机器学习 课件 第5章 决策树与集成学习.pptx

第5章决策树与集成学习;

5.1决策树;

从本质上讲,决策树是一种启发式结构,通过按一定顺序进行一系列选择或比较,可以构建出决策树。以地球上不同物种的分类为例,先问这样的问题:“它能飞吗?”根据答案,可以把整个物种分成两部分:一部分能飞,另一部分不能飞,然后转到不能飞的物种的分支。接着再问另一个问题:“它有几条腿?”基于这个问题的答案,创建多个分支,包括2条腿、4条腿、6条腿等。同样的,在能飞的分支可以问相同的问题,也可以问不同的问题,继续分支物种,直到叶子节点(那里只有一个物种)时停止。这种方法基本上展示了建立决策树的过程,如图5.1所示。;;

构造决策树的方法,通常是递归地去选择最优的特征,并根据选择的特征对训练数据进行划分,最终得到一个最优分类器。这个过程实际上是对样本特征空间的分割。当然,决

策树也可以处理回归问题,此时每个叶子节点代表一个预测值。通常,决策树算法的核心步骤包括以下四点:

(1)分析输入数据。

(2)设计属性选择指标(基尼系数、交叉熵等)。

(3)选择数据特征,以便能将数据进行最优划分。

(4)根据特征进行数据划分。;

虽然决策树存在着容易过拟合、容易忽略样本特征之间的关系等缺点,但相对于其他的机器学习方法,决策树具有更像人类行为、可以直接处理非数字数据、可以直接处理丢

失的数据(跳过数据清理步骤)、更具解释性、易于从线性数据扩展到非线性数据、无需超参数调整等优点,因此,简单易用的决策树得到了人们的广泛使用。根据应用问题场景的

不同,决策树可分为分类决策树与回归决策树。本章主要介绍一些决策树的基本概念及经典算法,不单独按照实际使用场景对决策树进行分类。;

5.2经典决策树算法;

熵的计算公式如下:

其中,S表示一个样本集合;ui表示第i个类别;P(ui)表示类别ui在样本S上出现的概率,且P(ui)=|ui|/|S|;m表示类别数;定义0lb0=0。信息熵具有三个重要性质:首先,它是单调的,也就是说某件事发生的概率越高,它的不确定性越小,信息熵就越小,将变量或信息源的状态确定下来所需要的信息量也就越小;其次,信息熵是非负的,由于是对概率求对数,所以在公式的最前方添加了负号,从而保证了信息熵的广度;最后,信息熵具有累加性,即多个事件的总不确定性,可用每个事件的不确定性累加得到。;

信息增益表示在某一条件下,信息不确定性减少的程度,在决策树中,指的是划分前后熵的变化,计算公式如下:

其中,A表示样本特征,Value(A)表示该特征所有取值的集合,V是Value(A)中的一个值,SV则是样本集S中特征A值为V的样本的集合。;

5.2.2C4.5算法

C4.5算法是由ID3算法改进而来的,与ID3不同的是,C4.5使用了信息增益率作为属性选择指标来选择特征。信息增益率使用“分裂信息值”将信息增益规范化,分裂信息值的定义如下:;

其中变量的定义与式(5-2)相同。由式(5-3)获得的分裂信息值表示了训练数据集S按特征A划分后产生的信息,根据其可获得对应的信息增益率:;

5.2.3CART算法

分类回归树算法不同于上面介绍的几种经典算法,它既可以实现分类任务,也可以实现回归任务。

基尼系数是指随机选择的输入样本在给定节点上的类分布进行标记时的误分类概率,某个随机变量p的基尼系数为;;

CART算法也可被认为是一个二分递归分割技术,在决策树生成中每个非叶子节点都只有两个分支,最后生成一个二叉树。在CART算法中,选择获得最小基尼系数的特征来

划分数据,如果某个特征对应获得的基尼系数越小,则暗示该节点的不纯度越小。CART算法的停止条件有:

(1)没有特征可继续划分。

(2)样本个数小于某个阈值。

(3)如果样本本身的基尼系数小于了某个阈值,则当前节点也要停止递归。;

CART算法较容易处理离散和连续数据的混合输入,算法对输入的单调变换不敏感,对异常值比较稳健,对大数据集的伸缩性较好,并且可以修改,以处理丢失的输入。但是,该算法本质上仍然使用的是贪婪性质的构造方法,所以预测准确度有限。此外,在CART算法中要对数据进行剪枝处理。;

5.3决策树的剪枝;

5.3.1预剪枝

预剪枝是在决策树生成的过程中进行的,具体是:在一个新的树节点被创建之前,先观察该节点的划分是否能够提升决策树的泛化能力,若能提高泛化能力则继续划分,否则将其设置为叶子节点。所谓泛化能力,是指学习模型对于新的样本的预测能力,它能够反映出模型对训练样本中隐含规律的学习能力。实际上,在决策树的构建过程中,判断是否停止分裂产生叶子节点的方法也可以被考虑作为预剪枝的方法,也具有防止过拟合的