写在最前面：本文基于周志华老师的《机器学习》书籍，为了不照本宣科，本文尽可能从自己理解的角度来写，但行文目录及内容还是会参照该书，希望能帮助到大家，如果有理解有误的地方，欢迎大家留言。
1.基本流程
决策树是常见的一类机器学习方法，从名字上可以看出是帮助人做判断的一个工具。比如说：对于一个东西，是否有买的必要（yes or no），我们会综合考虑多种因素最终决定（yes or no），这其实就对应了机器学习中的二分类任务。
在判断的过程中，多种因素共同决定了最终要不要买，对于每种因素的考虑，总会存在一种先后顺序，而这种顺序，即是构建决策树的关键所在了：每一种因素都能影响买不买，但是，总有些因素在当前因素中起到关键作用。
例如：一件商品的价格是9磅15便士，但我现在只有9磅，我个人它的需求程度相对较高，但此时能买吗？显然不能。原因是：我的余额无法支撑起购买花销，此时，我的余额对买不买这个决策影响较大，如果不满足当前的条件的话，是没有必要再考虑下面的影响因素的。
再例如：一件商品的价格仍是9磅15便士，我现在有20磅，我对此件商品的需求程度一般，但有买家评论体验良好，那么此时，我先满足了购买的条件，接下来看需求程度、买家评论，最终可能趋于购买此件商品。当然如果评论一般甚至差的话，虽然满足了前面的购买条件，且有需求（一般），可能也不会购买了。
基于以上讨论，我们产生了一个新的问题：如何在当前因素中，选出决定性最大的那个因素呢？接着往下看。
2.划分选择
上面提到，如何选择决定性最大的因素，对应机器学习中的如何选择最优划分属性；随着决策的不断进行，决定是否购买的不确定性也更加明确，这对应机器学习中，随着划分过程不断进行，决策树分支结点所包含的样本尽可能输入同一类，即结点的”纯度“越来越高。
以上的例子对应专业术语可能存在偏差，但主要是为了帮助大家理解，希望大家可以从例子中走出来，回归专业语言。
2.1信息增益
在讨论信息增益之前，首先需要知道一个名词”熵“，关于这个名词，我在知乎上找到了一个讲的比较好的，链接：信息时代最重要的一个概念：熵
观看以上讲解后，我们在这里给出机器学习中的”信息熵“定义：信息熵是度量样本集合纯度最常用的一种指标，假定当前样本集合D中有|
γ
\gamma
γ|类样本，第k类样本所占比例为
p
k
p_k
pk?(k=1,2,3,…|
γ
\gamma
γ|)，则D的信息熵定义为：Ent(D) = -
∑
k
=
1
∣
γ
∣
\displaystyle \sum^{|\gamma|}_{k=1}
k=1∑∣γ∣?
p
k
p_k
pk?
log
?
2
p
k
\log_2{p_k}
log2?pk?
Ent(D)的值越小，则D对应的纯度越高。
机器学习书中很多这种描述符号化的描述对刚接触的人来说很不友好，下面我来说一下我的理解：
对于需要进行划分的样本，其本身有很多属性，以西瓜为例的话，西瓜的根蒂、色泽、敲声等都是其属性，对于每一个属性，又有不同的取值，如色泽有青绿、乌黑、浅白，根蒂有蜷缩、稍蜷、硬挺。对应关系即属性a会从属性集合{根蒂、色泽、敲声…}中选取一个，属性a确定之后，其对应的取值也就确定了，故而对于每个属性构成了一个{
a
1
a
2
a
3
.
.
.
.
a
V
{a^1}{a^2}{a^3}....{a^V}
a1a2a3....aV}集合，对于每个属性来说，对样本集D的划分所获得信息增益的计算如上(4.2)。
一般来说，属性对应的信息增益越大，则意味着使用该属性来划分样本集所获得的”纯度提升“越大。
2.2增益率
增益率的提出是针对信息增益存在的问题的，信息增益的问题是对可取值数目较多的属性有所偏好，例如色泽有青绿、乌黑、浅白三种取值，而触感只有硬滑、软粘两种属性，使用信息增益则跟倾向于以色泽为划分属性。那么如何计算得到增益率呢？
增益率定义为：Gain_ratio(D,a) =
G
a
i
n
(
D
,
a
)
Ⅳ
(
a
)
\frac{Gain(D,a)}{Ⅳ(a)}
Ⅳ(a)Gain(D,a)?
其中Ⅳ(a) = -
∑
v
=
1
V
\displaystyle \sum^{V}_{v=1}
v=1∑V?
∣
D
v
∣
∣
D
∣
\frac{|D^v|}{|D|}
∣D∣∣Dv∣?
log
?
2
∣
D
v
∣
∣
D
∣
\log_2{\frac{|D^v|}{|D|}}
log2?∣D∣∣Dv∣?
但是，增益率准则对可取值较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，二室使用一个启发式：先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的。
2.3基尼指数
继续采用上面的符号，数据集D的纯度可用基尼值来度量：Gini(D) =
∑
k
=
1
∣
γ
∣
∑
k
′
≠
k
p
k
p
k
′
\displaystyle \sum^{|{\gamma}|}_{k=1}\displaystyle \sum_{k'≠k}{{p_k}{p_{k'}}}
k=1∑∣γ∣?k′?=k∑?pk?pk′? = 1 -
∑
k
=
1
∣
γ
∣
p
k
2
\displaystyle \sum^{|γ|}_{k=1} {p^2_k}
k=1∑∣γ∣?pk2?
这个公式的含义即：样本有K个类别，每个类别所占的比例为
p
k
{p_k}
pk?，剩余样本的比例即
p
k
′
{p_{k'}}
pk′?
直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，Gini(D)越小，对应数据集的纯度越高。
对于数据集D，属性a的基尼指数定义为：Gini_index(D,a) =
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
G
i
n
i
(
D
v
)
\displaystyle \sum^{V}_{v=1} {\frac{|D^v|}{|D|}} {Gini(D^v)}
v=1∑V?∣D∣∣Dv∣?Gini(Dv)
在侯选属性集A中，计算出所有基尼指数最小的属性作为最优划分属性。
3.剪枝处理
基于某样本集训练产生一棵决策树时，容易产生过拟合的现象，所谓过拟合即是指基于某样本集进行学习时，将其所有的特征都学习到了，最简单的例子：如果对该样本集进行编号，将编号作为样本集的一个属性，则会学习得到一个两层，样本大小个叶子结点的决策树，显然这样的决策树对后续用于分类别的数据集帮助是不大的。我们需要的是样本集中的一般性质，因此我们可以通过主动去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有”预剪枝“和”后剪枝“
3.1预剪枝
预剪枝：在决策树生成的过程中，对每个结点在划分之前先进行估计，如果当前结点的划分不能带来决策树泛化性能提升，则停止划分，并把当前结点标记为叶结点。
3.2后剪枝
后剪枝则是先从训练集中生成一个完整的决策树，然后自底向上地对非叶结点进行考察，如将该结点对应的自述换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶子结点。
在《机器学习》这本书中，针对西瓜数据集2.0展开了详细的预剪枝和后剪枝步骤及计算，这里不再计算。
3.3剪枝处理比较
不管预剪枝还是后剪枝，都存在一定的优点和缺点。
首先对于预剪枝来说，其可以使很多分支都不“展开”，从而不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但同时，有些分支当前划分虽然不能带来泛化性能的提升甚至暂时下降，但是后续的划分却能使决策树的泛化性能显著提高，因此预剪枝基于”贪心“禁止分支展开，会给预剪枝决策树带来欠拟合的风险。
对于后剪枝来说，后剪枝决策树通常比预剪枝决策树保留更多的分支。一般情况下后剪枝的欠拟合风险很小，泛化性能往往优于预剪枝。但后剪枝过程是在生成完全决策树之后进行的，并且要白底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树 和预剪枝决策树都要大得多。
4.缺失值处理
现实任务中常会遇到不完整样本，即样本的某些属性值确实，例如由于诊测成本、隐私保护等因素，患者的医疗数据在某些属性上的取值未知；尤其是在属性数目较多的情况下，往往会有大量样本出现缺失值，如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大的浪费。
如表4.4所示，如果放弃不完整样本，则仅有少量样本能够被使用，因此，考虑利用有缺失属性值的训练样本来进行学习是非常有必要的。
我们需要解决的问题是：1、如何在属性值缺失的情况下进行划分属性选择？2、给定划分属性，若样本在该属性上的值确实，如何对样本进行划分？
以上两段文字取自书籍《机器学习》，解读：
对于某一属性a，我们首先找出所有数据集中该属性不缺失的样本，找出的所有样本组成新的数据集D’，此数据集仅针对属性a，此时我们可以得到数据集D’中各类别样本所占比例，基于此比例，我们可以推广上面的信息熵及信息增益计算公式。