决策树算法梳理

Posted on In Views: Disqus:
DataWhale暑期学习小组-初级算法梳理第八期Task3。

这个暑假参加了DataWhale暑期学习-高级算法梳理的第八期，在整个学习的过程当中发现，无论之前看过多少次视频，翻过几遍书，对于知识的系统理解都不如自己好好梳理、推导并用文字把它记下来那么有效果。因此，虽然这一期并没有参加初级算法（线性回归、决策树、逻辑回归等）梳理的学习，但是一直有这个念想等得空的时候也把这些算法一起梳理一遍，加深理解。特别是决策树和逻辑回归，前者是后面bagging和boosting等各种集成算法的主要基学习器，后者在神经网络以及基于神经网络的各种深度学习算法发挥重要的基础作用，特别是各种优化算法，梯度下降、牛顿法等等，这些都是相通的。

本篇主要对决策树进行梳理。

决策树算法的思想其实非常古老，我们可以将决策树看出一个if-then规则的集合，问题的关键是在面对很多条件特征的时候，用哪个条件特征先做if，哪个条件特征后做，各个特征条件的阈值如何确定。这些都是决策树机器学习算法的关键。

上世纪70年代，昆兰用信息论的熵来度量决策树的决策选择过程，它的简洁和高效立刻掀起了决策树研究的热潮，从最初的ID3，到后面昆兰持续优化的C4.0、C4.5，以及可用于回归的CART树，不断地被研究者提出。从决策树算法的发展历程来看，我们需要从信息论入手。

信息论基础

熵

熵（Entropy）起初是热力学中的概念，对，热力学就是本人的老本行，最早由德国物理学家克劳修斯于1865年提出。在热力学当中，熵是一种测量在动力学方面不能做功的能量总数，也就是当总体的熵增加，其做功能力也下降，熵的量度正是能量退化的指标。熵亦被用于计算一个系统中的失序现象，也就是计算该系统混乱的程度，系统越无序，熵越大。

香农大神在1948年将熵引入到信息论，用来表示接收的每条消息中包含的信息的平均量，“消息”代表来自分布或者数据流中的事件、样本或者特征。我们可以将熵理解为不确定性的度量，因为越随机的信号源，熵越大。

为了和玻尔兹曼熵公式形式上面的一致，香农将信息熵定义如下：

H(X)=E[I(X)]=E[−log⁡(P(X))]=E[log⁡1P(X)]H(X)=E[I(X)]=E[-\log(P(X))]=E[\log{\frac{1}{P(X)}}]

实际上，熵是随机变量XX的函数log⁡1P(X)\log{\frac{1}{P(X)}}的期望。

如果XX是一个取有限个值的离散随机变量，其概率分布为：

P(X=xi)=pi,  i=1,2,...,nP(X=x_i)=p_i,\,\, i=1,2,...,n

则随机变量XX的熵的定义为：

H(X)=−∑i=1npilog⁡piH(X)=-\sum_{i=1}^np_i\log p_i

如果pi=0p_i=0，则定义0log⁡0=00 \log 0=0，这与极限也是一致的。

联合熵

联合熵是针对联合分布概率的，用来度量一个联合分布的随机系统的不确定度，其物理意义是观察一个多个随机变量的随机系统获得的信息量。下面给出两个随机变量的联合熵的定义：

H(X,Y)=−∑x∈X∑y∈YP(x,y)log⁡P(x,y)=E[log⁡1P(X,Y)]H(X,Y)=-\sum_{x \in X}\sum_{y \in Y}P(x,y)\log P(x,y)=E[\log{\frac{1}{P(X,Y)}}]

条件熵

条件熵H(Y∣X)H(Y|X)表示已知随机变量XX的条件下，随机变量YY的信息熵还有多少。随机变量XX给定的条件下随机变量YY的条件熵H(Y∣X)H(Y|X)，定义为XX给定条件下YY的条件概率分布的熵对XX的数学期望：

H(Y∣X)=∑i=1npiH(Y∣X=xi)H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)

进一步化简有：

当且仅当YY的值完全由XX确定时，H(Y∣X)=0H(Y|X)=0。相反，当且仅当YY 和XX 为独立随机变量时 H(Y∣X)=H(Y)H(Y|X)=H(Y)。

链式法制

假设两个随机变量 XX 和 确定的组合系统的联合熵为 H(X,Y)H(X,Y)，即我们需要H(X,Y)H(X,Y) bits的信息来描述它的确切状态。

现在，若我们先学习 的值，我们得到H(X)H(X) bits的信息。 一旦知道了 $H ，我们只需，我们只需 H(X,Y)-H(X)$ bits来描述整个系统的状态。

这个量正是条件熵H(Y∣X)H(Y|X)，它给出了条件熵的链式法则：

H(Y∣X)=H(X,Y)−H(X)H(Y|X)=H(X,Y)-H(X)

可以根据以上联合熵、条件熵、信息熵的定义进行推导如下：

信息增益

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

信息增益（information gain）表示得知特征XX的信息而使得类YY的信息的不确定性减少的程度，具体定义如下：

特征AA对训练数据集的信息增益g(D,A)g(D,A)，定义为集合DD的经验熵H(D)H(D)与特征AA给定条件下DD的经验条件熵H(D∣A)H(D|A)子差，即：

g(D,A)=H(D)−H(D∣A)g(D,A)=H(D)-H(D|A)

一般的，熵H(Y)H(Y)与条件熵H(Y∣X)H(Y|X)之差也被称为互信息（mutual information），I(X,Y)I(X,Y)。

