决策树

一、了解决策树

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

  决策树就是一棵树（很像流程图），其内包含一个根节点，若干内部节点和若干叶子结点。树的最高层是就是根节点，包含样本全集。内部节点代表对应的一个特征的测试，每个节点包含的样本根据测试的结果被划分到子节点中，即树的分支代表该特征的每一个测试结果。每一个叶子节点代表一个类别或决策结果。从根节点到一个叶子结点对应一个判定测试序列。

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

  下图即为一个决策树的示意描述，内部节点用矩形表示，叶子节点用椭圆表示。

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

二、决策树的基本过程

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

三、划分属性

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

  在众多属性中选取最优划分特征属性是构建一棵完美决策树的重点。

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

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、后剪枝

  后剪枝：先从训练集生成一棵完整的决策树（相当于结束位置），然后自底向上的对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
  特点：后剪枝策略会加大决策树算法的计算量，但分类结果稍微准确。后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。
  示意图如下：