Decision Tree 决策树

摘要：决策树是一种基本的分类与回归方法。决策树由结点和有向边组成。决策树所表示的条件概率分布在由各个单元给定条件下类的条件概率分布组成。决策树学习用损失函数表示这一目标。解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

决策树(decision tree)是一种基本的分类与回归方法。《统计机器学习》主要介绍了用于分类的决策树，《机器学习实战》主要介绍了回归树，两者结合能帮助很好地理解决策树。

在分类问题中，表示基于特征对实例进行分类的过程。它可以被认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要有点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策书模型进行分类。

决策树学习通常包括3个步骤：特征选择、决策树的生成和修剪。

这些思想主要来源与Quinlan在1986年提出的ID3算法和1992年提出的C4.5算法，以及游Breiman等人在1984年提出的CART算法。

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部节点（internal node）和叶节点（leaf node）. 内部节点表示一个特征或属性，叶节点表示一个类。

用决策树分类，从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点；这时，每一个子节点对应着该特征的一个取值。如此递归地对实例进行测试并分配，直至到达叶节点。最后将实例分到叶节点的类中。

可以将决策树看成一个if-then规则的集合。由决策树的根节点到叶节点构建一条规则；内部节点的特征对应着规则的条件，而叶节点的类对应着规则的结论。
决策树的路径或其对应的if-then规则集合有一个重要的性质：互斥并且完备。这就是说，没一个实例都被一条路径或一条规则所覆盖，而且制备一条路径或一条规则所覆盖。

决策树的条件概率分布定义在特征空间的一个partition上。将特征空间划分为互不相交的单元cell或区域region，并且在每个单元上定义了一个类的概率分布就构成了一个条件概率分布。

决策树的一条路径就对应与划分中的一个单元。决策树所表示的条件概率分布在由各个单元给定条件下类的条件概率分布组成。
假设$X$为表示特征的随机变量,$X$表示为类的随机变量，那么这个条件概率分布为$P(Y|X)$.$X$取之于给定划分下但与的集合，$Y$取值于类的结合。各叶节点上的条件概率一般在某一个类上概率最大。

决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。

决策树学习用损失函数表示这一目标。决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
当损失函数确定以后，学习问题就变为在损失函数意义下选择最优的决策树的问题。因为从可能的决策树中选取最优决策树是NP（Non-Polynomial）完全问题，所以现实中决策树学习算法通常采用启发式（heuristic）方法，近似求解这一最优化问题。这样得到的决策树通常是次最优（sub-optimal）的。

启发式算法（Heuristic Algorithm）有不同的定义：一种定义为，一个基于直观或经验的构造的算法，对优化问题的实例能给出可接受的计算成本（计算时间、占用空间等）内，给出一个近似最优解，该近似解于真实最优解的偏离程度不一定可以事先预计；另一种是，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。我比较赞同第二种定义，因为启发式算法现在还没有完备的理论体系，只能视作一种技术。

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

决策树学习算法包含特征选择、决策树的生成与决策树的剪枝过程。由于决策树表示一个条件概率分布，所以深浅不同的决策树对应这不同复杂度的概率模型。决策书的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择。

如果利用一个特征进行分类的结果与随机分类的记过没有很差别则称这个特征没有分类能力。经验上扔掉这个特征对决策书学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

特征选择是决定用那个特征来划分特征空间。信息增益（information gain）就能够很好地表示这一直观的准则。

在信息论与概率统计中，上（entropy）是表示随机变量不确定性的度量。

随机变量$X$的熵定义为
$$H(X)=- sum_{i=1}^{n}p_{i}log p_{i} $$

定义$0log0=0 $
熵只依赖于$X$的分布，而与$X$的取值无关，所以也将$X$的熵记作
$$H(p)=- sum_{i=1}^{n}p_{i}log p_{i} $$
熵越大，随机变量的不确定就越大。

当p=0或者p=1的时候，随机变量完全没有不确定性。当p=0.5时，$H(p)=1$，熵取值最大，随机变量不确定最大。

设有随机变量$(X,Y)$,其联合概率分布为
$P(X=x_{i},Y=y_{j})=p_{ij},i=1,2,...,n; j=1,2,...,m$

条件熵$H(Y|X)$表示在已知随机变量$X$下随机变量$Y$的不确定性。定义为X在给定条件下Y的条件概率分布的熵对X的数学期望

$$H(Y|X)= sum_{i=1}^{n} p_{i}H(Y|X=x_{i})$$

当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的上与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。此时，如果有0概率，令$0long0=0$

表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
特征A对训练数据集的信息增益$g(D,A)$，定义为集合D的经验熵H(D)与特征A在给定条件下D的经验条件熵H（D|A）只差，即
$$g(D,A)=H(D)-H(D|A)$$

