Introduction
决策树也是机器学习中一种非常经典的分类和回归算法，在工业界有着非常广泛的应用，并且有着非常好的可解释性。
决策树学习
决策树学习的Loss Function通常是正则化的极大似然函数，决策树学习的策略是以Loss Function最小化为目标函数的最小化。
决策树的生成对应于模型的局部选择，决策树的剪枝对应模型的全局选择。决策树的生成只考虑局部最优，决策树的剪枝则考虑全局最优。
特征选择
Entropy是表示随机变量不确定性的度量，设$X$是一个取有限个值的离散随机变量，其概率分布为：
$P(X=x_i)=p_i$则随机变量$X$的Entropy定义为：
$H(X)=-\sum_{i=1}^n p_ilogp_i$由定义可知Entropy只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的Entropy记作$H(p)$：
$H(p)=-\sum_{i=1}^n p_ilogp_i$Entropy越大，随机变量的不确定性就越大，$0\leq H(p)\leq logn$
当随机变量只取两个值，即$X$的分布为：
$P(X=1)=p, P(X=0)=1-p$
Entropy为：
$H(p)=-plog_2p-(1-p)log_2(1-p)$条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性，随机变量$X$给定的条件下随机变量$Y$的条件熵，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望：
$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i), \quad p_i=P(X=x_i)$信息增益表示 得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度：
定义：特征$A$对dataset $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)$之差称为“互信息”，决策树学习中的信息增益等价于dataset中类与特征的互信息。
决策树学习应用 信息增益 准则选择特征，给定dataset $D$和特征$A$，经验熵$H(D)$表示对数据集$D$进行分类的不确定性，而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性，那么他们的差，即信息增益，就表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。信息增益大的特征具有更强的分类能力。
根据信息增益准则的特征选择方法是：对training set $D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
信息增益算法
设training set为$D$，$|D|$表示其样本容量，即样本个数，设有$K$个类$C_k,k=1,2,\cdots,K$，$|C_k|$为属于类$C_k$的样本个数，$\sum_{k=1}^K|C_k|=|D|$。设特征$A$有$n$个不同的取值$\{a_1,a_2,\cdots,a_n\}$，根据特征$A$的取值将$D$划分为$n$个子集$D_1,D_2,\cdots,D_n$，$|D_i|$为$D_i$的样本个数，$\sum_{i=1}^n|D_i|=|D|$。记子集$D_i$中属于类$C_k$的样本集合为$D_{ik}$，即$D_{ik}=D_i\cap C_k$，$|D_{ik}|$为$D_{ik}$的样本个数。于是信息增益算法如下：
计算数据集$D$的经验熵$H(D)$：
$H(D)=-\sum_{k=1}^K \frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$计算特征$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|}$计算信息增益：
$g(D,A)=H(D)-H(D|A)$
以信息增益作为划分训练数据集的特征，存在 偏向于选择取值较多的特征的问题。使用信息增益比可以对这一问题进行校正。
- 信息增益比：特征$A$对training set $D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比：
$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$
其中，$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}log_2\frac{|D_i|}{|D|}$，$n$是特征$A$取值的个数。
决策树的生成
ID3算法
ID3算法的核心是在决策树各个结点上应用 信息增益 准则进行特征选择，递归地构建决策树。具体做法是：从根节点开始对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。ID3相当于用极大似然法进行概率模型的选择。
- 若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将$C_k$作为该结点的类标记，返回决策树$T$；
- 若特征集$A=\varnothing$，则$T$为单结点树，并将$D$中实例数最大的的类$C_k$作为该结点的类标记，返回$T$；
- 否则，计算$A$中各个特征对$D$的信息增益，选择 信息增益 最大的特征$A_g$；
- 若$A_g$的信息增益小于阈值$\epsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；
- 否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；
- 对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归调用 1~5 步，得到子树$T_i$，返回$T_i$。
ID3算法只有树的生成，所以该算法生成的树容易过拟合。
C4.5
C4.5算法在生成的过程中，用 信息增益比 来选择特征。
- 若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将$C_k$作为该结点的类标记，返回决策树$T$；
- 若特征集$A=\varnothing$，则$T$为单结点树，并将$D$中实例数最大的的类$C_k$作为该结点的类标记，返回$T$；
- 否则，计算$A$中各个特征对$D$的 信息增益比，选择 信息增益比 最大的特征$A_g$；
- 若$A_g$的信息增益比小于阈值$\epsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；
- 否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；
- 对第$i$个子结点，以$D_i$为训练集，以$A-\{A_g\}$为特征集，递归调用 1~5 步，得到子树$T_i$，返回$T_i$。
决策树的剪枝
决策树的剪枝往往通过极小化决策树整体的Loss Function来实现，设树$T$的叶节点个数为$|T|$，$t$是树$T$的叶节点，该叶节点有$N_t$个样本点，其中$k$类的样本点有$N_{tk}$个，$k=1,2,\cdots,K$，$H_t(T)$为叶节点$t$上的经验熵，$\alpha\geq 0$为参数，则决策树学习的Loss Function可以定义为：
$C_{\alpha}(T)=\sum_{i=1}^{|T|}N_t H_t(T) + \alpha |T|$
其中经验熵为：
$H_t(T)=-\sum_k \frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$
在Loss Function中，将式子右端的第一项记作：
$C(T)=\sum_{i=1}^{|T|}N_t H_t(T)=-\sum_{i=1}^{|T|}\sum_{k=1}^K N_{tk}log \frac{N_{tk}}{N_t}$
这时有：
$C_{\alpha}(T)=C(T)+\alpha|T|$
$C(T)$表示模型对训练数据的预测误差，即模型对训练数据的拟合程度；$|T|$表示模型复杂度，参数$\alpha\geq 0$控制两者之间的影响。较大的$\alpha$促使选择较简单的模型，较小的$\alpha$促使选择较复杂的模型。
可以看出，决策树生成只考虑了通过提高信息增益(或信息增益比)对训练数据进行更好的拟合，而决策树剪枝通过优化Loss Function还考虑了减小模型复杂度。决策树生成学习局部模型，决策树剪枝学习整体模型。
Loss Function的极小化等价于正则化的极大似然估计，所以，利用Loss Function最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。
剪枝算法
- 计算每个节点的经验熵
- 递归地从树的叶节点向上回缩：
设一组叶节点回缩到其父节点之前与之后的整体树分别为$T_B$与$T_A$，其对应的Loss Function值分别是$C_{\alpha}(T_B)$与$C_{\alpha}(T_A)$，如果 $C_{\alpha}(T_A)\leq C_{\alpha}(T_B)$，则进行剪枝，即将父节点变为新的叶节点。 - 返回2，直到不能继续为止，得到Loss Function最小的子树$T_{\alpha}$。
CART算法
CART是在给定输入随机变量$X$条件下输出随机变量$Y$的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定条件下输出的条件概率分布。
CART算法由以下两步组成：
- 决策树生成：基于training set生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用validation set对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准
CART生成
决策树的生成就是递归地构建二叉决策树的过程，对回归树用MSE最小化准则，对分类树用Gini Index最小化 准则，进行特征选择，生成二叉树。
回归树的生成
假设已将输入空间划分为$M$个单元$R_1,R_2,\cdots,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可以表示为：
$f(x)=\sum_{m=1}^M c_mI(x\in R_m)$
当输入空间的划分确定时，可以用MSE来表示回归树对于training set的预测误差，用MSE Loss最小化准则求解每个单元上的最优输出值。易知，单元$R_m$上的$c_m$的最优值$\hat{c}_m$是$R_m$上所有输入实例$x_i$对应的输出$y_i$的均值，即：
$\hat{c}_m=AVG(y_i|x_i\in R_m)$
可以采用启发式的方法对输入空间进行划分：选择第$j$个变量$x^{(j)}$和它的取值$s$，作为切分变量和切分点，并定义两个区域：
$R_1(j,s)=\{x|x^{(j)}\leq s\}$ 和 $R_2(j,s)=\{x|x^{(j)}> s\}$
然后寻找最优切分变量$j$和切分点$s$，具体的，求解：
$\mathop{min} \limits_{j,s}[\mathop{min} \limits_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \mathop{min} \limits_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$
对固定输入变量$j$可以找到最优切分点$s$：
$\hat{c}_1=AVG(y_i|x_i\in R_1(j,s))$ 和 $\hat{c}_2=AVG(y_i|x_i\in R_2(j,s))$
遍历所有输入变量，找到最优的切分变量$j$，构成一个对$(j,s)$，依此将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树，成为最小二乘回归树。
最小二乘回归树生成算法
选择最优切分变量$j$和切分点$s$，求解：
$\mathop{min} \limits_{j,s}[\mathop{min} \limits_{c_1} \sum_{x_i\in R_1(j,s)}(y_i-c_1)^2 + \mathop{min} \limits_{c_2} \sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]$遍历$j$，对固定的切分变量$j$扫描切分点$s$，选择使得上式达到最小值的对$(j,s)$。
用选定的对$(j,s)$划分区域并决定相应的输出值：
$R_1(j,s)=\{x|x^{(j)}\leq s\}$， $R_2(j,s)=\{x|x^{(j)}> s\}$$\hat{c}_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i, \quad m=1,2$
继续对两个子区域调用步骤1和2，直至满足停止条件。
将输入空间划分为$M$个区域$R_1,R_2,\cdots,R_M$，生成决策树：
$f(x)=\sum_{m=1}^M\hat{c}_m I(x\in R_m)$
分类树的生成
分类树用Gini Index选择最优特征，同时决定该特征的最优二值切分点。
Gini Index: 分类问题中，假设有$K$个类，样本点属于第$k$类的概率是$p_k$，则概率分布的Gini Index定义为：
$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$对于二分类问题，若样本点属于第1类的概率是$p$，则概率分布的Gini Index为：
$Gini(p)=2p(1-p)$对于给定的样本集合$D$，其Gini Index为：
$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$这里，$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数。
如果样本集合$D$根据$A$是否取某一可能值$a$被分成$D_1$和$D_2$两部分，即：
$D_1=\{(x,y)\in D|A(x)=a\}, \quad D_2=D-D_1$则在特征$A$的条件下，集合$D$的Gini Index定义为：
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$Gini Index表示集合$D$的不确定性，Gini Index $G(D,A)$表示经$A=a$分割后集合$D$的不确定性，Gini Index越大，样本集合的不确定性也就越大，这一点与Entropy相似。
CART生成算法
- 设结点的training set为$D$，计算现有特征对该数据集的Gini Index，此时，对每一个特征$A$，对其可能取的每个值$a$，根据样本点对$A=a$的测试为“是”或者“否”将$D$分割成$D_1$和$D_2$两部分，并计算$A=a$时的Gini Index。
- 在所有可能的特征$A$及它们所有可能的切分点$a$中，选择Gini Index最小的特征及其对应的切分点作为最优特征与最优切分点。从该结点生成两个子结点，将training set依特征分配到两个子结点中去。
- 对两个子结点递归调用1和2，直至满足停止条件。
- 生成CART决策树。
算法停止的条件是结点中的样本个数小于指定阈值，或样本集的Gini Index小于阈值(样本基本属于同一类)，或者没有更多特征。
CART剪枝
CART剪枝算法由两步组成：首先从生成算法产生的决策树$T_0$底端开始不断剪枝，直到$T_0$的根结点，形成一个子树序列$\{T_0,T_1,\cdots,T_n\}$然后通过交叉验证在validation set上进行测试，从中选择最优子树。
剪枝，形成一个子树序列：
在剪枝过程中，计算子树的Loss Function：
$C_{\alpha}(T)=C(T)+\alpha |T|$
其中，$T$为任意子树，$C(T)$为对training set的预测误差(如Gini Index)，$|T|$为子树的叶结点个数，$\alpha \geq 0$为参数。可以用递归的方法对树进行剪枝，将$\alpha$从小增大，$0=\alpha_0 < \alpha_1 < \alpha_2 < \cdots < \alpha_n < +\infty$，产生一系列的区间$[\alpha_i,\alpha_{i+1}),\quad i=0,1,\cdots,n$；剪枝得到的子树序列对应着区间$\alpha \in [\alpha_i, \alpha_{i+1}), \quad i=0,1,\cdots,n$的最优子树序列$\{T_0,T_1,\cdots,T_n\}$，序列中的子树是嵌套的。
具体的，从整体树$T_0$开始剪枝，对$T_0$的任意内部结点$t$，以$t$为单结点树的Loss Function是：
$C_{\alpha}=C(t)+\alpha$以$t$为根结点的子树$T_t$的Loss Function是：
$C_{\alpha}(T_t)=C(T_t)+\alpha |T_t|$当$\alpha=0$及$\alpha$充分小时，有不等式：
$C_{\alpha}(T_t)<C_{\alpha}(t)$当$\alpha$增大时，在某一$\alpha$有：
$C_{\alpha}(T_t)=C_{\alpha}(t)$当$\alpha$再增大时，不等式反向，只要$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$，$T_t$与$t$有相同的Loss Function值，而$t$的结点少，因此$t$比$T_t$更可取，对$T_t$进行剪枝。
为此，对$T_0$中每一内部结点$t$，计算：
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$
它表示剪枝后整体Loss减少的程度，在$T_0$中剪去$g(t)$最小的$T_t$，将得到的子树作为$T_1$，同时将最小的$g(t)$设为$\alpha_1$，$T_1$为区间$[\alpha_1,\alpha_2)$的最优子树。如此剪枝下去，直至得到根结点。在这一过程中，不断增加$\alpha$的值，产生新的区间。在剪枝得到的子树序列$T_0,T_1,\cdots,T_n$中通过交叉验证选取最优子树$T_{\alpha}$
利用validation set测试子树序列$T_1,\cdots,T_n$中各棵子树的MSE或Gini Index，值最小的为最优决策树。每棵子树$T_1,\cdots,T_n$都对应于一个参数$\alpha_1,\cdots,\alpha_n$。所以当最优子树$T_k$确定时，对应的$\alpha_k$也确定了，即得到最优决策树了。
CART剪枝算法
- 设$k=0,T=T_0$
- 设$\alpha=+\infty$
- 自下而上地对各内部结点$t$计算$C(T_t)$，$|T_t|$以及
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1} \qquad \alpha=min(\alpha,g(t))$
$T_t$表示以$t$为根结点的子树，$C(T_t)$是对training set的预测误差，$|T_t|$是$T_t$的叶结点个数 - 自上而下地访问内部结点$t$，若有$g(t)=\alpha$，进行剪枝，并对叶结点$t$以多数表决法决定类别，得到树$T$。
- 设$k=k+1,\alpha_k=\alpha,T_k=T$
- 若$T$不是由根结点单独构成的树，则返回到步骤4
- 采用cross validation在子树序列中选取最优子树