理解决策树信息增益(information gain)

问题引出:信息增量是什么?干什么用?
一颗决策树中的非叶子节点有split函数,用于将当前所输入的数据分到左子树或者右子树。我们希望每一个节点的split函数的性能最大化。这里的性能是指把两种不同的数据分开的能力,不涉及到算法的时间复杂度。但是,怎么去衡量一个split函数的性能呢?这里我们使用信息增益来衡量 I I I。如果 I I I越大,说明该节点的split函数将输入数据分成两份的性能越好。

下面图片是一个决策树的例子。来自https://www.cnblogs.com/xiemaycherry/p/10475067.html
《理解决策树信息增益(information gain)》

下面图片表示决策树中的三个节点,其中父节点有一个split函数,用于分割所输入的数据成两份。
《理解决策树信息增益(information gain)》

如何计算信息增益 I I I?下面先给出公式,再讲本人的理解。

  • 香侬交叉熵公式
    H ( S ) = − ∑ p ( c i ) l o g ( p ( c i ) ) H(S) = – \sum p(c_i)log(p(c_i)) H(S)=p(ci)log(p(ci))

  • 信息增益公式
    I = H ( S ) − ∑ ∣ S i ∣ S H ( S i ) I = H(S) – \sum{\frac{|S^i|}{S} H(S^i)} I=H(S)SSiH(Si)

香侬交叉熵公式的理解:
这个公式应该分成两部分,第一部分是 ( − l o g ( p ( c i ) ) (-log(p(c_i)) (log(p(ci)), 第二部分是 p ( c i ) p( c_i) p(ci)。前者表示 c i c_i ci的信息量,后者表示 c i c_i ci出现的概率。所以,公式 H ( S ) = − ∑ p ( c i ) l o g ( p ( c i ) ) H(S) = – \sum p(c_i)log(p(c_i)) H(S)=p(ci)log(p(ci))表示对于所有的c的信息量的期望。

一件事情的信息量跟这件事情发生的概率相关。可以直观理解为。一件事发生的概率越小,说明这件事的不确定越大,情况也就越复杂,所以信息量大。反之亦然。为了表示这种关系,我们使用下面图示公式来建模已知的一件事情的信息量: − l o g ( p ( c i ) -log(p(c_i) log(p(ci)
《理解决策树信息增益(information gain)》
如果我们知道了每一件事所发生的信息量,再结合它所发生的概率,就可以计算它这些事情的信息量的期望了。(期望,其实是加权平均值,最简单的期望是均权平均值。所以公式 H ( S ) = − ∑ p ( c i ) l o g ( p ( c i ) ) H(S) = – \sum p(c_i)log(p(c_i)) H(S)=p(ci)log(p(ci))的前面的 p ( c i ) p( c_i) p(ci)可以理解为平均值的权重了)。

下面给出两棵树,输入两次数据,每次都输入100个(第一次输入一百个红色的,第二次是一百个蓝色的)。哪一棵树的split函数的分割性能更好呢?
通过观察,第二棵树好一点,因为,第二棵树把大部分红色数据分到了左边,把大部分蓝色数据分到了右边。所以,第二棵树的信息增益比第一颗的好。

如何使用上面的数学公式计算呢?
《理解决策树信息增益(information gain)》
下面的图片便是计算第一棵树的信息增量了,最后的结果约等于0.0054。通过同样的方式可以计算第二棵树的信息增量,比第一棵树大。
《理解决策树信息增益(information gain)》
通过上面的计算过程,我们发现,如果一个节点的split函数将输入的数据均匀地切分成两份,那么相应地信息熵的期望为 − 50 100 l o g 50 100 − 50 100 l o g 50 100 = 1 – \frac{50}{100} log \frac{50}{100} – \frac{50}{100} log \frac{50}{100} = 1 10050log1005010050log10050=1, log以2为底。
《理解决策树信息增益(information gain)》
如果把输入数据分成两份不同的数据,比如下图所示,那么,交叉熵的期望就会变小。即下面公式的 H ( S i ) H(S^i) H(Si)变小,如果其它部分不变, I I I会变大。 ∣ S i ∣ S \frac{|S^i|}{S} SSi表示分到一个分支上的数据量占该分支所有数据量的比值(建议结合上面计算公式理解)。该比值越大,说明本次分割对当前分支的影响也就越大了。本质上它是一个权重值。

I = H ( S ) − ∑ ∣ S i ∣ S H ( S i ) I = H(S) – \sum{\frac{|S^i|}{S} H(S^i)} I=H(S)SSiH(Si)
《理解决策树信息增益(information gain)》

以上便是决策树的信息增量和本人的理解。

    原文作者:ChainingBlocks
    原文地址: https://blog.csdn.net/liangyihuai/article/details/103206360
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