淘先锋技术网

首页 1 2 3 4 5 6 7

机器学习之决策树

基本思想

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

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

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

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

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

在进行节点切分的时候我们有四个选择，基于 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.5，p(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. 拿真实数据集调参一下。

转载于:https://juejin.im/post/5cee01d9f265da1ba431cfbf