开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 机器学习——决策树 -> 正文阅读

[数据结构与算法]机器学习——决策树

一、概述

1.组成

一、概述

决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3,?C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树(决策树)是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

1.组成

□--决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

○--状态节点，代表备选方案的经济效果(期望值)，通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

△--结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。

2.基本流程

决策树(decision tree) 是一类常见的机器学习方法.以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这个把样本分类的任务，可看作对"当前样本属于正类吗?"这个问题的"决策"或"判定"过程.顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制.例如，我们要对"这是好瓜吗?"这样的问题进行决策时，通常会进行一系列的判断或"子决策"我们先看"它是什么颜色?"，如果是"青绿色"，则我们再看"它的根蒂是什么形态?"，如果是"蜷缩"，我们再判断"它敲起来是什么声音?"，最后?我们得出最终决策:这是个好瓜.这个决策过程如图下图所示。

显然，决策过程的最终结论对应了我们所希望的判定结果，例如"是"或"不是"好瓜；决策过程中提出的每个判定问题都是对某个属性的"测试"，例如"色泽=?" "根蒂=?"；每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范国是在上次决策结果的限定范围之内，例如若在"色泽=青绿"之后再判断"根蒂=?"，则仅在考虑青绿色瓜的根蒂。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的"分而治之" (divide-and-conquer) 策略，如下图所示。

显然，决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回: (1) 当前结点包含的样本全属于同一类别，无需划分；?(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；(3) 当前结点包含的样本集合为空，不能划分。

在第(2)种情形下，我们把当前结点标记为叶结点，井将其类别设定为该结点所含样本最多的类别;在第(3) 种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同：情形(2)是在利用当前结点的后验分布，而情形(3)则是把父结点的样本分布作为当前结点的先验分布。

二、划分选择

由算法可看出，决策树学习的关键是第8 行，即如何选择最优划分属性一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的"纯度" (purity) 越来越高。

1.信息增益

“信息熵”?(information entropy)是度量样本集合纯度最常用的一种指标.假定当前样本集合D 中第k 类样本所占的比例为 $p_k(k=1,2,...,|y|)$ ，则D的信息熵定义为

$Ent(D)=-\sum_{k=1}^{|y|}p_k\log_2p_k$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1.1）

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。

假定离散属性 $a$ 布V 个可能的取值 $\begin{Bmatrix} a^{1},&a^{2}, &..., &a^{V} \end{Bmatrix}$ ，若使用 $a$ 来对样本集D 进行划分，则会产生V 个分支结点，其中第 $v$ 个分支结点包含了D 中所有在属性 $a$ 上取值为 $a^{v}$ 的样本，记为 $D^{v}$ ，我们可根据式(1.1) 计算出 $D^{v}$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^{v}|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出用属性 $a$ 对样本集 $D$ ，?进行划分所获得的"信息增益" (information gain)

? $Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{D^{v}}{D}Ent(D^{v})$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (1.2）

一般而言，信息增益越大，则意味着使周属性 $a$ 来进行划分所获得的"纯度提升"越大。因此，我们可用信息增益来进行决策树的划分属性选择，即在图1.2 算法第8 行选择属性 $a_*=\mathop{\mathbb{\arg }max}_{a\in A}Gain(D,a)$ 。?著名的ID3 决策树学习算法[Quinlan，1986] 就是以信息增益为准则来选择划分属性。

以表1.1 中的西瓜数据集2.0 为例，该数据集包含17 个训练样例，用以学习一棵能预测没剖开的是不是好瓜的决策树。显然， $|y|=2$ 在决策树学习开始时，根结点包含D 中的所有样例，其中正例占 $p_1=\frac{8}{17}$ ，反例占 $p_1=\frac{9}{17}$ ??于是，根据式(1.1)可计算出根结点的信息熵为

$Ent(D)=-\sum_{k=1}^{2}p_k\log_2p_k=-(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17})=0.998$

?表1.1?西瓜数据集2.0

然后，我们要计算出当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。以属性"色泽"为例，它有3 个可能的取值: {青绿，乌黑，浅白}，若使用该属性对D 进行划分，则可得到3 个子集，分别记为: $D^{1}$ ?(色泽=青绿)， $D^{2}$ (色泽=乌黑)， $D^{3}$ (色泽=浅白)。子集 $D^{1}$ 包含编号为{1 ， 4, 6, 10, 13, 17} 的6 个样例，其中正例占 $p_1=\frac{3}{6}$ ，反例占 $p_2=\frac{3}{6}$ ；? $D^{2}$ 包含编号为{2 ， 3, 7, 8, 9, 15} 的6 个样例，其中正、反例分别占 $p_1=\frac{4}{6}$ ， $p_1=\frac{2}{6}$ ； $D^{3}$ 包含编号为{5 ， 11, 12, 14, 16} 的5 个样例，其中正、反例分别占 $p_1=\frac{1}{5}$ ， $p_1=\frac{4}{5}$ .根据式(1.1)可计算出用"色泽"划分之后所获得的3 个分支结点的信息熵为
$Ent(D^{1})=-\sum_{k=1}^{2}p_k\log_2p_k=-(\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6})=1.000$ ,
$Ent(D^{2})=-\sum_{k=1}^{2}p_k\log_2p_k=-(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6})=0.918$ ，
$Ent(D^{2})=-\sum_{k=1}^{2}p_k\log_2p_k=-(\frac{1}{5}\log_2\frac{1}{5}+\frac{4}{5}\log_2\frac{4}{5})=0.722$ ,
于是，根据式(1.2)可计算出属性"色泽"的信息增益为

