决策树算法理论详解

Posted by mudux on February 24, 2020

1. 介绍

  决策树(decision tree)是一种基本的分类与回归方法。决策树模型呈树形结构。在分类问题中,表示基于特征对实例进行分类的过程,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性,分类速度快。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型。预测时,对新的数据,利用决策树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的剪枝。这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法,以及由Breiman等人在1984年提出的CART算法。
  这篇文章首先介绍决策树的基本概念,然后分别介绍ID3、C4.5和CART算法的特征选择、决策树的生成以及决策树的剪枝,以及它们对连续值和缺失值的处理,最后对决策树算法做个总结。

2. 决策树模型与学习

2.1 决策树模型

  定义2.1 (决策树):分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性,叶结点表示一个类。
  用决策树分类,从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点。这时,每一个子结点对应着特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点,最后将实例分到叶结点的类中。下图给出了一个决策树的是示意图,图中圆和方框分别表示内部结点和叶结点。

2.1

2.2 决策树与if-then规则

  可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的:由决策树的根结点到叶结点的每一条路径构建一条规则;路径上的内部结点的特征对应着规则的条件,而叶结点的类对应着规则的结论。决策树的路径或其对应的if-then规则集合具有一个重要的性质:互斥并且完备。这就是说:每一个实例都被一条路径或一条规则所覆盖,而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

2.3 决策树与条件概率分布

  决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分(partition)上。将特征空间划分为互不相交的单元(cell)或区域(region),并在每个单元定义一个类的概率分布就构成了一个条件概率分布,决策树的一条路径对应于划分中的一个单元。
  决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设$X$为表示特征的随机变量,$Y$为表示类的随机变量,那么这个条件概率分布可以表示为$P(Y|X)$。$X$取值于给定划分下单元的集合,$Y$取值于类的集合。各叶结点(单元)上的条件概率往往偏向某一个类,即属于某一类的概率较大。决策树分类时将该结点的实例强行分到条件概率大的那一类去

2.4 决策树学习

  决策树学习,假定给定训练数据集

  其中,$x^{(i)}=(x_1^{(i)}, x_2^{(i)}, \cdots, x_n^{(i)})$为输入实例(特征向量),$n$为特征个数,为类标记,$i=1,2,\cdots, m$,$m$为样本容量。学习的目标是根据给定的训练数据集构建一个决策树模型,使它能够对实例进行正确的分类。
  决策树学习本质上是从训练数据集中归纳出一组分类规则。与训练数据集不相矛盾的决策树可能有多个,也可能一个都没有。我们需要的是一个与训练数据矛盾较小的决策树,同时具有很好的泛化能力。从另一个角度看,决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合,而且对未知数据有很好的预测。
  决策树学习用损失函数表示这一目标。如下所述,决策树学习的损失函数通常是正则化的极大似然函数。决策树学习的策略是以损失函数为目标函数的最小化。
  当损失函数确定以后,学习问题就变成在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题,所以现实中决策树学习算法通常采用启发式方法,近似求解这一最优化问题。这样得到的决策树是次最优(sub-optimal)的。
  决策树学习的算法通常是一个递归地选择最优特征,并根据该特征对训练数据进行分割,使得对各个子数据集有一个很好的分类的过程。这一过程对应着对特征空间的划分,也对应着决策树的构建。开始,构建根结点,将所有训练数据都放在根结点。选择一个最优特征,按照这一特征将训练数据集分割成子集,使得各个子集有一个在当前条件下最好的分类。如果这个子集已经能够被基本正确分类,那么构建叶结点,并将这些子集分到所对应的叶结点去;如果还有子集不能被基本正确分类,那么就对这些子集选择新的最优特征,继续对其进行分割,构建相应的结点。如此递归地进行下去,直至所有训练数据子集被基本正确分类,或者没有合适的特征为止,最后每个子集都被分到叶结点上,即都有了明确的类,这就生成了一棵决策树。
  以上方法生成的决策树可能对训练数据有很好的拟合能力,但对未知的测试数据却未必有很好的分类能力,即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝,将树变得更简单,从而使它具有更好地泛化能力。具体地,就是去掉过于细分的叶结点,使其回退到父结点,甚至更高的结点,然后将父结点或更高的结点改为新的叶结点。
  如果特征数量很多,也可以在决策树学习开始的时候,对特征进行选择,只留下对训练数据有足够分类能力的特征。
  可以看出,决策树算法包含特征选择、决策树的生成和决策树的剪枝过程。由于决策树表示一个条件概率分布,所以深浅不同的决策树对应着不同复杂度的概率模型,决策树的生成对应于模型的局部选择,决策树的剪枝对应于模型的全局选择。决策树的生成只考虑局部最优,相对地,决策树的剪枝则考虑全局最优。