上面的概念较多，用下面这个图很容易明白他们的关系。左边的圆代表H(X)H(X)，右边的圆代表H(Y)H(Y)，中间重合的部分就是我们的互信息或者信息增益I(X,Y)I(X,Y)，左边的圆去掉重合部分就是H(X∣Y)H(X|Y)，右边的圆去掉重合部分就是H(Y∣X)H(Y|X)。两个圆的并就是H(X,Y)H(X,Y)。

示意图

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题，因为取值较多的特征在分类的时候可以分得更细，叶子节点更多，信息增益也越大。通常我们会使用信息增益比（information gain ratio）对这个问题进行校正。

信息增益比的定义如下：

特征AA对训练数据集的信息增益比gR(D,A)g_R(D,A)定义为其信息增益g(D,A)g(D,A)与训练数据集DD关于特征AA的值的HA(D)H_A(D)之比，即：

gR(D,A)=g(D,A)HA(D)g_R(D,A)=\frac{g(D,A)}{H_A(D)}

其中，HA(D)=−∑i=1n∣Di∣∣D∣log⁡∣Di∣∣D∣H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log {\frac{|D_i|}{|D|}}，n 是特征 AA 取值的个数，DiD_i为特征AA的第 ii 个取值对应的样本个数，∣D∣|D|为样本个数。

基尼不纯度

如果我们将信息熵换一种方式进行描述如下：

H(X)=−∑x∈Xp(x)log⁡p(x)H(X)=-\sum_{x \in X}p(x) \log p(x)

对上式中的log⁡p(x)\log p(x)进行泰勒展开，因为p小于1，忽略高阶项，就能够得到基尼不纯度（gini inpurity）的公式：

Gini(X)=∑x∈Xp(x)(1−p(x))Gini(X)=\sum_{x \in X}p(x)(1-p(x))

所以，本质上，基尼不纯度是熵的一个近似值，含义和熵差不多，可以衡量不确定性的大小，可以衡量杂乱程度也就是不纯度。

对于基尼不纯度换一个表述方式，在分类问题中，假设有KK个类，样点属于第kk类的概率为pkp_k，则概率分布的基尼不纯度可表示为：

Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2Gini(p)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^K p_k^2

上式的推导当中用到了一个性质：∑k=1Kpk=1\sum_{k=1}^K p_k=1

特别的，如果是二分类问题，若样本点属于第1个类的概率为pp，则属于第2个类的概率为1−p1-p，此时概率分布的基尼不纯度为：

Gini(P)=p(1−p)+(1−p)p=2p(1−p)Gini(P)=p(1-p)+(1-p)p=2p(1-p)

对于给定的样本集合DD，其基尼不纯度为：

Gini(D)=1−∑k=1K(∣Ck∣∣D∣)2Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2

其中，CkC_k是 DD 中属于第kk类的样本子集，KK是类的个数。

如果样本集合DD根据特征AA是否取某一个可能值被分割成两个子集D1D_1和 D2D_2，则在特征AA的条件下，集合DD的条件基尼不纯度定义为：

Gini(D,A)=∣D1∣∣D∣Gini(D1)+∣D2∣∣D∣Gini(D2)Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)

基尼不纯度Gini(D)Gini(D)表示集合DD的不确定性，条件基尼不纯度Gini(D,A)Gini(D,A)表示在特征AA的分类已知的情况下DD的不确定性。

ID3算法

原理

ID3算法采用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。

这里举一个信息增益计算的具体例子，有15个样本DD，输出为0或者1。其中9个输出为1，6个输出为0。样本当中有个特征AA，取值分别为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中，2个输出为1，3个输出为0，在取值为A3的样本中，4个输出为1，1个输出为0。

样本DD的经验熵为:

H(D)=−(915log⁡915+615log⁡615)H(D)=-(\frac{9}{15}\log{\frac{9}{15}}+\frac{6}{15}\log{\frac{6}{15}})

样本DD在特征AA下面的经验条件熵为:

对应的信息增益为:

g(D,A)=H(D)−H(D∣A)=0.971−0.888=0.083g(D,A)=H(D)-H(D|A)=0.971-0.888=0.083

具体的算法流程如下:

输入得是mm个样本, 样本输出集合为DD, 每个样本有nn个特征, 特征集合为AA, 输出为决策树TT, 通常用"分而治之"的递归思路来构建决策树.

    1. 初始化信息增益的阈值ϵ\epsilon
    1. 判断样本是否为同一类输出DiD_i，如果是则返回单节点树TT。标记类别为DiD_i
    1. 判断特征是否为空或者样本DD在特征AA上面取值相同, 如果任意一个条件满足, 则返回TT, 并标记类别为样本中输出类别DD样本数最多的类别
    1. 计算AA中各个特征对输出DD的信息增益, 选择信息增益最大的特征AgA_g
    1. 如果AgA_g的信息增益小于阈值ϵ\epsilon, 则返回单节点树TT, 并标记类别为样本中输出类别DD样本数最多的类别
    1. 如果AgA_g的信息增益大于阈值ϵ\epsilon, 按特征AgA_g的不同取值AgiA_{gi}将对应的样本输出DD分成不同得类别DiD_i, 每个类别产生一个子节点, 对应的特征值为AgiA_{gi}, 返回增加了节点的树TT
    1. 对于所有的子节点, 令D=Di,A=A−{Ag}D=D_i,A=A-\{A_g\}, 然后递归调用2~6步, 得到并返回子树TiT_i

应用场景和不足

