Press "Enter" to skip to content

机器学习之决策树

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

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

 

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

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

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

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

 

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

 

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

 

信息熵

 

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

 

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

 

假设有 2 个集合:

 

 

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

 

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

 

 

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

 

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

 

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

 

ID3

 

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

 

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

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

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

 

C4.5

 

信息增益率定义如下:

 

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

 

CART

 

分类树

 

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

 

表示 t 属于 的概率,节点 t 的基尼系数等于 1 减去各类别概率的平方和。下面举一个具体的例子来说明一下:

 

集合 1:六个男生。所以 。

 

集合 2:三个男生,三个女生。 , ,所以 。

 

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

 

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

 

也就是:

 

回归树

 

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

 

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

 

绝对值计算:

 

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

 

正则化

 

减枝

 

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

 

预减枝

 

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

 

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

 

后减枝

 

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

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注