机器学习之决策树

    决策树(Decision Tree)是一种树形结构，是基本的分类和回归方法，是一种监督学习算法。决策树学习通常包含3个步骤：特征选择、决策树的生成和决策树的剪枝。

基本概念

熵

    在信息论中，熵是表示随机变量不确定性的度量。$X$是取有限个值的离散随机变量，概率分布为：

$$P(X=x_i)=p_i,i=1,2,3,…,n$$

则随机变量$X$的熵定义为：

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

如果一个事件结果越不确定，则熵值越大，如果一个事件结果是确定性的，则该事件完全没有不确定性，熵值为0。均匀分布随机变量不确定性最大，熵值最大。

条件熵

    随机变量$(X,Y)$,联合概率分布可以表示为:

$$P(X=x_i,Y=y_i)=p_{ij},i=1,2,…,n;j=1,2,…,m$$

条件熵$H(Y|X)$表示在给定$X$的条件下，$Y$的不确定性，条件熵可以表示为:

$$H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i),p_i=P(X=x_i)$$

    当熵和条件熵中的概率由数据估计得到时，所对应的熵与条件熵分别称之为经验熵和经验条件熵。

信息增益

    决策树中，信息增益表示得知特征$X$的信息而使得类信息的不确定性减少的程度。特征$A$对训练数据集$D$的信息增益$g(D,A)$可以定义为集合$D$的经验熵与给定特征$A$条件下的D的经验条件熵$H(D,A)$之差，用数学表达式可以表示为：

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

在统计学中，熵和条件熵的差值成为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
用强大的Venn图来区分这几个概念。    其中，$I(X,Y)$代表的是互信息，$H(X|Y)$和$H(Y,X)$代表的是条件熵，$I(X,Y)$代表的是互信息，即信息增益。

信息增益比

    特征$A$对训练数据集$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$取值的个数。

$Gini$指数

    在分类问题中，假设有$K$个类，样本点属于第$K$类的概率为$p_k$,则概率分布的Gini指数可以定义为：

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

$Gini$理解

    将$f(x)=-lnx$在$x=1$处一阶展开，得到$f(x)$近似等于$1-x$，所以可以认为$Gini$系数是信息增益的近似。
    $Gini$系数是衡量一个国家贫富收入差距的一个主要指标。基尼系数介于0-1之间，基尼系数越大，表示不平等程度越高。

特征选择

    特征选择主要在于选取对训练数据由分类能力的特征。如果利用一个特征进行分类的结果与随机分类的结果相比没有很大的差别，则称这个特征是没有分类能力的，这样的特征需要被舍弃。特征选择是决定用哪个特征来划分特征空间。在特征选择时，要选用在当前情况下更具有分类能力的特征，在决策树当中通常特征选择通常是采用信息增益、信息增益比或者是Gini指数来度量特征的分类能力。
    决策树学习方法主要是$ID3$、$C4.5$和$CART$算法。针对不同的学习算法有不同的特征选择方法。
    $ID3$：在决策树各个结点上采用信息增益选择特征。
    $C4.5$:$C4.5$是$ID3$的升级版，以信息增益为划分数据集的特征，存在偏向于选择取值较多的特征问题，因此$C4.5$采用信息增益比选择特征，实现校正的目的。
    $CART$:$CART$是在决策树各个结点上采用Gini指数来选择特征。

决策树的生成

    决策树学习的算法通常时递归地选择最优特征，并根据该特征对训练数据划分，这一过程通常时对应着对决策树特征空间的划分，也对应着决策树的构建。不同的决策树学习方法，对应着不同的生成办法，但本质是相同的，唯一不同的是决策树选择特征的度量方法不同，即上一节提到的。
    构建过程：开始，构建根节点，将所有训练数据都放在根节点，依据信息增益、信息增益比或者是Gini系数选择一个最优特征，按照这一特征将训练数据集分成不同的子集，如果这些子集已经能够基本被分类正确，那么构建叶节点，并将这些子集划分到所对应的叶节点当中去，如果还有子集不能被基本分类正确，则对这些子集选择新的最优特征，继续讲子集进行划分，构建相应的节点，以此类推，直到每个子集都被分到叶节点上，即都有了明确的分类，那么构建了一颗决策树。