ID3算法可用于划分离散型数据集, 没有剪枝的过程, 为了预防过拟合, 可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。

可见, ID3算法的应用场景有限, 也存在许多优化的空间, 主要有以下几点:

  • ID3没有考虑连续特征，比如长度、密度等连续值，无法在ID3中运用，这大大限制了ID3的用途
  • ID3采用信息增益大的特征优先建立决策树的节点，但是，在相同条件下，取值较多的特征比取值较少的特征信息增益大，信息增益准则对可取值数较多的特征有所偏好，这个问题需要校正
  • ID3算法无法对缺失值进行处理
  • 最后，也没有考虑过过拟合的问题

ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢？那是因为决策树太火爆，他的ID3一出来，别人二次创新，很快 就占了ID4、ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。下面我们介绍下C4.5算法。

C4.5算法

原理

C4.5算法主要是基于ID3算法的不足进行针对性的优化，我们结合上面提到的ID3的不足，逐一讨论C4.5的优化之处。

连续特征处理

对于这个问题，C4.5的思路是将连续的特征离散化。比如mm个样本的连续特征AA有 mm 个，从小到大排列为a1,a2,...,ama_1,a_2,...,a_m，C4.5取相邻两个样本值的平均值，一共可以取到m−1m-1个划分点，其中第ii个划分点TiT_i表示为：

Ti=ai+ai+12T_i=\frac{a_i+a_{i+1}}{2}

对于这m−1m-1个点，分别计算以该点作为二元分类点时的信息增益比。选择信息增益比最大的点作为该连续特征的二元离散分散点。比如取到的信息增益比最大的点为ata_t，则小于ata_t的值为类别0，大于ata_t的值为类别1。这样就完成了连续特征的离散化。

需要注意的是，与离散特征不同的是，如果当前节点为连续特征，根据离散化的过程，则这个特征后续还可以参与子节点的产生选择过程。

信息增益准则校正

对于这个问题，C4.5算法使用了前面提到的信息增益比作为特征选择的准则。需要注意的是，信息增益比准则对于可取数较少的特征有所偏好，这个与信息增益正好相反。为了避免走向另外一个极端，C4.5算法并不是直接选择信息增益比最大的候选特征，而是使用了一个启发式：先从候选特征中找出信息增益比高于平均水平的特征，再从这个子候选特征集当中选择信息增益比最高的特征。

这里举一个信息增益比计算的具体例子，有15个样本DD，输出为0或者1。其中9个输出为1，6个输出为0。样本当中有个特征AA，取值分别为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中，2个输出为1，3个输出为0，在取值为A3的样本中，4个输出为1，1个输出为0。

样本DD的经验熵为:

H(D)=−(915log⁡915+615log⁡615)H(D)=-(\frac{9}{15}\log{\frac{9}{15}}+\frac{6}{15}\log{\frac{6}{15}})

样本DD在特征AA下面的经验条件熵为:

对应的信息增益为:

g(D,A)=H(D)−H(D∣A)=0.971−0.888=0.083g(D,A)=H(D)-H(D|A)=0.971-0.888=0.083

再由HA(D)=−∑i=1n∣Di∣∣D∣log⁡∣Di∣∣D∣H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log {\frac{|D_i|}{|D|}}，n 是特征 AA 取值的个数，DiD_i为特征AA的第 ii 个取值对应的样本个数，∣D∣|D|为样本个数，可得：

对应的 信息增益比为：

gR(D,A)=g(D,A)HA(D)=0.083/1.0986=0.0756g_R(D,A)=\frac{g(D,A)}{H_A(D)}=0.083/1.0986=0.0756

缺失值处理

对于缺失值处理的问题，主要解决以下两个问题：

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

对于第一个问题，C4.5算法的思路是将有缺失值的特征AA的数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值AA的数据集D1D_1，另外一部分是没有特征AA的数据集D2D_2。然后对于没有缺失特征AA的 数据集D1D_1来和对应的AA特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征AA缺失的样本加权后所占加权总样本的比例。

对于第二个问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征AA的样本DaD_a之前权重为1，特征AA有3个特征值A1,A2,A3A_1,A_2,A_3。 3个特征值对应的无缺失AA特征的样本个数为2、3、4。则DaD_a同时划分入A1，A2，A3A_1，A_2，A_3。对应权重调节为29,39,49\frac{2}{9}, \frac{3}{9}, \frac{4}{9}。

过拟合问题

C4.5引入了正则化系统进行初步的剪枝，对于决策树的剪枝，后面会专题进行讨论。

算法流程

除了以上4点，C4.5算法与ID3算法类似，主要流程如下：

输入得是mm个样本, 样本输出集合为DD, 每个样本有nn个特征, 特征集合为AA, 输出为决策树TT, 通常用"分而治之"的递归思路来构建决策树.

    1. 初始化信息增益的阈值ϵ\epsilon
    1. 判断样本是否为同一类输出DiD_i，如果是则返回单节点树TT。标记类别为DiD_i
    1. 判断特征是否为空或者样本DD在特征AA上面取值相同, 如果任意一个条件满足, 则返回TT, 并标记类别为样本中输出类别DD样本数最多的类别
    1. 计算AA中各个特征对输出DD的信息增益比, 选择信息增益比超出信息增益平均值的子集当中最大的特征AgA_g
    1. 如果AgA_g的信息增益比小于阈值ϵ\epsilon, 则返回单节点树TT, 并标记类别为样本中输出类别DD样本数最多的类别
    1. 如果AgA_g的信息增益比大于阈值ϵ\epsilon, 按特征AgA_g的不同取值AgiA_{gi}将对应的样本输出DD分成不同得类别DiD_i, 每个类别产生一个子节点, 对应的特征值为AgiA_{gi}, 返回增加了节点的树TT
    1. 对于所有的子节点, 令D=Di,A=A−{Ag}D=D_i,A=A-\{A_g\}, 然后递归调用2~6步, 得到并返回子树TiT_i

