决策树（Decision Tree）基础知识

（目录中带*注解的内容为通用部分，非本章节特定内容。）

一、回忆

1、*机器学习的三要素：

  - 函数族 $\mathcal{F}$：这是一个函数的集合，其中的每个函数 $f$ 都属于这个集合，即 $f\in \mathcal{F}$。

  - 目标函数 $J(f)$：这个函数用来衡量函数 $f$ 的性能或质量。它是一个评价标准，帮助我们了解函数的好坏。

  - 优化算法：我们的目标是找到一个函数 $f^{\ast }$，它在函数族 $\mathcal{F}$ 中使得目标函数 $J(f)$ 的值最小。用数学表达式表示就是 $f^{\ast }=\arg {\min }_{f}J(f)$。这意味着我们正在寻找一个函数，它在所有可能的函数中，目标函数的值是最小的。

  这些概念是优化问题的基础，也是在优化问题中，我们通常会遇到以下几个关键概念。无论是在机器学习、工程优化还是其他领域，理解和应用这些概念都是至关重要的。

1）*函数族

  在机器学习和统计学中，函数族是指一组具有相似形式或结构的函数。以下是一些常见的函数族：

  - 线性模型：$f(x)={\mathbf{w}}^{T}x$，其中 $\mathbf{w}$
是权重向量，$x$ 是输入向量。这种模型假设输出是输入的线性组合。

  - 多项式：一种扩展的线性模型，可以捕捉输入变量之间的非线性关系。

  - 核方法：由核函数决定，这种方法可以在高维空间中有效地处理数据，而不需要显式地计算高维特征。

  - 决策树：分段常数函数，通过一系列的决策规则将输入空间分割成不同的区域，并为每个区域分配一个常数值。

  - 神经网络：由网络结构决定，这是一种模仿人脑神经元连接方式的模型，能够学习和表示复杂的函数关系。

  - 集成学习：多棵决策树的加权平均，这种方法通过结合多个模型的预测来提高整体的预测性能。

• 随机森林：一种集成学习方法，通过构建多棵决策树并进行投票或平均来提高预测的准确性和鲁棒性。
• GBDT（梯度提升决策树）：另一种集成学习方法，通过逐步构建决策树来纠正前一个模型的错误。

  - 概率图模型：利用条件独立假设简化概率计算，这种模型可以有效地表示和推理变量之间的概率关系。

  函数族可以根据是否需要调整参数来分为两类：

• 参数模型：包括线性模型、多项式、神经网络、概率图模型。这些模型需要通过训练数据来调整模型参数。
• 非参数模型：包括核方法、决策树、集成学习。这些模型不依赖于固定的参数数量，而是根据数据的复杂性来调整模型的复杂度。

2）*目标函数

  在机器学习中，目标函数是用来评估模型性能的函数，它通常由两部分组成：损失函数和正则项。目标函数的一般形式为：

  $$J(f)=L(f)+\lambda R(f)$$

  其中，$J(f)$ 是目标函数，$L(f)$ 是损失函数，$R(f)$ 是正则项，$\lambda$
是正则参数，用于平衡损失函数和正则项的影响。

  - 损失函数 $L(f)$：衡量函数 $f$ 与训练数据的拟合程度。常见的损失函数包括：

• 负对数似然损失：如 L2/L1 损失、交叉熵损失。
• 合页损失（SVM）、$\epsilon$ 不敏感损失（SVR）。
• 聚类损失：如 K均值、谱聚类。
• 降维损失：如结构保持、重构。

  - 正则项 $R(f)$：衡量函数 $f$ 自身的复杂程度，以防止过拟合。常见的正则项包括：

• L2 正则、L1 正则。
• K-Lipschitz 连续（WGAN）。

  - 正则参数 $\lambda$：控制模型复杂度的参数。

• 当 $\lambda$ 越小，模型可以更复杂，训练误差越小，但可能导致偏差小、方差大。
• 当 $\lambda$ 越大，模型更简单，训练误差可能增大，但偏差大、方差小。

  通过调整正则参数 $\lambda$，我们可以在模型的偏差和方差之间找到一个平衡点，以获得最佳的泛化能力。

2.1）*模型的其他复杂度参数

  在机器学习中，模型的复杂度不仅由其基本结构决定，还受到一些关键参数的影响。以下是一些常见模型的复杂度参数：

  - 线性模型：特征的数目。特征越多，模型的表达能力越强，但也可能增加过拟合的风险。

  - 多项式：多项式阶数。阶数越高，模型能够捕捉的非线性关系越复杂，但同样可能导致过拟合。

  - 核方法：核函数超参数（如 RBF
核的核函数宽度）。这些参数决定了模型在特征空间中的映射方式，影响模型的复杂度和泛化能力。

  - 决策树：

• 树的最大深度：控制树的复杂度，防止过拟合。
• 叶子结点数目：影响模型的精细程度。
• 叶子结点代表的训练样本数目：决定每个叶子结点需要多少样本来分裂。

  - 神经网络：

• 网络的连接方式：全连接、局部连接等，影响信息的流动和模型的学习能力。
• 网络的层数：层数越多，模型的学习能力越强，但计算成本和过拟合风险也增加。
• 每层的神经元数目：影响模型的表达能力和计算复杂度。

  这些参数的选择对于模型的性能至关重要，需要根据具体问题和数据集进行调整和优化。

3）*优化算法

  优化算法是机器学习中用于寻找模型参数最优值的方法。目标是找到一个函数 $f^{\ast }$，使得目标函数 $J(f)$
最小化：

  $$f^{\ast }=\arg \underset{f}{\min }J(f)$$

  以下是一些常见的优化算法：

  - 梯度下降/上升：

