【机器学习】决策树系统 | 决策树基本原理，最优划分属性，剪枝处理

决策树是一种常用的机器学习算法，它模拟了人类决策过程中的思考方式。想象一下，你要决定是否出门散步，你可能会考虑几个因素：天气、心情、体力状况等。每个因素都像是一个问题，你的回答（是或否）会引导你做出最终的决定。决策树就是这样一种结构，它通过一系列的问题来帮助你做出选择。

通俗来说，决策树由以下几个部分组成：

1. 根节点（Root Node）：这是决策树的起点，相当于你要解决的问题。比如，你的问题可能是“今天是否出门散步”。

2. 内部节点（Internal Nodes）：这些节点代表决策过程中的考虑因素。比如，你可能要考虑“天气是否晴朗”、“心情是否好”、“体力是否充沛”。

3. 分支（Branches）：每个内部节点都会分出两个或更多的分支，这些分支代表了对问题的肯定或否定回答。例如，“天气晴朗”是一个分支，“天气不晴朗”是另一个分支。

4. 叶节点（Leaf Nodes）：这些是决策树的终点，代表了最终的决策结果。比如，一个叶节点可能是“出门散步”，另一个可能是“不出门”。

构建决策树的过程通常包括以下几个步骤：

• 数据准备：收集相关的数据，这些数据包含了不同的特征（比如天气、心情等）和对应的决策结果（是否出门）。

• 选择最佳特征：在每个节点上，算法会评估哪个特征最能区分数据，以便做出最好的决策。这通常涉及到计算特征的信息增益、基尼不纯度或熵等指标。

• 递归构建：从根节点开始，根据选择的最佳特征，递归地创建分支，直到达到叶节点。每个叶节点都对应一个决策结果。

• 剪枝：为了防止过拟合（模型在训练数据上表现很好，但在新数据上表现不佳），通常会对决策树进行剪枝，移除一些不必要的分支。

决策树的优点是模型简单直观，易于理解和解释。但它也有缺点，比如容易过拟合，对于数据中的小变化可能过于敏感。为了克服这些缺点，通常会使用一些改进的决策树算法，如随机森林和梯度提升树等。

1 基本原理

伪代码如下

def 决策树构建(数据集):
    if 数据集中所有实例都属于同一类别，则返回单节点树return ，类别为该类别
    if 特征集为空，则返回单节点树，类别为数据集中实例数最多的类别

    否则，选择最优特征 best_feature 划分数据集(在第二节讲，（最重要的）)
    使用最优特征 best_feature 划分数据集，得到子集合 sub_datasets
    对于每个子集合 sub_dataset：
        if 子集合为空，则将该子节点标记为叶节点，类别为数据集中实例数最多的类别
        else 递归调用 决策树构建(sub_dataset)，得到子树
            将子树作为当前节点的一个分支

    返回当前节点作为根节点的决策树

1
2
3
4
5
6
7
8
9
10
11
12
13

2 最优划分属性选择

其中

关键是，如何选择最优划分属性，使得节点纯度越来越高

用信息增益，增益率，基尼系数

2.1 信息增益选择最优属性方法

信息增益（Information Gain）是决策树算法中用来选择特征的一个关键指标。它基于信息论中的熵（Entropy）概念，用于衡量数据集的不确定性。在构建决策树时，我们希望选择那些能够最大程度减少数据集不确定性的特征，即具有最高信息增益的特征。利用C

信息增益的基本思想是：如果一个特征能够将数据集划分成几个子集，而这些子集在类别上更加纯净（即子集中的实例大多数属于同一个类别），那么这个特征就被认为是好的，因为它增加了我们对数据集分类的知识。

好的，我们来用一个简单的例子来讲解信息增益的计算。假设你想要决定是否去打篮球，而天气是一个影响因素。你有以下数据：

• 总共有 10 天的数据
• 其中 6 天是晴天，4 天是阴天
• 在晴天中，有 4 天去打篮球，2 天不去
• 在阴天中，有 1 天去打篮球，3 天不去

首先，我们需要计算在没有任何信息的情况下，天气对我们的决定产生的平均信息量。这个值称为信息熵（Entropy）。计算公式如下：

$\text{Entropy}=-p(\text{play})\times {\log }_2(p(\text{play}))-p(\text{not play})\times {\log }_2(p(\text{not play}))$

其中， $p(\text{play})$是打篮球的概率，$p(\text{not play})$ 是不打篮球的概率。在这个例子中，两个都等于0.5

所以，信息熵为：

$\text{Entropy}=-0.5\times {\log }_2(0.5)-0.5\times {\log }_2(0.5)=-0.5\times (-1)-0.5\times (-1)=1$

接下来，我们计算根据天气（晴天或阴天）来划分数据集后的信息增益。信息增益表示在知道了天气信息之后，对于打篮球决策的不确定性减少了多少,减少的越多越好，计算公式如下：

$\text{Gain}(S,\text{Weather})=\text{Entropy}(S)-{\sum }_{v\in \text{Values}(\text{Weather})}\frac{|S_v|}{|S|}\times \text{Entropy}(S_v)$

其中，( S ) 是原始数据集，$(\text{Weather})$ 是天气这个特征，$\text{Values}(\text{Weather})$ 是天气可能的取值（这里是晴天和阴天），$(S_v)$ 是在天气为 ( v ) 时的数据集。

在这个例子中，我们需要计算晴天和阴天两种情况下的信息熵：

对于晴天：

$\text{Entropy}(S_{\text{sunny}})=-\frac{4}{6}\times {\log }_2(\frac{4}{6})-\frac{2}{6}\times {\log }_2(\frac{2}{6})\approx 0.918$