应用场景和不足

ID3算法可用于划分离散型或者连续型数据集, 为了预防过拟合, 可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值），也有剪枝的过程。但是依然有比较多的优化空间。主要有以下几点：

  • 决策树算法非常容易过拟合，虽然C4.5算法采用了剪枝的处理方式，但是它的剪枝方法有优化的空间
  • C4.5算法和ID3算法一样，生成的是多叉树，学过数据结构应该知道在计算机当中二叉树的运算效率更高
  • C4.5算法对ID3算法的优化依然没有改变只能应用于分类的事实，对于机器学习当中另外一大类任务回归却无能为力
  • C4.5算法的优化同样还是采用熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能对模型进行简化并采用一些通用的优化算法，一方面可以大大提高效率，同时另外一方面，又不牺牲太多准确性就更好了

CART算法

上面针对C4.5算法所提到的不足，由Breiman等人在1984年提出的分类与回归树（classification and regression tree，CART）模型进行了较为全面的改进和优化。

从算法的名字就可以看出CART算法即可以做分类，也可以做回归。下面先从CART分类树算法开始，重点比较和C4.5算法的不同点。接着介绍CART回归树算法，重点介绍和CART分类树的不同点。然后我们讨论CART树的建树算法和剪枝算法。

CART分类树

特征选择方法优化

为了绕过涉及大量对数计算的熵模型，CART分类树算法采用对信息熵进行泰勒展开后的近似的基尼不纯度作为特征选择的标准。基尼不纯度代表了模型的不纯度，基尼不纯度越小，则不纯度越低，特征越好。这和信息增益(比)是相反的。

比较下基尼不纯度表达式和熵模型的表达式，二次运算是不是比对数简单很多？尤其是二类分类的计算，更加简单。但是简单归简单，和熵模型的度量方式比，基尼系数对应的误差有多大呢？对于二类分类，基尼系数和熵之半的曲线如下：

Gini不纯度

从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大，这和泰勒展开以后被忽略后的高阶部分有关。但是这种精度的近似是可以接受的。

另外，CART算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。

特征处理优化

连续特征优化

CART算法对于连续特征的离散化的总体思路与C4.5算法是类似的，只是在对第m−1m-1个划分点进行处理时的分类准则不同，一脉相承地用基尼不纯度来代替C4.5算法的信息增益比。具体思路如下：

。比如mm个样本的连续特征AA有 mm 个，从小到大排列为a1,a2,...,ama_1,a_2,...,a_m，C4.5取相邻两个样本值的平均值，一共可以取到m−1m-1个划分点，其中第ii个划分点TiT_i表示为：

Ti=ai+ai+12T_i=\frac{a_i+a_{i+1}}{2}

对于这m−1m-1个点，分别计算以该点作为二元分类点时的基尼不纯度。选择基尼不纯度最小的点作为该连续特征的二元离散分散点。比如取到的基尼不纯度最小的点为ata_t，则小于ata_t的值为类别0，大于ata_t的值为类别1。这样就完成了连续特征的离散化。

需要注意的是，与ID3或者C4.5处理离散特征不同的是，如果当前节点为连续特征，根据离散化的过程，则这个特征后续还可以参与子节点的产生选择过程。

离散特征优化

对于离散特征的优化点就是在于用二叉树代替了多叉树，通过增加二叉树的深度来增加叶子节点，达到原来多叉树分类的目的。下面举个简单的例子：

回忆下ID3或者C4.5，如果某个特征AA被选取建立决策树节点，如果它有A1,A2,A3A_1,A_2,A_3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把AA分成{A1}和{A2,A3}\{A_1\}和\{A_2,A_3\}, {A2}和{A1,A3}\{A_2\} 和 \{A_1,A_3\}, {A3}和{A1,A2}\{A_3\}和\{A_1,A_2\}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3}\{A_2\}和\{A_1,A_3\}，然后建立二叉树节点，一个节点是A2A_2对应的样本，另一个节点是{A1,A3}\{A_1,A_3\}对应的节点。同时，由于这次没有把特征AA的取值完全分开，后面我们还有机会在子节点继续选择到特征AA来划分A1A_1和A3A_3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。

建树算法流程

  • 输入：训练集DD，基尼不纯度的阈值ϵ\epsilon，样本个数阈值nn
  • 输出：决策树TT
  • 算法从根节点开始，用训练集递归地建立CART分类树
    • 1）初始化基尼不纯度阈值ϵ\epsilon和样本个数阈值nn
    • 2）对于当前节点的数据集为DD，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归
    • 3）计算样本集DD的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归
    • 4）计算当前节点现有的各个特征的各个特征值对数据集DD的基尼不纯度
    • 5）在计算出来的各个特征的各个特征值对数据集DD的基尼不纯度中，选择基尼不纯度最小的特征AA和对应的特征值aa。根据这个最优特征和最优特征值，把数据集划分成两部分D1D_1和 D2D_2，同时建立当前节点的左右节点，做节点的数据集DD 为D1D_1，右节点的数据集DD为 D2D_2
    • 6）对左右的子节点递归的调用2-5步，生成决策树

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

CART回归树

回归树与分类树区别