举个例子：
    下图中的数据是由15个样本所组成的贷款申请的训练数据，数据包括贷款申请人的4个特征：第一个是年龄，有三个可能值:青年、中年，老年；第二个特征是是否有工作，有两个可能值：是，否；第三个特征事是否有自己的房子，有两个可能的值：是，否；第四个特征是信贷情况，有三个可能值：非常好，好，一般。最后一列是类别，是否同意贷款，有两个可能值：是，否。
    希望通过所给的训练数据来训练学习一个决策树，对未来的贷款申请进行分类。分别用$ID3$、$CART$以及$C4.5$学习算法来构建一棵决策树。

$ID3$

    对图中15个训练样本数据,根据信息增益准则来选择特征，进而递归地选择最优特征，构建一颗决策树。

1. 计算经验熵$H(D)$: $$H(D)=-\frac{9}{15}log_2\frac{9}{15}-\frac{6}{15}log_2\frac{6}{15}=0.974$$ 在这里，15个训练样本中9个同意贷款，6个不同意贷款。
2. 计算各个特征对数据集的信息增益，分别用$A1$、$A2$、$A3$，$A4$表示年龄、有工作、有自己的房子和信贷情况四个特征，则：
   \begin{equation}\begin{split} g(D,A1)&=H(D)-H(D|A1)\\\\
   & =H(D)-[\frac{5}{15}H(D_1)+\frac{5}{15}H(D_2)+\frac{5}{15}H(D_3)]\\\\
   &=0.974-[\frac{5}{15}(-\frac{2}{5}log_2(\frac{2}{5})-\frac{3}{5}log_2(\frac{3}{5}))\\\\
   &\quad +\frac{5}{15}(-\frac{2}{5}log_2(\frac{2}{5})-\frac{3}{5}log_2(\frac{3}{5}))+\frac{5}{15}(-\frac{4}{5}log_2(\frac{4}{5})-\frac{1}{5}log_2(\frac{1}{5}))]\\\\
   & =0.086
   \end{split}\end{equation}在这里，$D1$、$D2$、$D3$表示数据集中$A1$取值为青年、中年、老年的样本子集，类似地：\begin{equation}\begin{split} g(D,A2)&=H(D)-H(D|A2)\\\\
   & =H(D)-[\frac{5}{15}H(D_1)+\frac{10}{15}H(D_2)]\\\\
   &=0.974-[\frac{5}{15}×0 +\frac{10}{15}(-\frac{4}{10}log_2(\frac{4}{10})-\frac{6}{10}log_2(\frac{6}{10}))]\\\\
   & =0.327
   \end{split}\end{equation}\begin{equation}\begin{split} g(D,A3)&=H(D)-H(D|A3)\\\\
   & =H(D)-[\frac{6}{15}H(D_1)+\frac{9}{15}H(D_2)]\\\\
   &=0.974-[\frac{6}{15}×0 +\frac{9}{15}(-\frac{3}{9}log_2(\frac{3}{9})-\frac{6}{9}log_2(\frac{6}{9}))]\\\\
   & =0.423
   \end{split}\end{equation}\begin{equation}\begin{split} g(D,A3)&=H(D)-H(D|A4)\\\\
   & =H(D)-[\frac{5}{15}H(D_1)+\frac{6}{15}H(D_2)+\frac{4}{15}H(D_3)]\\\\
   &=0.974-[\frac{5}{15}×(-\frac{1}{5}log_2\frac{1}{5}-\frac{4}{5}log_2(\frac{4}{5}))\\\
   &\quad+\frac{6}{15}×(-\frac{2}{6}log_2\frac{2}{6}-\frac{4}{6}log_2(\frac{4}{6}))+\frac{4}{15}×0]\\\\
   & =0.366
   \end{split}\end{equation}
3. 根节点特征选取
       由于特征$A3$的信息增益最大，则选取特征$A3$作为根节点的特征，将数据集分为两类，$D1$($A3$取“是”)和$D2$($A3$取“否”)，由于$D1$只有同一类的样本点，是个确定性的数据集，熵为0，所以称为一个叶节点，节点的类标记为“是”。