对于阴天：

$\text{Entropy}(S_{\text{overcast}})=-\frac{1}{4}\times {\log }_2(\frac{1}{4})-\frac{3}{4}\times {\log }_2(\frac{3}{4})\approx 0.811$

然后，我们计算信息增益：

$\text{Gain}(S,\text{Weather})=\text{Entropy}(S)-\left(\frac{6}{10}\times \text{Entropy}(S_{\text{sunny}})+\frac{4}{10}\times \text{Entropy}(S_{\text{overcast}})\right)=1-0.874\approx 0.126$

将具体的值代入计算即可得到信息增益的结果

例子中我们只有一个属性，即天气情况，实际中有可能有多个属性，比如心情，作业多少等等

我们要依次计算每一个属性的信息增益，选出信息增益最大的那个，不确定度减小最多的那个属性作为下一次的划分属性

2.2 信息增益率选择最优属性方法——C4.5决策树

信息增益率是在信息增益基础上的一些改进，可以减少对可取值数目较多的属性产生的偏好

首先计算出增益率Gain

$\text{Gain}(S,\text{Weather})=\text{Entropy}(S)-\left(\frac{6}{10}\times \text{Entropy}(S_{\text{sunny}})+\frac{4}{10}\times \text{Entropy}(S_{\text{overcast}})\right)=1-0.874\approx 0.126$

然后要计算一个新的指标

$IV(\text{feature})=-{\sum }_{i=1}^n\frac{|S_i|}{|S|}\times {\log }_2\left(\frac{|S_i|}{|S|}\right)$

最后两个一相除就可以了,得到GainRatio

$\text{GainRatio}(\text{feature})=\frac{\text{Gain}(\text{feature})}{IV(\text{feature})}$

对应到我们上面的例子

对于“天气”：

$IV(\text{Weather})=-\left(\frac{6}{10}\times {\log }_2(\frac{6}{10})+\frac{4}{10}\times {\log }_2(\frac{4}{10})\right)$[ ≈ 0.971 ]

最后，计算信息增益率：

对于“天气”：

$\text{GainRatio}(\text{Weather})=\frac{0.126}{0.971}$≈ 0.13

2.3 基尼指数选择最优属性——CART决策树

CART（Classification and Regression Trees）决策树是一种常用的机器学习算法，他用基尼指数进行节点的选择。

基尼指数越小，节点的纯度越高，也就是节点中包含的样本属于同一类别的概率越大。

基尼指数的计算公式如下：

$Gini(p)={\sum }_{k=1}^K{p}_k(1-p_k)$

其中，(p_k) 是样本属于第 (k) 类的概率，(K) 是类别的总数。对于二分类问题，(K=2)，可以简化为：

$Gini(p)=1-p^2-(1-p{)}^2$

在构建CART决策树时，算法会选择使得划分后基尼指数最小的特征和划分点作为节点的划分依据，从而构建出一棵具有较高预测准确率的决策树。

让我们来考虑一个更贴近日常生活的例子：假设有一个电商平台，想要通过用户的年龄和购买金额来预测用户是否会购买某种产品。我们有以下几位用户的数据：

我们以年龄作为划分特征，考虑以30岁和40岁为划分点进行划分。

1. 以30岁为划分点，划分后的基尼指数计算如下：

   • 年龄小于等于30岁的组：

     • 购买：25岁、200元
     • 未购买：无

   • 年龄大于30岁的组：

     • 购买：35岁、150元
     • 未购买：45岁、100元；55岁、50元；65岁、20元

   计算基尼指数：

   $Gin{i}_{\text{30岁}}=1-(1^2+0^2)=0$

2. 以40岁为划分点，划分后的基尼指数计算如下：

   • 年龄小于等于40岁的组：

     • 购买：25岁、200元；35岁、150元
     • 未购买：无

   • 年龄大于40岁的组：

     • 购买：无
     • 未购买：45岁、100元；55岁、50元；65岁、20元

   计算基尼指数：

   $Gin{i}_{\text{40岁}}=1-(0.5^2+0.5^2)\approx 0.5$

综合来看，以30岁为划分点的基尼指数更低，因此在构建决策树时，应该选择以30岁为划分点进行划分。

3 剪枝处理

决策树的剪枝是为了防止过拟合而进行的一种策略，通过去除一些决策树中的节点（即剪枝），可以提高模型的泛化能力。主要有两种剪枝策略：预剪枝（Pre-pruning）和后剪枝（Post-pruning）。

3.1 预剪枝

预剪枝（Pre-pruning）：在构建决策树的过程中，在每个节点划分前都先进行判断，若当前节点的划分不能提高泛化性能，则停止划分，将当前节点标记为叶节点。预剪枝的优点是简单高效，可以减少决策树的过拟合，但可能会导致欠拟合，因为有时会过早停止划分，导致模型过于简单。

3.2 后剪枝

后剪枝（Post-pruning）：先构建完整的决策树，然后自底向上地对树进行剪枝。具体做法是对每个非叶节点，尝试将其变为叶节点并评估剪枝前后的泛化性能差异，若剪枝后泛化性能提高，则进行剪枝操作。后剪枝的优点是可以获得更加精确的剪枝决策，但需要额外的计算开销。

无论是预剪枝还是后剪枝，剪枝的目的都是为了在保持模型准确性的同时，降低模型的复杂度，避免过拟合。在实际应用中，可以根据数据集的大小和特性，以及模型的性能要求来选择合适的剪枝策略。