首先，我们要明白什么是分类树，什么是回归树。两者的区别在于样本输出值的类型不同，如果样本输出值是离散型，那么这是一棵分类树；如果样本输出值是连续型，那么这是一棵回归树。

因此，分类或者回归本身的区别并不是太大。CART回归树和CART分类树的建立算法大体上也是类似的，主要有以下三点：

  • 特征选择方法不同
  • 连续值的处理方法不同
  • 决策树建立以后做预测的方式不同

首先，在分类树当中，对于特征的选择是基于基尼不纯度，对于连续型特征同样也是用基尼不纯度的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型，但是对于回归模型，我们使用了常见的平方误差∑xi∈D(yi−f(xi))2\sum_{x_i \in D}(y_i-f(x_i))^2的度量方式，来表示CART回归树相对于训练数据的预测误差。

对于给定的训练集D={(x1,y2),(x2,y2),...,(xn,yn)}D=\{(x_1,y_2),(x_2,y_2),...,(x_n,y_n)\}

一棵树模型对应着输入空间的一个划分以及在划分的单元上面对应的输出值。假设已经将输入空间划分为MM个单元R1,R2,...,RMR_1,R_2,...,R_M，并且每一个单元RmR_m上面对应一个固定的输出值cmc_m，于是回归树模型可以表示如下：

f(x)=∑m=1McmI(x∈Rm)f(x)=\sum_{m=1}^M c_m I(x \in R_m)

然后用平方误差最小的准则在划分输入空间时求解每个单元上面的最优输出值。令单元RmR_m上的cmc_m的最优值cm^\hat{c_m}是 RmR_m上面所有输入实例xix_i所对应的输出yiy_i的均值，表达式表示如下：

cm^=average(yi∣xi∈Rm)\hat{c_m}=average(y_i|x_i \in R_m)

这也是在CART回归树建立以后做预测方式与CART分类树不同的地方。上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子节点里面所包含所有实例的平均值或者中位数来预测输出结果，为了推导方便，后面还是暂用平均值。

在如何对输入空间进行划分上面，体现了CART回归树在特征选择和连续值处理方面与CART分类树的不同。

这里采用启发式的方法，选择第jj个特征x(j)x^{(j)}和它取的值ss，作为切分特征（splitting variable）和切分点（splitting point），并据此定义两个区域：

R1(j,s)={x∣x(j)⩽s},    R2(j,s)={x∣x(j)>s}R_1(j,s)=\{x|x^{(j)}\leqslant s\},\,\,\,\,R_2(j,s)=\{x|x^{(j)} > s\}

CART回归树的度量目标是，对于任意划分特征x(j)x^{(j)}，对应的任意划分点ss两边划分成的数据集R1R_1和 R2R_2，求出使R1R_1和 R2R_2各自集合的均方差最小，同时R1R_1和 R2R_2均方差之和最小所对应的特征和特征值划分点。表达式为：

arg⁡min⁡j,s[arg⁡min⁡c1∑xi∈R1(j,s)(yi−c1)2+arg⁡min⁡c2∑xi∈R2(j,s)(yi−c2)2]\mathop{\arg\min}_{j,s}\left[ \mathop{\arg\min}_{c_1}\sum_{x_i \in R_1(j,s)}(y_i-c_1)^2+\mathop{\arg\min}_{c_2}\sum_{x_i \in R_2(j,s)}(y_i-c_2)^2\right]

对于固定的输入特征jj可以找到最优切分点ss，此时：

c1^=average(yi∣xi∈R1(j,s))    c2^=average(yi∣xi∈R2(j,s))\hat{c_1}=average(y_i|x_i \in R_1(j,s))\,\,\,\,\hat{c_2}=average(y_i|x_i \in R_2(j,s))

遍历所有输入特征，找到最优的切分特征jj，构成一个最优切分特征和切分点对(j,s)(j,s)。依此将输入空间划分为两个 区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。

建树算法流程

下面对CART回归树的建树算法流程做一个梳理。

  • 输入：训练集DD，树的最大深度，叶子节点最小实例数等
  • 输出：回归树f(x)f(x)
  • 算法从根节点开始，在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树建立CART回归树
    • 1）选择最优切分特征jj和切分点ss，求解

    arg⁡min⁡j,s[arg⁡min⁡c1∑xi∈R1(j,s)(yi−c1)2+arg⁡min⁡c2∑xi∈R2(j,s)(yi−c2)2]\mathop{\arg\min}_{j,s}\lbrack \mathop{\arg\min}_{c_1}\sum_{x_i \in R_1(j,s)}(y_i-c_1)^2+\mathop{\arg\min}_{c_2}\sum_{x_i \in R_2(j,s)}(y_i-c_2)^2\rbrack

    • 2）用选定的最优切分特征和最优切分点对(j,s)(j,s)划分区域并确定相应子节点所含实例相应的输出值：

    R1(j,s)={x∣x(j)⩽s},    R2(j,s)={x∣x(j)>s}R_1(j,s)=\{x|x^{(j)}\leqslant s\},\,\,\,\,R_2(j,s)=\{x|x^{(j)} > s\}

    cm^=1Nm∑xi∈Rm(j,s)yi,   x∈Rm,   m=1,2\hat{c_m}=\frac{1}{N_m}\sum_{x_i \in R_m(j,s)}y_i, \,\,\, x \in R_m,\,\,\, m=1,2

    • 3）继续对划分出来的两个子区域调用1-2步，直到满足停止条件，停止条件可以是树的最大深度、叶子节点最小实例数等，可以提高树模型的泛化能力
    • 4）最后将输入空间划分为MM个区域R1,R2,...,RmR_1,R_2,...,R_m，生成回归决策树模型：

    f(x)=∑m=1Mcm^I(x∈Rm)f(x)=\sum_{m=1}^M\hat{c_m}I(x \in R_m)