• 梯度：计算损失函数的梯度，指导参数更新的方向。
  • 批处理梯度下降：使用所有数据计算梯度。
  • 随机梯度下降：每次使用一个样本计算梯度。
  • 小批量梯度下降：每次使用一小部分样本计算梯度。
  • 动量法：加速梯度下降，减少震荡。
• 学习率：控制每次更新的步长。
  • 学习率的影响：学习率过大可能导致不收敛，过小则收敛速度慢。
  • 自适应学习率：根据训练过程动态调整学习率。

  - 坐标下降/上升：每次选择一个或一部分参数进行更新。

• K均值聚类：一种常用的聚类算法。
• EM（期望最大化）：一种迭代算法，用于含有隐变量的概率模型。
• Lasso、SMO：用于解决正则化问题的优化算法。

  这些算法各有优缺点，选择合适的优化算法可以显著提高模型的训练效率和性能。

2、*前处理/后处理

1）前处理：特征工程

（*特征工程的具体细节会在单独章节讲到） 大致流如下：
  - 数据探索性分析
  -特征编码
  - 特征预处理
  - 特征选择
   - 特征工程与机器学习模型一起考虑
  - 天下没有免费的午餐原则：
  表明没有任何单一的机器学习算法能够在所有问题上都表现最好。这个原则强调了算法选择的相对性和问题依赖性。“没有免费的午餐”（No Free Lunch,NFL）原则是机器学习领域中的一个重要概念，它表明没有任何单一的机器学习算法能够在所有问题上都表现最好。这个原则强调了算法选择的相对性和问题依赖性
  理解“没有免费的午餐”原则：
  1.算法的局限性：不同的算法对不同类型的数据和问题有不同的适应性。例如，线性回归可能在线性可分的数据上表现良好，但在非线性问题上可能就不够有效。

  2.问题的特性：问题的复杂性、数据的分布、特征的数量和类型等都会影响算法的性能。一个算法可能在某些特定类型的问题上表现优异，但在其他问题上可能表现平平。

  3.算法的权衡：在选择算法时，通常需要在准确性、效率、可解释性等方面做出权衡。没有一种算法能在所有方面都做到最优。

  4.经验的重要性：在实际应用中，选择最适合特定问题的算法往往需要基于经验和实验。这意味着需要对数据和问题有足够的理解，以及对不同算法的性能有足够的了解。

  5.组合方法：由于单一算法可能无法解决所有问题，研究者和实践者可能会采用集成学习等方法，将多个算法结合起来，以提高整体性能。

  6. 持续学习：随着数据和问题的不断变化，算法也需要不断更新和调整。这意味着机器学习是一个持续学习和适应的过程。
  总之，“没有免费的午餐”原则提醒我们，在机器学习中，没有一种万能的解决方案。我们需要根据具体问题的特点和需求，选择合适的算法，并可能需要结合多种方法来达到最佳效果。

2）后处理：模型选择和模型评估

（*详细内容会在单独章节展开讲解）
  - 训练集、验证集、测试集划分
  - 训练集和验证集
   - 留出法
   - 交叉验证
  - 训练误差、验证误差、测试误差
  - 统计学习理论
   - 奥卡姆剃刀原理

  在模型选择和评估过程中，我们将数据集划分为训练集、验证集和测试集。训练集用于训练模型，验证集用于调整模型参数和选择最佳模型，测试集则用于评估模型的最终性能。训练误差是我们在训练数据上得到的误差，验证误差是在验证数据上得到的误差，而测试误差则是在未见过的数据上得到的误差，它更能反映模型在实际应用中的表现。
  统计学习理论为我们提供了理解模型性能的理论基础，其中奥卡姆剃刀原理强调在模型选择时应该倾向于更简单的模型，除非有充分的理由选择更复杂的模型。这是因为更简单的模型更不容易过拟合，同时也更容易理解和解释。

3、*机器学习开发流程

  机器学习项目的开发过程可以概括为以下几个关键步骤：

1）数据收集

• 给定任务，分析可能的相关特征，收集数据。

2）特征探索分析

• 对收集到的数据进行分析，以发现有用的特征。

3）特征工程

• 将原始数据转换成算法制定的输入。

4）模型训练

• 确定机器学习算法（函数集合）$\mathcal{F}$。
• 模型训练：在给定超参数的情况下，确定模型参数。
• 模型选择：在验证集上评估模型预测性能。

5）性能评估

• 模型测试和评估。
• 模型应用。

  在整个过程中，我们的目标是找到一个能够从输入数据 $x$ 预测输出结果 $y$ 的模型，即 $y=f(x)$。这需要我们不断地调整模型参数和特征，以提高模型的预测准确性和泛化能力。

  以上就是对机器学习基础知识的回顾和复习，接下来我们将进入本章的正题，由分段常数函数族定义的决策树模型。

二、决策树（Decision Tree）

a、基本概念

  决策树是一种多级分类器，特别适用于多类分类任务和多峰分布数据。

  分级是指将一个复杂问题转化为若干个简单的分类问题来解决。

• 从根结点到叶子结点的有向边代表了$一条决策路径$。
• 每个叶子结点对应一个分类器，判别结果为样本占比最高的类别。
• 决策树的路径是互斥并且完备的。

  决策树可视化工具：

   - dtreeviz 介绍
   - dtreeviz GitHub

  在决策树中，从根节点开始，根据特征的不同取值，数据被分配到不同的路径上。每个中间节点代表一个特征的测试，而叶子节点则代表最终的分类结果。例如，在图中，根据花萼长度（sepal length）和花萼宽度（sepal width）的不同，数据被分配到不同的路径上，最终在叶子节点上得到分类结果。

