决策树详解

决策树是一种以树状结构表示的分类和回归模型，从根节点开始，根据最优属性从上往下层层划分，最终输出叶子节点为分类结果值。

决策树代表对象属性和对象值之间的一种映射关系。它由节点（node）和有向边（directed edge）组成，其节点有两种类型：内节点（internal node）和叶节点（leaf node），内部节点表示一个特征或属性，叶节点表示一个类。根节点是决策树最开始的结点，内部结点是可以继续分类的结点。

决策树的学习本质上是从训练集中归纳出一组分类规则，得到与数据集矛盾较小的决策树，同时具有很好的泛化能力。决策树学习的损失函数通常是正则化的极大似然函数，通常采用启发式方法，近似求解这一最优化问题。
决策树学习算法包含特征选择、决策树生成与决策树的剪枝。决策树表示的是一个条件概率分布，所以深浅不同的决策树对应着不同复杂程度的概率模型。决策树的生成对应着模型的局部选择（局部最优），决策树的剪枝对应着全局选择（全局最优）。决策树常用的算法有ID3，C4.5，CART，下面通过一个简单的例子来分别介绍这几种算法。

特征选择

宗旨是在每一个决策点，选择能够使得样本的熵降低得最快，样本纯度提升最大的那个特征作为该决策点的划分特征。

特征选择就是选择对训练数据具有分类能力的特征，也就是我们在背景里面提到的对工作好坏评判起作用的指标，这样就可以提高决策树学习的效率。如果一个特征的分类能力与随机分类的结果没什么差异，则称这个特征是没有分类能力的。一般我们把这类特征是直接去掉的，我们优先那些能够对我们的分类起到决定作用的特征，我们在具体选取的时候会用到三个准则：信息增益、信息增益比和基尼系数。

在信息论和概率统计中，熵表示随机变量不确定性的度量。

信息增益表示在得知特征X的信息而使得类Y的不确定性减少的程度。

以信息增益作为划分训练数据集的特征，存在偏向于选取取值较多的特征的问题使用信息增益比可以对这一问题进行校正。

决策树的生成

决策树的生成主要分以下两步，这两步通常通过学习已经知道分类结果的样本来实现。

节点的分裂：一般当一个节点所代表的属性无法给出判断时，则选择将这一节点分成2个子节点（如不是二叉树的情况会分成n个子节点）
阈值的确定：选择适当的阈值使得分类错误率最小（Training Error）。

算法

ID3

ID3算法的核心是在决策树各个结点的上应用信息增益准则选择特征，递归地构建决策树。

具体方法就是从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直至所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

算法步骤

输入：训练数据集D，特征集A，阈值z。

输出：决策树T。

若D中所有的实例都属于同一类Ck(k表示样本D本身按照结果分成k个类别),则T为单节点树，并将类Ck作为该节点的类标记，返回T。
若特征A集合为空，则T为单节点树，并将D中实例数最大的类Ck作为该节点的类标记，返回T。
如果不符合上面两种情况，则按照信息增益算法公式计算A中每个特征对D的信息增益，选择信息增益最大的特征Ag。
如果Ag的信息增益小于阈值z,则置T为单节点树，并将D中的实例数最大的类Ck作为该节点的类标记，返回T。
如果Ag的信息增益大于阈值z,则对Ag的每一个取值ai,依据Ag=ai将D分割为若干非空子集Di,将Di中实例数最大的类作为标记，构建子节点，由结点及其子节点构成树T，返回T。
对第i个子节点，以Di为训练集，以A-Ag为特征集，递归地调用上面5个步骤，得到子树Ti,返回Ti。

C4.5

C4.5和ID3算法相似，C4.5是在ID3的基础上进行了改进，从ID3用信息增益来选取特征改成了用信息增益比来选取特征，其他步骤均与ID3算法一致

CART

选择Gini系数最小的作为划分特征，Gini系数越小，纯度越高。
CART（Classification And Regression Tree）算法主要有两部分组成：
(1) 决策树的生成：基于训练数据集生成决策树，生成的决策树要尽量打。这与ID3算法类似，不同之处也是特征选取的方式；
(2) 决策树的剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，此时用损失函数最小作为剪枝的标准。
CART算法可以用于回归，即建立回归树。在终于分类时，其算法流程与ID3较为类似，不同的是特征选取，选择的是最小基尼指数。

总结

决策树剪枝

目的是防止过拟合，增强其泛化能力。

决策树生成算法是通过递归的方法产生决策树，直到不能继续下去为止，这样产生的树往往对训练数据的分类很准确，但对未知数据的分类却没那么准确，即出现过拟合的现象。过拟合的原因在于学习时过度考虑如何提高训练数据的正确分类，从而构建出过于复杂的决策树。解决这个问题的方法是考虑决策树的复杂度，对已生成的决策树进行简化，我们把这种对已生成的树进行简化的过程称为剪枝。

剪枝是从已生成的树上裁掉一些子树或叶节点，并将其根结点或父节点作为新的叶节点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。

剪枝是应该决策树过拟合的一种重要方法，主要分为以下两种：

预剪枝：该策略就是在对一个节点进行划分前进行估计，如果不能提升决策树泛化精度，就停止划分，将当前节点设置为叶节点。那么怎么测量泛化精度，就是留出一部分训练数据当做测试集，每次划分前比较划分前后的测试集预测精度。
- 优点：降低了过拟合风险，降低了训练所需的时间。
- 缺点：预剪枝是一种贪心操作，可能有些划分暂时无法提升精度，但是后续划分可以提升精度。故产生了欠拟合的风险。
后剪枝：该策略是首先正常建立一个决策树，然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序，依次对内部节点进行剪枝，如果将某以内部节点为根的子树换成一个叶节点，可以提高泛化性能，就进行剪枝。
- 优点：降低过拟合风险，降低欠拟合风险，决策树效果提升比预剪枝强
- 缺点：时间开销大得多

决策树的优缺点

优点

可解释性强：易于理解和解释，可以可视化分析，容易提取出规则。
数据预处理：只需很少的数据准备，以同时处理类别型和数值型数据，允许缺失值，能够处理不相关的特征
大规模数据处理：决策树可以很好的扩展到大型数据库中，处理大规模数据

缺点
过拟合：容易出现过拟合问题，导致无法很好的预测训练集之外的数据
忽略特征关联：忽略数据集中属性的相互关联。当数值型变量之间存在许多错综复杂的关系，如金融数据分析，不是一个好选择
模型敏感：模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。