2.5 决策树剪枝方法

  对决策树进行剪枝是防止过拟合。剪枝方法主要有预剪枝和后剪枝。
  预剪枝
  在结点划分前来确定是否继续增长,及早停止增长的主要方法有:

  • 结点内数据样本低于某一阈值;
  • 所有结点特征都已分裂;
  • 结点划分前准确率比划分后准确率高。 预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间,但另一方面它是基于“贪心”策略,会带来欠拟合风险。

  后剪枝
  在已经生成的决策树上进行剪枝,从而得到简化版的剪枝决策树。

3. 决策树ID3算法

3.1 特征选择问题

  特征选择在于选取对训练数据具有分类能力的特征,这样可以提高决策树学习的效率。如果利用一个特征进行分类的结果与随机分类的结果没有很大差别,则称这个特征是没有分类能力的。经验上扔掉这样的特征对决策树学习的精度影响不大。通常特征选择的准则是信息增益或信息增益比。

3.2 ID3算法信息论基础

  在信息论与概率统计中,熵(entropy)是表示随机变量不确定性的度量,不确定性越大,熵越大。设$X$是一个取有限个值得离散随机变量,其概率分布为:

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

  其中$n$代表$X$的$n$种不同的离散取值。若$p_i=0$,则定义$0\log 0 =0$。通常,上式中的对数以2为底或以$e$为底(自然对数),这时熵的单位分别称作比特(bit)或纳特(nat)。由定义可知,熵只依赖于$X$的分布,而与$X$的取值无关,所以也可将$X$的熵记作$H(p)$,即

  从定义可以验证

  当随机变量只取两个值,例如1,0时,熵$H(p)$随概率$p$变化的曲线如下图所示:

3.1

  当$p=0$或$p=1$时,$H(p)=0$,随机变量完全没有不确定性。当$p=0.5$时,$H(p)=1$,熵取值最大,随机变量不确定性最大。
  设有随机变量$(X,Y)$,其联合概率分布为

  随机变量 的条件熵(conditional entropy) ,定义为$X$给定条件下$Y$的条件概率分布的熵$X$的数学期望

  这里,$p_i=P(X=x_i),\ i=1,2,\cdots, n$。
  当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到是,所对应的熵与条件熵分别称为经验熵(empirical entropy)和经验条件熵(empirical conditional entropy)。此时,如果有0概率,令$0\log 0=0$。
  信息增益(information gain)表示得知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度

  定义3.1 (信息增益):特征 对训练数据集 的信息增益 ,定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差,即

  一般地,熵$H(Y)$与条件熵$H(Y|X)$之差称为互信息(mutual information),决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
  决策树学习应用信息增益准则选择特征。给定训练数据集$D$和特征$A$,经验熵$H(D)$表示对数据集$D$进行分类的不确定性。而经验条件熵$H(D|A)$表示在特征$A$给定的条件下对数据集$D$进行分类的不确定性,它们的差即信息增益,就表示由于特征$A$而使得对数据集$D$的分类的不确定性减少的程度。显然,对于数据集$D$而言,信息增益依赖于特征,不同的特征往往具有不同的信息增益,信息增益大的特征具有更强的分类能力。
  根据信息增益准则的特征选择方法是:对训练数据集$D$,计算器每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
  设训练数据集为$D$,$|D|$表示其样本容量,即样本个数。设有$K$个类$C_k,\ k=1,2,\cdots, K$,$|C_k|$为属于类$C_k$的样本个数,$\sum\limits_{k=1}^K|C_k|=|D|$。设特征$A$有$n$个不同的取值${a_1,a_2,\cdots,a_n}$,根据特征$A$的取值将$D$划分为$n$子集$D_1,D_2,\cdots,D_n$,$|D_i|$为$D_i$的样本个数,$\sum\limits_{i=1}^n |D_i|=|D|$。记子集$D_i$中属于类$C_k$的样本的集合为$D_{ik}$,即$D_{ik}=D_i \cap C_k$,$|D_{ik}|$为$D_{ik}$的样本个数。于是信息增益的算法如下:

