美文网首页
1-2 决策树节点划分时的特征选择依据

1-2 决策树节点划分时的特征选择依据

作者: 迪丽娜扎 | 来源:发表于2018-12-09 15:07 被阅读0次

依据不同的决策树算法,在划分子节点时进行特征选择的依据有信息增益、信息增益比(又称信息增益率)、基尼系数三种。依次阐述如下:

0. 什么是信息熵?

如果没有学过信息论等与信息理论相关的书,初看信息熵是会有点懵逼的。在机器学习领域,信息熵的定义如下:

信息熵是度量样本集合纯度的一种最常用的指标,假设样本集合D的样本数一共有D个,一共有K类(标签),其中第k类样本所占的比例为pk,则该样本集的信息熵为:

信息熵计算公式

有两点可以加强理解:① 信息熵是一个与类别标签相关,而与特征无关的量;②其实际反映的就是这个样本集中不同类别的样本的占比情况,也就是前面所说的纯度

如何直观的理解信息熵?可以从熵的最初概念出发,熵是表示体系混乱程度的度量,熵越大自然纯度就越小。

吊诡的地方在哪里呢?在于前面的信息二字,信息熵越大到底代表信息量越大还是信息量越小?如果我们把信息量理解的直观一点,两者是反着的,信息熵越大,能给我们利用的信息就越少。

举个简单的栗子,样本集D有10个人。如果是5个好人5个坏人,信息熵就会大于8个好人2个坏人的情况。

样本分布的越均衡,信息熵越大,信息量越小

为什么呢?因为5:5的比例确实带不来任何信息,假设我们现在就只有这么个样本集,然后来一个新样本,我们判断这个新样本是个好人还是坏人?5:5的样本集告诉我们,有0.5的概率是好人0.5的概率是坏人,也就是跟随机抛硬币一样,无论我们最后给新样本定什么标签,都有50%的错误率。但假设我们的样本集是8:2,其它什么特征都不用,我们可以判断,这个新样本80%的概率是好人,20%的概率是坏人,所以我们应该无脑的把所有人都判断为好人,这样我们预计只有20%的错误率。

这就是信息熵发挥的作用,样本类别越均衡,就是纯度越小,信息熵越大,可用的信息就越少。

1. 信息增益

前面扯了这么多废话把信息熵弄明白,信息增益就简单多了。如果我们按照某个特征的取值,把原始样本集划分为若干个子集,然后用某种方式求一下这些子集的信息熵“之和”,我们希望什么,我们希望划分后的信息熵要减小得尽可能的多,这个信息熵的减小量,就是信息增益

第一个问题:划分后的子集信息熵之和怎么算?按照信息熵定义,每个子集都能算一个信息熵出来,简单求个和吗?那肯定不行,毕竟还有个样本量的问题,把样本量考虑进去,就相当于给每个子集的信息熵配一个权重,这个权重就是这个子集的样本数占样本总数的比例,然后加权求个和,这就是划分子集后的信息熵求法。

假设按某个特征的取值把原始样本集划分为D1、D2、Dv等若干个子集,划分后的整体信息熵这么求

用原始的信息熵减去上面这个划分后的信息熵,就是信息增益咯。再说一遍,信息增益就是信息熵的减小量。

基于特征a划分样本集后的信息增益求法

补充点废话:信息增益大意味着什么?意味着划分后的样本集们普遍的信息熵较小,也就是纯度较大,纯度较大意味着什么,意味着划分后的各个子集有可能这个子集全是好人,那个子集全是坏人,这不正是我们想要的吗,我们要的恰恰就就是根据特征来有效判断人的好坏,所以选信息增益大的特征进行样本划分也就是理所当然的了。

使用信息增益来划分节点的决策树算法叫ID3算法

2. 信息增益比(率)

信息增益有什么问题?假设我们有两个特征可供选择,性别与年龄,其中性别的取值只有男和女两种,而年龄的取值有18、19、20、...、64、65几十个。这会带来什么问题呢?定性想一下,特征取值越多,划分后的各个子集就会越小,而越小的子集其分布就越有可能偏。还是按前面的栗子来说,10个人按性别划分成5个男人5个女人,而这两个子集里有分别都有好人和坏人,信息增益可能just soso,但如果按年龄分,假设10个人恰好是10个不同的年龄,那划分后每个子集里要么是一个好人要么是一个坏人,纯度杠杠的,信息增益杠杠的。但这是否代表年龄真的是个更好用得特征?并不是,这是因为我们的样本集终究是有限个样本构成的,当特征取值很多时,子集越小,越小就越有可能出现统计学意义上的偏差,从而使其信息增益看起来大。废话了这么多,想说明什么问题呢?就是“依据信息增益划分子集”这个标准会偏爱可取值数多的特征,而这个特征在刻画样本时不一定强

