[人工智能][机器学习导论]—— 第四课——决策树

第四课——决策树

会出一道大题

决策树与机器学习

决策树简介

决策树是一种基于树结构的分类预测方法

决策树引入

决策树（DecisionTree）又称为判定树，是用于分类的一种树结构。其中每个内部结点（internalnode）代表对某个属性的一次测试，叶结点（leaf）代表某个类（class）或者类的分布（classdistribution），最上面的结点是根结点

决策树提供了一种展示在什么条件下会得到什么类别的方法。

决策树组成

决策树的基本组成部分：根节点、决策结点、分枝和叶子结点。树是由节点和分枝组成的层次数据结构。

决策树是描述分类过程的一种数据结构，从上端的根节点开始，各种分类原则被引用进来，并依这些分类原则将根节点的数据集划分为子集，这一划分过程直到某种约束条件满足而结束。

决策树基本原理

首先对数据进行处理，利用归纳法生成可读的规则和决策树，然后使用决策对新数据进行分析。

本质上决策树是通过一系列规则对数据进行分类的过程。

决策树技术发现数据模式和规则的核心是采用递归分割的贪婪算法。

决策树基本流程

1??收集待分类的数据，这些数据的所有属性应该是完全标注的。

2??设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量化。

3??分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树更令人满意。

4??设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性往往是有限几个，因此在必要的时候应该停止数据集分裂：

该节点包含的数据太少不足以分裂，

继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献，

树的深度过大不宜再分。

ID3算法

针对第三个步骤，ID3算法在决策树各个节点上使用信息增益准则选择特征（属性）进行数据划分，从而递归地构建决策树。

具体方法

1??从根节点（rootnode）开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征。

2??由该特征的不同取值建立子节点。

3??再对子节点递归的调用以上方法，构建决策树，直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

🔥信息熵

信息熵使信息得以量化

1948年，香农(ClaudeShannon)在他著名的论文“通信的数学原理”中指出：“信息是用来消除随机不确定性的东西”，并提出了“信息熵”的概念（借用了热力学中熵的概念），来解决信息的度量问题。

一条信息的信息量和它的不确定性有着直接的关系

比如，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚

信息熵是消除不确定性所需信息量的度量，也即未知事件可能含有的信息量。需要引入消除不确定性的信息量越多，则信息熵越高，反之则越低。

例如“中国男足进军2022年世界杯决赛圈”，这个因为确定性很高，几乎不需要引入信息，因此信息熵很低。

信息熵的计算

Shannon定义的信息熵的计算公式如下：

其中X表示随机变量，随机变量的取值为{𝑥1,𝑥2,…,𝑥𝑛}，𝑃(𝑥𝑖)表示事件𝑥𝑖发生的概率，且有$\sum P(xi)=1$。信息熵的单位为比特（bit）

熵越小表示概率分布的纯度越高，反之，熵越大表示概率分布的纯度越低。

数据集的信息熵

设数据集D中有m个不同的类C1,C2,C3,…,Cm

设Di是数据集D中Ci类的样本的集合,|D|和|Di|分别是D和Di中的样本个数

数据集D的信息熵
$$Info(D)=?\sum _{i=1}^m{p}_i{\log }_2{p}_i$$
其中𝑝𝑖是数据集D中任意样本属于类Ci的概率，用$\frac{|D_i|}{|D|}$估计

使用熵衡量数据纯度

假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类。计算D中正例类和负例类在三种不同的组分下熵的变化情况。
（1）D中包含有50%的正例和50%的负例。
$$Info(D)=?0.5?{\log }_{2}0.5?0.5?{\log }_{2}0.5=1$$
（2）D中包含有20%的正例和80%的负例。
$$Info(D)=?0.2?{\log }_{2}0.2?0.8?{\log }_{2}0.8=0.722$$
（3）D中包含有100%的正例和0%的负例。
$$Info(D)=?1?{\log }_{2}1?0?{\log }_{2}0=0$$
当数据变得越来越“纯”时，熵的值变得越来越小：当D中正反例比例相同时，熵取最大值；当D中所有数据属于一个类时，熵取最小值。因此，熵可以作为数据纯净度的衡量指标。

信息增益

信息增益可以衡量划分数据集前后数据纯度提升程度。信息增益=原数据信息熵?数据划分之后的信息熵

其中，离散属性𝑎有𝐾个可能的取值{𝑎1,𝑎2,…,𝑎𝐾}，其中第𝑘个分支节点包含了𝐷中所有在属性𝑎上取值为$a^k$的样本，记为$D^k$。

选择划分属性示例

以买电脑为例进行决策树划分说明

1?? 确立初始的信息熵

|D|=14，|D1|=5，|D2|=9，即不买的有5个人，买的有9个人