算法3.1 (信息增益的算法)
 输入:训练数据集$D$和特征$A$;
 输出:特征$A$对训练数据集$D$的信息增益$g(D,A)$。

  1. 计算数据集$D$的经验熵$H(D)$

  2. 计算特征 对数据集 的经验条件熵

  3. 计算信息增益

3.3 ID3算法

  ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征,递归地构建决策树。具体方法是:从根结点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立子结点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树,ID3相当于用极大似然法进行概率模型的选择。
算法3.2 (ID3算法)
 输入:训练数据集$D$,特征集$A$,阈值$\epsilon$;
 输出:决策树$T$。

  1. 若$D$中所有实例属于同一类$C_k$,则$T$为单结点树,并将类$C_k$作为该结点的类标记,返回$T$;
  2. 若$A=\emptyset$,则$T$为单结点树,并将$D$中实例数最大的类$C_k$作为该结点的类标记,返回$T$;
  3. 否则,按算法3.1计算$A$中各特征对$D$的信息增益,选择信息增益最大的特征$A_g$;
  4. 如果$A_g$的信息增益小于阈值$\epsilon$,则置$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$为训练集,以为特征集,递归地调用步骤1-5,得到子树$T_i$,返回$T_i$。
    注意这里离散属性被选择后后面就不会再被选择

3.4 ID3算法的不足

  ID3算法虽然提出了新思路,但是还是有很多值得改进的地方。

  • ID3没有考虑连续特征,比如长度,密度都是连续值,无法在ID3运用,这大大限制了ID3的用途;
  • ID3采用信息增益大的特征优先建立决策树的结点。很快就被人发现,在相同条件下,取值比较多的特征比取值少的特征信息增益大。我认为可以从两个方面考虑,一是取值多导致数据集$D$类别分散,熵值大,二是取值多导致每个子集数据类别更加纯,例如对于ID类特征,每个子集肯定只有一个类别,熵为零。总的来说就是类别更多条件熵更小。两者综合导致信息增益大。
  • ID3算法对于缺失值的情况没有做考虑;
  • ID3没有考虑过拟合的问题。

4. 决策树C4.5算法

