机器学习——决策树

1.什么要学习决策树？

        处处都是选择,并且到处都是岔路口。比如你发现某只股票几天时间内涨了很多,如果是你,你会买进吗？如果买进了,你就得承担后果,要么会大赚一笔,要么会血本无归。总之，用算法替代主观判断，避免情绪化投资决策。

2.什么是决策树？

        决策树是一种常见的分类和回归模型。通俗来说，决策树其实就是一颗能替我们做决策的树,或者说是是一种树，一种依托于策略抉择而建立起来的树。（有点类似于编程语言中的if-else结构）

2.1基本概念

        节点（Node）：表示一个特征或属性。

        根节点（Root Node）：树的最顶层节点，表示整个数据集的初始分割。

        内部节点（Internal Node）/子节点：除根节点和叶节点外的节点，用于进一步分割数据。

        叶节点（Leaf Node）：树的末端节点，表示分类或回归结果。

        边（Edge）：节点之间的连接，表示特征或属性的可能取值。

        路径（Path）：从根节点到叶节点的一条路径，表示一系列决策。

2.2图示例

        在这个推断的过程中,其实已经不知不觉中运用了一次,决策树的预测流程,也就是说这个脑回路就是一个决策树的模型。但模型确定好了,不管输入什么样的信息,都能预测出来到底是打篮球还是不打篮球,所以这才是理解决策树算法的关键！并不是理解如何根据输入来预测结果，关键在于如何构建出一个好的决策树模型,让我们的预测结果更加精准！

3.决策树的历史背景

      决策树的概念可以追溯到20世纪60年代。最早的决策树算法之一是ID3（Iterative Dichotomiser 3），由Ross Quinlan在1986年提出。ID3通过信息增益（Information Gain）选择特征来构建决策树。随后，Quinlan提出了C4.5算法，它是ID3的改进版，处理了缺失值和连续属性问题。在20世纪90年代，Leo Breiman等人提出了CART（Classification and Regression Trees）算法，该算法不仅适用于分类任务，还适用于回归任务。此外，CART算法引入了基尼指数（Gini Index）作为分裂标准。

4.构建决策树

        决策树算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

4.1 选择最佳特征

        一般来说，构建决策树时会遵循一个指标,有的是按信息增益来构建的,这种就叫ID3算法;有的是按信息增益比来构建的,这种叫C4.5算法;有的是按照基尼系数来构建的，这种叫CART算法。

4.1.1 ID3算法

        整个ID3算法是围绕着信息增益来的,所以要弄清楚ID3算法的流程。首先需要弄清楚什么是信息增益？但是要搞清楚信息增益之前,还得弄明白一个概念—熵（entropy）。所以什么是熵？在信息论和概率统计中,为了表示某个随机变量的不确定性,就引出了一个概念叫熵。

        这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

        对于某个数据集D来说，假设数据集中有n类样本，其中第k样本的比例为pk,则该数据集的信息熵为：

        数据集D的信息熵，反映了数据集D的混乱程度。Ent(D)越大，数据集中类别分布越混乱；Ent(D)越小，数据集D中类别越纯（比较极端的情况是：只有一个类别，此时Ent(D)为0）。

        假设某个属性a把数据集D划分成了V个子集D1,D2,...,DV,那么划分后，每个子集的信息熵为Ent(D1),Ent(D2),...,Ent(DV)。将子集的熵加权求和，结果作为划分后子集的熵。权为每个子集中元素的比例，因此，引入属性a划分数据集后，新的熵为：

        公式（1）为数据集初始的信息熵，公式（2）是引入属性a划分数据集后的信息熵，引入属性a前后，信息熵发生了改变。这种改变称为该属性带来的“信息增益”（information gain）,记为：

         既然属性可以带来信息的改变，就可以用信息增益大的属性来划分数据。因此，需要分别计算每个属性的信息增益，选择信息增益最大的属性作为决策树的根节点，然后根据根节点的属性值划分数据集。对划分后的数据集继续计算其余属性的信息增益，再选择信息增益最大的作为子树的根节点，如此进行下去，直到某个子集“纯”了为止。

        在理解了信息增益后,需要转变一下思路,把它套在机器学习上。

        举个案例：

        有11个样本的数据集D，其中标签属性中有7个输出为打篮球，4个为不打篮球。

        第一次划分：计算每个属性的信息增益，选择信息增益最大的节点作为根节点。

        根据公式（1）计算出训练集初始的熵为：

        属性“天气”有3个取值（晴、阴、小雨），如果以天气作为属性进行划分：

        如果以温度作为属性划分：

        湿度、刮风的计算细节就不再展示，同样的方法计算得出，当湿度作为属性进行划分，信息增益为0.6176；刮风作为属性进行划分，信息增益为0.0238。

        计算结果显示，当天气作为属性时，信息增益最大。因为ID3算法就是寻找信息增益最大的属性作为节点，所以我们最终选取天气作为根节点。

        天气已经确定为根节点，所以天气这个属性后面也不必再重复计算，以确保已经确定为节点的属性在任意路径最多只出现一次。

        当天气等于晴天时，所有的结果都是打篮球，没有任何不确定性，所以不必再继续分下去，叶子节点就是打篮球；

        当天气等于小雨时，所有的结果都是不打篮球，没有任何不确定性，所以也不必再继续分下去，叶子节点就是不打篮球；

        当天气等于阴天时，结果有打篮球，也有不打篮球。所以我们必须再从温度、湿度、刮风等条件属性中，找到信息增益最大的属性作为节点，继续分裂下去。

        计算方法和上面一样，分别求出当条件是温度、湿度、刮风时的信息增益。经过计算会发现选择属性温度时，信息增益最大，所以阴天这个分支，继续选择温度作为子节点。温度作为节点之后，再继续分裂，没有任何不确定性。当温度为中的时候，结果都是打篮球，低的时候，结果是不打篮球。所以整个决策树就构造完成了。