CART剪枝

CART回归树和CART分类树的剪枝策略除了在度量损失的时候一个使用均方差，一个使用基尼不纯度，算法基本完全一样，这里我们一起来讲。

由于决策树算法很容易对训练集过拟合，而导致泛化能力差，为了解决这个问题，我们需要对CART树进行剪枝，即类似于线性回归的正则化，来增加决策树的泛化能力。

但是，剪枝方法很多，我们应该这么选择呢？CART采用的办法是后剪枝法，即先生成决策树，然后产生所有可能的剪枝后的CART树，然后使用交叉验证来检验各种剪枝的效果，选择泛化能力最好的剪枝策略。

也就是说，CART树的剪枝算法可以概括为两步，第一步是从原始决策树生成各种剪枝效果的决策树，第二部是用交叉验证来检验剪枝后的预测能力，选择泛化预测能力最好的剪枝后的数作为最终的CART树。

剪枝形成子树序列

在剪枝的过程当中，对于任意一棵子树TT，其损失函数的度量为：

Cα(Tt)=C(Tt)+α∣Tt∣C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|

其中，α\alpha为正则化参数，恒大于等于0，用来权衡训练数据的拟合程度与模型的复杂度，这和线性回归的正则化类似。C(Tt)C(T_t)为训练集的预测误差，分类树用的是基尼不纯度，回归树用的是均方差，∣Tt∣|T_t|是子树TT的叶子节点的数量。

对于固定的α\alpha，一定存在使损失函数Cα(T)C_{\alpha}(T)最小的子树TαT_\alpha，在损失函数Cα(T)C_{\alpha}(T) 最小的意义下，TαT_{\alpha}是最优的，而且容易证明，最优子树是唯一的。

当α=0\alpha=0时，即没有正则化，原始的生成的CART树即为最优子树。当α=∞\alpha=\infty时，即正则化强度达到最大，此时由原始的生成的CART树的根节点组成的单节点树为最优子树。当然，这是两种极端情况。一般来说，α\alpha越大，则剪枝剪的越厉害，生成的最优子树相比原生决策树就越偏小。

对于任意一棵位于节点tt的子树TtT_t，如果没有剪枝，它的损失为：

Cα(Tt)=C(Tt)+α∣Tt∣C_{\alpha}(T_t)=C(T_t)+\alpha|T_t|

如果将其剪掉，仅仅保留根节点，则损失为：

Cα(T)=C(T)+αC_{\alpha}(T)=C(T)+\alpha

当α=0\alpha=0或者α\alpha很小时，Cα(Tt)<Cα(T)C_{\alpha}(T_t)<C_{\alpha}(T)，当α\alpha增大到一定的程度时，有

Cα(Tt)=Cα(T)C_{\alpha}(T_t)=C_{\alpha}(T)

当α\alpha继续增大时不等式反向，也就是说，如果满足下式：

α=C(T)−C(Tt)∣Tt∣−1\alpha=\frac{C(T)-C(T_t)}{|T_t|-1}

TtT_t与 TT有相同的损失函数值，而TT的节点更少，更为可取，对TtT_t进行剪枝。

假设T0T_0为未剪枝前构建的完整的全树，对它的每一个内部节点tt，计算：

g(t)=C(t)−C(Tt)∣Tt∣−1g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}

用来表示剪枝后整体损失函数减少的程度。在T0T_0当中减去g(t)g(t)最小的TtT_t，将得到的子树作为T1T_1，同时将最小的g(t)g(t)设为α1\alpha_1。则在区间[α1,α2)[\alpha_1,\alpha_2) 上的最优子树为T1T_1。

如此剪枝下去，直至得到根结点，可以得到一个子树序列T0,T1,...,TnT_0,T_1,...,T_n。在这一过程中，不断地增加α\alpha的值，产生新的区间。

交叉验证确定最优子树

利用独立的验证数据集，测试子树序列T0,T1,...,TnT_0,T_1,...,T_n当中各棵子树的平方误差或者基尼不纯度。平方误差或者基尼不纯度最小的决策树被认为是最优的决策树。另外，在子树序列当中，每棵子树TT都对应一个参数α\alpha。所以，当最优子树TkT_k确定的时候，对应的αk\alpha_k也就确定了。

剪枝算法流程

  • 输入：CART算法生产的决策树T0T_0
  • 输出：最优决策树TαT_{\alpha}
  • 算法从不断遍历原树的各个节点开始
    • 1）设k=0,  T=T0k=0,\,\,T=T_0
    • 2）初始化αmin=∞\alpha_{min}=\infty，最优子树集合ω={T}\omega=\{T\}
    • 3）从叶子节点开始自下而上计算各内部节点tt的训练误差损失函数Cα(Tt)C_{\alpha}(T_t)（回归树为平方误差，分类树为基尼不纯度），叶子节点数∣Tt∣|T_t|，以及正则化阈值：

    g(t)=C(t)−C(Tt)∣Tt∣−1g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}

    αmin=min(αmin,g(t))\alpha_{min}=min(\alpha_{min},g(t))

    • 4）得到所有节点的α\alpha值的集合MM
    • 5）从MM中选择最小的值αk\alpha_k，自上而下地访问的内部节点tt，如果有g(t)=αg(t)=\alpha，进行剪枝，并决定叶节点tt的值。如果是分类树，则是概率最高的类别，如果是回归树，则是所有样本输出的均值。这样得到αk\alpha_k对应的最优子树TkT_k
    • 6）最优子树集合ω=ω∪Tk,   M=M−{αk}\omega=\omega \cup T_k,\,\,\,M=M-\{\alpha_k\}，更新kk： k=k+1k=k+1
    • 7）如果MM不为空，则回到步骤5。直到MM为空，得到所有的可选最优子集ω\omega
    • 8）采用交叉验证在ω\omega上面选择最优子树TαT_{\alpha}

