源码下载：https://github.com/csuldw/MachineLearning/tree/master/DecisionTree
在决策树理论中，有这样一句话，“用较少的东西，照样可以做很好的事情。越是小的决策树，越优于大的决策树”。数据分类是一个两阶段过程，包括模型学习阶段（构建分类模型）和分类预测阶段（使用模型预测给定数据的类标号）。决策树分类算法属于监督学习（Supervised learning），即样本数据中有类别标号。下面是两个阶段的简单描述：
- 第一阶段（以分类为例），可以看做是根据样本来学习一个映射或函数
y=f(x)表达式，能够使用它预测给定元组X的类标号y。 - 第二阶段，使用第一阶段学习得到的模型进行分类。首先评估分类器的预测准确率。这个过程要尽量减少过拟合（为什么是尽量减少？因为过拟合是避免不了的，再好的模型也会有过拟合的情况的）。
简介
决策树归纳是从有类标号的训练元组中学习决策模型。常用的决策树算法有ID3，C4.5和CART。它们都是采用贪心（即非回溯的）方法，自顶向下递归的分治方法构造。这几个算法选择属性划分的方法各不相同，ID3使用的是信息增益，C4.5使用的是信息增益率，而CART使用的是Gini基尼指数。下面来简单介绍下决策树的理论知识。内容包含熵、信息增益、信息增益率以及Gini指数的概念及公式。
决策树原理
决策树原理很简单，通俗易懂，最简单的就是二元划分，类似于二叉树。例如只考虑某一层某个节点的划分，如果年龄大于18，就表示成年人，如果年龄小于18就表示未成年人。
算法优点
决策树算法的优点如下：
- 算法比较简单；
- 理论易于理解；
- 对噪声数据有很好的健壮性。
目前，决策树是应用最为广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。衍生出很多出色的集成算法，如random forest、adaboost、gradient tree boosting都是基于决策树的模型。
算法一般流程
- 收集数据：任意方法和途径。
- 准备数据：书构造算法只适用于标称型数据，因此数据必须离散化。
- 分析数据：构造树完成后，检查图形是否符合预测。
- 训练算法：决策树的数据构造。
- 测试算法：一般将决策树用于分类，可以用错误率衡量，而错误率使用经验率计算。
- 使用算法：决策树可以用于任何监督学习算法。
实例分析
信息增益和熵（克劳德.香农提出）
1.使用信息增益作为划分属性
信息增益度量属性选择
熵被用来衡量一个随机变量出现的期望值。熵越大，一个变量的不确定性就越大（也就是可取的值很多），把它搞清楚所需要的信息量也就越大，熵是整个系统的平均消息量。 信息熵是信息论中用于度量信息量的一个概念。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。所以，信息熵也可以说是系统有序化程度的一个度量。
熵（Entropy）的计算公式
熵定义为信息的期望值。先看看信息的定义：
$$l(x_i)=-log_2p(x_i)$$
其中，$p(x_i)$是选择该分类的概率。对$D$中的元组所有分类所有可能值的信息期望，即熵，计算公式如下：
$$Entropy=H(D)=E(I(D))=-\sum_i^{n} p_ilog_2(p_i)，p_i是D中任意元组属于类C_i非零概率。$$
熵越大，说明系统越混乱，携带的信息就越少。熵越小，说明系统越有序，携带的信息就越多。信息的作用就是在于消除不确定性。
ID3划分特征使用的就是信息增益IG。一个属性的信息增益越大，表明属性对样本的熵减少的能力就更强，该属性使得数据所属类别的不确定性变为确定性的能力越强。信息增益在统计学中称为互信息，互信息是条件概率与后验概率的比值，化简之后就可以得到信息增益。所以说互信息其实就是信息增益。计算方法【互信息=熵-条件熵】。熵描述的是不确定性。熵越大，不确定性就越大，条件熵H（B|A）描述的是在A给定的条件下B的不确定性，如果条件熵越小，表示不确定性就越小，那么B就越容易确定结果。所以使用熵减去条件熵，就得到了信息增益，他描述的不确定性的降低程度，可以用来度量两个变量的相关性。比如，在给定一个变量的条件下，另一个变量它的不确定性能够降低多少，如果不确定性降低得越多，那么它的确定性就越大，就越容易区分，两者就越相关。注：期望信息越小，分区的纯度越高。
信息增益计算
首先计算特征A对数据集D的经验条件熵$H(D|A)$,在数学上就是条件概率分布（Condition Probability）.
$$H(D|A)=\sum_j\dfrac{|D_j|}{|D|}\times H(D_j)，项\dfrac{|D_i|}{|D|}充当第j个分区的权重$$
引入条件熵，在信息论中主要是为了消除结果的不确定性。然后计算信息增益
$$Gain(A) = H(D) - H(D|A)$$
其中，$Gain(A)$即为所求的信息增益。下面来应用一个实例，训练元组数据D
在这里
$$H(D)=-\dfrac{9}{14}log_2\dfrac{9}{14}-\dfrac{5}{14}log_2\dfrac{5}{14}=0.940位$$
$$H(D|age)=\dfrac{5}{14}\times(-\dfrac{2}{5}log_2\dfrac{2}{5}-\dfrac{3}{5}log_2 \dfrac{3}{5})+\dfrac{4}{14}\times(-\dfrac{4}{4}log_2\dfrac{0}{4}-\dfrac{0}{4}log_2 \dfrac{0}{4})+\dfrac{5}{14}\times(-\dfrac{3}{5}log_2\dfrac{3}{5}-\dfrac{2}{5}log_2 \dfrac{2}{5})=0.694位$$
根据计算出来的条件熵，计算按$age$划分的信息增益，计算方法如下：
$$Gain(age)=H(D)-H(D|age)=0.940-0.964=0.246位$$
类似的可以计算出其它属性的信息增益：
$$ Gain(income)=0.029位，
Gain(student)=0.151位，Gain(credit_rating)=0.048位 $$
由于$age$在属性中具有最高的信息增益，所以它被选作分裂特征。下面再进行递归计算信息增益，在此就不展示了。ID3采用的就是就是IG，算法步骤如下：
2.使用增益率计算
在决策树中，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{Gain(A)}{Split_H(D|A)}$$
选择具有最大增益率的特征作为分裂特征。
3.基尼指数Gini index
基尼指数主要在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指数的自己作为它的分裂信息。
学习推介
Andrew W. Moore PPT DTree
决策树Python实现，单独成文，网址：决策树实现
Wikipedia维基百科-Decision Tree决策树
最后，附一张决策树的优点和缺点图：
参考文献
- [1]数据挖掘概念与技术 Third Edition,韩家伟.
- [2]机器学习实战 ,Peter Harrington.