信息熵如下：
$$Info(D)=?\frac{5}{14}{\log }_2\frac{5}{14}?\frac{9}{14}{\log }_2\frac{9}{14}=0.940$$

2?? 确立第一次分裂的属性

🍎 如果按照年龄划分

年龄<30的有5个,其中3个为“否”

年龄30-40的有4个,其中0个为“否”

年龄>40的有5个,其中2个为“否”

🍌 如果按照收入划分

收入=高的有4个,其中2个为“否”

收入=中的有6个,其中2个为“否”

收入=低的有4个,其中1个为“否”

🍑 如果按照学生划分

是学生的有7个,其中1个为“否”

不是学生的有7个,其中4个为“否”

🥝 如果按照信用划分

信用好的有6个,其中3个为“否”

信用一般的有8个,其中2个为“否”

综上，“年龄”属性具有最高信息增益，成为分裂属性

3?? 确立第二次分裂的属性

按照上述方法，可以确定第二次分裂的属性为学生

4?? 划分到不可划分为止

ID3算法总结

算法流程

自上而下贪婪搜索

遍历所有的属性，按照信息增益最大的属性进行分裂

根据分裂属性划分样本

重复上述流程，直至满足条件结束

优点

分类过程和领域知识无关，几乎所有模式和场景都可以得到结果

缺点

ID3算法倾向于选择属性值较多的属性，有些时候不能提供有价值的信息

不适用于连续变量

只能用于分类

一次只用一个特征值进行划分

在样本量较小时，可能会导致过度分类

对属性值缺失的情况无法处理

ID3算法改进—C4.5

改进1：用信息增益率代替信息增益来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足

改进2：能够完成对连续值属性的离散化处理

改进3：能处理属性值缺失的情况

改进4：在决策树构造完成之后进行剪枝，一定程度上解决了过拟合问题

改进1：信息增益率

D3采用信息增益度量。它优先选择较多属性值的feature，因为属性值多的feature会有相对较大的信息增益。

极端例子：对ID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。

C4.5使用增益率将信息增益规范化,选择具有最大信息增益率的属性作为分裂属性

当K越大时，则SplitInfo (𝐷,𝑎)越大，从而 GainRatio(D,a)越小，计算举例如下

改进2：处理连续值属性

采用二分法对连续属性进行处理

假定连续属性a在D上出现了n个不同取值，将这些值从小到大进行排序，记为𝑎1,𝑎2,…,𝑎𝑛
取每对相邻值的中点作为可能的分裂点
T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n ? 1 } T_a=\{\frac{a^i+a^{i+1}}{2}|1\le i \le n-1\} Ta?={2ai+ai+1?∣1≤i≤n?1}
基于划分点𝑡∈𝑇𝑎,将D分成两个子集D1:a≤𝑡和D2:a>𝑡（二叉树），选择信息增益比率最大的划分
$$GainRatio(D,a)=\underset{t\in T_a}{\max }\frac{gain(D,a,t)}{SplitInfo(D,a,t)}$$

举例说明：

对属性“密度”，其候选划分点集合包含16个候选值：{(0.243+0.245)/2,(0.245+0.343)/2,…，(0.774+0.719)/2}

逐一计算每个二划分对应的信息增益率，选择可以使信息增益率最大的划分

改进3：处理缺失值

在某些情况下，可供使用的数据可能缺少某些属性的值，例如：

针对缺失值问题，在决策树的建模过程中，需要解决两个问题：

1??如何在属性值缺失的情况下进行划分属性选择？

2??给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

$$Gain(D,a)=F_r(Info(D)?Inf{o}_A(D))$$

其中𝐹𝑟为属性值未缺失的实例所占比例；计算 Info(D)和 InfoA(D)时忽略属性值缺失的实例
KaTeX parse error: No such environment: align at position 8: \begin{?a?l?i?g?n?}? Info(D)&= -8/1…

计算 SplitInfo 时，将缺失的属性值当作一个正常值进行计算。本例中，当作天气有四个值，分别是晴，多云，雨，?
$$
\begin{align}
\text{SplitInfo}_{天气}（D)&=-\frac{5}{14}\times\log(\frac{5}{14})\Rightarrow\ 晴\
&=-\frac{3}{14}\times\log(\frac{3}{14})\Rightarrow\ 多云\
&=-\frac{5}{14}\times\log(\frac{5}{14})\Rightarrow\ 雨\
&=-\frac{1}{14}\times\log(\frac{1}{14})\Rightarrow\ 缺失\
&=1.809\ bits\

\end{align}
$$

$$GainRatio(D,天气)=Gain(D,天气)/SplitInf{o}_{天}气(D)=0.199/1.809$$

分裂时，将属性值缺失的实例分配给所有分支，但是带一个权重

本例14个实例中共13个实例天气属性值未缺失：5个实例的天气属性为“晴”，3个实例的天气属性为“多云”，5个实例的天气属性为“雨”。

