决策树
- 决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成，节点分为内部结点和外部结点，其中每个内部结点表示一个特征或者属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别(即叶结点)中。
- 决策树作为最基本、最常见的有监督学习模型，常被用于分类问题和回归问题，再市场营销和生物医药等领域具有广大应用场景。将决策树应用集成学习的思想可以得到随机森林、梯度提升决策等模型。完成生长的决策树模型具有简单直观、解释性强的特点，值得读者认真理解，这也是为融为贯通集成学习相关内容所作的铺垫。
- 常见的决策树算法有ID3、C4.5、CART,接下来逐一讲解构建树所使用的启发式函数、准则、区别与联系。
- 为了便于理解，本文通过如下实例进行推导相关算法的计算和实现。假设共有5个人追求场景中的女孩，年龄有两个属性(老、年轻)；长相有三个属性(帅、一般、丑)；工资有三个属性(高、中等、低)；会写代码有两个属性(会、不会)；最终分类结果有两类(见、不见)，具体如表《5个候选对象的属性以及女孩对应的主观意愿》所示：
| 年龄 | 长相 | 工资 | 写代码 | 类别 | |
|---|---|---|---|---|---|
| 小A | 老 | 帅 | 高 | 不会 | 不见 |
| 小B | 年轻 | 一般 | 中等 | 会 | 见 |
| 小C | 年轻 | 丑 | 高 | 不会 | 不见 |
| 小D | 年轻 | 一般 | 高 | 会 | 见 |
| 小L | 年轻 | 一般 | 低 | 不会 | 不见 |
1. ID3 最大信息增益
对于样本集合D，类别数为K，数据集D的经验熵表示为：
$$H\big(D\big)=-\sum_{k=1}^{k}\frac{|C_k|}{|D|}log_2\frac{|C_k|}{|D|}$$
其中$C_k$是样本集合$D$中属于第$k$类的样本子集，$C_k$表示该子集的元素个数，$|D|$表示样本集合的元素个数。
然后计算某个特征$A$的对于数据集$D$的经验条件熵$H\big(D|A\big)$为：
$$H\big(D|A\big)=\sum_{i=1}^n\frac{|D_i|}{|D|}\Big(-\sum_{k=1}^k\frac{|D_{ik}|}{|D_i|}log_2\frac{|D_{ik}|}{|D_i|}\Big)$$
其中，$D_i$表示$D$中特征$A$取第$i$个值的样本子集，$D_{ik}$表示$D_i$中属于第$k$类的样本子集。
于是信息增益$g\big(D,A\big)$可以表示为二者之差，可得:
$$g\big(D,A\big)=H\big(D\big)-H\big(D|A\big)$$
- 计算经验熵计算为：
$$H\big(D\big)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971$$ - 计算四个分支结点的信息熵为：
$$H\big(D|年龄\big)=\frac{1}{5}H\big(老\big)+\frac{4}{5}H\big(年轻\big)=\frac{1}{5}\big(-0\big)+\frac{4}{5}\Big(-\frac{2}{4}log_2\frac{2}{4}-\frac{2}{4}log_2\frac{2}{4}\Big)=0.8$$
$$H\big(D|长相\big)=\frac{1}{5}H\big(帅\big)+\frac{3}{5}H\big(一般\big)+\frac{1}{5}H\big(丑\big)=0+\frac{3}{5}\Big(-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\Big)+0=0.551$$
$$H\big(D|工资\big)=\frac{3}{5}H\big(高\big)+\frac{1}{5}H\big(中等\big)+\frac{1}{5}H\big(低\big)=\frac{3}{5}\Big(-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3}\Big)+0+0=0.551$$
$$H\big(D|写代码\big)=\frac{3}{5}H\big(不会\big)+\frac{2}{5}H\big(一会\big)=\frac{3}{5}\Big(0)+\frac{2}{5}(0)=0$$
可计算各个特征的信息增益为：
$$g\big(D,年龄\big)=H\big(D\big)-H\big(D|A\big)=0.971-0.8=0.171$$
$$g\big(D,年龄\big)=H\big(D\big)-H\big(D|A\big)=0.971-0.551=0.42$$
$$g\big(D,年龄\big)=H\big(D\big)-H\big(D|A\big)=0.971-0.551=0.42$$
$$g\big(D,年龄\big)=H\big(D\big)-H\big(D|A\big)=0.971-0=0.971$$
显然，特征”写代码”的信息增益最大，所有的样本根据此特征，可以直接被分到叶结点(即见/不见)中，完成决策树生长。当然，再实际应用中，决策树往往不能通过一个特征完成构建，需要在经验熵非0的类别中继续生长。
2. C4.5 最大信息增益比
特征A对于数据集$D$的信息增益比定义为：
$$g_{R}\big(D,A\big)=\frac{g(D,A)}{H_A(D)}$$
其中，$$H_A(D)=-\sum_{i=1}^n\frac{D_i}{D}log_2\frac{D_i}{D}$$，称为数据集$D$关于$A$的取值熵，针对以上描述问题，可以使用此公式计算数据集关于每个特征的的取值熵为：
$$H_{年龄}(D)=-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2\frac{4}{5}=0.722$$
$$H_{长相}(D)=-\frac{1}{5}log_2\frac{1}{5}-\frac{3}{5}log_2\frac{3}{5}-\frac{1}{5}log_2\frac{1}{5}=1.371$$
$$H_{工资}(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{1}{5}log_2\frac{1}{5} -\frac{1}{5}log_2\frac{1}{5}=1.371$$
$$H_{写代码}(D)=-\frac{3}{5}log_2\frac{3}{5}-\frac{2}{5}log_2\frac{2}{5}=0.971$$
于是，根据公式即可计算每个特征对于数据集D的信息增益比，具体如下：
$$g_R(D,年龄)=\frac{g(D,A)}{H_A(D)}=0.171-0.722=0.236$$
$$g_R(D,长相)=\frac{g(D,A)}{H_A(D)}=0.171-1.371=0.402$$
$$g_R(D,工资)=\frac{g(D,A)}{H_A(D)}=0.171-1.371=0.0.402$$
$$g_R(D,写代码)=\frac{g(D,A)}{H_A(D)}=0.171-.0971=1$$
信息增益比最大的仍是特征“写代码”，但通过信息增益比，特征“年龄”对应的指标上升了，而特征“长相”和特征“工资”却有所下降。
3. CART 最大基尼指数Gini
Gini描述的时数据的纯度，与信息熵含义类似：
$$Gini(D)=1-\sum_{k=1}^n\Big(\frac{|C_k|}{D}\Big)^2=\sum_{i=1}^np(x_i)*(1-p(x_i))=1-\sum_{i=1}^np(x_i)^2$$
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类，但与ID3、C4.5不同的是，CART是一颗二叉树，采用二元切分法，每一步将数据按特征A的取值切分成两份，分别进如左右子树。特征$A$的Gini指数定义为：
$$Gini(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i)$$
依然使用上述数据进行应用CART分类准则，可以计算出每个特征的Gini指数为:
按照年龄、长相、工资和写代码四个离散特征以及最后的类别分类结果进行如下归纳：
| 老 | 年轻 | |
|---|---|---|
| 见 | 0 | 2 |
| 不见 | 1 | 2 |
按照以上归纳表和相应的公式便可计算对应的Gini分数：
$$Gini(老)=1-\sum_{i=1}^np(x_i)^2=1-p(见|老)-p(不见|老)=1-\Big(\frac{0}{1}\Big)^2-\Big(\frac{1}{1}\Big)^2=0$$
$$Gini(年轻)=1-\sum_{i=1}^np(x_i)^2=1-p(见|年轻)-p(不见|年轻)=1-\Big(\frac{2}{4}\Big)^2-\Big(\frac{2}{4}\Big)^2=\frac{1}{2}$$
$$所以:Gini(D|A)=Gini(类别|年龄)=\sum_{i=1}^n\frac{|D_i|}{D}Gini(D_i)=\frac{1}{5}*0+\frac{4}{5}*0.5=0.4$$
| 帅 | 一般 | 丑 | |
|---|---|---|---|
| 见 | 0 | 2 | 0 |
| 不见 | 1 | 1 | 1 |
按照以上归纳表和相应的公式便可计算对应的Gini分数：
$$Gini(帅)=1-\sum_{i=1}^np(x_i)^2=1-p(见|帅)-p(不见|帅)=1-\Big(\frac{0}{1}\Big)^2-\Big(\frac{1}{1}\Big)^2=0$$
$$Gini(一般)=1-\sum_{i=1}^np(x_i)^2=1-p(见|一般)-p(不见|一般)=1-\Big(\frac{2}{3}\Big)^2-\Big(\frac{1}{3}\Big)^2=\frac{4}{9}$$
$$Gini(丑)=1-\sum_{i=1}^np(x_i)^2=1-p(见|丑)-p(不见|丑)=1-\Big(\frac{0}{1}\Big)^2-\Big(\frac{1}{1}\Big)^2=0$$
$$所以:Gini(D|A)=Gini(类别|长相)=\sum_{i=1}^n\frac{|D_i|}{D}Gini(D_i)=\frac{1}{5}*0+\frac{3}{5}*\frac{4}{9}+\frac{1}{5}*0=0.27$$
| 高 | 中等 | 低 | |
|---|---|---|---|
| 见 | 1 | 1 | 0 |
| 不见 | 2 | 0 | 1 |
按照以上归纳表和相应的公式便可计算对应的Gini分数：
$$Gini(高)=1-\sum_{i=1}^np(x_i)^2=1-p(见|高)-p(不见|高)=1-\Big(\frac{1}{3}\Big)^2-\Big(\frac{2}{3}\Big)^2=\frac{4}{9}$$
$$Gini(中等)=1-\sum_{i=1}^np(x_i)^2=1-p(见|中等)-p(不见|中等)=1-\Big(\frac{1}{1}\Big)^2-\Big(\frac{0}{1}\Big)^2=0$$
$$Gini(低)=1-\sum_{i=1}^np(x_i)^2=1-p(见|低)-p(不见|低)=1-\Big(\frac{0}{1}\Big)^2-\Big(\frac{1}{1}\Big)^2=0$$
$$所以:Gini(D|A)=Gini(类别|工资)=\sum_{i=1}^n\frac{|D_i|}{D}Gini(D_i)=\frac{3}{5}*\frac{4}{9}+\frac{1}{5}*0+\frac{1}{5}*0=0.27$$
| 会 | 不会 | |
|---|---|---|
| 见 | 2 | 0 |
| 不见 | 0 | 3 |
按照以上归纳表和相应的公式便可计算对应的Gini分数：
$$Gini(会)=1-\sum_{i=1}^np(x_i)^2=1-p(见|会)-p(不见|会)=1-\Big(\frac{2}{2}\Big)^2-\Big(\frac{0}{2}\Big)^2=0$$
$$Gini(不会)=1-\sum_{i=1}^np(x_i)^2=1-p(见|不会)-p(不见|不会)=1-\Big(\frac{0}{3}\Big)^2-\Big(\frac{3}{3}\Big)^2=0$$
$$Gini(低)=1-\sum_{i=1}^np(x_i)^2=1-p(见|低)-p(不见|低)=1-\Big(\frac{0}{1}\Big)^2-\Big(\frac{1}{1}\Big)^2=0$$
$$所以:Gini(D|A)=Gini(类别|写代码)=\sum_{i=1}^n\frac{|D_i|}{D}Gini(D_i)=\frac{2}{5}*0+\frac{3}{5}*0=0$$
4. 对决策树进行剪枝
一颗完全生长的决策树会面临一个很严重的问题，即过拟合，因此需要通过简直来解决。剪枝可分为预剪枝(Pre-Pruning)和后剪枝(Post-Pruning)，预剪枝是指在构造的过程中就知道那些节点可以剪掉。后剪枝是指构造出完整的决策树之后再来考查娜些子树可以剪掉。常见的后剪枝方法有：错误率降低剪枝、悲观剪枝、代价复杂剪枝、最小误差剪枝、CVP、OPP等方法。
- 代价复杂剪枝(CCP):
对于分类回归树中的每一个非叶子节点计算它的表面误差率增益值$α$
$$α=\frac{C(t)-C(T_i)}{T_i-1}$$
其中$T_i$为子树中包含的叶子节点个数，$C(t)$为以$t$为单节点树的误差代价，该节点被剪枝，$C(t)=r(t)*p(t)$，$r(t)$为节点$t$的误差率，$p(t)$节点$t$上的数据占所有用户的比例。$C(T_i)$是以$t$为根节点的子树$T_t$的误差代价，如果该节点不被剪枝，它等于子树$T_t$上所有叶子节点的误差代价之和。
5、ID3、C4.5和CART之间的对比分析
通过对比三种决策树的构造准则，以及在同一个例子上的不同表现，我们不难发现总结三者之间的差异：
- ID3是采用信息增益作为评价指标，除了“会写代码”这一逆天特征外，会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件傻熵越小，信息增益越大。
- C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根绝切分点把连续属性转换为布尔型，从而将连续变量转换多个取值区间离散型变量。
- 三者之间的对比分析表
| 算法 | 树结构 | 支持模型 | 特征选择 | 连续值处理 | 缺失值处理 | 剪枝 |
|---|---|---|---|---|---|---|
| ID3 | 多叉树 | 分类 | 信息增益 | 不支持 | 不支持 | 不支持 |
| C4.5 | 多叉树 | 分类 | 信息增益 | 不支持 | 支持 | 不支持 |
| CART | 二叉树 | 分类、回归 | 基尼系数、平方误差和 | 支持 | 支持 | 不支持 |
6、总结