$Gain(D,seze)=Ent(D)-\sum_{v=1}^{3}\frac{D^{v}}{D}Ent(D^{v})$

$=0.998-(\frac{6}{17}\times 1.000+\frac{7}{16}\times 0.918+\frac{5}{17}\times 0.722)=0.109$

类似的，我们可计算出其他属性的信息增益:

根蒂? ? $Gain(D,gendi)=0.143$ ；敲声? $Gain(D,qiaosheng)=0.143$ ；

纹理 ?? $Gain(D,wenli)=0.143$ ；脐部? $Gain(D,qibu)=0.143$ ；

触感 ?? $Gain(D,chugan)=0.143$

显然，属性"纹理"的信息增益最大?于是它被选为划分属性.图1.3 给出了基于"纹理"对根结点进行划分的结果，各分支结点所包含的样例子集显示在结点中。

?图1.3 基于"纹理"属性对根结点划分

然后，决策树学习算法将对每个分支结点做进一步划分.以图1.3 中第一个分支结点( "纹理=清晰" )为例，该结点包含的样例集合 $D^{1}$ 中有编号为{1 ，2, 3, 4, 5, 6, 8, 10, 15} 的9 个样例，可用属性集合为{色泽，根蒂，敲声，脐部7触感}。基于 $D^{1}$ 计算出各属性的信息增益:?

色泽 ?? $Gain(D^{1},sezhe)=0.043$ ；? ? ? ?根蒂? $Gain(D^{1},gendi)=0.458$ ；

敲声 ?? $Gain(D^{1},qiaosheng)=0.331$ ；脐部? $Gain(D^{1},qibu)=0.458$ ；

触感 ?? $Gain(D^{1},chugan)=0.458$

?"根蒂"、"脐部"、"触感" 3 个属性均取得了最大的信息增益，可任选其中之一作为划分属性.类似的，对每个分支结点进行上述操作，最终得到的决策树如圈1.4 所示。

2.增益率

在上面的介绍中，我们有意忽略了表1.1 中的"编号"也作为一个候选划分属性，则根据式件均可计

算出它的信息增益为0.998 ，远大于其他候选划分属性。这很容易理解"编号"将产生17 个分支，每个分支结点仅包含一个样本，这些分支结点的纯度己达最大。然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5 决策树算法[Quinlan，1993]?不直接使用信息增益，而是使用"增益率" (gain ratio) 来选择最优划分属性.采用与式(1.2) 相同的符号表示，增益率定义为

$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(1.3)

其中

$IV(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}\log _2\frac{|D^{v}|}{|D|}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (1.4)

称为属性 $a$ 的"固有值" (intrinsic value) [Quinlan, 1993]。?属性 $a$ 的可能取值数目越多(即V 越大)，则 $IV(a)$ 的值通常会越大.例如，对表1.1 的西瓜数据集2.0，有 $IV$ (触感) = 0.874 (V = 2), $IV$ (色泽) = 1.580 (V = 3), $IV$ (编号) = 4.088 (V = 17)。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此， C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式[Quinlan，1993]: 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3.基尼指数

CART 决策树[Breiman et al., 1984] 使用"基尼指数" (Gini index)来选择划分属性.采用与式(1.1) 相同的符号，数据集D 的纯度可用基尼值来度量:

$Gini(D)=\sum_{k=1}^{|y|}\sum_{k'\neq k}^{}p_kp_k'=1-\sum_{k=1}^{|y|}p_k^{2}$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(1.5)

直观来说， Gini(D) 反映了从数据集D 中随机抽取两个样本，其类别标记不一致的概率。因此， Gini(D) 越小，则数据集D 的纯度越高。采用与式(1.2)相同的符号表示，属性 $a$ 的基尼指数定义为?

$Gini\_index(D,a)=\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Gini(D^{v})$ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (1.6)?

于是，我们在候选属性集合A 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_*=\mathop{\mathbb{\arg }\min}_{a\in A}Gain\_index(D,a)$ 。

三、剪枝处理

剪枝是应该决策树过拟合的一种重要方法，主要分为以下两种：

1.预剪枝

预剪枝：该策略就是在对一个节点进行划分前进行估计，如果不能提升决策树泛化精度，就停止划分，将当前节点设置为叶节点。那么怎么测量泛化精度，就是留出一部分训练数据当做测试集，每次划分前比较划分前后的测试集预测精度。

优点：降低了过拟合风险，降低了训练所需的时间。
缺点：预剪枝是一种贪心操作，可能有些划分暂时无法提升精度，但是后续划分可以提升精度。故产生了欠拟合的风险。

2.后剪枝

后剪枝：该策略是首先正常建立一个决策树，然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序，依次对内部节点进行剪枝，如果将某以内部节点为根的子树换成一个叶节点，可以提高泛化性能，就进行剪枝。

优点：降低过拟合风险，降低欠拟合风险，决策树效果提升比预剪枝强
缺点：时间开销大得多

四、特殊值处理

1.连续值处理

到目前为止我们仅讨论了基于离散居性来生成决策树. 现实学习任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场. 最简单的策略是采用二分法(bi-partition)对连续属性进行处理，这正是C4 . 5 决策树算法中采用的机制[Quinlan， 1993].

2.缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失.例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值(如HIV 测试结果)未知；尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费.例如，表1?.4是表1.1 中的西瓜数据集2.0 出现缺失值的版本，如果放弃不完整样本，则仅有编号{4， 7, 14, 16} 的4 个样本能被使用。显然，有必要考虑利用有缺失属性值的训练、样例来进行学习。

以上内容主要是来自周志华《机器学习》（西瓜书）的内容，并结合自己的理解，后续会不断完善。

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列