4.1 C4.5算法改进

  上一节讲到ID3算法有四个主要的不同,昆兰在C4.5算法中改进了上述4个问题。
  对于第一个问题,不能处理连续特征,C4.5的思路是将连续的特征离散化。比如$m$个样本的连续特征$A$有$m$个,从小到大排列为$a_1,a_2,\cdots,a_m$,则C4.5取相邻两样本值的平均数,一共取得$m-1$个切分点,其中第$i$个切分点$T_i$表示为:$T_i=\frac{a_i+a_{i+1}}{2}$。对于这$m-1$个点,分别计算以该点作为二分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为$a_t$,则小于$a_t$的值为类别1,大于$a_t$的值为类别2,这样就做到了连续特征的离散化。要注意的是,与离散属性不同的是,如果当前结点为连续属性,则该属性后面还可以参与子结点的特征选择过程
  对于第二个问题,信息增益作为标准容易偏向取值较多的特征的问题。引入了信息增益比(information gain ratio)。使用信息增益比可以对这一问题进行校正。
  定义4.1 (信息增益比): 特征$A$对数据集$D$的信息增益比$g_R(D,A)$定义为其信息增益$g(D,A)$与训练数据集$D$关于特征$A$的值的特征熵$H_A(D)$之比,即:

  其中,特征熵$H_A(D)=-\sum\limits_{i=1}^n \frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|}$,$n$为特征$A$取值的个数。
  特征数越多的特征对应的特征熵越大,它作为分母,可以校正信息增益容易偏向于取值较多的特征的问题。
  这里需要注意,信息增益比对可取值较少的特征有所偏好,因此C4.5不是直接用信息增益比最大的特征进行划分,而是使用一个启发式方法:先从候选划分特征中找到信息增益高于平均值的特征,再从中选择信息增益比最高的。
  对于第三个问题缺失值处理的问题,主要解决的是两个问题:

  • 一是样本某些特征缺失的情况下选择划分的属性;
  • 二是选定了划分属性,对于在该特征上缺失特征的样本的处理。

  对于第一个子问题,对于某一个有缺失特征值的特征$A$。C4.5的思路是将数据分成两部分,对每个样本设置一个权重(初始可以都为1),然后划分数据,一部分是有特征值$A$的数据$D_1$,另一部分是没有特征$A$的数据$D_2$。计算$D_1$的信息增益比,然后乘上一个系数,这个系数是$D_1$中样本加权后所占加权总样本的比例。
  对于第二个问题,可以将缺失特征的样本同时划分入所有的子结点,不过将该样本的权重按各个子结点样本的数量比例来分配。比如缺失特征$A$的样本a之前权重为1,特征$A$有3个特征值$A_1,A_2,A_3$。3个特征值对应的无缺失$A$特征的样本个数为2,3,4。则a同时划分入$A_1,A_2,A_3$。对应权重调节为2/9,3/9,4/9。

  对于第四个问题,C4.5引入了正则化系数进行初步的剪枝。C4.5采用的悲观剪枝方法,用递归的方式从下往上针对每一个非叶结点,评估用一个最佳叶结点去代替这棵子树是否有益。如果有益,则这棵子树就可以被替换掉。C4.5在训练数据集上进行测试。
  后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。但同时其训练时间会大得多。

4.2 C4.5算法不足

  C4.5算法虽然改进了ID3算法的几个主要问题,但仍然有优化的空间。

  • C4.5的剪枝方法有优化的空间;
  • C4.5生成的是多叉树,如果采用二叉树,可以提高效率;
  • C4.5只能用于分类;
  • C4.5使用了熵模型,里面有大量耗时的对数运算;
  • C4.5在构造树的过程中,对数值属性需要按照其大小进行排序,从中选择一个分割点,所以只适合能够驻留与内存的数据集,但训练集大得无法在内存容纳时,程序无法运行。

  这几个问题在CART树里面部分加以了改进。

5. CART树

  CART(Classification and Regression Tree)树既可以做分类,也可以做回归。这里先从CART分类树算法开始,重点比较和C4.5算法的不同点。接着介绍CART回归树算法,重点介绍和CART分类树的不同点。然后讨论CART树的建树算法和剪枝算法。

5.1 CART分类树特征选择方法

  在ID3中使用信息增益选择特征,在C4.5算法中,采用信息增益比选择特征。无论是ID3还是C4.5都是基于信息论的熵模型,这里面会涉及大量耗时的对数运算。CART分类树使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。
  定义4.1 (基尼系数):分类问题中,假设有$K$个类,样本点属于第$k$个类的概率为$p_k$,则概率分布的基尼指数定义为:

  对于二类分类问题,若样本点属于第1个类的概率是$p$,则概率分布的基尼系数为

  对于给定的样本$D$,假设有$K$个类别,第$k$个类别的数量为$C_k$,则样本$D$的基尼系数为:

  特别的,对于样本$D$,如果根据特征$A$的某个值a,把$D$分成$D_1$和$D_2$两部分,则在特征$A$的条件下,$D$的基尼系数为:

  下图显示二类分类问题中基尼系数$Gini(p)$、熵(单位比特)之半$\frac{1}{2}H(p)$和分类误差率的关系,横坐标表示概率$p$,纵坐标表示损失,可以看出基尼系数和熵之半的曲线很接近。

5.1

  那么基尼系数和熵之半差距有多大?
  根据泰勒公式有对数$\ln (x)$在$\frac{1}{2}$处展开为:

  所以

  并且熵之半严格大于基尼系数。因此基尼系数可以作为熵模型的一个近似替代。
  误差率可以理解为二分类问题中取一类的概率为$p$,取另一类的概率为$1-p$,所以$p$越接近0.5,误差率越大,同时$p$从0.5增大或者减小时,取某一类的概率增大,误差率减小。
  CART分类树每次仅仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。这样一可以简化基尼系数的计算,二可以建立一个更加优雅的二叉树模型。