b、决策树的构建

  决策树的构建过程是一个递归的划分过程，通过不断地将数据集划分为更小的子集，直到满足停止条件。以下是构建决策树的详细步骤：

1）初始化

  构建根节点，将所有训练数据放在根节点，并根节点加入叶子节点列表；

  若叶子节点列表为空，算法结束，返回生成的决策树；

  否则从叶子节点列表中挑选1个叶子节点，

• 2.1：若该叶子节点的样本集合已足够纯净，计算该叶子节点的预测值，并将其从叶子节点列表中删除（不再划分）；
• 2.2：否则，对该叶子节点进行进一步划分：
  • （1）对每个特征的每个可能的划分方式，尝试将该节点的样本集合进行划分，计算划分后数据的纯净度和划分的分数；
  • （2）从第（1）步所有的划分中，选择一个最优划分（分数最高），将训练数据划分成若干子集，每个子集为当前节点的子节点，并将这些子节点加入叶子节点列表，同时将当前节点从叶子节点列表中删除；

2）选择一个合适的树结构

• 二叉树、多叉树

3）确定在每个非叶子节点上要使用的特征

• 所有特征（训练性能更好）、随机选择特征子集（更快，测试性能可能也不差）

4）在每个非叶子节点上选择合适的决策规则

• 划分点的选择：精确搜索/穷举所有可能的划分点（训练性能更好）、近似搜索/直方图（更快，测试性能可能也不差）
• 划分点的评价准则：信息熵增益、信息熵增益率、Gini指数、带正则的Gini指数

5）停止划分条件

• 足够纯净、最大深度、最大叶子节点数目、节点的最小样本数目、…

6）剪枝

*拓展知识：熵 &信息增益

1、熵：系统不确定的度量

  熵是衡量系统不确定性的一种度量。对于一个随机变量$Y$，其可能的取值为 { 1 , 2 , . . . , C } \{1, 2, ..., C\} {1,2,...,C}，熵的定义为：
$$H(Y)=-\sum _{c=1}^{C}P(Y=c){\log }_2(P(Y=c))$$

2、数据集的经验熵

  数据集$\mathcal{D}$的经验熵表示数据的不确定性或不纯净度的度量，定义为：
$$H(\mathcal{D})=-\sum _{c=1}^C\frac{N_c}{N}{\log }_2\left(\frac{N_c}{N}\right)$$
  其中，$N$是数据集$\mathcal{D}$中的样本数目，$N_c={\sum }_{i=1}^N\mathbb{I}(y_i=c)$是第$c$个类别的样本数目。

  用样本的比例估计概率分布，相当于$P(Y=c)={\hat{\pi }}_c=\frac{N_c}{N}=\frac{{\sum }_{i=1}^N\mathbb{I}(y_i=c)}{N}$。

3、条件熵

  条件熵是衡量在已知特征$X$的取值后，随机变量$Y$的不确定性。特征$X$的取值为 { 1 , 2 , . . . , M } \{1, 2, ..., M\} {1,2,...,M}，知道$X$后，$Y$还有多少不确定，条件熵定义为：
$$H(Y|X)=\sum _{m=1}^{M}P(X=m)H(Y|X=m)=\sum _{m=1}^{M}P(X=m)\sum _{c=1}^{C}P(Y=c|X=m){\log }_2(P(Y=c|X=m))$$

4、经验条件熵

  经验条件熵是根据特征$X$的取值，将数据划分为$M$个子集${\mathcal{D}}_m$。经验条件熵定义为：
$$H(\mathcal{D}|X)=\sum _{m=1}^M\frac{|{\mathcal{D}}_m|}{|\mathcal{D}|}H({\mathcal{D}}_m)$$
  其中，$N_m=|{\mathcal{D}}_m|={\sum }_{i=1}^N\mathbb{I}(x_i=m)$表示第$m$个子集的样本数目，$N_{m,c}={\sum }_{i=1}^N\mathbb{I}(x_i=m,y_i=c)$表示第$m$个子集中第$c$个类别的样本数目。

  进一步展开经验条件熵的计算公式：
$$H(\mathcal{D}|X)=\sum _{m=1}^M\frac{N_m}{N}\sum _{c=1}^C-\frac{N_{m,c}}{N_m}{\log }_2\left(\frac{N_{m,c}}{N_m}\right)$$

  将数据集$\mathcal{D}$按照特征$X$取值分为$M$个子集后，各子集的平均不纯净程度。

5、信息增益

1）信息增益的定义

  特征$X$对训练数据集$\mathcal{D}$的信息增益$g(\mathcal{D},X)$定义为：
$$g(\mathcal{D},X)=H(\mathcal{D})-H(\mathcal{D}|X)$$
  这表示将数据集$\mathcal{D}$根据特征$X$的取值划分为$M$个子集后，各子集的平均不确定性减少量。

2）ID3算法

  ID3算法选择信息增益最大的特征进行分裂（即对标签$Y$提供信息最多的特征），倾向于选择取值多的特征进行分裂。

3）多叉树

  在决策树中，多叉树是指每个节点可以有多于两个子节点的树结构。

4）图示说明

  下图展示了在知道某特征前后数据集的经验信息熵的变化：

• 划分前：经验信息熵为1
• 划分后：经验信息熵为0

  图中，$x_1$和$x_2$表示特征，通过特征$x_1$的取值将数据集划分为两个子集，显著减少了不确定性，从而提高了模型的纯净度。

6、信息增益与决策树分裂

1）数据集概览

  下表展示了一个包含日志密度（L）、好友密度（F）、是否使用真实头像（H）和账号是否真实（R）的数据集：

