1 核心术语介绍
•决策树：分类决策树模型是一种描述对实例进行分类的树状结构。决策树由结点和有向边组成。结点有两种类型：内部结点和页结点。内部结点表示一个特征或属性，叶结点表示一个类。
•信息增益：表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。基于信息增益进行特征选择的是ID3决策树学习算法模型。
•信息增益率：增益率的定义如下图所示，IV称为属性 α 的"固有值" (intrinsic value)。属性 α 的可能取值数目越多(即IV越大)，则 IV(α) 的值通常会越大。从下列式子可以看出，增益率准则对可取值数目较少的属性有所偏好。因此，C4.5算法利用信息增益率在ID3决策树学习算法模型的基础上进行了改进。C4.5算法并不是直接选择增益率最大的候选划分属性，而是先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
•GINI杂质系数：Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大。CART 决策树 [Breiman et al., 1984] 使用"基尼指数" (Gini index)来选择划分属性。
•后验概率：预先已知结果，根据结果估计原因的概率分布是后验概率。
•先验概率：在结果发生前开始预测，根据历史规律确定原因的分布叫先验概率。
2 决策树算法原理
决策树算法应用原理是从给定训练数据集学得一个模型用以对新示例进行分类。对样本进行分类的任务，可看作对"当前样本属于正类吗?"这个问题的"决策"或"判定"过程。也就是说，决策树是基于树结构来进行决策的。
一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点，叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。
在决策树基本算法中，有三种情形导致递归返回：1、当前结点包含的样本全属于同一类别，无需划分 2、当前属性集为空，或是所有样本在所有属性上取值相同，无法划分 3、当前结点包含的样本集合为空，不能划分。在第2种情形下，把当前结点标记为叶节点，但类别设定为该结点所含样本最多的类别。在第3种情形下，把当前结点标记为叶节点，但类别设定为其父结点所含样本最多的类别。它们的不同点是 ，第2种是利用当前结点的后验分布，第3种则是把父结点的样本分布作为当前结点的先验分布。
为了更方便理解上述这段话，本文引用博主MingRachel对此的深入说明，链接如下图所示：
该博主运用了kaggle上经典的Titanic数据集来说明这个问题：
上图的红色数字代表第几类递归返回，绿色数字代表结点。
（1）结点1：在sex=female这一分类下，所有的Survived全部为1 (数据组1，2的Survived全为1)，没有继续划分的必要，遂把该结点直接作为叶结点，种类就为1。属于三类递归返回的第一种情况。
（2）结点2：在Pclass=1这一划分之后，所有的经过结点2的数据集Dv在所有的属性A上的取值相同，无法继续划分，所以把该结点标记为叶结点，划分的种类为Dv中出现次数最多的类别0。属于递归返回的第二种情况。
（3）结点4和5，同理所有属性取值相同或者说是划分完了所有的属性(新属性集为空)，无法继续划分，直接标记为叶结点，虽然就只有一组数据但是他们也是属于第二类递归返回的范围。属于递归返回的第二种情况。
（4）结点3，在Sex=m之后，Pclass=3的样本集合为空集，不能划分，直接标记为叶结点，返回的种类为父结点 (也就是sex=m时)数据集的类别中出现次数最多的类别0。属于递归返回的第三种情况。
3 划分选择
主要的划分选择有基本术语里介绍的三种：信息增益、信息增益率和GiNi系数，这里主要深入介绍一下GiNi系数。
