决策树

一、了解决策树

决策树(Decision Tree)是一类常见的机器学习算法，属于非参数的监督学习方法，主要用于分类和回归，也可以用于特征提取。

决策树是一棵树（很像流程图），它包含一个根节点、几个内部节点和几个叶节点。树的最高层是根节点，它包含完整的样本集。内部节点代表对应特征的测试，每个节点包含的样本根据测试结果划分为子节点，即树的分支代表该特征的每个测试结果。每个叶节点代表一个类别或决策结果。从根节点到叶节点对应一个决策测试序列。

决策树的目的是构造一种模型，使之能够从样本数据的特征属性中，通过学习简单的决策规则——if-then规则，从而预测目标变量的值。

下图是决策树的示意图。内部节点用矩形表示，叶节点用椭圆表示。

示意图解释：如有一个孩子升学选学校，根据自己意愿选择学校性质，只去公立学校。然后根据自己分数（低于500），500多分的学校去不了。最后根据学费收取情况，想去好一点的，最后选择了8k的学校。举个例子，逻辑不是很通，理解理解。

二、决策树的基本流程

决策树的生成过程主要包括决策树的生成和剪枝两部分。
基本流程：
1.从开始位置，将所有数据划分到一个节点，即根节点。
2.经历两个步骤判断条件：
（1）若数据为空集，跳出循环。
（2）若样本都属于同一类，跳出循环，节点标记为该类别；
3.如果经过橙色标记的判断条件都没有跳出循环，则考虑对该节点进行划分。
4.经历上步骤划分后，生成新的节点，然后循环判断条件，不断生成新的分支节点，直到所有节点都跳出循环。
5.结束，最后形成一棵决策树。

3.划分属性

划分属性是指从训练数据的众多特征中选择一个特征属性作为当前节点的划分标准。然后根据属性进行拆分，自上而下的顺序生成子节点，直到数据集密不可分，形成完整的决策树。

构建完美决策树的关键是在众多属性中选择最优的划分特征属性。

节点纯度：决策树的分支节点中包含的样本尽可能属于同一类别。

1、Hunt算法

Hunt算法采用贪心策略构建决策树。在选择划分数据的属性时，采取一系列局部最优决策来构建决策树。

算法过程：

如果样本集D中包含属于多个类的实例，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将D中的实例分布到子结点中。然后，对于每个子结点，递归地调用该算法。

注：hunt算法是比较早的算法之一（数据挖掘中可能会讲到），现今机器学习中常用的是以下三种算法。

2、ID3算法

ID3算法是决策树的一个经典的构造算法，内部使用信息熵以及信息增益来进行构建，每次迭代选择信息增益最大的特征属性作为分割属性。

ID3算法的核心是在决策树各级节点上选择属性时，用信息增益衡量不纯度，使得在每一个非叶节点进行测试时能获得关于被测试记录最大的类别信息。

算法过程：

计算根节点的信息熵，然后根据属性依次划分计算其节点的信息熵和信息增益，并按照信息增益从大到小排列。决策树的形状。

信息熵（information entropy）是度量样本集合纯度最常用的一种指标。节点属性越混乱，信息熵越大，信息熵越大，一个节点中的样本属性就越多。

计算公式：样本D中第k类样本所占的比率pk（k=1,2,3,…|K|），其中K为类别总数，公式为：

Ent(D)的值越小，则D的纯度越高

信息增益（information gain）：根节点信息熵-属性节点的信息熵=信息增益。

计算公式：假定离散属性a有V个可能的取值{a1,a2,a3,…av}，若使用a来对样本集D进行划分，则会产生V个分支节点，Dv为第v个分支节点包含了D中所有在属性a上取值为av的样本，为信息熵赋予权重|Dv|/|D|（样本越多的分支节点影响越大），公式为：

ID3特点

优势：
ID3算法理论清晰，方法简单，计算量小，学习能力强，比较适用于处理规模较大的学习问题。

缺点：
1、信息增益计算依赖特征数目较多的特征，但属性取值多的属性不一定最优；
2、是非递增算法，不能对连续属性进行处理；
3、抗噪性差，噪声数据比较敏感；
4、需计算每一个属性的信息增益值，计算代价较高。

3、C4.5算法

C4.5是基于ID3算法的改进，衡量不纯度的指标采用信息增益比率。它使用了信息增益和增益比率两种选择算法，先选出信息增益高于平均水平的属性，然后再在这些属性中选择增益比最高的，作为最优划分属性。这样综合了信息增益和增益比的优点，可以取得较好的效果。

增益比率(gain ration)：信息增益除以该属性本身的熵.

计算公式：

在：

C4.5特点
优点：分类规则简单易懂，准确率高。
缺点：在构建树的过程中，需要对数据集进行多次扫描和排序，效率低下。

ID3和C4.5对比：
1、使用信息增益率替换了信息增益下降度作为属性选择的标准；
2、在决策树构造的同时进行剪枝操作；避免了树的过度拟合情况；
3、可以对不完整属性和连续型数据进行处理；
4、使用k交叉验证降低了计算复杂度；
5、针对数据构成形式，提升了算法的普适性。

3、CART算法

CART(Classification and RegressionTrees, CART)算法：是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子节点都有两个分支，因此，CART算法生成的决策树是结构简洁的二叉树。

CART衡量不纯度的指标是基尼系数。CART算法使用GINI增益作为分割属性选择的标准，选择GINI增益最大的作为当前数据集的分割属性。

其基本思想是递归地划分训练样本集的自变量空间，依次构建决策树模型，然后用验证数据的方法剪枝，从而得到满足的决策树分类模型要求。

基尼指数(gini index)：表示在样本集合中一个随机选中的样本被分错的概率。

注：Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

计算公式：基尼指数=样本被选中的概率*样本被错误分类的概率

CART特点

优势：
1、可解释性强；
2、可处理非线性问题；
3、模型简单：比其它模型更容易理解，从模型中得到的规则能获得非常直观的解释；
4、不太容易显式的用数学表达式表达，不可微；
5、模型预测效率高：能够处理空缺值，这样就避免了因空缺值造成的偏差；能够处理孤立的叶子结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进一步分支产生影响；
6、使用的是二元分支，能够充分地运用数据集中的全部数据，进而发现全部树的结构。

缺点：
1、对连续性的字段比较难预测；
2、对有时间顺序的数据，需要很多预处理的工作；
3、当类别太多时，错误可能就会增加的比较快；
4、一般的算法分类的时候，只是根据一个字段来分类。

四、剪枝策略

决策树剪枝：通过剪枝减小树结构的大小，缓解过拟合。剪枝有两种类型：预剪枝和后剪枝。

1、预剪枝

预剪枝：在决策树生成的过程中，在划分之前估计每个节点的前进。如果当前节点的划分不能提高决策树的泛化性能，则停止划分并将当前节点标记为叶子。节点。在每个分支节点生成之前，判断其位置是否需要生成，如果不需要，则停止划分。
特点：首创的剪枝算法避免了不必要的计算浪费，可以直接生成最终的分类号，因此被广泛使用。

2、后剪枝

后剪枝：首先从训练集中生成一棵完整的决策树（相当于结束位置），然后自下而上检查非叶子节点。如果将节点对应的子树替换为叶子节点，如果提高了决策树的泛化性能，则将子树替换为叶子节点。
特点：后剪枝策略会增加决策树算法的计算量，但分类结果略准确。 post-pruning 的计算成本比 pre-pruning 大很多，尤其是在大样本集中，但是对于小样本，post-pruning 仍然比 pre-pruning 好。
示意图如下：