1. 决策树的概念与构建
可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。
构建决策树的过程：
决策树的生成只考虑局部最优，相对地，决策树的剪枝则考虑全局最优。
特征选择是决定用哪个特征来划分特征空间。特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。
在信息论与概率统计中，熵是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量，其概率分布为：$P(X=x_i)=p_i$，i=1,2,…,n；则随机变量X的熵定义为：
$$
H(x)=H(p)=-\sum_{i=1}^np_i\log p_i
$$
熵越大，随机变量的不确定性就越大。式中对数以2为底或以e为底，这时熵的单位分别称作比特(bit)或纳特(nat)。随机变量X给定的条件下，随机变量Y的条件熵H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望：
$$
H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)
$$
这里$p_i=P(X=x_i)$，i=1,2,..,n当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差：
$$
g(D,A)=H(D)-H(D|A)
$$熵H(Y)与条件熵H(Y|X)之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
数据集D的经验熵H(D)：
$$
H(D)=-\sum_{k=1}^K\frac{|C_k|}{D}\log_2{\frac{|C_k|}{D}}
$$
其中，$C_k$为类别。特征A对数据集D的经验条件熵H(D|A)：
$$
H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik|}}{|D_i|}\log_2{\frac{|D_{ik|}}{|D_i|}}
$$
其中$D_i$为根据特征A的取值将D划分为n个对应的子集：$D_1,D_2,…,D_n$ ， $|D_i|$为对应的样本个数。决策根据信息增益$g(D,A=H(D)-H(D|A)$来选择可以最大限度降低数据集不确定性的特征，每轮迭代都会使用信息增益来选择最优特征。
信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在训练数据集的经验熵大的时候，信息增益值会偏大，反之则偏小。因此可以使用信息增益比对这一问题进行校正，这是特征选择的另一个准则。
信息增益比：
$$
g_R(D,A)=\frac{g(D,A)}{H(D)}
$$ID3算法：在决策树各个节点上应用信息增益选择特征，递归地构建决策树。
C4.5算法：与ID3算法类似，区别在于使用信息增益比选择特征。
2. 决策树剪枝
决策树生成算法递归地产生决策树，直到不能继续下去为止，这样的树往往出现过拟合现象。
在决策树学习中将已生成的树进行简化的过程，称为剪枝。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
决策树的剪枝往往通过极小化决策树整体的损失函数或代价函数来实现。
结点的经验熵：
$$
H_t(T)=-\sum_{t=1}^{|T|}\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}
$$决策树的损失函数：
$$
C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|=-=\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}\log{\frac{N_{tk}}{N_t}}+\alpha|T|=C(T)+\alpha|T|
$$
其中，t为树T的叶节点，该叶结点有$N_t$个样本，其中k类的样本点有$N_{tk}$个，$H_t(T)$为叶结点t上的经验熵，$a\geq0$为参数。式中C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数$\alpha\geq0$控制两种之间的影响。剪枝就是当$\alpha$确定时，选择损失函数最小的模型。
决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。
决策树剪枝算法：
- 计算每个结点的经验熵；
- 递归地从叶结点向上回缩：设一组叶结点回缩到其父结点之前与之后到整体树分别为$T_B$与$T_A$，其对应的损失函数值分别是$C_\alpha(T_B)$与$C_\alpha(T_A)$，如果$C_\alpha(T_A)\leq C_\alpha(T_B)$，则进行剪枝，将父结点变为新的叶结点。
- 重复第2步骤，直到不能继续为止，得到损失函数最小的子树$T_\alpha$。
3. CART算法
- CART是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。
- CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
- CART决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。
3.1 回归树
选择第$j$个变量$x^j$和它取的值s，作为切分变量和切分点，并定义两个区域：
$$
R_1(j,s)={ x|x^j\leq s},R_2(j,s )={x|x^j>s}
$$
寻找最优切分变量$j$和最优切分点s，即求解：
$$
min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c1)^2+min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c2)^2]
$$
$c_1,c_2$为指定二分区域内对应y的平均值。
遍历所有输入变量，找到最优的切分变量$j$以及每个切分变量的最优切分点s，依次将输入空间划分为两个区域，对每个区域重复上述划分过程，直到满足停止条件为止。
3.2 分类树
分类树使用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
假设有K个类，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为：
$$
Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^Kp_k^2
$$对于给定样本集合D，$C_k$是D中属于第k类的样本子集，K是类的个数，其基尼指数定义为：
$$
Gini(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2
$$在特征A条件下，集合D的基尼指数定义为：
$$
Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)
$$
4. 总结
决策树使用逐步分解的过程，使用信息熵的概念，递归的使用最优特征对数据集进行划分，最终完成分类过程，决策树的每个路径都是一个分类规则，叶子结点为最终的分类结果。
利用信息熵选择最优特征的想法，对统计学习方法中，模型特征的选择很有借鉴意义。