日志密度L	好友密度F	是否使用真实头像H	账号是否真实R
s	s	no	no
s	l	yes	yes
l	m	yes	yes
m	m	yes	yes
l	m	yes	yes
m	l	no	yes
m	s	no	no
l	m	no	yes
m	s	no	yes
s	s	yes	no

2）总体数据集的信息熵 $H(\mathcal{D})$

  计算得到数据集$\mathcal{D}$的信息熵为：
$$H(\mathcal{D})=-\frac{7}{10}{\log }_2\frac{7}{10}-\frac{3}{10}{\log }_2\frac{3}{10}=0.879$$

3）根据特征划分后的信息熵

3.1）日志密度L

  根据日志密度L划分后的信息熵$H(\mathcal{D}|L)$计算如下：
$$H(\mathcal{D}|L)=\frac{3}{10}\times H({\mathcal{D}}_s)+\frac{4}{10}\times H({\mathcal{D}}_m)+\frac{3}{10}\times H({\mathcal{D}}_l)$$
具体计算为：
$$=\frac{3}{10}\times \left(-\frac{1}{3}{\log }_2\frac{1}{3}-\frac{2}{3}{\log }_2\frac{2}{3}\right)+\frac{4}{10}\times \left(-\frac{3}{4}{\log }_2\frac{3}{4}-\frac{1}{4}{\log }_2\frac{1}{4}\right)+\frac{3}{10}\times \left(-\frac{3}{3}{\log }_2\frac{3}{3}-\frac{0}{3}{\log }_2\frac{0}{3}\right)$$
$$=0.603$$

4）信息增益计算

• 根据日志密度L的信息增益$g(\mathcal{D},L)$：
  $$g(\mathcal{D},L)=H(\mathcal{D})-H(\mathcal{D}|L)=0.276$$
• 根据好友密度F的信息增益$g(\mathcal{D},F)$：
  $$g(\mathcal{D},F)=0.553$$
• 根据是否使用真实头像H的信息增益$g(\mathcal{D},H)$：
  $$g(\mathcal{D},H)=0.033$$

5）决策树分裂

  因为好友密度F具有最大的信息增益（或最小熵），所以第一次分裂选择F为分裂属性。分裂后的结果如下表所示：

日志密度L	是否使用真实头像H	账号是否真实R
s	no	no
m	no	no
m	no	yes
s	yes	no

  对应的决策树结构图如下：

7、信息增益率

1）ID3算法的局限性

  ID3算法选择信息增益最大的特征进行分裂，倾向于选择取值多的特征。例如，如果一个特征（如ID号）取值非常多，ID3算法可能会分裂出很多子节点，但这些分裂对分类可能没有实际意义。

3）C4.5算法：信息增益率

  C4.5算法改进了ID3算法，选择信息增益率最大的特征进行分裂。特征$X$对训练集$\mathcal{D}$的信息增益比$g_R(\mathcal{D},X)$定义为：
$$g_R(\mathcal{D},X)=\frac{g(\mathcal{D},X)}{H_X(\mathcal{D})}$$
  其中，$g(\mathcal{D},X)$是特征$X$的信息增益，$H_X(\mathcal{D})$是特征$X$的熵。通过计算信息增益率，C4.5算法对信息增益乘以一个加权系数，希望在增加信息的同时，不要以分割太细为代价。

4）总结

  信息增益率是C4.5算法中用于选择分裂特征的关键指标，它平衡了信息增益和特征取值的数量，从而避免了ID3算法中可能出现的过分裂问题。

c、决策树的损失函数

  决策树中使用的损失函数取决于任务的类型：

• 分类任务：通常使用Gini指数作为损失函数。Gini指数衡量的是数据集的不纯度，值越小表示数据集越纯。

• 回归任务：通常使用L2损失（平方损失）作为损失函数。L2损失衡量的是预测值与真实值之间差的平方和，值越小表示模型的预测越准确。

  L2正则在线性回归模型章节已经讲过，下面我们主要来讲应用在分类任务中的Gini指数。

1）Gini指数

  Gini指数是一种衡量数据集不纯度的指标，它无需使用对数函数，因此计算速度更快。对于一个数据集$\mathcal{D}$，其Gini指数定义为：
$$H(\mathcal{D})=\sum _{c=1}^C{\hat{\pi }}_c(1-{\hat{\pi }}_c)$$
  其中，${\hat{\pi }}_c=\frac{N_c}{N}=\frac{{\sum }_{i=1}^N\mathbb{I}(y_i=c)}{N}$是第$c$类样本在数据集中的比例。

2）为什么不使用错误率？

  错误率定义为：
Err ( D ) = 1 − max ⁡ c { π ^ c } \text{Err}(\mathcal{D}) = 1 - \max_{c} \{\hat{\pi}_c\} Err(D)=1−cmax​{π^c​}
  错误率曲线将数据集分为两个区间，在每个区间内是直线。如果划分后的子节点和父节点在同一条直线上，则划分后错误率不会下降，从而无法进一步分裂节点。

3）Gini指数的优势

  与错误率曲线不同，Gini指数的曲线也分为两个区间，但在每个区间内是向上凸起的。这样，划分后子节点的熵的平均值会比分裂前的熵小，从而可以继续分裂节点，直到达到分裂停止标准。

4）图示说明

  下图展示了两类分类的不纯度度量，包括Gini指数、熵和错误率随类别概率变化的曲线：

2）错误率 vs. Gini指数

2.1）示例说明

  假设父节点包含10个样本，其中正样本有7个，负样本有3个。我们可以计算错误率和Gini指数如下：

• 样本中正类($c=1$)和负类($c=0$)的比例分别为${\hat{\pi }}_1=0.3$和${\hat{\pi }}_0=0.7$。

