决策树学习的本质是从训练数据集中归纳出一组分类规则，从另一个角度看，决策树学习是由训练数据集估计条件概率模型，我们选择的模型应该不仅对训练数据拟合的好，还应具有很好的泛化能力。

决策树学习的三个步骤：

特征选择

特征选择在于选取对训练数据具有分类能力的特征，如果一个特征的分类效果不优于随机分类，那么这个这个特征是没有分类能力的，应当放弃。特征选择决定用哪个特征来划分空间，特征选择的准则通常是信息增益 、信息增益比 、基尼指数。

使用信息增益计算

特征A对训练数据集D的信息增益 $g(D,A)$ ，定义为集合D的经验熵 $H(D)$ 与特征更A给定条件下D的经验条件熵 $H(D|A)$ 之差，即：

$g(D,A) = H(D)-H(D|A)$

熵越大，说明系统越混乱，携带的信息就越少。熵越小，说明系统越有序，携带的信息就越多。信息的作用就是在于消除不确定性。

ID3划分特征使用的就是信息增益IG。一个属性的信息增益越大，表明属性对样本的熵减少的能力就更强，该属性使得数据所属类别的不确定性变为确定性的能力越强。

信息增益计算

首先计算特征A对数据集D的经验条件熵 $H(D|A)$ ,在数学上就是条件概率分布（Condition Probability）.

$H(D|A)=\sum_j\dfrac{|D_j|}{|D|}\times H(D_j) =\sum_j\dfrac{|D_j|}{|D|} \sum_k\dfrac{|D_{jk}|}{|D_j|}log\dfrac{|D_{jk}|}{|D_j|}$

其中项 $\dfrac{|D_i|}{|D|}$ 充当第j个分区的权重

在决策树中，ID3属性划分标准使用的是信息增益，C4.5使用的是信息增益率。

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。另外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

另外，无论是ID3还是C4.5最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法，ID3得出的效果会非常差，因为使用信息增益划分时它倾向于取值多的属性。

计算信息增益率时，用到了分裂信息计算公式：

$Split_H(D|A)=-∑\dfrac{|D_j|}{|D|}\times log_2(\dfrac{|D_j|}{|D|})$ $Gain_Rate(A)=\dfrac{g(D,A)}{Split_H(D|A)}$

基尼指数主要在CART算法中用到，随机森林中用到的属性划分标准也是它。Gini index划分是二元的，它度量的是数据分区或训练元组集D的不纯度，表示的是一个随机选中的样本在子集中被分错的可能性。计算方式如下：

$Gini(D)=1-\sum p^{2}_i ，其中，p_i 是D中元组数以C_i 类的概率，对m个类计算和。$

Gini指数越大，不纯度越大，越不容易区分。假设A有v个不同的值出现在特征D中，它的二元划分有 $2^v−2$ 种（除去自己和空集）。当考虑二元划分裂时，计算每个结果分区的不纯度加权和。比如A有两个值，则特征D被划分成D1和D2,这时Gini指数为：

上面的式子表示的是不确定性的大小。对于每个属性，考虑每种可能的二元划分，对于离散值属性，选择该属性产生最小Gini指数的自己作为它的分裂信息。