因此针对天气属性值缺失的第6个实例：估计天气是晴的概率是5/13，是多云的概率是3/13，是雨的概率是5/13

叶节点以(N/E)的形式定义，其中 N 为到达该叶节点的实例数， E 为其中属于其它分类的实例数。例如，不玩(3.4/0.4)表示3.4个实例到达“不玩”节点，其中0.4个实例不属于“不玩”

待分类实例有缺失值，如何测试该实例属于哪个分支？

对于任一实例

湿度<=75 的可能性是2.0/(2.0 +3.4)，湿度>75 的可能性是3.4/(2.0 +3.4)

当湿度<=75 时，

分类为玩的可能性= 100%|
分类为不玩的可能性= 0

当湿度>75 时，

分类为玩的可能性= 0.4/3.4=12%
分类为不玩的可能性= 3/3.4=88%

最终分类的概率分布为：
玩= 2.0/5.4×100%+3.4/5.4×12%= 44%
不玩= 2.0/5.4×0%+3.4/5.4×88%= 56%

改进4：通过剪枝降低过拟合

过拟合：可以完美地拟合训练数据，但是不能很好地拟合训练数据外的数据

实际应用中，当训练样本中有噪声或训练样例的数量太少时或缺乏代表性样本时，都容易导致机器学习模型出现过拟合问题。

上述的决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类，会造成决策树分支过多，从而极有可能导致过拟合问题。

所以我们需要通过剪枝减少过拟合

1?? 预剪枝（pre-pruning）：在完全正确分类训练集之前就停止树的生长

在构造决策树的同时进行剪枝。决策树通常是在无法进一步降低熵的情况下才会停止创建分枝，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，停止继续创建分枝。但是这种方法实际中的效果并不好。

2?? 后剪枝（post-pruning）：由“完全生长”的树剪去子树。

剪枝的过程是对拥有同样父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否小于某一阈值。如果小于阈值，则这一组节点可以合并成一个节点，赋予该节点关联的训练数据的最常见分类。后剪枝是目前最普遍的做法。

训练过程中允许对数据的过度拟合，然后再利用验证集对树进行修剪

使用留出法定义一个验证集，后剪枝的目标是通过剪枝使得在验证集上的误差率降低。

1. 自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树中剪去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。
2. 计算剪去节点前后的分类损失，如果剪去节点之后分类损失变小，则说明该节点是可以剪去的，并将其剪去；如果发现损失并没有减少，说明该节点不可剪去，则将树还原成未剪去之前的状态。
3. 重复上述过程，直到所有的非叶节点(除了根节点)都被尝试。

C4.5总结

优点

通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足

通过将连续性属性进行离散化处理，克服ID3算法不能处理连续型数据缺陷，C4.5算法能够处理离散型和连续型的两种属性类型

能够处理具有缺失属性值的数据

构造决策树之后进行剪枝操作，解决ID3算法中可能会出现的过拟合问题

缺点

在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效

针对含有连续属性值的训练样本时，计算效率较低

算法在选择分类属性时没有考虑到条件属性间的相关性，只计算数据集中的每一条件属性与决策属性之间的期望信息，有可能影响到属性选择的正确性

CART算法

Gini指标

分类回归树（CART: Classification and Regression Tree）

使用Gini指标度量数据集的纯度或者不确定性

在分类问题中，假设有m个类，样本点属于第i类的概率为$p_i$，使用$\frac{|D_i|}{|D|}$估计，则数据集D的纯度可以用Gini值度量：
$$\text{Gini}(D)=1?\sum _{i=1}^m{p}_i^2$$
例：在是否买了电脑数据集中，9个样本属于“购买电脑”，5 个样本属于“未购买电脑”
$$\text{Gini(D)}=1?(\frac{9}{14}{)}^2?(\frac{5}{14}{)}^2$$
如果D根据某个属性a被分割为K个子集𝐷1 ，𝐷2 ,…,𝐷𝐾，那么属性 a 的基尼指数(Gini Index)定义为：
$$\text{Gini(D,a)}=|\frac{D^1}{D}|\text{Gini}(D^1)+\dots \dots +|\frac{D^K}{D}|\text{Gini}(D^K)$$
基尼指数Gini(D,a)表示基于属性a划分后的数据的不确定性。 Gini指数值越大，不确定性也就越大，这一点与熵的概念比较类似。Gini指数最小，划分越纯。选择具有最小Gini指数(或最大?Gini)的属性作为分裂属性
$$\Delta \text{Gini(D,a)}=\text{Gini(D)}?\text{Gini(D,a)}$$
基于以上理论，通过Gini指数来确定某个特征的最优切分点(也即只需要确保切分后某点的Gini指数值最小)，这就是决策树CART算法中类别变量切分的关键所在。

