决策树（decision tree）

简介

决策树是一种基本的分类与回归方法。主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括包括3个步骤：特征选择、决策树的生成和决策树的修剪。

决策树学习的思想主要来源于由$Quinlan$在$1986$年提出的**$ID3$算法和$1993$年提出的$C4.5$算法**，以及$Breiman$等人在$1985$年提出的**$CART$算法。**

决策树特征选择的常用指标

特征选择常用指标有：信息增益，信息增益比，基尼指数

• 熵（entropy）

在信息论和概率统计中，熵是表示随机变量不确定性的度量。设$X$是一个取有限个值得离散随机变量，其概率分布为
$\begin{aligned} P(X=x_i)=p_i, \quad i=1,2,\cdots,n \end{aligned}$
则随机变量$X$的熵定义为$
$\begin{aligned} H(X)=-\sum\limits_{i=1}^np_ilogp_i \end{aligned}$
由定义可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵记作$H(p)$，即
$\begin{aligned} H(p)=-\sum\limits_{i=1}^np_ilogp_i \end{aligned}$
熵越大，随机变量的不确定性就越大。

• 条件熵（conditional entropy）

设由随机变量$(X,Y)$，其联合概率分布为：
$\begin{aligned} P(X=x_i,Y=y_i)=p_{ij}, \quad i=1,2,\cdots,n;\quad j=1,2,\cdots,m \end{aligned}$
条件熵$H(Y|X)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。随机变量$X$给定的条件下随机变量$Y$的条件熵$H(Y|X)$，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望
$\begin{aligned} H(Y|X)=\sum\limits_{i=1}^np_iH(Y|X=x_i) \quad \quad 其中p_i=P(X=x_i),\quad i=1,2,\cdots,n \end{aligned}$

• **信息增益（information gain）---- **$ID3$

  信息增益表示得知特征​的信息而使得类​的信息的不确定性减少的程度。

信息增益表示得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。

定义：

特征$A$对训练数据集$D$的信息增益$g(D,A)$，定义为集合$D$的熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即：
$\begin{aligned} g(D,A)=H(D)-H(D|A) \end{aligned}$
一般地，熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息，决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

根据信息增益准则的特征选择方法是：对训练数据集（或子集）$D$，计算其内阁特征的信息增益，并比较它们的大小，选择信息增益最大的特征。

**信息增益的缺点：**以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征问题。

• **信息增益比 (information gain ratio) ---- **$C4.5$

针对信息增益的缺点，提出了信息增益比，可以校正这一问题，这是特征选择的另一准则

**定义：**特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的熵$H_A(D)$之比，即
$\begin{aligned} g_R(D,A)=\frac{g(D,A)}{H_A(D)} \end{aligned}$
其中，$H_A=-\sum\limits_{i=1}^n\frac{|D_i|}{|D|}\log _2{\frac{|D_i|}{|D|}}$，$n$是特征$A$取值的个数。

• 基尼指数 ---- $CART$

分类问题中，假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为：
$\begin{aligned} Gini(p)=\sum\limits_{k=1}^Kp_k(1-p_k)=1-\sum\limits_{k=1}^Kp_k^2 \end{aligned}$
对于二分类问题，若样本点属于第$1$个类的概率是$p$，则概率分布的基尼指数为
$\begin{aligned} Gini(p)=2p(1-p) \end{aligned}$
对于给定的样本集合$D$，其基尼指数为
$\begin{aligned} Gini(D)=1-\sum\limits_{k=1}^K(\frac{|C_k|}{|D|})^2 \end{aligned}$
这里，$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数。

如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_1$和$D_2$两部分，即
$\begin{aligned} D_1={(x,y)\epsilon D|A(x)=a}, \quad D_2=D-D_1 \end{aligned}$
则在特征$A$的条件下，集合$D$的基尼指数定义为
$\begin{aligned} Gini(D|A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) \end{aligned}$
基尼指数$Gini(D)$表示集合$D$的不确定性，基尼指数$Gini(D,A)$表示经$A=a$分割后集合$D$的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

例子

假设共有$5$个人追求场景中的女孩，年龄有两个属性（老，年轻），长相有三种属性（帅，一般，丑），工资有三个属性（高，中等，低），会写代码有两种属性（会，不会），最终分类结果有两类（见，不见）。我们根据女孩有监督的主观意愿可以等到下表

	年龄	长相	工资	写代码	类别
小A	老	帅	高	不会	不见
小B	年轻	一般	中等	会	见
小C	年轻	丑	高	不会	不见
小D	年轻	一般	高	会	见
小L	年轻	一般	低	不会	不见

• $ID3----$最大信息增益

$\begin{aligned} H(D)=-\frac{3}{5}\log_2 \frac{3}{5}-\frac{2}{5}\log_2\frac{2}{5}=0.971 \end{aligned}$

