本文重点内容

1. 什么是决策树
2. 决策树的基本原理
3. 决策树训练方法，防止过拟合的方法
4. 分类和回归决策树筛选原则

一. 基础内容

1. 决策树基本原理

1.1. 定义

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成。其中节点有两种类型：内部节点和叶节点。内部节点表示一个特征或属性，叶结点表示一个类，结构如下图：

 

1.2. 表示成条件概率

决策树还可以表示成在给定条件下类的条件概率分布。

决策树将特征空间划分为会不相交的单元，在每个单元定义一个类的概率分布，这就构成了一个条件概率分布。

条件概率计算方式:

• 概率分布计算：由各个单元给定条件下类的条件概率分布组成，将这些概率沿着分支相乘，即得出所需的概率。

 

极大似然函数：损失函数的优化。

 

2. 决策树的训练算法

决策树学习算法通常是递归的原则最优特征，根据该特征对训练数据进行分割：即特征空间的分割。

决策树的结构收到很多因素影响：特征选择、分裂点选择、树的深度、复杂度控制、剪枝等。

 

2.1. 划分选择的算法

特征选择：在每个节点上，如何选择一个特征进行分裂，常用的特征选择指标有：信息增益、信息增益率，以及基尼指数：ID3、C4.5、CART的等决策树算法。

信息增益（ID3 算法）

信息熵的定义与计算

信息增益的计算

 

信息增益：衡量了信息对数据集分类结果的贡献度。
在构建决策树时，ID3 算法选择信息增益最大的特征作为当前节点的划分特征。

例如，在一个判断水果是苹果还是橙子的决策树中，有颜色、形状等特征，通过计算这些特征的信息增益，若颜色特征的信息增益最大，那么就先根据颜色来划分节点。

 

信息增益比（C4.5 算法）

信息增益比的引入原因：

• 信息增益存在一个问题，它偏向于选择取值较多的特征。为了克服这个问题，C4.5 算法引入了信息增益比。
• 在决策树构建过程中，C4.5 算法选择信息增益比最大的特征作为划分特征。例如，在一个包含很多特征的数据集里，有些特征虽然信息增益较大，但它可能有过多的取值，通过计算信息增益比，可以更合理地选择划分特征。

 

 

基尼指数（CART 算法）

基尼指数的含义：

基尼指数用于衡量数据集的纯度，其值越小表示纯度越高。
 
例如，在客户流失预测的决策树中，基尼不纯度可以帮助我们了解每个节点中客户流失（或不流失）的纯度情况。如果一个节点的基尼不纯度很高，说明这个节点中的客户在流失与否的分类上很混乱，需要进一步划分来提高纯度。

 

基尼指数的作用：划分特征。

对于每个候选特征，计算按照该特征划分后的基尼指数，选择使得基尼指数最小的特征作为划分特征。这是因为最小的基尼指数意味着划分后子数据集的纯度最高，这样可以构建出更有效的决策树。
 
例如，在信用风险评估决策树中，有收入、负债、信用记录等多个特征。通过计算每个特征划分后的基尼指数，选择能使基尼指数最小的特征（如信用记录）进行划分，从而更好地将高风险和低风险客户区分开来。

 

基尼指数可以防止过拟合

基尼指数的使用有助于控制决策树的生长，防止过拟合。如果不加以控制，决策树可能会过度划分数据，导致在训练数据上表现很好，但在新数据上性能很差。
 
通过选择基尼指数最小的特征进行划分，决策树会优先选择最能有效降低数据集不纯度的特征，避免构建过于复杂的决策树结构。
 
例如，在图像分类决策树中，使用基尼指数来选择划分特征可以避免因一些噪声特征而构建出过于复杂的决策树，从而使模型在新的图像数据上有更好的泛化能力。

 

举例说明：计算各个类别的信息增益

计算各个类别的信息增益:

1. 计算数据集的经验熵H(D)
2. 计算特征A下(n个类别)各个类别的加权平均熵$H(D_{Ai})$
3. 计算特征A的加权熵：$H(D_A)={\sum }_{i=1}^n(D_{Ai}/D)H(D_{Ai})$
4. 求信息增益：$H(D_A)=H(D)-H(A)$
   类别B同上，然后对比信息增益，选择大的信息增益作为分裂点

 

2.2. 叶子节点的选择

p108

 

2.3. 剪枝

采用剪枝操作防止决策树出现过拟合，可以把这种操作看成是一种对决策树采取的正则手段。

常用的剪枝有预剪枝、后剪枝操作。

预剪枝

预剪枝是指在模型训练之前给定一些限制条件，这些限制条件可以阻止节点的进一步分裂。常见预剪枝的策略有：

1. 限制树的最大深度。如果所有叶子都已经达到最大深度，将停止训练。
2. 限制树的最大叶子数目。如果叶子数目达到这个上限，将停止训练。
3. 限制每片叶子上最少的样本数。为每个节点设置最小样本数阈值，如果节点的本数少于这个阈值，则停止分裂。
4. 规定分割带来训练误差下降的下限。比如，规定此下限为-0.3，那么将无视所有致训练误差下降达不到0.3的分割条件。
5. 利用验证集进行预剪枝。如果有验证集，可在决策树的训练过程中不断用验证进行评估。如果一次分割无法降低验证集上的误差，该分割将不被进行。

预剪枝的优点是可以在树的生长过程中减少计算量，但缺点是可能会错过一些有用分裂，导致模型的表达能力不足。

 

后剪枝

后剪枝是在将决策树训练好之后，从决策树的底部开始评估删除一个分割是否导致验证集误差下降。如果是，则删除该分割，即删除该分割产生的两个叶子节点，并将它的父节点重新设为叶子节点；否则，保留该分割，不断重复该步骤。

后剪枝的优点是可以灵活控制模型的复杂度，但缺点是计算量较大，因为需要在树完全生长后进行剪枝。

 
 

2.4. 决策树训练算法分类

算法名称	分裂准则	处理类型	树的结构	缺失值处理	剪枝处理	应用范围
ID3	信息增益	离散特征	可以是多叉树	不处理	没有剪枝过程，容易过拟合	分类
C4.5	信息增益率	连续特征	可以是多叉树	能处理数据集中存在缺失值的情况。它通过估算该特征对分类的贡献进行处理，而不是简单地删除缺失数据。对于有缺失值的特征，C4.5会计算每个可能的分裂点，并考虑缺失值的不同处理方式对分类结果的影响	采用了一种后剪枝方法，即先完整地生长树，然后再通过悲观剪枝策略来减少树的复杂性，提高泛化能力	分类
CART	基尼指数	离散、连续均可	二叉树	对于缺失值的处理采用了概率加权的方法。它通过计算缺失随机变量的预测概率，然后对每个可能的值进行加权平均	使用后剪枝策略，即先生成完整的树，然后通过交叉验证来选择最优的剪枝树	分类和回归

 

二. 习题

1. 归一化对决策树的影响

题目：对于一些机器学习模型（例如，神经网络），对特征进行归一化(normalization)是一个有效的预处理操作。一个常见的归一化方式是对每一个特征数据，减去该特征的均值，然后除以该特征的方差。请回答，对于基于决策树的一系列算法，归一化是否会影响训练结果？

解答：
对于基于决策树的一系列算法，归一化通常不会影响训练结果。

决策树算法在构建树的过程中主要依据特征的信息增益、基尼系数等标准来进行分裂，并不依赖于特征的绝对数值大小。它更关注的是特征之间的相对关系以及特征对分类或回归目标的区分能力。
而归一化主要是改变特征的数值范围和分布，对于决策树算法来说，特征的相对大小关系和顺序通常不会因归一化而改变。

所以，对基于决策树的算法进行特征归一化一般不会对训练结果产生实质性的影响。

 

2. 选择决策树模型

 

3. 决策树计算

 
 

4. 基尼系数的优势

 

 

5. 在叶子上使用线性模型的优缺点

 

参考：《人工智能基础-姚期智》