基于信息熵的决策树算法

type

Post

status

Published

date

Dec 16, 2022

slug

summary

1. 信息量 2. 信息熵 3. 基于信息熵的决策树算法流程

基于信息熵的决策树算法

信息量

信息熵

基于信息熵的决策树算法流程

信息量Information content (又名self-information, surprisal, or Shannon information)

定义：一个随机变量出现具体事件的概率

理解：某个特定结果的“surprise”；传输本事件的最佳编码所需要的信息长度

背景公理：

一个事件发生的概率是100%，那么就没有surprise，没有信息
一个事件发生概率越小，那么其的suprise越大，包含越多信息
如果有两个独立事件分别测量，他们的信息量是他们分别的信息量相加

公式：

公式含义：

：信息的单位（用什么进制就是多少）

b = 2,单位=bit；b = e,单位=nat；b=10,单位=hartleys；decimal digits；dits

：信息出现的概率
注：概率越大，信息量越小

例子：

规则的8面色子

扔一个规则的八面色子，出现1-8的概率分别是

假设我们知道扔出色子是4

那么传输这个事件所需的信息量

为什么需要这个信息量呢？我们来计算传输这个所需要的编码


#传统编码 表达1-8
000  -》1
001
010
011
100
101
110
111 -》8

信息熵

公式：

公式含义

每一个事件的信息量
每个事件发生的概率

优缺点

决策树优点

有限的区分数据
features is intutive
适合分类cate特性的数据

缺点：

容易overfit
accuracy不一定高

信息熵决策树算法

步骤

计算每个属性带来的信息获得信息熵计算器

A代表attribute

获得信息最高的属性成为新的节点或分支

如果获得信息为0，则停止分支开始计算到结果间的概率，连接起来

不断循环上述过程，直到所有分支都连向结果

例子

步骤

开始第一个循环，先找到选取的第一个节点

首先，计算information的值

对于属性X1的计算=属性X1出现T的概率属性X1为T所有结果的信息熵+属性X1出现F的概率属性X1为F所有结果的信息熵

$E(X_1)=X_1出现第一种可能性（T）的概率出现该概率结果的信息熵+X_1出现另一种可能性（F）的概率出现该概率结果的信息熵$

在第一个算法中之所以是计算$I(1,3)$和$I(3,0)$是因为,在T的情况中有1个是P，3个是N。在F的情况中有3个P。

因为X1能够获得的信息最多，所以选择$X_1$作为节点

计算X1且选择T时的信息获得

因为每个属性的信息获得都一样，随机选择一个节点，比如选择$X_2$作为新的节点

计算X1且选择F时的信息获得

因为这个节点本身信息量为0，所以信息获得只能为0，所以停止分支，直接进入结果

根据表格可知，这个节点上所有的结果都是P，故而进入P的概率是100%，因此选择P作为该分支的叶子

开始进行X2节点的运算

X2-T节点的运算

所以选择X4作为新的节点

X2-F节点的运算

因为这个节点本身信息量为0，所以信息获得只能为0，所以停止分支，直接进入结果

根据表格可知，这个节点上所有的结果都是N，故而进入N的概率是100%，因此选择N作为该分支的叶子

X4节点的运算

X4-T节点

因为这个节点本身信息量为0，所以信息获得只能为0，所以停止分支，直接进入结果

根据表格可知，这个节点上所有的结果都是N，故而进入N的概率是100%，因此选择N作为该分支的叶子

X4-F节点

因为只有X3属性了，所以连上X3

X3节点的运算

发现信息获得在这个节点上所以停止分支，直接进入结果

因为有一半结果是P，一半结果是N。这个节点有两片叶子，分别是50%P和50%N