16. 机器学习——决策树

机器学习面试题汇总与解析——决策树

本章讲解知识点

1. 什么是决策树
1. 决策树原理
1. 决策树优缺点
1. 决策树的剪枝
1. 决策树的改进型

本专栏适合于Python已经入门的学生或人士，有一定的编程基础。
本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。
本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵
如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。
相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。
关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。
关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。
B站机器学习视频：https://space.bilibili.com/10781175/channel/detail?cid=133301

1. 什么是决策树

1.1 前言

决策树是一种基于树形结构的机器学习模型，其灵感源自人类的决策过程。通过对数据进行逐步划分和推理，决策树能够自动学习和生成规则，从而在分类和回归任务中发挥作用。与其他复杂的机器学习算法相比，决策树的优势在于其易于理解和解释性强的特点，使得非专业人士也能够轻松理解和应用。

1.2 什么是决策树

决策树是一种基于树状结构的机器学习模型，用于解决分类和回归问题。它模拟了人类在面对决策时的思考过程，并通过构建一系列决策规则来预测目标变量的值。

决策树的构建过程始于根节点，通过对数据的特征进行划分，逐步生成分支和叶节点。每个内部节点代表一个特征，每个分支代表该特征的一个取值，而每个叶节点代表一个类别或一个数值。

在构建决策树的过程中，通过选择合适的划分准则和特征选择方法，使得每一次划分都能最大程度地提高数据的纯度或减少不确定性。常用的划分准则包括基尼系数、信息增益和信息增益率等。决策树构建完成后，可以根据输入样本的特征值通过从根节点开始的路径来预测样本的类别或数值。

2. 决策树原理

2.1 概述

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果

下面先来看一个小例子，看看决策树到底是什么概念：

我们有一系列的公民数据，记录了公民是否拥有房产、婚姻状况、年收入、是否能偿还债务等信息，我们需要通过这些信息训练出一个决策树模型，用来判断新的公民是否具备偿还债务的能力。

决策树的训练数据往往就是这样的表格形式，表中的前三列（ID不算）是数据样本的属性，最后一列是决策树需要做的分类结果。通过该数据，构建的决策树如下：

有了这棵树，我们就可以对新来的用户数据进行是否可以偿还的预测了。比如有一个新用户没有房产、没有结婚、年收入 1w，那么按决策树的流程判断，拥有房产（否）--> 已婚（否）--> 年收入（<80），因此最终的判断是该用户无法偿还债务。

2.2 如何构建决策树

决策树最重要的是决策树的构造。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。

构建决策树的过程可以分为以下几个步骤：

特征选择：选择最优的特征来进行划分是构建决策树的关键步骤。常用的特征选择方法有信息增益、信息增益比、基尼指数等。这些方法通过计算特征对于分类结果的纯度提升程度，选择对分类起到最大影响的特征作为划分依据。
样本划分：根据选定的特征，将数据集划分成子集。每个子集代表了特征取值相同或相似的样本子集。
递归构建子树：对于每个子集，重复步骤1和步骤2，继续划分子集，构建子树。这个过程是一个递归的过程，直到满足终止条件。
终止条件：构建决策树时需要定义终止条件，即停止划分的条件。常见的终止条件有以下几种：达到预定的树的深度、节点中样本数量小于预定阈值、节点中样本类别纯度达到一定阈值等。
叶节点标记：最后，对叶节点进行标记，将叶节点与对应的类别关联起来，表示最终的决策结果。

2.3 特征选择

刚才我们已经讲了，构建决策树的关键就在于特征选择。是否拥有房产、婚姻状况、年收入，这些都是特征。

我们来看看刚才已经构建好的决策树：

那我们就有疑问了，决策树凭什么将拥有房产这个特征作为第一个判断条件？为什么不是婚姻状况或者年收入呢？回答清楚这个问题后，就等于回答了决策树是如何构建的。

ok，决策树凭什么将拥有房产这个特征作为第一个判断条件？肯定会有一个衡量标准，常用的有三个：信息增益、信息增益比、基尼指数。

1.信息增益

信息论中有熵（entropy）的概念，表示状态的混乱程度，熵越大越混乱。熵的变化可以看做是信息增益，决策树 ID3 算法的核心思想是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。

设 D 为用（输出）类别对训练元组进行的划分，则 D 的熵表示为：

$info(D)=-\sum_{i=1}^m p_ilog_2(p_i)$

其中 $p_{i}$ 表示第 $i$ 个类别在整个训练元组中出现的概率， $m$ 表示类别数。一般来说会用这个类别的样本数量占总量的占比来作为概率的估计。

信息增益（Information Gain）是一种用于特征选择的指标，用于衡量使用某个特征对数据进行划分后所带来的信息增加量。在决策树算法中，通过计算信息增益来确定最优的划分特征。

如果将训练元组 D 按属性 A 进行划分，则 A 对 D 划分的期望信息为， $v$ 表示子集数：

$info_A(D) = \sum_{j=1}^v \frac{|D_j|}{|D|}info(D_j)$

于是，信息增益就是两者的差值：

$g a i n (A) = i n f o (D) - i n f o_{A} (D)$

在每次分裂的时候贪心选择信息增益最大的属性，作为本次分裂属性。可以这么理解，选择一个特征，数据集按这个特征来划分子集，划分前熵较大（不确定性高），划分后熵较小（确定性高），换个角度理解：其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。

每次分裂就会使得树长高一层。这样逐步生产下去，就一定可以构建一颗决策树。

我们以上面的例子来举例信息增益如何计算：