4.1.2 C4.5算法

        采用信息增益作为选择最佳根节点的标准，会对取值数量较多的属性有偏好，为了避免这种偏好产生负面影响，著名的C4.5算法采用“增益率（比）”来作为确定最佳根节点的标准，其中，增益率的计算公式为：

其中,

        IV(a)是属性a固有的属性。|D|表示数据集D中元素的数量。公式5本质上是熵。某个属性a的取值很多的时候，就会把数据集|D|划分成多个子集，那么这种划分就相当于比较混乱，IV(a)值就大，将其倒数作为系数去乘属性a的信息增益Gain(D,a),会压制信息增益对属性取值多的偏好。

        例如，如上面所讲，对于天气属性取值有3个，将数据集划分为3部分，每部分数据的数量分别为5个、3个、3个。此时，天气属性的IV（天气）为：

        从上面可以看出，属性的取值越多，其IV值越大，其IV值倒数越小，则按公式(4)计算出来的增益率被压制得越大。然而这样做又有了新的偏好，偏好属性取值数量少。C4.5算法在解决问题的时候，是将信息增益与增益率结合起来使用的，首先从候选属性中找到信息增益高于平均水平的属性，再选择增益率最高的属性作为根节点。

[天气]

/   |   \

晴 /   阴    \ 雨

/      |      \

打篮球  [温度]    不打篮球

/   \

中/     \低

/       \

打篮球    不打篮球

4.1.3 CART算法

        除了信息增益、增益率可以作为构造决策树的标准外，还可以使用基尼指数来生成决策树。分类与回归树（classification and regression tree,CART）是一种基于基尼指数生成决策树的方法。

        假设在分类问题中，数据集D有K个类，样本点属于第K类的概率为Pk,则数据集D的基尼值定义为：

        当数据集D中只有1个类别时，该类别出现的概率为1，Gini(D)=0,数据集是纯的，当数据集纯度越大，其基尼值越小。

        引入某个属性a后，将数据集D划分为若干子集，属性a的基尼指数定义为：

        在构造决策树时，选择基尼指数最小的属性作为根节点。

        依次计算每个属性的基尼指数，并将基尼指数最小的属性作为决策树的根节点。其余过程与ID3决策树的构造过程类似。

[天气]

/   |   \

晴 /   阴    \ 雨

/      |      \

打篮球  [温度]    不打篮球

/   \

中/     \低

/       \

打篮球    不打篮球

5.决策树剪枝

        无论是采用信息增益、增益率还是基尼指数构造决策树，构造出来一棵完全生长的决策树都会存在过拟合现象。为了降低过拟合的风险，需要对决策树进行剪枝处理（pruning）。决策树的剪枝有两种方法：预剪枝（pre-pruning）和后剪枝（post-pruning）。

        预剪枝是指在决策树的生成过程中，在每一步划分时，确定了划分属性后，先要估计一下泛化能力。（泛化能力是指机器学习模型对未见过的数据（即训练数据之外的数据）的适应和预测能力。）若当前划分能带来泛化性能的提升，则划分，否则，停止划分，并将当前节点标记为叶节点。后剪枝则是先利用训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察泛化性能。做法就是将数据集分成训练集和验证集。训练集用于构造决策树，验证集用于泛化性能的评估。