• 错误率（Error Rate）计算为：
  Err ( D ) = 1 − max ⁡ { π ^ c } = 1 − 0.7 = 0.3 \text{Err}(\mathcal{D}) = 1 - \max\{\hat{\pi}_c\} = 1 - 0.7 = 0.3 Err(D)=1−max{π^c​}=1−0.7=0.3

• Gini指数（Gini Index）计算为：
  $$H(\mathcal{D})=\sum _{c=1}^C{\hat{\pi }}_c(1-{\hat{\pi }}_c)=0.7\times 0.3\times 2=0.41$$

2.2）决策树分裂效果

  如果我们根据特征$H$的值将数据集分裂为两个子集，我们可以计算每个子集的不纯度度量：

• 子集1（$H=\text{no}$）：

  • 错误率：$E({\mathcal{D}}_{\text{no}})=\frac{2}{5}$
  • 样本数：5
  • 类别分布：$[3/5,2/5]$
  • Gini指数：$H({\mathcal{D}}_{\text{no}})=0.48$

• 子集2（$H=\text{yes}$）：

  • 错误率：$E({\mathcal{D}}_{\text{yes}})=\frac{1}{5}$
  • 样本数：5
  • 类别分布：$[4/5,1/5]$
  • Gini指数：$H({\mathcal{D}}_{\text{yes}})=0.32$

  通过比较错误率和Gini指数，我们可以看到Gini指数在决策树分裂中提供了一个更加平滑的度量，有助于更好地评估分裂效果。在本例中，尽管子集2的错误率较低，但子集1的Gini指数较低，表明子集1的不纯度较低。因此，Gini指数可以帮助我们更全面地评估决策树的分裂效果。

2.3）左子结点分析

  左子结点包含5个样本，其中正样本3个，负样本2个。计算如下：

• 正负样本比例分别为 ${\hat{\pi }}_0=3/5$ 和 ${\hat{\pi }}_1=2/5$。
• 错误率计算为 Err L ( D ) = 1 − max ⁡ { π ^ c } = 1 − 3 / 5 = 2 / 5 \text{Err}_L(\mathcal{D}) = 1 - \max\{\hat{\pi}_c\} = 1 - 3/5 = 2/5 ErrL​(D)=1−max{π^c​}=1−3/5=2/5。
• Gini指数计算为 $H_L(\mathcal{D})={\sum }_{c=1}^C{\hat{\pi }}_c(1-{\hat{\pi }}_c)=3/5\times 2/5\times 2=12/25$。

左子结点分裂效果

• 初始错误率 $E(\mathcal{D})=3/10$，样本数10，分布 $[0.7,0.3]$。
• 分裂后：
  • 子集1（$H=\text{no}$）：错误率 $E({\mathcal{D}}_{\text{no}})=2/5$，样本数5，分布 $[3/5,2/5]$，Gini指数 $H({\mathcal{D}}_{\text{no}})=0.48$。
  • 子集2（$H=\text{yes}$）：错误率 $E({\mathcal{D}}_{\text{yes}})=1/5$，样本数5，分布 $[4/5,1/5]$，Gini指数 $H({\mathcal{D}}_{\text{yes}})=0.32$。

2.4）右子结点分析

  右子结点包含5个样本，其中正样本4个，负样本1个。计算如下：

• 正负样本比例分别为 ${\hat{\pi }}_0=4/5$ 和 ${\hat{\pi }}_1=1/5$。
• 错误率计算为 Err R ( D ) = 1 − max ⁡ { π ^ c } = 1 − 4 / 5 = 1 / 5 \text{Err}_R(\mathcal{D}) = 1 - \max\{\hat{\pi}_c\} = 1 - 4/5 = 1/5 ErrR​(D)=1−max{π^c​}=1−4/5=1/5。
• Gini指数计算为 $H_R(\mathcal{D})={\sum }_{c=1}^C{\hat{\pi }}_c(1-{\hat{\pi }}_c)=4/5\times 1/5\times 2=8/25$。

右子结点分裂效果

• 初始Gini指数 $H(\mathcal{D})=0.41$，样本数10，分布 $[0.7,0.3]$。
• 分裂后：
  • 子集1（$H=\text{no}$）：Gini指数 $H({\mathcal{D}}_{\text{no}})=0.48$，样本数5，分布 $[3/5,2/5]$。
  • 子集2（$H=\text{yes}$）：Gini指数 $H({\mathcal{D}}_{\text{yes}})=0.32$，样本数5，分布 $[4/5,1/5]$。

  通过比较左子结点和右子结点的分裂效果，我们可以看到Gini指数在评估分裂质量时提供了一个更细致的视角。尽管错误率在右子结点上更低，但Gini指数在两个子结点上都显示出较低的不纯度，表明Gini指数是一个有效的分裂评估指标。

3）分裂后的平均效果

3.1）分裂后的平均错误率和熵

  在进行数据集分裂后，我们可以计算平均错误率和平均熵来评估分裂的效果：

• 平均错误率：
  $$\text{Err}(\mathcal{D}|X)=\frac{5}{10}{\text{Err}}_L(\mathcal{D})+\frac{5}{10}{\text{Err}}_R(\mathcal{D})=0.3$$

• 平均熵：
  $$H(\mathcal{D}|X)=\frac{5}{10}{H}_L(\mathcal{D})+\frac{5}{10}{H}_R(\mathcal{D})=0.4$$

3.2）分裂前的情况

• 错误率：
  Err ( D ) = 1 − max ⁡ c { π ^ c } = 1 − 0.7 = 0.3 \text{Err}(\mathcal{D}) = 1 - \max_{c}\{\hat{\pi}_c\} = 1 - 0.7 = 0.3 Err(D)=1−cmax​{π^c​}=1−0.7=0.3

