1.0 重识决策树

        决策树是在已知各种情况发生概率的基础上，通过构成预测点，判断其是否会发生的分析方法，是直观运用概率分析的一种图解法。由于这种决策树分支的图形很像树的枝干，故称决策树。

        决策树本质上是基于经验信息对目标结论的判断的总结，通过一句常用语来说：“历史总是惊人的相似”，即由于某件事在过去某环境下有大概率发生，那么现在相同特征的环境下这件事也很可能会发生。

        决策树基于的假设较少，适用于大部分情况。但其缺点也很明显：1）精度较低；2）每次只会根据单一特征划分数据，不会根据数据组合切分。但当特征间存在关联时，决策树只会用多次切分拟合这一情况。

2.0 决策树的构建过程

        决策树作为基于树结构的学习模型，也是由根节点，分叉，叶组成的，其生成过程也是按照“根节点-->分叉（内节点）-->叶节点”的过程进行。

        决策树生成的核心思想就是找出更加纯净的子集。理想情况下，每个子集里都是结论（标签）极其一致的数据。

        判断纯度的方法不同决策树的生成也不同，常用的判断方法有：1）使用信息增益作纯度判断，称为ID3树；2）使用信息增益率作纯度判断，称为C4.5树；3）使用基尼系数作纯度判断，称为CART树。

        总的来说，决策树的生成步骤为

        1）寻找最佳分割特征和分割点，把数据集分割成两部分

        2）判断是否达到要求，若未达到，重复步骤1）继续分割，直到达到要求停止，生成叶节点

        3）判断叶节点的标签

        4）剪枝，防止过拟合

3.0 数据纯度判断方法

3.1 补充说明：信息熵、条件熵和经验熵

       1）信息熵

        信息熵，也称香农熵，是衡量系统数据混乱程度的一个指标，熵值越大表示数据越混乱。决策树使用信息熵来衡量划分数据后各子集的纯净程度，纯净程度越低说明划分越合理。

        假定目标集合中有种标签（label）的样本，第种标签所占比例为，则的信息熵Entrophy为：

        注：1）取负号的原因：作为比例取值范围在0-1之间，取对数后将是一个负数，且概率越小，对数值也越小。但概率越小，表明标签可取值的种类越多，数据越杂乱，因此用负号取相反数，表明数据越杂乱熵值越大。2）log的底：log实际上是可以以任何大于1的正数为底，常见有2，e和10，虽然计算得到的数值有不同，但对数函数始终是单调曲线，并不会对信息纯度的比较结果造成影响）

       2）条件熵

        类似于条件概率，就是在给定条件下系统的信息熵。

        假定目标集合中有种（标签）样本，现按照某一特征将划分为若干子集，（将看成是一个独立的系统）根据所包含的标签的种类和概率，其信息熵为。此时基于特征划分下，系统的信息熵就是条件熵：

       3）经验熵

        经验熵比较特别，是以某一特征作为样本的标签，计算此时系统的信息熵。

        假定目标集合中有种（标签）样本，现按照某一特征作为样本标签，特性有种取值（临时标签），为特征某一取值的概率，计算系统信息熵就是经验熵：

3.3 信息增益和ID3树

        ID3树使用信息增益来评价系统的数据混乱程度。假定目标集合中有种（标签）样本，此时系统的信息熵为。现按照某一特征将划分为若干子集，那么系统在划分前后的信息熵变化就是信息增益：

        由于决策树的目标是提高信息纯度，即降低系统的信息熵，因此信息增益越大，说明分类后的数据越纯净。

        使用信息增益生成决策树的步骤：

        1）寻找最佳分割特征和分割点，对数据集进行划分：遍历集合中所有可能的分割点（每个特征的每个取值），选择信息增益最大的划分特征和特征值作为最佳分割点

        2）判断是否达到停止要求，若未达到，重复步骤1）继续分割，直到达到要求停止：节点中全部样本的标签同属于一个类别；如果分叉后的样本数目小于给定的阀值，也停止进行分叉

        3）选择叶节点里数量最多的标签作为叶节点的标签（投票法）

        4）剪枝，防止过拟合

3.4 信息增益率和C4.5树

        C4.5树使用信息增益率来评价系统的数据混乱程度。信息增益体现了系统分割前后信息熵变化的绝对程度，信息增益率则是以百分比体现信息熵变化相对程度。

        假定目标集合中有种（标签）样本。现按照某一特征划分为若干子集，在划分前后的信息信息增益为，经验熵为，则信息增益率为：

        C4.5算法生成决策树是以信息增益率最大作为最佳分割点的判断标准。

3.5 基尼系数和CART树

        假定目标集合中有种标签（label）的样本，第种标签所占比例为，那么任抽两次样本，所得标签错误的概率就是基尼值：

        当按照某一特征将划分为若干子集，根据所包含的标签的种类和概率，此时系统的基尼值为：

        CART树在判断分割停止条件上与ID3和C4.5树不同，具体包含三点：1）决策树到达最大深度；2）分叉节点的样本数小于阀值；3）分叉的叶内的样本数小于阀值

4.0 过拟合处理方法

        在决策树生成过程中，随着数据分割使得子集的样本量越来越小，剩余待分割的数据越有可能是特殊情况，这就导致着决策树分割总是向着过拟合的方向进行。为了降低过拟合风险，需要主动去除一些分类效果不明显的分叉来防止过拟合，这一过程被称为剪枝。剪枝主要有两种方法：预剪枝和后剪枝

       预剪枝

        预剪枝是在生成决策树过程中，在节点划分前进性预评估，若节点分叉不能使决策树得到泛化提升，则停止分叉生成叶。代表算法是悲观错误剪枝法PEP（Pesimistic-Error Pruning）。

       后剪枝：

        后剪枝是生成一棵完整的决策树后，自下而上对每个叶节点和分叉点进行评估，若减少分叉可以使决策树得到泛化提升，则转化分叉为一个叶。代表算法有错误率降低剪枝REP（Reduced-Error Pruning），代价复杂度剪枝CCP（Cost-Complexity Pruning）。