决策树

Decision Tree

机器学习最基本模型之一，DT

决策树可以看成路径的集合，路径的集合可以看成$if-then$规则的集合，内部结点表示特征或属性，叶结点表示一个类别（结论）。决策树的$if-then$规则集合是互斥且完备的（每一个实例都被包含在DT里）

决策树也可以对应于一个条件概率分布

数据集$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$

其中$x_i=(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(n)})^T$为输入实例（特征向量），$n$为特征个数，$y_i∈\{1,2,\cdots,K\}$为类别标记，

$i=1,2,\cdots,N$，$N$为样本容量。

目标就是学习到这个$if-then$规则集合，同时与训练数据矛盾较小（不欠拟合），又可以很好的预测位置数据（不过拟合）。DT学习算法是对训练数据分割的过程，也是特征空间划分的过程，也是决策树的构建过程。

DT算法一般三大步骤①特征选择②决策树生成③剪枝

剪枝的目的是防止过拟合（剪掉了树上过于细分的结点，使其退回到父节点或更高的结点）

DT是一种启发式算法，求得的是近似最优解

特征选择

熵

特征用来划分特征空间，对数据进行实际分类。我们通过信息增益或信息增益比来选择特征。

$P(X=x_i)=p_i\quad,P(X=x_i,Y=y_j)=p_{ij}\quad,i=1,2,\cdots,n;j=1,2,\cdots,m$

随机变量$X$的熵：

$H(X)=-\sum_{i=1}^np_i\log p_i$

熵表达了随机变量$X$的不确定性

由于只依赖$X$的分布而与$X$的取值没关系，则也可表示为$H(p)=-\sum_{i=1}^np_i\log p_i$

(对于$X=0,1$的熵表达式可以写为$H(p)=-p\log_2p-(1-p)\log_2(1-p)$)

给定$X$下随机变量$Y$的条件熵即为条件概率分布的熵$H(Y|X=x_i)$对$X$分布的数学期望（给每个$X_i$下的熵加了一个权值）：

$H(Y|X)=\sum_{i=1}^nP(X=x_i)H(Y|X=x_i)$

条件熵表达了在已知条件$X$下随机变量$Y$的不确定性

信息增益(Information Gain)

信息增益(Information Gain)：表示如果得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度

对于决策树，特征$A$对训练数据集$D$的信息增益$g(D,A)$为：

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

$H(D)$为数据集的经验熵，$H(D|A)$为条件经验熵（$H(Y)-H(Y|X)$叫互信息，与决策树中的信息增益等价）

很明显可以理解，某特征的信息增益越大，该特征分类能力越强（因为IG越大，就代表我能够因此获得的确定性越多，也就是分类越好）

信息增益比(Information Gain Ratio)

信息增益比(Information Gain Ratio)：

$g_R(D,A)=\frac{g(D,A)}{H_A(D)}\quad，H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$

其中$n$为特征$A$的取值个数，$H_A(D)$为训练数据集$D$关于特征$A$的值的熵（$\frac{1}{H_A(D)}$是一个惩罚系数，将特征$A$的取值作为随机变量，求的是特征$A$的熵，具体见下面-理解）

信息增益存在偏向选择取值较多的特征的问题，于是信息增益比可以对这一问题进行校正。

对于实际训练集：如果由数据估得则为经验熵，经验条件熵。那么设定$D$为数据集，$C_k$是类别为第$k$的样本集（真实标签），总共有$K$个类别；根据特征$A$可以将数据集划分为$n$个子集。$D_1,D_2,\cdots,D_n$（根据特征判断的标签），第$i$个子集即为$D_i$，$D_{ik}$表示$D_{i}$中同属于类$C_k$样本集的样本即$D_{ik}=D_i∩C_k$（也就是该类别中标签打对了的样本），则：