输入： 训练数据集D和特征A:
输出：特征A对训练集D的信息增益g（D,A）.
(1)计算数据集D的经验熵H(D)
$$H(D)=-sum_{k=1}^{K} frac{|C_{k|}}{|D|}log_{2}frac{|C_{k}|}{|D|}$$

（2）计算特征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)$$

在数据类别越多的属性上信息增益越大，比如在主键上信息增益非常大，但明显会导致overfitting，所以信息增益有一定缺陷

对于信息增益的问题，我们采用信息增益比（information gain ratio）来对这一问题进行校正。
$g_{R}(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取值的个数。
$H_{A}(D)$可以理解为一个惩罚项。

ID3 算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。具体方法是：从根节点（root node）开始，对结点计算所有的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小（小于阈值$varepsilon$）或没有特征可以选择为止。

ID3选用信息增益最大的特征作为结点的特征。相当于用极大似然法进行概率模型的选择

算法

输入：训练集D，特征集A，阈值$varepsilon$ 
输出：决策树T.
(1)若D中所有实例属于同一类$C_{k}$,则T为单节点树，并将$C_{k}$作为该结点的类标记，返回T；
(2)若$A=phi$,则T为单结点树，并将D中实例数最大的类$C_{k}$作为该结点的类标记，返回T
(3)否则，计算A中各特征对D的信息增益，选择信息增益最大的特征$A_{g}$
(4)如果$A_{g}$的信息增益小于阈值$varepsilon$,则置T为单结点树，并将D中实例最大的类$C_{k}$作为该结点的类标记，返回T；
(5)否则，对$A_{g}$的每一可能值$a_{i}$,依$A_{g}=a_{i}$将D分割为若干非空子集$D_{i}$,将$D_{i}$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
(6)对第i个子结点，以$D_{i}$为训练集，以$A-{A_{g}}$为递归地调用（1）-（5）得到子树$T_{i}$，返回$T_{i}$

如果信息增益小于阈值$varepsilon$，或结点为空时停止并返回

ID3只有树的生成，所以改算法生成的树容易产生过拟合。

而且只用信息增益每次容易选择变量值多的feature。

C4.5算法与ID3算法相似，C4.5算法对ID3做了改进，在生成的过程中用信息增益比来选择特征。

算法

输入：训练集D，特征集A，阈值$varepsilon$ 
输出：决策树T.
(1)若D中所有实例属于同一类$C_{k}$,则T为单节点树，并将$C_{k}$作为该结点的类标记，返回T；
(2)若$A=phi$,则T为单结点树，并将D中实例数最大的类$C_{k}$作为该结点的类标记，返回T
(3)否则，计算A中各特征对D的信息增益比，选择信息增益比最大的特征$A_{g}$
(4)如果$A_{g}$的信息增益比小于阈值$varepsilon$,则置T为单结点树，并将D中实例最大的类$C_{k}$作为该结点的类标记，返回T；
(5)否则，对$A_{g}$的每一可能值$a_{i}$,依$A_{g}=a_{i}$将D分割为若干非空子集$D_{i}$,将$D_{i}$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
(6)对第i个子结点，以$D_{i}$为训练集，以$A-{A_{g}}$为递归地调用（1）-（5）得到子树$T_{i}$，返回$T_{i}$

决策树生成算法递归地产生决策树，直到不能继续下去为止。这样产生的树往往训练集很准确，但对未知测试数据却不那么准确，容易overfitting。
解决这个问题的办法是考虑决策树的复杂度，对已生成的决策树进行简化。

在决策树学习中将已生成的树进行简化的过程称为剪枝(pruning)。具体地，剪枝从已生成的树上裁掉一些子树或叶结点，并将其父结点作为新的叶节点，从而简化分类树模型。

决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）或代价函数（cost function）来实现。

设树T的叶节点个数为|T|,t是树T的叶结点，该叶结点有${N_{t}}$个样本点，其中k类的样本点有$N_{tk}$个，$H_{t}(T)$为叶结点上t的经验熵，$alphage0$为参数，则决策树学习的损失函数可以定义为

$$C_{alpha}(T)=sum_{t=1}^{|T|}N_{t}H_{t}(T)+alpha|T| （5.11）$$
其中经验熵为
$$H_{t}(T)=-sum_{k}frac{N_{tk}}{N_{t}}logfrac{N_{tk}}{N_{t}} （5.12） $$

在损失函数中，将式（5.11）右端的第1项记作
$$C(T)=sum_{t=1}^{|T|}N_{t}H_{t}(T)=-sum_{t=1}^{|T|}sum_{k}frac{N_{tk}}{N_{t}}logfrac{N_{tk}}{N_{t}}) （5.13） $$

