机器学习之决策树

2,107 阅读9分钟

基本思想

决策树是一个树结构。每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

作为一个基本的机器学习算法,目前很多实用性很强的著名算法都是基于决策树构建的,比如 XGBoost, LightGBM, GBDT, Adaboost, Random Forest。可参考 -> 集成学习

上面说的大概有些抽象,举一个例子,下面是一个数据集,我们需要根据天气属性判断是否有人会打高尔夫球,其中:

  • 天气状况有晴、云、雨。
  • 气温用华氏温度表示。
  • 湿度用百分比表示。
  • 风度用有风无风表示。

Golf dataset.png

假设在树的第一层选用 outlook 属性作为切分的话,我们可以划分成如下图所示的这样一棵树:

Decision tree model.png

在进行节点切分的时候我们有四个选择,基于 outlook/temperature/humidity/windy,那么我们到底应该选择哪一个进行切分的?

对于这种分类问题,通常有三种方式,信息增益、信息增益率、基尼系数,分别对应三大算法:id3、c4.5、cart。下面我们来具体看一下。

p.s: 本文主要介绍决策树的三种构建算法,具体的优化细节比如剪枝以及处理连续值缺失值等问题,后续在补充。

信息熵

在分析信息增益之前,我们先来看一下信息熵。在信息论中,随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性,信息学之父香农引入了信息熵(entropy)的概念,并给出了计算信息熵的数学公式:

\text {Entropy}(t)=-\sum_{i=0}^{c-1} p(i | t) \log _{2} p(i | t)

p(i|t) 代表了节点 t 为分类 i 的概率,其中 log2 为取以 2 为底的对数。当不确定性越大时,信息熵也就越高。

假设有 2 个集合:

  1. 集合 1:5 个男生,1 个女生。
  2. 集合 2:3 个男生,3 个女生。

将男生看做类别 1,女生看做是类别 2。在集合一种类别 1 的概率是 1/6,类别 2 的概率为 5/6,所以可以算出信息熵为:

\text {Entropy}(t)=-(1 / 6) \log _{2}(1 / 6)-(5 / 6) \log _{2}(5 / 6)=0.65

在集合二中,类别 1 和类别 2 的概率都是 0.5,所以信息熵为:

\text {Entropy}(t)=-(3 / 6) \log _{2}(3 / 6)-(3 / 6) \log _{2}(3 / 6)=1

可以看到,信息熵越大,纯度越低。当集合中的所有样本均匀混合时,信息熵最大,纯度最低。

ID3

信息增益指的就是划分可以带来纯度的提高,信息熵的下降。它的计算公式,是父亲节点的信息熵减去所有子节点的信息熵。

\operatorname{Gain}(D, a)=E n t r o p y(D)-\sum_{v=1}^{V} \frac{\left|D_{v}\right|}{|D|} \text {Entropy }\left(D_{v}\right)

ID3 生成算法核心是在决策树的每个结点上应用信息增益准则选择特征,递归地构建决策树。

  • 从根结点开始,计算结点所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征划分出子结点。
  • 再对子结点递归地调用以上方法,构建决策树。
  • 直到所有特征的信息增益均很小或者没有特征可以选择为止,最后得到一个决策树 。如果不设置特征信息增益的下限,则可能会使得每个叶子都只有一个样本点,从而划分得太细。

类比上面的高夫球例子,在第一次拆分的时候,a 有四个取值:outlook/temperature/humidity/windy,分别计算出这四个属性下根节点的信息增益,选择让信息增益取值最大来拆分。类比树的第二层、第三层也是同理。

C4.5

信息增益率定义如下:

\text {Gain}_{-} \text {ratio}=\frac{\operatorname{Gain}(D, a)}{I V(a)}, \text { where } I V(a)=-\sum_{v=1}^{V} \frac{\left|D_{v}\right|}{D} \log _{2} \frac{\left|D_{v}\right|}{D}

因为 ID3 在计算的时候,倾向于选择取值多的属性,也就是说 v 越多的话,信息增益越大。为了避免这个问题,C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵。当属性有很多值的时候,相当于被划分成了许多份,虽然信息增益变大了,但是对于 C4.5 来说,属性熵也会变大,所以整体的信息增益率并不大。

CART

前面提到的 id3/c4.5 算法都是 n 叉树,cart 树是一棵二叉树,所以在决策时,只能做是或否的决策,即使一个 feature 有多个取值。

分类树

CART 树采用基尼指数选择最优特征。基尼系数反应了样本的不确定程度。当基尼系数越小的时候,说明样本之间的差异小,不确定程度低。CART 算法在构建分类树的时候,会选择基尼系数最小的属性作为属性划分。

G I N I(t)=1-\sum_{k}\left[p\left(C_{k} | t\right)\right]^{2}

p\left(C_{k} | t\right) 表示 t 属于 C_k 的概率,节点 t 的基尼系数等于 1 减去各类别概率的平方和。下面举一个具体的例子来说明一下:

  • 集合 1:六个男生。所以 \mathrm{GINI}(\mathrm{t})=1-1=0
  • 集合 2:三个男生,三个女生。p(C_1|t)=0.5p(C_2|t)=0.5,所以 \mathrm{GINI}(\mathrm{t})=1-(0.5 \times 0.5+0.5 \times 0.5)=0.5

集合1的基尼系数更小,相比集合2更稳定。