$\begin{aligned} H(D|年龄)&=\frac{1}{5}H(老)+\frac{4}{5}H(年轻) \\&=\frac{1}{5}(-0)+\frac{4}{5}(-\frac{2}{4}\log_2\frac{2}{4}-\frac{2}{4}\log_2\frac{2}{4})=0.8 \\ H(D|长相)&=\frac{1}{5}H(帅)+\frac{1}{5}H(丑)+\frac{3}{5}H(一般) \\&=\frac{1}{5}(-0)+\frac{1}{5}(-0)+\frac{3}{5}(-\frac{1}{3}\log_2\frac{1}{3}-\frac{2}{3}\log_2\frac{2}{3}) =0.551 \\ H(D|工资)&=\frac{3}{5}H(高)+\frac {1}{5}H(中等)+\frac{1}{5}H(低) \\&=\frac{3}{5}(-\frac{1}{3}\log_2\frac{1}{3}-\frac{2}{3}\log_2\frac{2}{3})+\frac{1}{5}(-0)+\frac{1}{5}(-0)=0.551 \\ H(D|写代码)&=\frac{2}{5}H(会)+\frac{3}{5}H(不会) \\&=\frac{2}{5}(-0)+\frac{3}{5}(-0)=0 \end{aligned}$

根据$g(D,A)=H(D)-H(D|A)$得
$\begin{aligned} g(D,年龄)&=0.171 \\ g(D,长相) &= 0.42 \\ g(D,工资) &=0.42 \\ g(D,写代码) &=0.971 \end{aligned}$
由此可得，特征”写代码“得信息增益最大，所有得样本根据此特征，可以直接被分到叶结点（即见或不见）中，完成决策树生长。

• $C4.5 ----$ 最大信息增益比

$\begin{aligned} 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 \end{aligned}$

根据$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$得
$\begin{aligned} g_R(D,年龄)&=0.236 \\ g_R(D,长相)&=0.402 \\ g_R(D,工资)&=0.402 \\ g_R(D,写代码)&=1 \end{aligned}$
信息增益比最大的仍然是"写代码"，但是通过信息增益比，特征”年龄“对应的指标上升了，而特征”长相“和特征”工资“却有所下降。

• $CART----$最大基尼指数

$Gini$描述的是数据的纯度，与信息熵含有类似。$CART$在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类。但与$ID3$、$C4.5$不同的是，$CART$是一棵二叉树，采用二元切割法，每一步将数据按特征$A$的取值切成两份，分别进入左右子树。特征$A$的$Gini$指数定义为
$\begin{aligned} Gini(D|A)=\sum\limits_{i=1}^n\frac{|D_i|}{|D|}Gini(D_i) \end{aligned}$

$\begin{aligned} Gini(D|年龄=老)&=\frac{1}{5}(2\times0\times1)+\frac{4}{5}(2\times\frac{2}{4}\times\frac{2}{4})=0.4 \\ Gini(D|年龄=年轻)&=\frac{4}{5}(2\times\frac{2}{4}\times\frac{2}{4})+\frac{1}{5}(2\times0\times1)=0.4 \\ Gini(D|长相=帅)&=\frac{1}{5}(2\times0\times1)+\frac{4}{5}(2\times\frac{2}{4}\times\frac{2}{4})=0.4 \\ Gini(D|长相=一般)&=\frac{3}{5}(2\times\frac{2}{3}\times\frac{1}{3})+\frac{2}{5}(2\times1\times0)=0.27 \\ Gini(D|长相=丑)&=\frac{1}{5}(2\times0\times1)+\frac{4}{5}(2\times\frac{2}{4}\times\frac{2}{4})=0.4 \\ Gini(D|工资=高)&=\frac{3}{5}(2\times\frac{1}{3}\times\frac{2}{3})+\frac{2}{5}(2\times\frac{1}{2}\times\frac{1}{2})=0.47 \\ Gini(D|工资=中等)&=\frac{1}{5}(2\times1\times0)+\frac{4}{5}(2\times\frac{1}{4}\times\frac{3}{4})=0.3 \\ Gini(D|工资=低)&=\frac{1}{5}(2\times0\times1)+\frac{4}{5}(2\times\frac{2}{4}\times\frac{2}{4})=0.4 \\ Gini(D|代码=会)&=\frac{2}{5}(2\times1\times0)+\frac{3}{5}(2\times0\times1)=0 \\ Gini(D|代码=不会)&=\frac{3}{5}(2\times0\times1)+\frac{2}{5}(2\times1\times1)=0 \end{aligned}$

在”年龄“ ”长相“ ”工资“ ”写代码“四个特征中，我们可以很快地发现特征”写代码“的$Gini$指数最小为$0$，因此选择特征”写代码“作为最优特征，”写代码=会“为最优切分点。按照这种切分，从根结点会直接产生两个叶结点，基尼指数降为$0$，完成决策树生长。

比较三种方式

1. $ID3$是采用信息增益作为评价标准；信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大，如$DNA$，使得这种分类的泛化能力是十分弱的，严重会出现过拟合现象。$C4.5$实际上是对$ID3$进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行处罚，避免$ID3$出现过拟合的特征，提升决策树的泛化能力。
2. $ID3$只能处理离散型变量，而$C4.5$和$CART$可以处理连续性变量。
3. $ID3$和$C4.5$只能用于分类任务，$CART$既可以做分类任务也可以做回归任务（回归树使用最小平方误差准则）。
4. $ID3$对样本特征缺失值比较敏感，$C4.5$和$CART$可以对缺失值进行不同方式的处理。
5. $ID3$和$C4.5$可以有多叉分支，$CART$每个结点只会有两个分支。

参考文献

李航-------统计学习方法
诸葛越-------百面机器学习