这时有
$$C_{alpha}(T)=C(T)+alpha|T| (5.14)$$

式（5.14）中，C(T)表示模型对训练数据的预测误差，即模型与训练数据的拟合程度，|T|表示模型复杂度，参数$alphage0$控制两者之间的影响。较大的$alpha$促使选择较简单的模型（树），较小的$alpha$促使选择较复杂的模型（树）。$alpha=0$意味着只考虑模型与训练数据的拟合程度，不考虑模型的复杂度。

可以看出，决策树生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

式（5.11）或（5.14）定义的损失函数的极小化等价于正则化的极大似然估计。所以，利用损失函数最小原则进行剪枝就是用正则化的极大似然估计进行模型选择。

剪枝算法

输入： 生产算法产生的子树，参数$alpha$
输出：修剪后的子树$T_{alpha}$
(1)计算每个结点的经验熵
(2)递归地从树的叶结点向上往回缩
(3)如果退回后的树的子树$T_{B}$损失函数的值更小，则进行剪枝，返回（2），直到不能得到损失函数更小的子树$T_{A}$

分类与回归树（classification and regression tree, CART）模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、数的生成和剪枝组成，即可用于分类也可用于回归。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为"是"和"否"，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出条件概率分布。

CART算法由以下两步组成：
（1）决策树生成：基于训练数据生成决策树，生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼系数（Gini index）最小化准则，进行特征选择，生成二叉树。

回归树的生成
假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集考虑如何生成回归树。

一个回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元$R_{1},R_{2},...,R_{M}$,并且在每个单元$R_{m}$上有一个固定的输出值$C_{m}$，于是回归树模型可表示为：
$$f(x)=sum_{m=1}^{M}c_{m}I(x in R_{m})$$

当输入空间的划分确定时，可以用平方误差$sum_{x_{i}R_{m}}(y_{i}-f(x_{i}))^2$来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元$R_{m}$上的$C_{m}$的最优值$hat{ C_{m}}$是$R_{m}$上的所有输入实例$x_{i}$对应的输出$y_{i}$的均值，即
$$hat{c_{m}}=ave(y_{i}|x_{i} in R_{m})$$
问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第j个变量$x^{(j)}$和它取的值s，作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域：

$R_{1}(j,s)={x | x^{j} le s}$ 和 $R_{2}(j,s)={x | x^{j} ge s}$

然后寻找最优切分变量j和最优切分点s。具体地，求解：
$$minlimits_{j,s} left[ minlimits_{c_{1}}sum_{x_{i} in R_{1}(j,s)}(y_{i}-c_{1})^2+minlimits_{c_{2}}sum_{x_{i} in R_{2}(j,s)}(y_{i}-c_{2})^2 ight] $$

对固定输入变量j可以找到最优切分点s。

$hat{c_{1}}=ave(y_{i}|x_{i} in R_{1}(j,s))$ 和 $hat{c_{2}}=ave(y_{i}|x_{i} in R_{2}(j,s))$

遍历所有输入变量，找到最优的切分变量j，构成一个对（j,s）.依次将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，指导满足停止条件为止。这样就生成一个回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree），现将算法叙述如下：

算法（最小二乘回归树生成算法）

输入：训练数据集D：
输出：回归树$f(x)$
在训练集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
(1)选择最优划分变量j与切分点s，求解

$$minlimits_{j,s} left[ minlimits_{c_{1}}sum_{x_{i} in R_{1}(j,s)}(y_{i}-c_{1})^2+minlimits_{c_{2}}sum_{x_{i} in R_{2}(j,s)}(y_{i}-c_{2})^2 ight] (5.21)$$

遍历变量j，对固定的切分变量j扫描切分点s，选择使式（5.21）达到最小值的对（j,s）.
（2）用选定的对（j,s）划分区域并决定相应的输出值

$$hat{c_{m}}=frac{1}{N_{m}}sum_{x_{i} in R_{m}(j,s)}y_{i},x in R_{m}, m =1,2$$

继续对两个子区域调用步骤（1）（2），直到满足停止条件。
将输入空间划分为M个区域$R_{1},R_{2},...,R_{M}$,生成决策树：

$$f(x)=sum_{m=1}^{M}hat{c_{m}}I(X in R_{m})$$

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

分类问题中，假设有K个类，样本点属于第k类的概率为$p_{k}$，则概率分布的基尼指数定义为
$$Gini(p)=sum_{k=1}^{K}p_{k}(1-p_{k})=1-sum_{k=1}^{K}p_{k}^2 (5.22)$$