应用场景和不足

应该说相比去ID3和C4.5算法，CART算法做了很大的提升，能同时处理离散型变量和连续型变量，即可以用于分类，也可以用于回归。无论是以对信息熵进行近似的基尼不纯度或者在线性回归当中非常常用的平方误差为损失函数，都有着不错的计算效率和较好的精度，而且还支持剪枝，能够较大幅度的提高泛化能力。但是作为基本的树模型还是有本身固有的一些缺陷存在：

  • 无论是ID3、C4.5还是CART，在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的，而且还要考虑特征之间的交叉特性。这样决策得到的决策树更加准确
  • 决策树算法非常容易过拟合，且本身极为不稳定，如果样本发生一点点的改动，就会导致树结构的剧烈改变。这看似是个缺点，但是却非常适合在集成学习当中被选为基学习器。比如XGBoost的基学习器就是CART树。

sklearn参数详解

scikit-learn决策树算法类库内部实现是使用了调优过的CART树算法，既可以做分类，又可以做回归。分类决策树的类对应的是DecisionTreeClassifier，而回归决策树的类对应的是DecisionTreeRegressor。

DecisionTreeClassifier

参数（Parameters）

  • criterion : string, optional (default=”gini”)

    • 特征选择标准：可以使用"gini"或者"entropy"，前者代表基尼系数，后者代表信息增益。一般说使用默认的基尼系数"gini"就可以了，即CART算法。除非你更喜欢类似ID3, C4.5的最优特征选择方法

  • splitter : string, optional (default=”best”)

    • 特征划分点选择标准：可以使用"best"或者"random"。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。默认的"best"适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐"random"

  • max_depth : int or None, optional (default=None)

    • 树的最大深度：默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间

  • min_samples_split : int, float, optional (default=2)

    • 分裂一个内部节点所需要的最小的样本数：这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值

  • min_samples_leaf : int, float, optional (default=1)

    • 叶子节点所需要的最小样本数：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值

  • min_weight_fraction_leaf : float, optional (default=0.)

    • 叶子节点最小的样本权重和：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了

  • max_features : int, float, string or None, optional (default=None)

    • 寻找最优分裂的特征数量：可以使用很多种类型的值，默认是"None",意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑log⁡N\log N个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑N\sqrt{N}个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xNN）取整后的特征数。其中NN为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的"None"就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间

  • random_state : int, RandomState instance or None, optional (default=None)

    • 随机数种子

  • max_leaf_nodes : int or None, optional (default=None)

    • 最大叶子节点数：通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到

  • min_impurity_decrease : float, optional (default=0.)

    • 一个节点当且仅在分裂所减小的不纯度大于或者等于该值时才会分裂

  • min_impurity_split : float, (default=1e-7)

    • 建树时候早停的基尼不纯度阈值：这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。后续被min_impurity_decrease代替

  • class_weight : dict, list of dicts, “balanced” or None, default=None

    • 类别权重：指定样本各类别的的权重，主要是为了防止训练集某些类别的样本过多，导致训练的决策树过于偏向这些类别。这里可以自己指定各个样本的权重，或者用“balanced”，如果使用“balanced”，则算法会自己计算权重，样本量少的类别所对应的样本权重会高。当然，如果你的样本类别分布没有明显的偏倚，则可以不管这个参数，选择默认的"None"。注意这些权重会与sample_weight相乘

  • presort : bool, optional (default=False)

    • 数据是否预排序，对于大数据集如果预排序会增加训练时间

属性（Attributes）

  • classes_ : array of shape = [n_classes] or a list of such arrays

    • 类别标签

  • feature_importances_ : array of shape = [n_features]

    • 返回特征重要性系数

  • max_features_ : int,

    • 最大特征数

  • n_classes_ : int or list

    • 类别数

  • n_features_ : int

    • 入模型的特征数

  • n_outputs_ : int

    • 输出类别数

  • tree_ : Tree object

    • 树对象

方法（Methods）

方法名称 方法解释
apply(self, X[, check_input]) Returns the index of the leaf that each sample is predicted as.
decision_path(self, X[, check_input]) Return the decision path in the tree
fit(self, X, y[, sample_weight, …]) Build a decision tree classifier from the training set (X, y).
get_depth(self) Returns the depth of the decision tree.
get_n_leaves(self) Returns the number of leaves of the decision tree.
get_params(self[, deep]) Get parameters for this estimator.
predict(self, X[, check_input]) Predict class or regression value for X.
predict_log_proba(self, X) Predict class log-probabilities of the input samples X.
predict_proba(self, X[, check_input]) Predict class probabilities of the input samples X.
score(self, X, y[, sample_weight]) Returns the mean accuracy on the given test data and labels.
set_params(self, **params) Set the parameters of this estimator.

DecisionTreeRegressor