CART算法

CART关键点：

1?? 决策树生成：基于训练数据集生成决策树。 CART假设决策树是二叉树，内部节点特征的取值为“是”和“否”，左分枝为“是”的分支，右分枝是取值为“否”的分支。 CART决策树的生成就是递归的构建二叉决策树的过程。

2?? 决策树后剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树。

3?? CART决策树既可以用于分类也可以用于回归。

具体步骤

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

1?? 设结点的训练数据集为D，计算现有特征对该数据集的Gini指标。对每一个特征a，对其可能取的每个值$a^k $，根据“是”或“否”将D分割成$D^1$和$D2$两部分，计算Gini指标。

2?? 在所有可能的特征a以及它们所有可能的切分点$a^k $中，选择Gini 指标最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

3?? 对两个子结点递归地调用步骤1~2，直至满足停止条件。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的Gini指数小于预定阈值（样本基本属于同一类）。

举例说明

第一步，生成决策树。

对数据集属性{是否有房，婚姻状况，年收入}分别计算它们的Gini指数增益，取Gini指数增益值最大的属性作为决策树的根节点属性。

首先，使用Gini值计算数据集D的纯度：
$$Gini(是否拖欠贷款)=1?(3/10{)}^2?(7/10{)}^2=0.42$$
处理离散值属性：以婚姻状况为例，列举所有可能的子集：{Single}，{Married，Divorced}; {Divorced}，{Single, Married}; {Married}，{Single，Divorced}

考虑所有可能的二元划分，并计算划分前后的Gini指标，选择能产生最小Gini指标的子集作为分裂子集

1??当分组为{married}|{single, divorced}时：
$$\Delta (married)=0.42?\frac{4}{10}\times 0?\frac{6}{10}\times (1?(\frac{3}{6}{)}^2?(\frac{3}{6}{)}^2)=0.12$$
2?? 当分组为{single}|{married, divorced}时:
$$\Delta (single)=0.42?\frac{4}{10}\times 0.5?\frac{6}{10}\times (1?(\frac{1}{6}{)}^2?(\frac{5}{6}{)}^2)=0.053$$
3?? 当分组为{divorced}|{single, married}时:
$$\Delta (divorced)=0.42?\frac{2}{10}\times 0.5?\frac{8}{10}\times (1?(\frac{2}{8}{)}^2?(\frac{6}{8}{)}^2)=0.02$$
对比计算结果，根据婚姻状况属性来划分根节点时取Gini指数增益最大的分组作为划分结果，也就是{married}|{single, divorced}。

当根据是否有房来进行划分时，Gini 系数增益计算过程为:

处理连续值属性：年收入属性是一个连续的属性。需要对数据 按升序排序，然后依次用相邻值的中间值作为分隔将样本划分 为两组。例如当面对年收入为60和70这两个值时，算得中间值 为65。以中间值65作为分割点，于是则得Gini系数增益为:
$$\Delta (年收入)=0.42?\frac{1}{10}\times (1?1)?\frac{9}{10}\times (1?(\frac{6}{9}{)}^2?(\frac{3}{9}{)}^2)=0.02$$
其他值的计算同理可得，列出结果如下（最终取使得增益最大 化的那个二分准则来作为构建二叉树的准则）：

划分依据：基尼指数增益最大。根据计算知道，三个属性划分 根节点的增益最大的有两个： 年收入和婚姻状况，增益都为 0.12。此时，随机选择一个属性作为第一次划分。例如选择婚 姻状况进行第一次划分。

接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini指数为 （此时是否拖欠贷款的各有3个记录）：
$$Gini(是否有拖欠贷款)=1?(\frac{3}{6}{)}^2?(\frac{3}{6}{)}^2=0.5$$
与前面的计算过程类似，对于是否有房属性，可得
$$\Delta (是否有房)=0.5?\frac{2}{6}\times 0?\frac{4}{6}\times (1?(\frac{3}{4}{)}^2?(\frac{1}{4}{)}^2)=0.25$$
对于年收入 属性则有：

最后构建的CART如下图所示：

CART总结

CART的缺点

1）无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。

2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

决策树总结

优点

简单直观，生成的决策树很直观。

基本不需要预处理，不需要提前归一化，处理缺失值。

既可以处理离散值也可以处理连续值。

可以处理多维度输出的分类问题。

相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释。

推理过程容易理解，决策推理过程可以表示成If Then形式

缺点

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。

决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。可以通过集成学习之类的方法解决。

寻找最优的决策树是一个NP难的问题，启发式方法容易陷入局部最优。可以通过集成学习之类的方法来改善。

有些比较复杂的关系，决策树很难学习，比如异或。可以换神经网络分类方法来解决。

参考资料

[1]庞善民.西安交通大学机器学习导论2022春PPT

[2]CART树算法详解

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