首先计算数据集 D 的熵 Entropy(D)，类别为可以偿还债务的数量为 3，占比为 3/10，类别不可以偿还债务的数量为 7，占比为 7/10，则熵 Entropy(D)： $E n t r o p y (D) = - (3 / 10) * l o g 2 (3 / 10) - (7 / 10) * l o g 2 (7 / 10) \approx 0.881 Entropy(D) = - (3/10) * log2(3/10) - (7/10) * log2(7/10) ≈ 0.881$

接下来，根据特征拥有房产进行划分，计算划分后的子集 D1 和 D2 的熵 Entropy(D1) 和 Entropy(D2)：

在特征拥有房产的取值为是的情况下，子集 D1 包含 3 个样本，其中类别为可以偿还债务的数量为 0，类别为不可以偿还债务的数量为 3。

$E n t r o p y (D 1) = - (0 / 3) * l o g 2 (0 / 3) - (3 / 3) * l o g 2 (3 / 3) = 0$

在特征拥有房产的取值为否的情况下，子集 D2 包含 7 个样本，其中类别可以偿还债务的数量为 3，类别不可以偿还债务的数量为 4。

$E n t r o p y (D 2) = - (3 / 7) * l o g 2 (3 / 7) - (4 / 7) * l o g 2 (4 / 7) \approx 0.985 Entropy(D2) = - (3/7) * log2(3/7) - (4/7) * log2(4/7) ≈ 0.985$

最后，计算信息增益Information Gain：

$I n f o r m a t i o n G a i n = E n t r o p y (D) - (∣ D 1 ∣ / ∣ D ∣) * E n t r o p y (D 1) - (∣ D 2 ∣ / ∣ D ∣) * E n t r o p y (D 2)$ $I n f o r m a t i o n G a i n = 0.881 - (3 / 10) * 0 - (7 / 10) * 0.985 \approx 0.1915 Information Gain = 0.881 - (3/10) * 0 - (7/10) * 0.985 ≈ 0.1915$

这是特征拥有房产的信息增益，特征是否婚姻、年收入可以用同样方法计算，就会发现拥有房产的信息增益最大，因此第一个判断条件就以特征拥有房产为先。

由此我们就解释了特征如何选择，决策树如何构建。

2.信息增益比

ID3 有一些缺陷，就是选择的时候容易选择一些比较容易分纯净的属性，尤其在具有像 ID 值这样的属性，因为每个 ID 都对应一个类别，所以分的很纯净，ID3 比较倾向找到这样的属性做分裂。

C4.5 算法定义了分裂信息，表示为：

$splitinfo_A(D) = -\sum_{j=1}^v \frac{|D_j|}{|D|}log_2(\frac{|D_j|}{|D|})$

很容易理解，这个也是一个熵的定义，，可以看做是属性分裂的熵，分的越多就越混乱，熵越大。定义信息增益率：

$gainratio(A) = \frac{gain(A)}{splitinfo(A)}$

C4.5 就是选择最大增益率的属性来分裂，其他类似 ID3.5。

3.基尼系数

信息增益和信息增益率涉及到对数运算，计算量大，这是一个缺点。

CART 算法采用基尼系数对属性进行划分，基尼系数越小越好。

$Gini(D)=1 - Σ_{j=1}^v(p_j^2)$

2.4 小结

通过特征选择后，我们就能构建出一颗决策树来，用来决策了，原理其实不复杂。决策树其实不难，是一种分类方法，像一棵树一样进入不同的分支，然后直到叶子节点得到分类结果。那么如何进入不同的分支？这就是最重要的内容，涉及到节点（特征）的划分标准，有三种划分标准：最大信息增益、最大信息增益率、基尼系数。而这三种不同的划分标准就对应了三种典型决策树：ID3（最大信息增益）、C4.5（最大信息增益率）、CART（基尼系数）。

3. 决策树优缺点

优点：

易于理解和解释：决策树的构建过程类似于人类的决策过程，易于理解和解释，可以提供可解释性的规则。
可处理离散和连续特征：决策树可以处理各种类型的特征，包括离散特征和连续特征。
能够处理多输出问题：决策树可以处理多输出问题，而不仅仅是二分类或多分类问题。
对异常值和缺失值具有鲁棒性：决策树对于异常值和缺失值具有一定的鲁棒性，能够处理这些数据异常情况。
一次构建，反复使用。
输入值不需要做归一化处理。

缺点：

容易过拟合：决策树容易过拟合训练数据，特别是在处理复杂问题时，可能会生成过于复杂的树结构，导致过拟合。
不稳定性：对于数据的小变化非常敏感，稍微改变训练数据可能会导致完全不同的树结构，这使得决策树在一些情况下不够稳定。
忽略属性之间的相关性：决策树通常独立考虑每个特征，忽略了特征之间的相关性，这可能导致一些相关特征在划分时没有得到充分利用。
高计算复杂度：决策树的构建过程需要遍历特征空间，计算信息增益或基尼系数，对于大规模数据集而言，计算复杂度较高。

4. 决策树的剪枝

决策树的剪枝是为了减少过拟合而进行的一种技术，通过修剪决策树的一部分节点或子树，以降低模型复杂度，提高泛化能力。决策树的剪枝可以分为预剪枝（Pre-Pruning）和后剪枝（Post-Pruning）两种方法。

预剪枝（Pre-Pruning）：

预剪枝是在决策树构建过程中，在决策树生长过程中进行剪枝。具体来说，预剪枝在决策树的构建过程中对每个节点进行评估，决定是否停止划分该节点并将其标记为叶子节点。预剪枝的常用策略包括以下几种：

最大深度限制：设定决策树的最大深度，超过该深度则停止划分。
叶