5.2 CART分类树对于连续特征和离散特征的处理

  CART分类树对于连续值的处理思想和C4.5是相同的,都是将连续的特征离散化。唯一的区别在于选择划分点时的度量方式不同,C4.5使用的是信息增益比,CART分类树使用的是基尼系数。
  具体的思路如下,比如$m$个样本的连续特征$A$有$m$个,从小到大排列为$a_1,a_2,\cdots,a_m$,则CART算法取相邻两样本值的平均数,一共取得$m-1$个划分点,其中第$i$个划分点$T_i$表示为:$T_i=\frac{a_i+a_{i+1}}{2}$。对于这$m-1$个点,分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为$a_t$,则小于$a_t$的值为类别1,大于$a_t$的值为类别2,这样我们就做到了连续特征的离散化。要注意的是,如果当前节点为连续属性,则该属性后面还可以参与子节点的特征选择过程
  CART分类树对于离散值的处理采用的思路是不停的二分离散特征。
  在ID3或者C4.5中,如果某个特征$A$被选取建立决策树结点,如果它有$A_1,A_2,A_3$三种类别,会在决策树建立一个三叉的结点。这样导致的决策树是多叉树。但是CART分类树使用的方法不同,它才用的方法是不停的二分,在这个例子中,CART分类树会考虑把$A$分成${A_1}$和${A_2,A_3}$,${A_2}$和${A_1,A_3}$,${A_3}$和${A_1,A_2}$三种情况,找到基尼系数最小的组合,比如${A_2}$和${A_1,A_3}$,建立二叉树结点。同时,由于这次没有把特征$A$的取值完全分开,后面还有机会在子结点继续选择到特征$A$来划分${A_1,A_3}$,这和ID3、C4.5算法不同,在ID3、C4.5的一棵子树中,离散特征只会参与一次结点的建立

5.3 CART分类树算法

算法5.1 (CART分类树算法)
 输入:训练数据集$D$,基尼系数的阈值,样本个数的阈值;
 输出:决策树$T$。
 从根结点开始,用训练集递归的建立CART分类树。

  1. 对于当前结点的数据集$D_i$,如果样本个数小于阈值或者没有特征,则返回决策树子树$T_i$,当前结点停止递归;
  2. 计算样本集$D_i$的基尼系数,如果基尼系数小于阈值,则返回决策树子树$T_i$,当前结点停止递归;
  3. 计算当前结点现有的各个特征的各个特征值对数据集$D_i$的基尼系数,对于离散值和连续值的处理方法和基尼系数的计算见上面两节。缺失值的处理方法和C4.5中相同。
  4. 在计算出来的各个特征的各个特征值对数据集$D_i$的基尼系数中,选择基尼系数最小的特征$A$和对应的特征值$a$。根据这个最优特征和最优特征值,把数据集划分成两部分$D_1$和$D_2$,同时建立当前结点的左右子结点,左子结点的数据集为$D_1$,右子结点的数据集为$D_2$;
  5. 对左右子结点递归调用1-4步,生成决策树。

  对于生成的决策树做预测的时候,假如测试集中的样本$A$落到某个叶子结点,而结点里有多个训练样本,则对于$A$的类别预测采用的是这个叶结点里概率最大的类别。

5.4 CART回归树算法

  CART回归树算法和CART分类树算法的建立算法大部分类似,这里只讨论CART回归树和CART分类树的建立不同的地方。
  CART回归树和CART分类树的建立和预测的区别主要有下面两点:

  1. 连续值的处理方法不同;
  2. 决策树建立后做预测的方式不同。

  对于连续值的处理,CART分类树采用基尼系数的大小度量特征的各个划分点的优劣情况。这比较适合分类模型,但是对于回归模型,使用常见的均方差度量方式,CART回归树的度量目标是,对于任意划分特征,对应的任意划分点$s$两边划分成的数据集$D_1$和$D_2$,求出使$D_1$和$D_2$各自集合的均方差最小,同时$D_1$和$D_2$的均方差之和最小所对应的特征和特征值划分点。表达式为:

  求解

  其中,$c_1$为数据集$D_1(A,s)$中样本的输出平均值,$c_2$为数据集$D_2(A,s)$中样本的输出平均值。
  对于回归决策树建立后做预测的方式,上面讲到了CART分类树采用叶结点里概率最大的类别作为当前结点的预测类别。而回归树输出不是类别,它采用的是用最终叶结点中输出的均值或中位数来预测输出结果。