表1 训练集D1

表2 验证集

        如果不进行剪枝处理：

根据训练集D1构造的未剪枝的决策树

5.1 预剪枝

        预剪枝过程是先确定的划分属性，再判断泛化性能是否会提升来决定是否进行划分。

        基于信息增益准则，在划分前，所有的样本都集中在根节点，若不进行划分，该节点将被标记为叶节点，其类别标记为训练样本数最多的类别。在训练集中，两类样本一样多，先随便选择一类。假设将这个叶节点标记为“是”，也就是说，不管什么样的数据，决策树都判断打球为“是”。验证集精度为57.1%，若要对数据集D1进行划分，选择信息增益最大的属性进行划分，计算各个属性的信息增益如下：

        “天气”和“温度”属性的信息增益最大且相同，这里选择温度属性进行样例的划分，得到结果如图所示：

用温度属性生成的预剪枝决策树

预剪枝第1次划分过程

        然后，决定是否对“温度=高”的分支进行划分。由于验证集中“温度=高”的样本只有编号为2的1个样例，而且已经分类正确，由于划分后不会增加验证集的精度，故不再进行划分。对“温度=适中”进行划分：

        “湿度”的信息增益最大，故选择“湿度”进行划分。

预剪枝第2次划分

        采用湿度进行第二次划分后，训练集被分割为2个分支，将样本类别出现最多的类别作为叶节点，可以得到第二次预剪枝决策树。

采用湿度进行划分后的决策树

        用上面的决策树在验证集上分类，由于划分导致验证集精度降低，因此不用湿度进行划分。

        接下来对“温度=低”进行划分：

        选择具有最大信息增益的风进行划分：

采用风进行划分的过程

        用上面的决策树在验证集上分类，由于划分导致验证集精度降低，因此不用风进行划分。用风划分取消。预剪枝的最终结果：

预剪枝最终的决策树

5.2 后剪枝

        后剪枝先从训练集生成一棵完整的决策树，根据表1中的训练集，构造的完全生成的决策树如下提，该决策树在验证集上的分类精度为71.4%。

根据训练集构建的完全生长的决策树

        后剪枝首先考虑节点4，若将其余分支剪除，则相当于把节点4替换为叶节点，替换后的叶节点包含编号为{5，6，10}的训练样本，选择这几个样本中最多的类别作为叶节点的标签。此时决策树的验证集精度下降为42.9%，于是，节点4保留。如下图所示。

剪枝节点4验证集精度前后对比

        接下来考虑是否剪掉节点3，若将其余分支剪除，则相当于把节点3替换为叶节点，替换后的叶节点包含编号{3，13，15}的训练样本，该叶节点的类别标记为是。此时决策树的验证集精度仍为71.4%，没有得到改善。节点3得到保留。

剪枝节点3验证集精度前后对比

        然后考虑节点2，替换后的叶节点包含编号为{1，8，11，16}的训练样本。

剪枝节点2验证集精度前后对比

        对于节点1，如果将其分支剪除，节点1包含训练集中的所有样本，类别为是和否都为5个，则将叶节点的类别标记为是（当样本类别最多的类不唯一时，可任选其中一类），所得到的决策树的验证集精度下降到57.1%。节点1 保留。

        最终，基于后剪枝策略所生成的决策树，如下图：

最终的后剪枝决策树

预剪枝最终的决策树

        可以看出，后剪枝的决策树比预剪枝的决策树分支更多。一般，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝的决策树。但后剪枝需要先生成一棵完全生长的决策树，再自底向上地对树中所有的非叶子节点进行逐一判断，因此其训练过程中的时间开销比预剪枝决策树大很多。

6.决策树与集成学习

        集成学习是将多个弱模型（如决策树）组合成一个强模型，以提高整体的预测性能。主要思想是：多个模型的“集体智慧”要优于单个模型的判断。（决策树是集成学习中最常用的基础模型。）

        决策树比较容易过拟合，因此需要树的结构进行约束。利用剪枝等方法来砍掉冗余的分支，使得树结构尽量简单，以提高树模型在未训练数据上的预测表现(也就是泛化能力)。除此之外，集成学习(Ensemble Learning)，横向地增加多个树，并利用多个树模型结果综合判断，也是个能提高模型性能常用方法。（集成学习通过多个决策树组合，弥补单棵树的不足。）

        集成后的模型比单一决策树更强、更稳定、更精准。