• 熵：
  $$H(\mathcal{D})=\sum _{c=1}^C{\hat{\pi }}_c(1-{\hat{\pi }}_c)=0.7\times 0.3\times 2=0.41$$

  从上面的计算可以看出，虽然分裂前后的错误率没有变化，但熵有所减少。这意味着尽管分类错误的比例没有改变，数据集的不纯度（或不确定性）有所降低，这是决策树分裂的一个积极效果。

三、分类回归树（Classification And Regression Tree， CART ）

1、基本概念

  ID3和C4.5根据特征取值，生成的树为多叉树。

  CART（Classification And Regression Tree）采用二分递归划分的方法：将当前样本集合划分为两个子集，分别为左右两个子节点，使得生成的每个非叶子节点都有两个分支，从而形成二叉树。

• 离散型特征：左右分支的组合较多（亦可将离散型特征编码成连续型特征）。

• 连续型特征：设特征$X$在$\mathcal{D}$中出现了$M$个不同的取值，将这些值从小到大排序，记作$a_1,a_2,...,a_M$，则共有$M-1$个候选划分点依次为：
  $$\frac{a_1+a_2}{2},\frac{a_2+a_3}{2},...,\frac{a_{M-1}+a_M}{2}$$

• 对于大数据集，训练数据中特征的取值数目$M$可能会很多，要考虑所有$M-1$个候选点开销太大，可考虑将特征分成多个区间，采用直方图方式快速寻找近似的最佳划分点（XGBoost、LightGBM）。

2、例：离散型特征

  根据日志密度$L$，候选分裂方式有3种（左右分支可交换为6种=8种减去空集和全集）：

日志密度$L$	好友密度$F$	是否使用真实头像$H$	账号是否真实$R$
s	s	no	no
l	l	yes	yes
l	m	yes	yes
m	m	yes	yes
l	m	yes	yes
m	l	no	yes
m	s	no	no
l	m	no	yes
m	s	no	yes
s	s	yes	no

  1. 左侧分支$L=s$，右侧分支 R = { l , m } R = \{l, m\} R={l,m}：

• $N_L=3$，$N_R=7$，$H({\mathcal{D}}_L)=\frac{4}{9}$，$H({\mathcal{D}}_R)=\frac{12}{49}$
• $H(\mathcal{D})=\frac{3}{10}\times \frac{4}{9}+\frac{7}{10}\times \frac{12}{49}=\frac{64}{210}$

  2. 左侧分支$L=l$，右侧分支 R = { s , m } R = \{s, m\} R={s,m}

• $N_L=3$，$N_R=7$，$H({\mathcal{D}}_L)=0$，$H({\mathcal{D}}_R)=\frac{24}{49}$
• $H(\mathcal{D})=\frac{3}{10}\times 0+\frac{7}{10}\times \frac{24}{35}=\frac{12}{210}$

  3. 左侧分支$L=m$，右侧分支 R = { s , l } R = \{s, l\} R={s,l}

• $N_L=4$，$N_R=6$，$H({\mathcal{D}}_L)=\frac{3}{8}$，$H({\mathcal{D}}_R)=\frac{4}{9}$
• $H(\mathcal{D})=\frac{4}{10}\times \frac{3}{8}+\frac{6}{10}\times \frac{4}{9}=\frac{5}{12}$

3、例：连续型特征

3.1）根据特征width的取值，对所有样本进行排序，得到可能的阈值为：6.25, 6.55, 6.75, 6.95。

width	height	Class
7.0	9.5	Orange
6.9	6.0	Orange
6.6	6.6	Orange
6.5	6.6	Lemon
6.0	6.6	Lemon
6.9	9.6	Lemon

  对每个可能的阈值，计算划分后的Gini指数：

• $H_{\text{width}>6.25}(\mathcal{D})=H_{\text{width}>6.95}(\mathcal{D})=\frac{1}{6}\times (0)+\frac{5}{6}\times \left(\frac{2}{5}\times \frac{3}{5}\times 2\right)=\frac{2}{5}$

• $H_{\text{width}>6.55}(\mathcal{D})=\frac{2}{6}\times (0)+\frac{4}{6}\times \left(\frac{1}{4}\times \frac{3}{4}\times 2\right)=\frac{1}{4}$

• $H_{\text{width}>6.75}(\mathcal{D})=\frac{3}{6}\times \left(\frac{1}{3}\times \frac{2}{3}\times 2\right)+\frac{3}{6}\times \left(\frac{2}{3}\times \frac{1}{3}\times 2\right)=\frac{4}{9}$

  通过计算不同阈值下的Gini指数，我们可以选择Gini指数最小的阈值作为最佳划分点，从而实现样本的最优分类。

3.2）根据特征height的取值，对所有样本进行排序，得到可能的阈值为：6.3, 8.05, 9.55。

width	height	Class
6.9	6.0	Orange
6.0	6.6	Lemon
6.5	6.6	Lemon
6.6	6.6	Orange
7.0	9.5	Orange
6.9	9.6	Lemon

  对每个可能的阈值，计算划分后的Gini指数：

• $H_{\text{height}>9.55}(\mathcal{D})=H_{\text{height}>6.3}(\mathcal{D})=\frac{1}{6}\times (0)+\frac{5}{6}\times \left(\frac{2}{5}\times \frac{3}{5}\times 2\right)=\frac{2}{5}$