5.5 CART树算法的剪枝

  CART回归树和CART分类树除了在度量损失的时候一个使用均方差,一个使用基尼系数,算法基本完全一样,这里合在一起讲。
  CART采用的是后剪枝法,即先生成决策树,然后产生所有可能的剪枝后的CART树,然后使用交叉验证来检验各种剪枝的效果,选择泛化能力最好的剪枝策略。

  1. 剪枝,形成一个子树序列 在剪枝过程中,计算子树的损失函数:

  其中,$T$为任意子树,$C(T)$为对训练数据的预测误差(如基尼系数),$|T|$为子树的叶结点的个数,$\alpha \ge 0$为参数,$C_{\alpha}(T)$为参数是$\alpha$时的子树$T$的整体损失。参数$\alpha$权衡训练数据的拟合程度与模型的复杂度。
  对固定的$\alpha$,一定存在使损失函数$C_{\alpha}(T)$最小的子树,将其表示为$T_{\alpha}$。$T_{\alpha}$在损失函数$C_{\alpha}(T)$最小的意义下是最优的。当$\alpha$大的时候,最优子树$T_{\alpha}$偏小;当$\alpha$小的时候,最优子树$T_{\alpha}$偏大。极端情况,当$\alpha=0$时,整体树是最优的,当$\alpha \rightarrow \infty$时,根结点组成的单结点树是最优的。
  Breiman等人证明:可以用递归的方法对树进行剪枝。将$\alpha$从小增大,$0 \lt \alpha_1 \lt \cdots \lt \alpha_n \lt \infty$,产生一系列区间$[\alpha_i, \alpha_{i+1}), i=0,1,\cdots, n$;剪枝得到的子树序列对应着区间$\alpha \in [\alpha_i, \alpha_{i+1}),i=0,1,\cdots,n$的最优子树序列,序列中的子树是嵌套的。
  具体地,从整体树$T_0$开始剪枝。对$T_0$的任意内部结点$t$,以$t$为单结点树的损失函数是

  以$t$为根结点的子树$T_t$的损失函数是

  当$\alpha=0$及$\alpha$充分小时,有不等式

  当$\alpha$增大时,在某一$\alpha$有

  当$\alpha$再增大时,不等式反向。只要$\alpha=\frac{C(t)-C(T_t)}{|T_t|-1}$,$T_t$与$t$有相同的损失函数值,而$t$的结点少,因此$t$比$T_t$更可取,对$T_t$进行剪枝。
  为此,对$T_0$中每一内部结点$t$,计算

  它表示剪枝后整体损失函数减少的程度。在$T_0$中剪去$g(t)$最小的$T_t$,将得到的子树作为$T_1$,同时将最小的$g(t)$设为$\alpha_1$。$T_1$为区间$[\alpha_1, \alpha_2)$的最优子树。
  如此剪枝下去,直至得到根结点。在这一过程中,不断地增加$\alpha$的值,产生新的区间。

  1. 在剪枝得到的子树序列$T_0, T_1,\cdots,T_n$中通过交叉验证选择最优子树$T_{\alpha}$

  具体地,利用独立的验证数据集,测试子树序列$T_0,T_1,\cdots,T_n$中各棵子树的平方误差或基尼系数。平方误差或基尼系数最小的决策树被认为是最优的决策树。在子树序列中,每棵子树$T_1,T_2,\cdots,T_n$都对应于一个参数$\alpha_1,\alpha_2,\cdots,\alpha_n$。所以,当最优子树$T_k$确定时,对应的$\alpha_k$也确定了,即得到最优决策树$T_{\alpha}$。