参数（Parameters）

  • criterion : string, optional (default=”mse”)

    • 特征选择标准：可以使用"mse"或者"mae"，前者是均方差，后者是和均值之差的绝对值之和。推荐使用默认的"mse"。一般来说"mse"比"mae"更加精确。除非你想比较二个参数的效果的不同之处

  • splitter : string, optional (default=”best”)

    • 特征划分点选择标准：可以使用"best"或者"random"。前者在特征的所有划分点中找出最优的划分点。后者是随机的在部分划分点中找局部最优的划分点。默认的"best"适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐"random"

  • max_depth : int or None, optional (default=None)

    • 树的最大深度：默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间

  • min_samples_split : int, float, optional (default=2)

    • 分裂一个内部节点所需要的最小的样本数：这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值

  • min_samples_leaf : int, float, optional (default=1)

    • 叶子节点所需要的最小样本数：这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值

  • min_weight_fraction_leaf : float, optional (default=0.)

    • 叶子节点最小的样本权重和：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。 默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了

  • max_features : int, float, string or None, optional (default=None)

    • 寻找最优分裂的特征数量：可以使用很多种类型的值，默认是"None",意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑log⁡N\log N个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑N\sqrt{N}个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xNN）取整后的特征数。其中NN为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的"None"就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间

  • random_state : int, RandomState instance or None, optional (default=None)

    • 随机数种子

  • max_leaf_nodes : int or None, optional (default=None)

    • 最大叶子节点数：通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到

  • min_impurity_decrease : float, optional (default=0.)

    • 一个节点当且仅在分裂所减小的不纯度大于或者等于该值时才会分裂

  • min_impurity_split : float, (default=1e-7)

    • 建树时候早停的基尼不纯度阈值：这个值限制了决策树的增长，如果某节点的不纯度(基尼系数，信息增益，均方差，绝对差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。后续被min_impurity_decrease代替

  • presort : bool, optional (default=False)

    • 数据是否预排序，对于大数据集如果预排序会增加训练时间

属性（Attributes）

  • feature_importances_ : array of shape = [n_features]

    • 返回特征重要性系数

  • max_features_ : int,

    • 最大特征数

  • n_features_ : int

    • 入模型的特征数

  • n_outputs_ : int

    • 输出类别数

  • tree_ : Tree object

    • 树对象

方法（Methods）

方法名称 方法解释
apply(self, X[, check_input]) Returns the index of the leaf that each sample is predicted as.
decision_path(self, X[, check_input]) Return the decision path in the tree
fit(self, X, y[, sample_weight, …]) Build a decision tree classifier from the training set (X, y).
get_depth(self) Returns the depth of the decision tree.
get_n_leaves(self) Returns the number of leaves of the decision tree.
get_params(self[, deep]) Get parameters for this estimator.
predict(self, X[, check_input]) Predict class or regression value for X.
score(self, X, y[, sample_weight]) Returns the mean accuracy on the given test data and labels.
set_params(self, **params) Set the parameters of this estimator.

sklearn决策树可视化

sklearn决策树可视化需要通过pip命令预先安装graphviz和pydotplus这两个模块。

以下是以sklearn自带的iris数据集为例的一个决策树可视化示例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 载入类库

from sklearn.datasets import load_iris
from sklearn import tree

# 载入数据

iris_data = load_iris()

# 初始化决策树对象

clf_model = tree.DecisionTreeClassifier()

# 调用fit函数拟合模型

clf_model = clf_model.fit(iris_data.data, iris_data.target)

# 载入pydotplus 直接在notebook可视化决策树
import pydotplus

from IPython.display import Image  

dot_data = tree.export_graphviz(clf_model, out_file=None, 
                         feature_names=iris_data.feature_names,  
                         class_names=iris_data.target_names,  
                         filled=True, rounded=True,  
                         special_characters=True)  
graph = pydotplus.graph_from_dot_data(dot_data)  
Image(graph.create_png())

以上代码生产的决策树的图形如下：

决策树算法小结

这里从决策树算法这一个大类来总结决策树算法的优缺点，参考sklearn的文档进行整理。

优点

  • 理解简单，易于解释，可以对树进行可视化
  • 基本不需要太多的数据准备和预处理，比如归一化、类别特征编码、缺失值处理等
  • 树模型的算法复杂度是训练样本的对数
  • 可以同时处理数值型变量和类别型变量，其它一些算法往往特别针对其中一类的数据
  • 天然可以处理多分类问题
  • 并非黑盒模型，从逻辑上面来讲模型解释性极强
  • 可以用统计测试对模型进行交叉验证，提高模型泛化能力和稳定性
  • 对于数据有较好的容错能力

缺点

  • 决策树非常容易过拟合，剪枝机制、设置叶子节点最小样本数或者树的最大深度可以一定程度上面减少这个问题
  • 决策树模型非常不稳定，数据的极小波动都会引起模型的剧烈变化，这是个缺点，但是也使得决策树非常适合于用作集成学习的基学习器
  • 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法比如贪心算法获得对于每一个节点的局部最优解。这种算法无法确保获得全局最优解，这个也为通过集成学习之类的方法来改善模型留足了空间
  • 有些比较复杂的关系，决策树很难学习，比如异或，这个和感知机类似，可以换神经网络的分类方法来解决
  • 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这也是建议在建模之前进行样本平衡的原因

应用场景

从任务功能上来讲，分类和回归决策树都不在话下，从笔者的从业经历来看，单纯使用决策树模型的场景不太多，仅在金融领域的贷前审核会使用到，通会决策树算法与其它机器学习算法结合起来使用或者用作Bagging或者Boosting算法的基学习器。

参考