$H(D)=-\sum_{i=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$ $H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{i=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$

代入信息增益即可求得特征$A$对数据集$D$的信息增益

理解

这里的$H(D)$表达了数据集整体的不确定性，随机变量为$p(第i类的样本集)$；

条件熵中求的依然是数据集的熵，只是先让特征$A$进行了划分，而不是特征的熵。我们在求被$A$划分成的第$i$个$H(D_i)$的时候，$H(D_i)=-\sum_{i=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$。注意$H(D_i)$的随机变量是被$A$划分之后的条件下（这里就是条件熵多的东西）第$i$个数据集中属于$k$类的概率。

条件熵$H(D|A)$即表达了在用特征$A$对$D$进行划分为$D_1,D_2,\cdots,D_n$，所有$D_i$的不确定性之和，即每个被$A$划分为$D_i$后的熵的和。然后再在求和的时候乘了一个权值——$A$取该第$i$个划分的概率（也就是期望，此即条件熵）。

不确定性即为我们对数据分类的预测的不确定性

$P(A取第i个取值)=\frac{|D_i|}{|D|}$

特征的熵$H_A(D)$：特征$A$的取值作为随机变量。通过数据集中被$A$打为第$i$个标签的数量与总数量的比即可求得特征$A$打第$i$个标签的概率，因此可以求得特征$A$的熵；见上面的IGR的惩罚系数

注意在计算每个子数据集$D_i$的经验熵时，随机变量为$D_i$中$D_{ik}$的概率，即$D_i$中属于$k$类（真实标签）的样本的概率。凡是求数据集的熵，随机变量必然都是该数据里某类（真实标签）的概率。

基尼指数(Gini)

对于IGR，当特征取值较少时$H_A(D)$的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。于是引入基尼指数。

分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为：

$Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$

对于二分类问题，则为$Gini(p)=2p(1-p)$

于是对于样本集合：

$Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2$

基尼指数$Gini(D)$表示集合$D$的不确定性

若$D$被特征划分$D_1,D_2$，则在特征$A$的集合下，集合$D$的基尼指数定义为：

$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$

式子中如$\frac{|D_i|}{|D|}$与上面一样，也就是划分为$D_1$的概率（特征$A$取值为第一个的概率）。

$Gini(D,A)$表示经$A=a$划分后集合$D$的不确定性。基尼指数越大，样本集合的不确定性也越大，与熵一致。

决策树的生成

以下ID3和C4.5都是生成多叉树，且只适用分类问题

ID3算法

在决策树各个结点上用信息增益来选择特征

设置一个阈值$\epsilon$，当$D_i$的IG小于该阈值的时候，表示该数据集可认为全是同一类别，无需再继续划分

只用于分类（离散数据）

举例：

有$K$个特征

①对$D$，求$g(D,A_1),g(D,A_2),\cdots,g(D,A_K)$

②于是可以求得使得IG：$g(D,A_k)$最大的特征$A_{g_1}$

③使用$A_g$将$D$划分为$D_1,D_2,\cdots,D_n$；（假设$A_g$有$n$个取值）

已经确定特征$A_g$，则特征集$A\to A-A_g$，特征数量变为$K-1$

④对每一个$D_i$，求$g(D_i,A_1),g(D_i,A_2),\cdots,g(D_i,A_{K-1})$

⑤求使得IG最大的$A_{g_2}$

⑤若此时$A_{g_2}＜\epsilon$ ，则表示$D_i$可认为全是同一类别，无需再继续划分，该结点为叶子结点；

否则：再继续对$D_i$进行划分，上一个特征节点$A_g$为中间结点

再对每个划分的划分，求使得对应IG最大的$A_{g_k}$，判断继续划分or停止…

⑥依次类推$\cdots\cdots$

其中第④步就是返回到了第①步，$D换成了D_i$。（不过注意这里默认$D$并不是同一类，默认要继续划分）

具体略

C4.5算法

在决策树各个结点上用信息增益比来选择特征

设置一个阈值，当IGR小于该阈值的时候，算法停止

具体略

（连续属性值算法见后记-2）

以上两种算法容易过拟合，所以要剪枝

决策树的剪枝

决策树的剪枝是从全局角度减小决策树复杂度以防止过拟合

通过极小化DT整体的损失函数来实现

设：树$T$，叶结点个数$|T|$，$t$为某叶结点，该叶结点上有$N_t$个样本点，其中$k$类样本点有$N_{tk}$个，$k=1,2,\cdots,K$，$H_t(T)$为叶结点$t$上的经验熵，$\alpha≥0$为参数。

DT学习的损失函数：

$C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|\quad\quad H_t(T)=-\sum_k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$ $记C_\alpha(T)右端第一项为：C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log \frac{N_{tk}}{N_t}$ $则有简记：C_\alpha(T)=C(T)+\alpha|T|$

$C(T)$就是计算出每个叶子结点的已分类数据集的熵之和，熵越小，则DT整体的不确定性程度越低，就代表分类越确定。此项越小，就代表模型与训练集的拟合程度越高。

$|T|$是叶子结点的个数，它就能表征DT模型的复杂度。此项越小，模型的复杂度就越低，就越不容易过拟合。

于是$\alpha≥0$就控制了两者之间的关系；如当$\alpha=0$，就代表模型只考虑拟合度不考虑复杂度，etc。该损失函数就相当于一个正则化的极大似然估计

含有这两者的损失函数就代表了拟合度和复杂度的一个平衡关系。可以看到决策树的生成是学习局部模型的，但决策树的剪枝是学习整体的模型。该

剪枝算法的目的，就是在给定$\alpha$下，求出使得损失函数$C_\alpha(T)$最小的子树$T’$

剪枝算法：（在用前面的算法生成完决策树之后）

①计算每个结点的经验熵

②递归地从树的叶结点$t_{|T|}$向上回缩直到根节点$T$。具体地，

对于该叶结点，如果将其回缩到其父节点之后：

——如果树整体的损失函数变小，则回缩该结点；

——否则，不回缩该结点。

③以此迭代

由于回缩计算差值的时候，树上只有局部有改变，所以在计算损失函数差值的时候只需要在局部进行

CART算法

CART: classification and regression tree 分类与回归树。CART既可以用于分类也可以用于回归。

生成

CART算法生成的是二叉决策树。（二叉决策树不是哈夫曼树形式，别搞错了）

思想：使用启发式算法，不断地寻找最优特征和最优切割点$(j,s)$，对数据集进行二元切分。

多值/多段回归特征很明显可以重复使用，一次无法将多值的某特征从数据集分离开（二值特征使用一次就不能再使用）（多段回归特征类似于分类中的多值特征，只不过预测的连续变量可以被划分为多个段）

分类：

（使用基尼指数来衡量最优特征和最优切分点，基尼指数越小，不确定越低，每个样本分类越相同）

通过对数据集$D_m$求$D_m$对每个特征$A_i$的基尼系数：即遍历$i,k$，求使得$Gini(D,A_i=k)$最小的最优特征和最优特征的切分点$(j,s)$组合（对应于遍历组合的标号$i,k$）。求出一个$D_m$的$(j,s)$就能将其划分为两个子数据集。再对两个子数据集重复迭代上述过程，若结点中的样本个数小于预订阈值/样本集的基尼指数低于预定阈值（样本基本属于同一类）/没有更多特征，该结点就是叶子结点。

具体算法略
回归：【重要，是Boosting中许多模型的基础】

CART回归树生成是先确定结构（划分），再确定回归值(CART分类树就只有前面那个步骤)，以此到Boosting（GDBT XGBoost)也是这个求法

在回归问题中，模型输出一个连续变量。

$D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，数据集被划分为了$M$个单元$R_1,R_2,\cdots,R_M$，在每个单元上有一个固定的输出值为$c_m$

在回归中用平方误差来替代分类中的基尼指数：使用该结点数据集的每个样本中的【每个真实输出$y_i$与模型输出$f(x_i)$的均值$c_m$】的平方误差$\sum_{x_i}(y_i-c_m)^2$来找最优特征和最优切分点$(j,s)$。平方误差越小，样本分类越准确。（这个是回归与分类不同的关键）【平方误差即是这里CART使用的损失函数，也可以用其它损失函数，比如Boosting里的损失函数就都不一样】

与分类中一样的思路：

①根据损失函数选定最优特征和切割第$j$个特征和其取值$s$为切分点，将父节点数据集$R$切分成了两个子节点（子数据集）：

$R_1(j,s)=\{x|x^{(j)}≤s\}$，$R_2(j,s)=\{x|x^{(j)}＞s\}$

以$R_1$为例，$\{x|x^{(j)}≤s\}$是指数据集中第$j$个特征的取值$≤s$的样本组成的新数据集，也就是一个划分，$R_2$同理。

这里就确定了决策树的结构，于是：

②根据损失函数选取最优回归输出值

这里损失函数为平方误差，对其就0导容易推得最优回归输出$c$就是划分上的均值

设$c_m=ave(y_i|x∈R_m)=\frac{1}{N_m}\sum_{x_i∈R_m(j,s)}y_i$，表示被特征与切分组合$(j,s)$切分后数据集上模型输出$y$的均值，则这个$c_m$就是该节点的最优回归输出

于是我们想要求得能够使得平方误差最小的特征与划分选取组合$(j,s)$以及其对应的最优输出（均值$\hat c_m$）：
$\min_{j,s}[\min_{c_1}\sum_{x_i∈R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i∈R_2(j,s)}(y_i-c_2)^2]$
于是再对两个被划分的子节点重复上面的步骤，直到满足停止条件

这样生成的树叫最小二乘回归树

理解：

①【选特征与切割】：求得$(j,s)$就告诉我们决策树怎么生成，选什么特征怎么切分（同分类），遍历选择$j,s$选最优划分。即【确定了决策树的结构】【这时候计算损失就是根据左\右划分（结点）的[所有点各自的真实输出]与切割点（一个回归输出值）之间的损失之和，来选取使共损失最小的特征与切割。】

②【决定回归输出】：每确定一个最优结点划分（即确定一组$(j,s)$），就能根据损失函数求出该结点内的最优输出：在各自每一个划分（结点）内选择一个最优的输出（即计算结点内的各点真实输出到选择的输出回归值的损失之和），使得该划分每个样本的损失最小。

由于这里用的损失函数是平方误差，可以求得其最优值就是样本均值，对应特征$j$在划分数据集上的均值$\hat c_{1}$（特征值$≤s$的子结点）和$\hat c_2$（特征值$＞s$的子节点），所以这个均值就是特征值$j$的回归输出。

【注意①和②在求最优切割和最优均值中求的损失都是用的[同一个损失函数计算]！看这个公式说得很明白，理解透这个公式】

对于使用一般损失函数的形式：
$\min_{j,s}[\min_{c_1}\sum_{x_i∈R_1(j,s)}L(y_i,c_1)+\min_{c_2}\sum_{x_i∈R_2(j,s)}L(y_i,c_2)]$

（连续属性值算法见后记-2）

（注意，如果每个训练样本是一维的，就不需要选切分特征（切分变量）了，回归和分类都是。如$x∈[0.5,10.5]$，在实数轴上，特征维度为1）

剪枝

思想：尝试所有的$\alpha$对树进行剪枝，找出最佳子树

过程：

迭代$\alpha$，剪枝，求每个$\alpha$下的最小子树

①对一棵树$T$，令$\alpha$从0从小到大开始进行一次迭代。

对一个$\alpha$，对从下到上对每一个结点$t$，以$t$为单结点（即$t$以下的树结点全部剪掉）的损失函数为：

$C_\alpha(t)=C(t)+\alpha|t|=C(t)+\alpha$

以$t$为根节点（即不剪枝）的树$T_t$的损失函数为：$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$

当$C_\alpha(T_t)=C_\alpha(t)$的时候，联立以上两式得：$\alpha^o=\frac{C(t)-C(T_t)}{|T_t|-1}$，这个式子即表示剪枝与不剪枝损失函数相等的时候$\alpha$的值$\alpha^o$，我们把它用$g(t)$表示。

根据上述式子推可得，$\alpha$越大，那么不剪枝的整体损失函数就会大于剪枝的整体损失函数（因为$C_\alpha(T_t)$的$\alpha$项后面跟着$|T_t|≥1$)，那么就该剪（因为目的是最小化损失函数），反之就不该剪。于是$g(t)$就可以作为一个用来判断对于一个结点$t$，给定$\alpha$下该不该剪枝的阈值。

于是对于本次迭代的$\alpha$下，计算树$T$中每个结点$t$的剪枝判断阈值$g(t)$值：
$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$
于是从下往上对树中的每个结点$t$作阈值判断：如果$\alpha≥g(t)，剪；\alpha＜g(t)，不剪$

②继续增大$\alpha$，选择下一个$\alpha$重复上述过程

③迭代结束，得到一个子树序列：$\{T_0,T_1,\cdots,T_n\}$，每个子树对应于不同的$\alpha$值，每个子树都是对应$\alpha$值的最小子树
对获取的最小子树序列进行选择最优$\alpha$和最优子树

利用独立验证数据集测试各子树的平方误差或基尼指数，求得最优解

比较ID3/C4.5和CART来理解

划分

在ID3和C4.5中，通过IG或IGR求出最优特征之后，直接将特征的所有可能取值作为切分点，那么就成了多分类。那么ID3/C4.5生成的是一个多叉树

而CART要求出最优特征和最优切分点的组合，以将该特征下的取值切分成二类。CART生成一个二叉树。

举例：特征为年龄，取值为青年、中年、老年，那么ID3/C4.5就可能分成$O\{青年\}\{中年\}\{老年\}$，CART就可能分为$O\{青年\}\{中年、老年\}$ （$O$代表父节点，$\{\}代表子节点集合$）
特征变量的使用

特征变量的使用中，多分的分类变量ID3和C4.5层级之间只单次使用，CART可多次重复使用

举例：继续上面的例子，在ID3/C4.5中，该特征（年龄）被一次划分为三个子数据集$\{青年\}\{中年\}\{老年\}$，于是该特征被删除特征集，不再使用。继续迭代就在其它特征中来选择最优特征

而在CART中，两个子节点为$O\{青年\}\{中年、老年\}$，对于这两个子节点进行迭代的时候，由于特征（年龄）并没有将所有年龄特征分开，则还可以再使用用过的特征（年龄）来继续二分类！（假设在右节点使用年龄的基尼系数相比其他特征和划分最低的话，那么下次就再使用年龄特征，只有二分类所以直接划分为$\{中年\}\{老年\}$）不过再次使用该特征并不一定是接着使用，这需要根据基尼指数最小/平方误差最小计算。

也因此CART一般比ID3/C4.5深
输入与输出

ID3和C4.5只能做分类，CART可以做回归和分类

ID3只能作用离散值属性，C4.5和CART可以作用连续值属性

注意区别见后记-3
计算代价

CART计算更快，消耗资源更少，因为CART不需要进行熵中的log运算（基尼指数和熵效果差不多，但没用log，这就是用基尼指数的原因）
缺失值

ID3对缺失值敏感，而C4.5和CART对缺失值可以进行多种方式的处理 O
剪枝方法不同

C4.5是通过枝剪来修正树的准确性，而CART是直接利用全部数据发现所有树的结构进行对比
C4.5是ID3的优化 IGR替代了IG

因为信息增益的缺点是倾向于选择取值较多的屬性，在有些情况下这类属性可能不会提供太多有价值的信息。
样本量

只从样本量考虑，小样本建议考虑c4.5、大样本建议考虑cart。而cart本身是一种大样本的统计方法，小样本处理下泛化误差较大

后记

缺失值处理

①抛弃缺失值

②补充缺失值

③概率化缺失值（C4.5使用此方式，对缺失值的样本赋予该属性所有属性值的概率分布）

④缺失值单独分支
属性为连续值的划分问题

离散化技术

C4.5用于连续值属性的算法：（于是就成了二叉树了）

采用离散化技术（如二分法）进行处理。将属性值从小到大排序，然后选择中间值作为分割点，数值比它小的点被划分到左子树，数值不小于它的点被分到又子树，对所有可能的分割法，计算分割的信息增益率，选择信息增益率IGR最大的属性值进行分割。

CART的连续值属性的算法：只是把IGR换成了基尼指数或平方误差，其它一样
【注意】回归预测与连续值属性的区别

回归预测指输出（预测）的是一个连续变量的值，比如要求输出概率（又比如说要预测房价）

属性为连续值指的是输入的属性是连续的，即取值无限，如输入的$x是实数$，那就得用离散化方法，C4.5采用了二分，即把$x是实数\to \{x<A_i\},\{x≥A_i\}$两个结点。（或者如输入的值是房价）

属性就是特征，属性的值即特征的取值
CART回归树的例可以见Boosting的GDBT后记
寻找最优切分和特征一般都是贪心算法，只考虑当前结点下的最优特征和最优分割
决策树以及基于Boosting的算法的优点

①天然对缺失值和噪音有很好的鲁棒性

②天然可以很好的处理各种类型的特征

③天然对离群值有很好的鲁棒性

④（对Boosting DT）数据规模影响不大，因为我们对弱分类器的要求不高
但也有缺点，就在于假设无噪音的情况下，性能不如SVM，LR等，但如果数据集有噪音的话，这个弱势就不能么明显了。而且，可以用Boosting嘛，一个DT不给力，多个DT一起干，效果就更强