4. 各个节点特征的选取
       对于数据子集$D2$需要从特征$A1$、$A2$和$A4$中选择新的特征，计算各个特征的信息增益: $$g(D2,A1)=H(D2)-h(D2|A1)=0.918-0.667=0.251$$ $$g(D2,A2)=H(D2)-h(D2|A2)=0.918$$ $$g(D2,A4)=H(D2)-h(D2|A4)=0.474$$     选择信息增益最大的特征$A2$是否有工作来作为节点的特征。由于$A2$有两个可能取值，从这个节点引出两个子节点：一个对应”是”的有工作的节点，包含3个样本，属于同一类，类标记为“是”，另一个是对应”否”的没有工作的节点，一共6个样本，他们也属于同一类，类标记为“否”。
   生成的决策树如下：
   

   $C4.5$

       计算过程如同$ID3$，只不过是在选择特征的标准是信息增益比。在信息增益的基础之上，除以训练集关于该特征的值的熵。

   $CART$

       计算过程如同$ID3$,只不过是在选择特征的标准是Gini指数。
5. 求特征的Gini指数
   (1)求特征$A1$的$Gini$指数 $$Gini(D,A1=“青年”)=\frac{5}{15}(2×\frac{2}{5}(1-\frac{2}{5}))+\frac{10}{15}(2×\frac{7}{10}(1-\frac{7}{10}))=0.44$$ $$Gini(D,A1=“中年”)=0.48$$ $$Gini(D,A1=“老年”)=0.44$$     由于$Gini(D,A1=“青年”)$和$Gini(D,A1=“老年”)$相等，且最小，所以$Gini(D,A1=“青年”)$和$Gini(D,A1=“老年”)$均可以作为特征$A1$的最优切分点。
   (2)求特征$A2$和$A3$的$Gini$指数 $$Gini(D,A2)=\frac{5}{15}(2×\frac{5}{5}(1-\frac{5}{5}))+\frac{10}{15}(2×\frac{4}{10}(1-\frac{4}{10}))=0.32$$ $$Gini(D,A3)=\frac{9}{15}(2×\frac{3}{9}(1-\frac{3}{9}))+\frac{6}{15}(2×\frac{6}{6}(1-\frac{6}{6}))=0.267$$     由于$A2$和$A3$只有一个切分点，所以它们是最优切分点。
   (2)求特征$A4$的$Gini$指数 $$Gini(D,A4=“非常好”)=0.36$$ $$Gini(D,A4=“好”)=0.47$$ $$Gini(D,A4=“一般”)=0.32$$     由于$Gini(D,A4=“一般”)$最小，所以由于$Gini(D,A4=“一般”)$是最优切分点。
6. Gini系数比较
       在$A1$、$A2$、$A3$和$A4$几个特征中，$Gini(D,A3)$最小，所以选择特征$A3$作为最优特征,$A3=”是”$为最优切分点，于是根节点生成两个子节点，一个是叶节点。对另一个节点继续使用以上方法在其余几个特征中选择$Gini$指数最小的特征作为最优切分点，依次类推。与$ID3$生成的数完全一致。

   决策树的剪枝

       由于在学习生成决策树的时候过多地考虑如何提高对训练数据的正确分类，生成的决策树有可能存在过拟合的情况，为了防止过拟合现象，主要有两种思路，一是预剪枝：在学习的时候对树的深度、子集的样本数量等进行限定，二是对已经生成的树进行自下而上的剪枝，通过剪枝，使得树变得简单，从而使其具有更好的泛化能力。
   主要介绍第二种方法：
       决策树的剪枝往往通过极小化决策树整体的损失函数来实现。假设树的叶节点个数为$|T|$,$t$是树的叶节点，叶节点有$N_t$个样本，其中$k$类的样本有$N_{tk}$个，$H_t(T)$为叶节点$t$上的经验熵，$\alpha\ge0$为参数，则决策树的损失函数可以表示为: $$L(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|，H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$$

   针对连续数据的处理

       先占坑，后期补全。

   参考资料

   李航，统计学习方法，清华大学出版社,2012