• $H_{\text{height}>8.05}(\mathcal{D})=\frac{4}{6}\times \left(\frac{2}{4}\times \frac{2}{4}\times 2\right)+\frac{2}{6}\times \left(\frac{1}{2}\times \frac{1}{2}\times 2\right)=\frac{1}{2}$

  最佳决策规则为width > 6.55，划分后的Gini指数为$\frac{1}{4}$。

  根据这个规则，我们可以得到以下分类结果：

• 左侧分支（width ≤ 6.55）：2个Lemons
• 右侧分支（width > 6.55）：1个Lemon, 3个Oranges

4、划分停止条件

  建树过程是一个自顶向下的递归过程。在递归过程中，我们需要设定一些停止条件来避免过拟合和提高模型的泛化能力。

  递归的停止条件包括：

• 划分带来的损失的减小太小：当进一步划分不能显著提高模型的性能时，停止划分。
• 树的深度超过了最大深度：限制树的最大深度，防止树过于复杂。
• 叶子结点数目超过了最大数目：限制叶子结点的最大数量，控制模型复杂度。
• 左/右分支的样本分布足够纯净：当分支中的样本已经足够纯净，即大部分样本属于同一类别时，停止划分。
• 左/右分支中样本数目足够少：当分支中的样本数量少于某个阈值时，停止划分，以避免模型过拟合。

  通过这些停止条件，我们可以有效地控制决策树的生长，避免过拟合，提高模型的泛化能力。

5、剪枝

  分类回归树算法容易过拟合，通过剪枝去除部分分支，降低模型复杂度。

  剪枝：给定一个完全树，自底向上进行剪枝，直到根节点。

  剪枝准则：
$$C_{\alpha }(T)=\sum _{t=1}^{|T|}|{\mathcal{D}}_t|H({\mathcal{D}}_t)+\alpha |T|=C(T)+\alpha |T|$$

• 其中，$|{\mathcal{D}}_t|$ 是叶子结点$t$的样本数目，$H({\mathcal{D}}_t)$ 是叶子结点$t$的不纯净度，$\alpha$ 是正则因子，$|T|$ 是叶子结点数目。

  决策树划分得越细致，叶子结点的样本越纯净，但此时叶子结点越多。所以最佳模型是这两方面的折中。

  当$\alpha$从0开始增大，树的一些分支被剪掉，得到不同$\alpha$对应的树。

1）剪枝过程

  剪枝前费用：$T$表示绿色虚线框中的子树
$$C_A(T)=C(T)+\alpha |T|$$

  剪枝后的费用：子树$T$变成了一个叶子结点$t$
$$C_B(t)=C(t)+\alpha$$

  当$C_A(T)=C_B(t)$时，得到
$${\alpha }_{\text{eff}}=\frac{C(t)-C(T)}{|T|-1}$$

  某个结点是否要被剪枝的$\alpha$的临界点。

  当$\alpha >{\alpha }_{\text{eff}}$时，剪枝后的费用$C_B(t)$更小。进行剪枝会得到更优的决策树。

  $\alpha$不同时，得到的剪枝策略不同。

  最佳的$\alpha$通过验证集上的性能得到。

  蓝色虚线框内未剪枝部分费用不变，故而在此忽略

2）剪枝策略

  基于当前决策树结构，计算树中每个中间结点的${\alpha }_{\text{eff}}$。

  选择${\alpha }_{\text{eff}}$最小的中间结点，对其进行剪枝，得到新的决策树。

  迭代地进行剪枝，直到达到停止条件（如只有2层）。

3）验证集

  对一系列子树，计算其在验证集上的性能。

  验证集上性能最好的剪枝树胜出。

  子树$T_0$在验证集上的性能，子树$T_1$在验证集上的性能，输出在验证数据集中的预测误差，子树$T_2$在验证集上的性能，子树$T_n$在验证集上的性能。

4）Scikit-Learn中对剪枝的支持

  为了了解${\alpha }_{\text{eff}}$的哪些值可能是合适的，Scikit-learn中的决策树模型提供函数cost_complexity_pruning_path()，返回在修剪过程中每一步$\alpha$的有效性ccp_alpha（${\alpha }_{\text{eff}}$）和相应的总叶子结点的不纯净度。

  再根据验证集上的性能寻找最佳${\alpha }_{\text{eff}}$。

  以下是在Scikit-learn中实现剪枝的代码示例：

path = clf.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas, impurities = path.ccp_alphas, path.impurities
clfs = []for ccp_alpha in ccp_alphas:clf = DecisionTreeClassifier(random_state=0, ccp_alpha=ccp_alpha)clf.fit(X_train, y_train)clfs.append(clf)train_scores = [clf.score(X_train, y_train) for clf in clfs]
test_scores = [clf.score(X_test, y_test) for clf in clfs]

  图中展示了训练集和测试集上的准确率与α值的关系。可以看到，随着α值的增加，模型的复杂度降低，测试集上的准确率先是保持稳定，然后逐渐下降。最佳${\alpha }_{\text{eff}}$即为测试集准确率最高的点对应的α值。

四、决策树的优缺点

1、决策树模型的优点

  决策树是一种非常直观且易于理解的模型，它具有以下几个显著优点：

• 容易解释：决策树的结构清晰，易于解释和展示，使得非专业人士也能理解和使用。
• 对特征预处理要求少：
  • （理论上）能处理离散值和连续值混合的输入（实际需根据具体工具包的要求）
  • 对特征的单调变换不敏感（只与数据的排序有关）
  • 能自动进行特征选择
• 可扩展到大数据规模：决策树可以处理大规模数据集，且在大数据环境下表现良好。

2、决策树模型的缺点

  尽管决策树有许多优点，但它也有一些缺点：

• 正确率不高：建树过程过于贪心，可能导致过拟合。
  • 可作为Boosting的弱学习器（深度不太深）
