决策树

概述

决策树(Decision Tree)是一种常用的机器学习方法，是一种对实例进行分类的树形结构。以二分类问题为例，假设我们要对是否买西瓜进行决策。
定义决策树结构包括：

1. 内部结点：属性
2. 分支：属性值
3. 叶子结点：分类结果

于是，学习过程就是通过对训练样本的训练来确定“划分属性”（即内部结点对应的属性）；预测过程则是将测试用例从根节点开始，沿着树形结构下行，直到叶结点。
具体结构举例：

图片.png

if is_red:
    if is_cold:
        if has_seed:
            print("buy")
        else:
            print("don't buy")
    else:
        if is_cheap:
            print("buy")
        else:
            print("don't buy")
else:
    print("don't buy")

决策树的根节点(root node)到叶结点(leaf node)的每一条路径构成一条规则：路径上的内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。其基本策略是“分而治之”（divide-and-conquer），即在自根至叶的递归过程中，在每个中间结点寻找一个“划分”(split or test)属性

决策树学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，通常包括三个步骤：特征选择、决策树的生成和决策树的修剪。主要的决策树算法包括ID3算法、C4.5算法和CART算法。

特征选择

特征选择在于选取对训练数据具有分类能力的特征，一个合适的特征可以极大提高决策树的学习效率。相反，如果利用一个特征进行分类的结果与随机分类的结果没有很大的差别，则认为该特征没有分类能力。特征选择的标准一般有三类：信息增益、信息增益比和基尼指数。

熵

熵（entropy）表示随机变量的不确定性。假设是一个有限离散随机变量，其概率分布为

则随机变量的熵为：

条件熵

设有随机变量，其联合概率分布为：

随机变量给定的条件下随机变量的条件熵（conditional entropy），定义为给定条件下的条件概率分布的熵对的数学期望：
其中，

信息增益

信息增益（information gain）表示得知特征的信息而使得类的信息的不确定性减少的程度。定义特征对训练数据集的信息增益为：
熵与条件熵之差称为互信息（mutual information），于是决策树学习中的信息增益等价于训练数据集中类和特征的互信息。
此外，当熵和条件熵中的概率有数据估计得到时，所对应的熵和条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。

信息增益算法

输入：训练数据集和特征
输出：特征对训练数据集的信息增益

1. 计算数据集的经验熵
   
2. 计算特征对数据集的经验条件熵
   
3. 计算信息增益
   

信息增益比

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义，比如在训练数据集的经验熵大的时候，信息增益值会偏大。利用信息增益比（information gain ratio）对这一问题进行校正，定义特征对训练数据集的信息增益比为：

基尼指数

CART决策树使用基尼指数（Gini index）来选择划分属性，基尼指数表示集合的不确定性，基尼指数则表示经分割后集合的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。
分类问题中，假设有个类，样本点属于第类的概率为，则概率分布的基尼指数定义为
对于给定的样本集合，其基尼指数为

其中，是中属于第类的样本子集，是类的个数。
如果样本集合根据特征是否取某一可能值被分割成和两部分，则在特征的条件下，集合的基尼指数定义为

决策树的生成

ID3算法

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归调用以上方法，构建决策树。

具体流程

输入：训练数据集，特征集，阈值
输出：决策树

1. 若中所有实例属于同一类，则为单结点树，并将类作为该结点的类标记，返回；
2. 若，则为单结点树，并将中实例数量最大的类作为该结点的类标记，返回；
3. 否则，计算中各特征对的信息增益，选择信息增益最大的特征；
4. 如果的信息增益小于阈值，则置为单结点树，并将中实例数最大的类作为该结点的类标记，返回；
5. 否则，对的每一个可能指，依照将分割为若干非空自己，将中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树，返回；
6. 对第个子节点，以为训练集，以为特征集，递归地调用前5步，得到子树，返回

C4.5算法

C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进。C4.5在生成过程中选择用信息增益比来选择特征。

具体流程

输入：训练数据集，特征集，阈值
输出：决策树