算法5.2 (CART剪枝算法)
 输入:CART算法生成的决策树$T_0$;
 输出:最优决策树$T_{\alpha}$。

  1. 设$k=0,T=T_0$;
  2. 设$\alpha=+\infty$;
  3. 自下而上地对内部结点$t$计算$C(T_t)$, 以及

  这里, 表示以 为根结点的子树, 是对训练数据的预测误差, 是$T_t$的叶结点个数。

  1. 从上而下的访问内部结点$t$,如果$g(t)\le \alpha$,进行剪枝。并决定叶结点的值。如果是分类树,则是概率高的类别,如果是回归树,则是所有样本输出的均值。得到树$T$;
  2. 设$k=k+1,\ \alpha_k=\alpha,\ T_k=T$;
  3. 如果$T_k$不是由根结点及两个叶结点构成的树,则回到步骤2;否则令$T_k=T_n$;
  4. 采用交叉验证法在子树序列$T_0,T_1,T_2,\cdots,T_n$中选取最优子树$T_{\alpha}$。

  注意,这里我认为剪枝后下次迭代时应该剪去$g(t)$最小的内部结点对应的子树,直到只剩根结点和两个叶结点。所以在第6步返回时是返回第2步,而不是李航统计学习方法中的第3步。这也和scikit-learn实现一致,给定ccp-alpha参数,剪枝直到最小$g(t)$大于ccp-alpha时停止

5.6 类别不平衡

  CART 的一大优势在于:无论训练数据集有多失衡,它都可以将其自动消除不需要建模人员采取其他操作。
  CART使用了一种先验机制,其作用相当于对类别进行加权。这种先验机制嵌入于CART算法判断分裂优劣的运算里,在CART默认的分类模式中,总是要计算每个节点关于根节点的类别频率的比值,这就相当于对数据自动重加权,对类别进行均衡。
  对于一个二分类问题,结点被分成类别1当且仅当:

  比如二分类,根结点属于 1 类和 0 类的分别有 20 和 80 个。在子结点上有 30 个样本,其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80,该结点就属于 1 类。
  通过这种计算方式就无需管理数据真实的类别分布。假设有 K 个目标类别,就可以确保根结点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。

5.7 CART树算法小结

  CART树和ID3,C4.5决策树算法对比如下表所示:

算法 支持模型 树结构 特征选择 连续值处理 缺失值处理
ID3 分类 多叉树 信息增益 不支持 不支持
C4.5 分类 多叉树 信息增益比 支持 支持
CART 分类,回归 二叉树 基尼系数,均方差 支持 支持

  CART算法的缺点:

  • ID3,C4.5,CART在做特征选择是都是选择最优的一个特征来做分类决策。但大多数分类决策不应是有某一个特征决定的,而是应该有一组特征决定,即聚合特征。这样的决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候,多变量决策树不是选择某一个最优特征,而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1。
  • 如果样本发生一点点改动,就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

6. 决策树算法小结

决策树算法优点:

  • 简单直观,生成的决策树很直观;
  • 基本不需要预处理,不需要提前归一化,处理缺失值,因为信息增益,信息增益比,基尼系数都是基于分布的,和值大小无关;
  • 使用决策树预测的代价是$O(\log_2m)$,$m$为样本数;
  • 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值;
  • 可以处理多维度输出的分类问题;
  • 相比于神经网络之类的黑盒分类模型,决策树在逻辑上可以得到很好的解释;
  • 可以交叉验证的剪枝来选择模型,从而提高泛化能力;
  • 对于异常点的容错能力好,健壮性高,因为连续值是以大于小于划分的。

决策树算法缺点:

  • 决策树算法非常容易过拟合,导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进;
  • 决策树会因为样本发生一点点的改动,就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决;
  • 寻找最优的决策树是一个NP难的问题,我们一般是通过启发式方法,容易陷入局部最优。可以通过集成学习之类的方法来改善;
  • 有些比较复杂的关系,决策树很难学习,比如异或。这个就没有办法了,一般这种关系可以换神经网络分类方法来解决;
  • 如果某些特征的样本比例过大,生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

7. Reference

1 决策树算法原理(上)-刘建平
2 决策树算法原理(下)-刘建平
3 决策树
4. sklearn-decison tree
5 统计学习方法第五章-李航