• 模型不稳定（方差大）：输入数据小的变化会带来树结构的变化。
  • Bagging & 随机森林
• 当特征数目相对样本数目太多时，容易过拟合：在特征数量远大于样本数量的情况下，决策树容易过拟合训练数据。

  这些缺点可以通过集成学习方法（如随机森林、Boosting等）来缓解，提高模型的泛化能力和稳定性。

五、DecisionTreeClassifier类

  DecisionTreeClassifier是Scikit-learn库中用于分类任务的决策树模型。其构造函数如下：

class sklearn.tree.DecisionTreeClassifier(*, criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, class_weight=None, ccp_alpha=0.0)

  决策树算法特有的参数：

• criterion、splitter、max_features
• max_depth、max_leaf_nodes
• min_samples_split、min_samples_leaf
• min_weight_fraction_leaf、min_impurity_decrease
• min_impurity_split、ccp_alpha

1、DecisionTreeClassifier的参数

参数	说明	备注
criterion	权衡划分质量的指标 'gini'（默认）：Gini指数 'entropy'：熵
splitter	划分方式： 'best'（默认）：在特征的所有划分点中找出最优值 'random'：在一些随机划分点中找最优分裂点	'best'适合样本量不大的时候，如果样本数据量非常大，推荐'random'。
max_features	寻找最佳分裂点时，考虑的特征数目 None（默认）：考虑所有的特征； "log2"：最多考虑${\log }_{2}D$个特征； "sqrt"/"auto"：最多考虑$\sqrt{D}$个特征。 整数：考虑的特征的绝对数目。 浮点数：考虑特征数目的百分比，即（百分比$\times D$）取整后的特征数。其中$D$为样本总特征数。	如果样本特征数不多，如小于50，用默认的"None"即可。如果特征数非常多，可以控制分裂时考虑的最大特征数，以控制决策树的生成时间。
max_depth	树的最大深度。 None（默认），在建树时不限制树的深度，直到每个叶子结点都是纯净的或叶子结点的样本数目小于min_samples_split。	数据少或者特征少的时候可以默认值。如果模型样本量多，特征也多的情况下，推荐限制最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
max_leaf_nodes	最大叶子节点数目。 以最好优先（best-first）的方式生成树时，用该参数限制叶子结点数目。 None（默认）：不限制叶子结点数目。	如果不为None，则忽略max_depth。
min_samples_split	对中间结点进行分裂的最小样本数。 整数：样本绝对数目 浮点数：样本百分比 默认值为2	如果样本量数量级非常大，则推荐增大该参数。如10万样本，min_samples_split=10。
min_samples_leaf	叶子节点包含的最小样本数。 整数：样本绝对数目 浮点数：样本百分比 默认值为1	如果某叶子节点数目小于该参数，则会和兄弟节点一起被剪枝。min_samples_split约为min_samples_leaf的2倍。
min_weight_fraction_leaf	叶子结点所有样本权重和的最小值。 默认值为0，不考虑权重约束。当没有设置sample_weight时，每个样本的权重相等。	如果某叶子结点样本权重和小于该参数，则会和兄弟结点一起被剪枝。
min_impurity_decrease	结点划分最小不纯度下降量。如果结点划分带来的不纯度下降小于这个阈值，则该结点不再划分，为叶子结点。	不纯度下降（可带样本权重）： $$\frac{N_m}{N}\left(\text{impurity}-\frac{N_{\text{left}}}{N_m}H({\mathcal{D}}_L)-\frac{N_{\text{right}}}{N_m}H({\mathcal{D}}_R)\right)$$
class_weight	每个类别的权重：{class_label: weight}。如果不给定，所有类别的权重均1。"balanced"模式：自动调整权重。n_samples / (n_classes * np.bincount(y))	还可以设置样本权重（fit函数）
random_state	随机种子
ccp_alpha	后剪枝中结点有效性的阈值。

2、DecisionTreeClassifier的属性

  DecisionTreeClassifier提供了一些有用的属性，可以帮助我们了解模型的结构和特征的重要性。以下是这些属性的详细说明：

属性	说明	备注
classes_	类别标签	模型训练后，所有可能的类别标签。
n_classes_	类别数目	模型训练后，类别的总数。
feature_importances_	特征重要性	每个特征对模型预测的贡献程度，可根据特征重要性做特征选择。
max_features_	max_features的值	实际用于模型训练的特征数目的最大值。
n_features_	训练模型（fit）的特征数目	模型训练时使用的特征总数。
n_outputs_	训练模型（fit）的输出的数目	模型训练时目标变量的数目。
tree_	树	训练后的决策树模型本身，可以用于可视化和分析。

  这些属性为我们提供了模型的详细信息，有助于我们更好地理解和解释模型的行为。

3、DecisionTreeClassifier的方法

  DecisionTreeClassifier提供了一系列的实用方法，用于模型训练、预测和评估。以下是这些方法的详细说明：

方法	说明
apply(X[, check_input])	返回每个样本对应的叶子结点索引。
fit(X, y[, sample_weight])	模型训练。参数X, y为训练数据，也可以通过sample_weight设置每个样本的权重。
predict(X)	返回X对应的预测值（类别标签）。
predict_log_proba(X)	返回X对应的预测值（每个类别对应的概率的log值）。
predict_proba(X)	返回X对应的预测值（每个类别对应的概率）。
score(X, y[, sample_weight])	评估模型预测性能，返回模型预测的正确率。
decision_path(X[, check_input])	返回每个样本对应的树的决策路径。

  这些方法使得DecisionTreeClassifier不仅能够进行分类任务，还能够提供模型内部的详细信息，如特征重要性、决策路径等，有助于模型的解释和优化。