在 CART 算法中,假设基于某属性对集合 D 进行分裂,划分成了上面集合一 D_1 和集合二 D_2。集合 D 的基尼系数为:

G I N I(D, A)=\frac{D_{1}}{D} G I N I\left(D_{1}\right)+\frac{D_{2}}{D} G I N I\left(D_{2}\right)

也就是:

G I N I(D, A)=\frac{6}{12} G I N I\left(D_{1}\right)+\frac{6}{12} G I N I\left(D_{2}\right)=0.25

多离散值处理

CART 对连续型属性的处理与 C4.5 差不多,通过最小化分裂后的 GINI 值或者样本差值寻找最优分割点,将节点一分为二,在这里暂时先不描述。

对于离散型属性,理论上有多少个离散值就应该分裂成多少个节点。但 CART 是一棵二叉树,每一次分裂只会产生两个节点,怎么办呢?只要将其中一个离散值独立作为一个节点,其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法,举一个简单的例子:如果某离散属性一个有三个离散值 X,Y,Z,则该属性的分裂方法有 {X}、{Y,Z},{Y}、{X,Z},{Z}、{X,Y},分别计算每种划分方法的基尼值或者样差值确定最优的方法。

回归树

上面讲的基尼系数可以应用到分类场景中,对于回归场景,我们可以使用样本的离散程度来评价不纯度。样本离散程度的计算方式是,先计算所有样本的均值,然后计算每个样本值到均值的差值。假设 x 为样本个体,均值为 u。有两种计算方式,一种是去差值的绝对值,一种是根据方差。

绝对值计算:

|x-\mu|

方差为每个样本值减去样本均值的平方和除以样本个数:

s=\frac{1}{n} \sum(x-\mu)^{2}

因此不管是分类树还是回归树,CART 都要选择使子节点的 GINI 值或者回归差值最小的属性作为分裂的方案。

正则化

减枝

基于训练样本来生成决策树时,如果不做任何限制,那么就会完全过拟合,这样决策树就没有任何泛化能力了。如何防止过拟合呢?通常可以进行预减枝和后减枝。

预减枝

预减枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化能力(在训练时加入验证集随时进行泛化验证)的提升,则停止划分并将当前结点标记为叶节点。

预剪枝抑制了很多分支的展开,这降低过拟合的同时还减少了训练时间,但是却存在欠拟合的风险;预剪枝基于贪心策略,往往可以达到局部最优解却不能达到全局最优解,也就是说预剪枝生成的决策树不一定是最佳的决策树。XGBoost 和 LightGBM 使用的树就是预剪枝的 CART 决策树,这能保证他们的训练速度较快。

后减枝

后剪枝则是先从训练集中生成一颗完整的树,然后自底向上对非叶节点进行考察,若该节点对应的子树替换为叶节点能够提升泛化能力,则进行剪枝将该子树替换为叶节点,否则不剪枝。后剪枝技术通常比预剪枝保留了更多的分支,它是自底向上的剪枝,因此它的欠拟合风险较小,泛化能力往往优于预剪枝,然而因为总是要完全生长一棵树,这就要花费很多时间训练了,数据集规模大、维度高时并不适用实际应用。

CCP

CCP(代价复杂度)是一种用在 CART 算法中后减枝算法,在此单独说明一下。CCP 选择节点表面误差率增益值最小的非叶子节点,删除该非叶子节点的左右子节点,若有多个非叶子节点的表面误差率增益值相同小,则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。

表面误差率增益值的计算公式:

\alpha=\frac{R(t)-R(T)}{N(T)-1}
  1. R(t) 表示叶子节点的误差代价,R(t)=r(t) \cdot p(t)r(t) 为节点的错误率,p(t) 为节点数据量的占比。
  2. R(T) 表示子树的误差代价,R(T)=\sum_{i}^{m} r_{i}(t) \cdot p_{i}(t)r_{i}(t) 为子节点 i 的错误率,p_{i}(t) 表示节点 i 的数据节点占比。
  3. N(T) 表示子树节点个数。

比如下图是一颗子树,设决策树的总数据量为 40。该子树的表面误差率增益值可以计算如下:

\begin{array}{l}{R(t)=\frac{8}{18} \cdot \frac{18}{40}=\frac{1}{5}} \\ {R(T)=\sum_{i}^{m} r_{i}(t) \cdot p_{i}(t)=\frac{1}{3} \cdot \frac{3}{40}+\frac{4}{9} \cdot \frac{9}{40}+\frac{1}{6} \cdot \frac{6}{40}=\frac{6}{40}} \\ {\alpha=\frac{R(t)-R(T)}{N(T)-1}=\frac{\frac{1}{5}-\frac{6}{40}}{3-1}=\frac{1}{40}}\end{array}

调参

如果使用 sklearn 的话,也可以通过设置相关的超参数来进行正则化:

  • max_depth,通过设置决策树的最多深度来防止过拟合。
  • min_samples_split,节点在分裂之前必须具有的最小样本数。如果该节点上的样本数量小于参数设置的数目时,节点将不再继续进行分裂。
  • min_samples_leaf,叶子节点必须拥有的最小样本数。
  • max_leaf_nodes,叶子节点最大的样本数。

todo

  1. 查阅周志华的西瓜书补充连续值和缺失值处理。
  2. 补充剪枝算法。
  3. 拿真实数据集调参一下。