决策树信息熵数理剖析

信息熵记录拓展决策树

张⼀极 

2019年年3⽉月9日

假如有一个集合为a[1,2,3,4,5],另⼀一个集合为b[1,2,3,2,2,4]

那么我们对应的应该如何获取两个数据集的信息熵呢,首先我们需要了了解信息熵的
定义,在数学上,信息熵作为数据集混乱程度的计算量化指标,我们获得最后的结果应该是通
过这个公式:

熵 = −∑n pilog2(pi)
i=1

在log2n当中,有这么⼀一个特点:与x轴交于[0,1],所以当体系混乱的时候,会有特别⼤的负值,那么体系稳定的时候,会有⼩小的负值存在log函数当中,最后归正,体系混乱的数据集,
信息熵就特别⼤大,体系稳定的数据,信息熵就会趋于0.

在数学当中,与信息熵有相同含义的数据有Gini系数:
Gini(p) = ∑k pk(1 − pk)

k=1
构造决策树的基本想法是随着树深度的增加,节点的熵迅速降低,降低速度越快越好,

1

信息熵记录拓拓展决策树
那么⼀一开始我们应该如何去寻找rootnode,我们需要计算当前节点的熵值,⽐比如正样

本的概率为0.23,负样本的概率为0.77,熵为[ -0.23*log2_0.23-0.77log2_0.77 ]
信息增溢,gain(feature):为标准信息熵减去节点信息熵,也就是⼀一开始使⽤用的信息熵

减去使⽤用这个节点作为根节点产⽣生的信息熵,信息增溢让信息熵迅速降低,越快越好,所以我
们选择⼀一个节点肯定是让信息熵下降最快的.

Algorithms:

ID3算法:
信息增溢率,利利⽤用信息增溢值,来与节点⾃自身信息做商,得到信息增溢率,⽐比如说我们⼀一开始⽤用

id作为根节点,那么信息增溢将会最⼤大化,也就是对于整个决策树⽽而⾔言,⽤用id每⼀一个分数都平均的概率
C4.5算法:

那么知道了了信息增溢率,那我们来描述⼀一下评价函数,整个决策树的评价函数就是: 

func = ∑ NTH(t)

t−>leaf
那么对应的就是作为评价函数的我们设为func,那么func肯定是越⼩小越好,leaf的意思

是叶⼦子,就是叶⼦子节点的⼀一个信息熵与叶⼦子节点的样本权重.
本算法的优点相⽐比于ID3来说是能够处理理连续性的属性,将连续的属性分成不不同区间,

依据就是Gain值(信息增溢)的⼤大⼩小,并且在构建决策树的时候,可以简单忽略略缺失数据,只计
算有属性值的记录.

决策树的剪枝:

预剪枝:
在构建决策树的过程中,提前停⽌止构建,也就是当样本量量少于某⼀一个阈值的时候,进⾏行行决策树的提前
停⽌止.
后剪枝:
决策树构建完成以后,进⾏行行裁剪:

信息熵记录拓拓展决策树

Loss = func =NT H(t) + a|Tleaf |

[a:叶子节点个数]类似于学习率.
叶⼦节点越多,loss函数越大.
每⼀一个节点对应的叶子节点,如果有叶⼦子节点,loss是多少,没有叶⼦节点,也就是剪枝后,loss⼜是多少,取少量为优.

此条目发表在Math分类目录。将固定链接加入收藏夹。

决策树信息熵数理剖析》有3条回应

  1. 纯情小白鼠说:

    我是小白 鼠
    求带带

  2. 须臾说:

    😯

发表评论

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