对于二分类问题，若样本点属于第1个类的概率是p，则概率分布的基尼指数为
$$Gini(p)=2p(1-p)$$

对于给定的样本集合D，其基尼指数为
$$Gini(D)=1-sum_{k=1}^{K} left( frac{|C_{k}|}{|D|} ight)^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(D,A)=frac{|D_{1}|}{|D|}Gini(D_{1})+frac{|D_{2}|}{|D|}Gini(D_{2})$$

基尼系数Gini（D）表示集合D的不确定性,基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性，基尼指数越大，样本集合的不确定性也就越大，这一点和熵相似。

算法 5.6

输入：训练数据集D，停止计算的条件
输出：CART决策树
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时，对每一特征A,对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”分割为$D_{1}$和$D_{2}$两部分，利用式（5.25）计算A=a时的基尼指数。
（2）在所有可能的特征A以及他们所有可能的切分点a中，选择基尼系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1）（2），直至满足停止条件
（4）生成CART决策树

算法停止计算的条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

在剪枝过程中，计算子树的损失函数：
$$C_{alpha}(T)=C(T)+alpha |T|$$

其中，T为任意子树，C(T)为对训练数据的预测误差（如基尼指数），|T|为子树的叶结点个数，$alpha ge 0$为参数， $C_{alpha}(T)$为参数是$alpha$时的子树T的整体损失。参数α权衡训练集的拟合程度与模型的复杂度。

对固定的α，一定存在使损失函数$C_{alpha}$最小的子树，将其表示为$T_{alpha}$。$T_{alpha}$在损失函数$C_{alpha}$最小的意义下是最优的。容易验证这样的最优子树是唯一的。当α大的时候，最优子树$T_{alpha}$偏小，当α小的时候，最优子树$T_{alpha}$偏大。极端情况下，α=0时，整体树是最优的。当$alpha rightarrow infty$时，根节点组成的单结点是最优的。

Breiman等人证明：可以用递归的方法对树进行剪枝。将α从小增大，$0=alpha_{0}

具体的，从整体书$T_{0}$开始剪枝。对$T_{0}$的任意内部结点t，以t为单结点树的损失函数是
$$C_{alpha}(T_{t})=C(T_{t})+alpha |T_{t}|$$

当α=0及α充分小时，有不等式
$$C_{alpha}(T_{t})

当α再增大时，不等式（5.29）方向。只要$alpha=frac{C(t)-C(T_{t})}{|T_{t}|-1}$,$T_{t}$与t有相同的损失函数值，而t的结点少，因此t比$T_{t}$更可取，对$T_{t}$进行剪枝。
为此，对$T_{0}$中每一内部节点，计算
$$g(t)=frac{C(t)-C(T_{t})}{|T_{t}|-1} (5.31)$$

它表示剪枝后整体损失函数减少的程度.在$T_{0}$中减去g(t)最小的$T_{t}$,将得到的子树作为$T_{1}$，同时将最小的g(t)设为$alpha_{1}$. $T_{1}$为区间$ [alpha_{1},alpha_{2})$的最优子树。

如此剪枝下去，直到得到根结点。在这一过程中，不断地增加$alpha$的值，产生新的区间。

具体地，利用独立的验证数据集，测试子树序列${T_{0},T_{1},dots,T_{n}}$中各棵子树的平方误差或基尼指数。平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，各棵子树${T_{0},T_{1},dots,T_{n}}$都对应一个参数${alpha_{0},alpha_{1},dots,alpha_{n}}$。所以，当最优子树$T_{k}$确定是，对应的$alpha_{k}$也确定了，即得到最优决策树$T_{alpha}$.

CART剪枝算法

输入: CART算法生成的决策树$T_{0}$
输出: 最优决策树$T_{alpha}$
(1) 设k=0，$T=T_{0}$
(2) 设$alpha=+infty$
(3) 自上而下地对各内部结点t计算$C(T_{t})$, $|T_{t}|$以及
$$g(t)=frac{C_{t}-C(T_{t})}{|T_{t}|-1}$$
$$alpha=min (alpha, g(t))$$
这里， $T_{t}$表示以t为根节结点的子树，$C(T_{t})$是对训练数据的预测误差，$|T_{t}|$是$T_{t}$的叶结点个数。
(4) 对$g(t)=alpha$的内部节点t进行剪枝，并对叶结点t以多数表决发决定其类，得到树T
(5) 设k=k+1, $alpha_{k}=alpha$, $T_{k}=T$
(6) 如果$T_{k}$不是由根节点及两个叶结点构成的书，则退回到步骤(3);否则令$T_{k}=T_{n}$
(7) 采用交叉验证法在子树序列${T_{0},T_{1},dots,T_{n}}$中选取最优子树$T_{alpha}$