1.0 重识决策树

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

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

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

2.0 决策树的构建过程

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

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

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

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

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

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

3）判断叶节点的标签

4）剪枝，防止过拟合

3.0 数据纯度判断方法

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

1）信息熵

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

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

$Ent(S)=\sum_{k=1}^n -p_k·log_2p_k$

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

2）条件熵

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

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