1. 若中所有实例属于同一类，则为单结点树，并将类作为该结点的类标记，返回；
2. 若，则为单结点树，并将中实例数量最大的类作为该结点的类标记，返回；
3. 否则，计算中各特征对的信息增益比，选择信息增益比最大的特征；
4. 如果的信息增益比小于阈值，则置为单结点树，并将中实例数最大的类作为该结点的类标记，返回；
5. 否则，对的每一个可能指，依照将分割为若干非空自己，将中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树，返回；
6. 对第个子节点，以为训练集，以为特征集，递归地调用前5步，得到子树，返回

CART算法

CART是在给定输入随机变量条件下输出随机变量的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为"是"和"否"，这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测地概率分布，也就是在给定地条件下输出地条件概率分布。
CART算法由以下两步组成：

1. 决策树生成：基于训练数据集生成决策树，生成地决策树要尽量大
2. 决策树剪枝：用验证数据集对已生成地树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝地标准

CART生成算法

输入：训练数据集，停止计算的条件；
输出：CART决策树

1. 假设结点的训练数据集为，计算现有特征对该数据集的基尼指数。此时，对每一个特征，对其可能取的每个值，更具样本点对的测试为"是"或"否"将分割成和两部分，利用公式计算时的基尼指数。
2. 在所有可能的特征以及它们所有可能的切分点中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
3. 对两个子结点调用前两步，直至满足停止条件。
4. 生成CART决策树。算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

CART剪枝算法

输入：CART算法生成的决策树；
输出：最优决策树

1. 设，
2. 设
3. 自下而上地对各内部结点计算，以及
   这里，表示以为根结点的子树，是对训练数据的预测误差，是的叶结点个数。
4. 自上而下地访问内部结点，如果，进行剪枝，并对叶结点以多数表决法决定其类，得到树
5. 设，，
6. 如果不是根结点单独构成的树，则返回步骤4
7. 采用交叉验证法在子树序列中选取最优子树

决策树的修剪

概述

剪枝（pruning）是决策树学习算法处理过拟合问题地主要手段。决策树剪枝地基本策略有"预剪枝"（prepruning）和"后剪枝"（postpruning）。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点地划分不能带来决策树泛化性能的提升，则停止划分；后剪枝则是先从训练集生成一颗完整地决策树，人后自下而上对非叶结点进行考察，若该结点对应地子树替换为叶结点能带来泛化性能地提升，则将该子树替换成叶结点.

预剪枝

预剪枝就是在决策树生成过程中，在没有划分时，考虑能否带来决策树性能的提升。若可以提升决策树的性能则会进行划分，若不能则停止生长。
常用的方法如下：

1. 当树的深度达到一定规模时，停止生长
2. 当前结点的数量达到特定阈值时，停止生长
3. 计算每次分裂对于测试集性能的提升，当小于指定阈值，甚至有所下降时，停止生长
4. 当信息增益，信息增益比或基尼指数小于指定阈值时，停止生长

预剪枝优点：思想简单，算法高效，采用了贪心策略，适合大规模问题
预剪枝缺点：提前停止生长，存在欠拟合的风险

后剪枝

后剪枝的主要分类包括：

• 错误率降低剪枝（Reduce Error Pruning, REP）
• 悲观剪枝（Pressimistic Error Pruning, PEP）
• 代价复杂度剪枝（Cost Complexity Pruning, CCP）
• 最小误差剪枝（Minimum Error Pruning, MEP）
• CVP（Critical Value Pruning）
• OPP（Optimal Pruning）

其中，最小误差剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树的叶结点个数为，是树的叶结点，该叶结点有个样本点，其中类的样本点有个，，为上的经验熵，为参数，则决策树学习中的损失函数可以定义为：
输入：生成算法产生的整个树，参数；
输出：修剪后的子树

1. 计算每个结点的经验熵
2. 递归地从树的叶结点向上回缩
   设一组叶结点回缩到其父结点之前与之后的整体树分别为与，其对应的损失函数分别是与，如果
   则进行剪枝，即将父节点变成新的叶结点。
3. 返回步骤2，直至不能继续为止，得到损失函数最小的子树

后剪枝优点：可以最大限度的保留树的各个结点，避免了欠拟合的风险
后剪枝缺点：相较于预剪枝的时间开销大