为了平衡这一点,我们要设法对信息增益做个类似归一化的操作,让不同特征间能有可比性。归一化肯定要考虑特征取值数了,但直接把信息增益除以特征取值数就太简单粗暴了,因此我们再定义一个指标,这个指标称之为特征的固有值,整体上与特征的可取值数会正相关,定义如下:

特征a的固有值

使用特征a的信息增益除以特征a的固有值,就是信息增益比了,使用信息增益比来划分节点的决策树算法叫C4.5算法。

前面说过,信息增益会偏爱取值数较多的特征,那么信息增益比是不是一视同仁了呢?没有,信息增益比会偏爱取值数较少的特征(捂脸哭)。所以最机智的做法应该是设法结合两者。

3. 基尼系数

其实决策树的节点划分这个事儿吧,搞这么多指标出来自然有它的理由,但这些指标说来说去呢,为的都是一件事儿,那就是我们要找到最有用的特征来划分节点。那什么是最有用呢?就是能最有效的区分样本的类别。不管什么指标,本质上度量的都是这个事儿。

基尼系数自然也是如此了,基尼系数反映了从样本集中随机抽取两个样本,其类别标记不一致的概率,原始样本集的基尼系数这么算:

跟信息熵一样,是个与类别有关但与特征无关的量

为毛说基尼系数反映了随机选取的两个样本类别不一致的概率呢?pk是不同类别的样本所占的比例,因此它们的和为1,一堆介于0~1之间的pk的平方和,什么时候最小?当所有的pk相等的时候平方和最小,这个可以用初中数学知识证明。而当每个类别所占的比例都一样的时候,随机抽取的两个样本不一样的概率最大。比如,在5个好人5个坏人里随机抽俩人,这俩人一个是好人一个是坏人的概率还是蛮大的,但如果在9个好人1个坏人里抽俩人,这俩人就有更大概率是两个好人。因此基尼系数度量的也是纯度,由于前面有个1-,基尼系数越大,意味着纯度越小(也意味着信息熵越大)。

理解了基尼系数和信息熵反应的本质是一样的之后,这事就好说了,信息增益是信息熵的减小量,对比想一下这儿就是用划分后基尼系数减小量咯?差不多,但不完全一样,这里是直接用了划分后基尼系数,哪个特征最小就用哪个。为毛呢?因为划分前大家都是一个基尼系数啊,划分后基尼系数最小,可不就是划分后基尼系数减小量最大嘛,所以是一回事。从这个角度来说,前面用信息增益最大也没必要,直接用划分后信息熵最小的那个就行了,效果是一样一样的。

按特征a划分子集后的基尼系数计算方法,跟前面的划分后的信息熵计算方法套用了几乎一毛一样的公式

使用基尼系数划分特征的决策树算法叫CART算法。CART的全称是classify and regression tree(分类和回归树),回归树是什么玩意,以后再说了。

以上就是决策树节点划分时特征选择所用的三个指标。

相关文章

  • 1-2 决策树节点划分时的特征选择依据

    依据不同的决策树算法,在划分子节点时进行特征选择的依据有信息增益、信息增益比(又称信息增益率)、基尼系数三种。依次...

  • 统计学习方法思路疏导—决策树

    决策树 算法过程 特征选择 生成决策树 决策树兼职 特征选择 选择下面 2 指标作为特征选择的依据 信息增益:使用...

  • 决策树: 特征选择之寻找最优划分

    前言决策树算法的三个步骤:特征选择、决策树生成、决策树剪枝。其中特征选择要解决的核心问题就是:每个节点在哪个维度上...

  • 机器学习-周志华 决策树

    决策树建立:当前节点选哪个特征,选择特征的哪个值作为分割点。 决策树建立的目标:结点的“纯度”越来越高。 决策树调...

  • ID3、C4.5、CART

    序 其实不同的决策树学习算法只是它们选择特征的依据不同,决策树的生成过程都是一样的(根据当前环境对特征进行贪婪的选...

  • 用于分类的决策树的理解

    决策树学习的三个步骤:特征选择,决策树生成,决策树剪枝。 特征选择 特征选择在于选取对训练数据具有分类能力的特征。...

  • 步步为营,有章可循:决策树

    决策树是包含根节点、内部节点和叶子节点的树结构,通过判定不同属性的特征来解决分类问题; 决策树的学习过程包括特征选...

  • 李航-第5章决策树

    决策树的学习算法包特征选择、决策树的生成与决策树的剪枝过程。决策树学习应用信息增益准则选择特征。信息增益大的特征具...

  • 机器学习实战-决策树

    决策树 决策树是一个选择的过程,以树的结构来展示,其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性...

  • 【理论篇】决策树算法 - 特征如何切分?

    决策树算法连载的系列文章,小鱼已经为大家介绍了决策树算法的特征选取:即从根节点开始,按照分类能力的强弱选取节点特征...

网友评论

      本文标题:1-2 决策树节点划分时的特征选择依据

      本文链接:https://www.haomeiwen.com/subject/vfghhqtx.html