概要
信息增益表示得知特征A的信息而使得类Z的信息的不确定性减少的程度。
特征A对数据集D的信息增益 G(D,A),定义为集合的信息熵 H(D) 与特征A给定条件下D的信息条件熵 H(D|A) 之差,即公式为:
G
(
D
,
A
)
=
H
(
D
)
−
H
(
D
∣
A
)
G(D,A)=H(D)-H(D|A)
G(D,A)=H(D)−H(D∣A)
由贷款数据来看我们的公式:
信息熵的计算:
H
(
D
)
=
−
∑
k
=
1
K
∣
C
k
∣
∣
D
∣
log
2
∣
C
k
∣
∣
D
∣
H(D)=-\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log_{2}\frac{|C_k|}{|D|}
H(D)=−k=1∑K∣D∣∣Ck∣log2∣D∣∣Ck∣
条件熵的计算:
H
(
D
∣
A
)
=
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
H
(
D
i
)
=
−
∑
i
=
1
n
∣
D
i
∣
∣
D
∣
∑
k
=
1
K
∣
D
i
k
∣
∣
D
i
∣
log
2
∣
D
i
k
∣
∣
D
i
∣
H(D|A)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^{n}\frac{|D_i|}{|D|}\sum_{k=1}^{K}\frac{|D_{ik}|}{|D_i|}\log_{2}\frac{|D_{ik}|}{|D_i|}
H(D∣A)=i=1∑n∣D∣∣Di∣H(Di)=−i=1∑n∣D∣∣Di∣k=1∑K∣Di∣∣Dik∣log2∣Di∣∣Dik∣
注:
C
k
C_k
Ck表示属于某个类别的样本数。
实例一
样本D如下(银行贷款数据):
序号 |
年龄 |
有工作 |
有自己的房子 |
信贷情况 |
类别 |
1 |
青年 |
否 |
否 |
一般 |
否 |
2 |
青年 |
否 |
否 |
好 |
否 |
3 |
青年 |
是 |
否 |
好 |
是 |
4 |
青年 |
是 |
是 |
一般 |
是 |
5 |
青年 |
否 |
否 |
一般 |
否 |
6 |
中年 |
否 |
否 |
一般 |
否 |
7 |
中年 |
否 |
否 |
好 |
否 |
8 |
中年 |
是 |
是 |
好 |
是 |
9 |
中年 |
否 |
是 |
非常好 |
是 |
10 |
中年 |
否 |
是 |
非常好 |
是 |
11 |
老年 |
否 |
是 |
非常好 |
是 |
12 |
老年 |
否 |
是 |
好 |
是 |
13 |
老年 |
是 |
否 |
好 |
是 |
14 |
老年 |
是 |
否 |
非常好 |
是 |
15 |
老年 |
否 |
否 |
一般 |
否 |
样本信息熵:
H
(
D
)
=
−
(
9
15
log
2
9
15
+
6
15
log
2
6
15
)
=
0.97095
H(D)=-(\frac{9}{15}\log_{2}\frac{9}{15}+\frac{6}{15}\log_{2}\frac{6}{15})=0.97095
H(D)=−(159log2159+156log2156)=0.97095
求样本信息熵时,只看类别这一列。因为其他的列都是特征列,是决定类别的值的因素。
年龄的信息增益:
G
(
D
,
年
龄
)
=
H
(
D
)
−
H
(
D
∣
年
龄
)
G(D,年龄)=H(D)-H(D|年龄)
G(D,年龄)=H(D)−H(D∣年龄)
将数据代入计算:
G
(
D
,
年
龄
)
=
0.97095
−
(
5
15
H
(
青
年
)
+
5
15
H
(
中
年
)
+
5
15
H
(
老
年
)
)
G(D,年龄)=0.97095-(\frac{5}{15}H(青年)+\frac{5}{15}H(中年)+\frac{5}{15}H(老年))
G(D,年龄)=0.97095−(155H(青年)+155H(中年)+155H(老年))
解析:年龄一共有三类,总数是15,青年有5个,中年有5个,老年有5个
- 在年龄为青年条件下,类别为“是”的有两个,类别为“否”的有三个
H
(
青
年
)
=
−
(
2
5
log
2
2
5
+
3
5
log
2
3
5
)
=
0.97095
H(青年)=-(\frac{2}{5}\log_{2}\frac{2}{5}+\frac{3}{5}\log_{2}\frac{3}{5})=0.97095
H(青年)=−(52log252+53log253)=0.97095
- 在年龄为中年条件下,类别为“是”的有三个,类别为“否”的有两个
H
(
中
年
)
=
−
(
3
5
log
2
3
5
+
3
5
log
2
2
5
)
=
0.97095
H(中年)=-(\frac{3}{5}\log_{2}\frac{3}{5}+\frac{3}{5}\log_{2}\frac{2}{5})=0.97095
H(中年)=−(53log253+53log252)=0.97095
- 在年龄为老年条件下,类别为“是”的有四个,类别为“否”的有一个
H
(
老
年
)
=
−
(
4
5
log
2
4
5
+
1
5
log
2
1
5
)
=
0.7219281
H(老年)=-(\frac{4}{5}\log_{2}\frac{4}{5}+\frac{1}{5}\log_{2}\frac{1}{5})=0.7219281
H(老年)=−(54log254+51log251)=0.7219281
最终结果:G(D,年龄)=0.083
同理:
工作 |
房子 |
信贷 |
G(D,工作)=H(D)-H(D/工作) |
G
(
D
,
房
子
)
=
H
(
D
)
−
H
(
D
/
房
子
)
G(D,房子)=H(D)-H(D/房子)
G(D,房子)=H(D)−H(D/房子) |
G
(
D
,
信
贷
)
=
H
(
D
)
−
H
(
D
/
信
贷
)
G(D,信贷)=H(D)-H(D/信贷)
G(D,信贷)=H(D)−H(D/信贷) |
G
(
D
,
工
作
)
=
0.97095
−
(
5
15
H
(
有
工
作
)
+
10
15
H
(
没
工
作
)
)
G(D,工作)=0.97095-(\frac{5}{15}H(有工作)+\frac{10}{15}H(没工作))
G(D,工作)=0.97095−(155H(有工作)+1510H(没工作)) |
G
(
D
,
房
子
)
=
0.97095
−
(
6
15
H
(
有
房
子
)
+
9
15
H
(
没
房
子
)
)
G(D,房子)=0.97095-(\frac{6}{15}H(有房子)+\frac{9}{15}H(没房子))
G(D,房子)=0.97095−(156H(有房子)+159H(没房子)) |
G
(
D
,
信
贷
)
=
0.97095
−
(
5
15
H
(
一
般
)
+
6
15
H
(
好
)
+
4
15
H
(
非
常
好
)
)
G(D,信贷)=0.97095-(\frac{5}{15}H(一般)+\frac{6}{15}H(好)+\frac{4}{15}H(非常好))
G(D,信贷)=0.97095−(155H(一般)+156H(好)+154H(非常好)) |
H
(
有
工
作
)
=
−
(
5
5
log
2
5
5
+
0
5
log
2
0
5
)
=
0
H(有工作)=-(\frac{5}{5}\log_{2}\frac{5}{5}+\frac{0}{5}\log_{2}\frac{0}{5})=0
H(有工作)=−(55log255+50log250)=0 |
H
(
有
房
子
)
=
−
(
6
6
log
2
6
6
+
0
6
log
2
0
6
)
=
0
H(有房子)=-(\frac{6}{6}\log_{2}\frac{6}{6}+\frac{0}{6}\log_{2}\frac{0}{6})=0
H(有房子)=−(66log266+60log260)=0 |
H
(
一
般
)
=
−
(
1
5
log
2
1
5
+
4
5
log
2
4
5
)
H(一般)=-(\frac{1}{5}\log_{2}\frac{1}{5}+\frac{4}{5}\log_{2}\frac{4}{5})
H(一般)=−(51log251+54log254) |
H
(
没
工
作
)
=
−
(
4
10
log
2
4
10
+
6
10
log
2
6
10
)
H(没工作)=-(\frac{4}{10}\log_{2}\frac{4}{10}+\frac{6}{10}\log_{2}\frac{6}{10})
H(没工作)=−(104log2104+106log2106) |
H
(
没
房
子
)
=
−
(
3
9
log
2
3
9
+
6
9
log
2
6
9
)
H(没房子)=-(\frac{3}{9}\log_{2}\frac{3}{9}+\frac{6}{9}\log_{2}\frac{6}{9})
H(没房子)=−(93log293+96log296) |
H
(
好
)
=
−
(
4
6
log
2
4
6
+
2
6
log
2
2
6
)
H(好)=-(\frac{4}{6}\log_{2}\frac{4}{6}+\frac{2}{6}\log_{2}\frac{2}{6})
H(好)=−(64log264+62log262) |
|
|
H
(
非
常
好
)
=
−
(
4
4
log
2
4
4
+
0
4
log
2
0
4
)
=
0
H(非常好)=-(\frac{4}{4}\log_{2}\frac{4}{4}+\frac{0}{4}\log_{2}\frac{0}{4})=0
H(非常好)=−(44log244+40log240)=0 |
信息增益(Information Gain)的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。也就是以下代码的计算思路。
import numpy as np
import pandas as pd
def createDataset():
# 银行贷款数据
row_data = {
'年龄': ['青年','青年','青年','青年','青年','中年','中年','中年','中年','中年','老年','老年','老年','老年','老年'],
'有工作': ['否', '否', '是', '是', '否', '否', '否', '是', '否', '否', '否', '否', '是', '是', '否',],
'有房子': ['否', '否', '否', '是', '否', '否', '否', '是', '是', '是', '是', '是', '否', '否', '否',],
'信贷情况': ['一般','好','好','一般','一般','一般', '好', '好','非常好','非常好','非常好','好','好','非常好','一般'],
'类型': ['否', '否', '是', '是', '否', '否', '否', '是', '是', '是', '是', '是', '是', '是', '否',]
}
dataset = pd.DataFrame(row_data)
return dataset
"""
函数功能:计算香农熵(信息熵):解决了对信息的量化度量问题
参数说明: dataSet:原始数据集
返回:ent:香农熵
"""
def calEnt(dataSet):
n = dataSet.shape[0] # 数据集总行数
iset = dataSet.iloc[:,-1].value_counts() # 标签的所有类别
p = iset/n # 每一类标签所占比
ent = (-p*np.log2(p)).sum() # 计算信息熵
return ent
"""
函数功能:根据信息增益选择出最佳数据集切分的列
参数说明: dataSet:原始数据集
返回:axis:数据集各特征列的信息增益(字典形式,降序排序)
"""
def bestSplit(dataSet):
baseEnt = calEnt(dataSet) # 原始信息熵
axis = {} # 存放对应列的序号,以及它的信息增益
for i in range(dataSet.shape[1]-1): # 对特征的每一列进行循环
levels= dataSet.iloc[:,i].value_counts().index # 提取出当前列的所有取值
ents = 0
for j in levels:
childSet = dataSet[dataSet.iloc[:,i]==j] # 筛选dataframe
ent = calEnt(childSet)
ents += (childSet.shape[0]/dataSet.shape[0])*ent # 计算当前列的信息熵
# print(f'第{i}列的信息熵为{ents}')
infoGain = baseEnt - ents # 计算当前列的信息增益
print(f'第{i}列的信息增益为{infoGain}')
axis["第"+str(i)+"列"] = infoGain
axis = sorted(axis.items(), key=lambda elem:elem[1], reverse=True)
return axis
DataSet = createDataset()
h = calEnt(DataSet)
dit = bestSplit(DataSet)
print(f"样本的信息熵为:{h}")
print(f"信息增益字典:{dit}")
'''
第0列的信息增益为0.08300749985576883
第1列的信息增益为0.32365019815155627
第2列的信息增益为0.4199730940219749
第3列的信息增益为0.36298956253708536
样本的信息熵为:0.9709505944546686
信息增益字典:[('第2列', 0.4199730940219749), ('第3列', 0.36298956253708536), ('第1列', 0.32365019815155627), ('第0列', 0.08300749985576883)]
'''
实例二
海洋生物数据
序号 |
no surfacing |
flippers |
fish |
1 |
1 |
1 |
yes |
2 |
1 |
1 |
yes |
3 |
1 |
0 |
no |
4 |
0 |
1 |
no |
5 |
0 |
1 |
no |
这是另一个不说人话的版本,但核心内容都差不多,官方解释都难理解:
假设离散属性a有V个可能的取值
{
a
1
,
a
2
,
.
.
.
,
a
V
}
\lbrace a^1,a^2,...,a^V \rbrace
{a1,a2,...,aV},若使用a对样本数据集D进行划分,则会产生V个分支节点。其中第v个分支节点包含了D中所有在属性a上取值为
a
v
a^v
av的样本,记为
D
v
D^v
Dv。我们可根据信息熵的计算公式计算出
D
v
D^v
Dv的信息熵,再考虑到不同的分支节点所包含的样本数不同,给分支节点赋予权重
∣
D
v
∣
∣
D
∣
\frac{|D^v|}{|D|}
∣D∣∣Dv∣。
所以信息增益的计算公式为:
G
a
n
i
(
D
,
a
)
=
E
n
t
(
D
)
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
E
n
t
(
D
v
)
Gani(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
Gani(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
海洋生物数据集中第0列的信息增益:
G
a
n
i
(
D
,
a
)
=
E
n
t
(
D
)
−
∑
v
=
1
V
∣
D
v
∣
∣
D
∣
E
n
t
(
D
v
)
Gani(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
Gani(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
G
a
i
n
(
′
N
o
S
u
r
f
a
c
i
n
g
′
)
=
E
n
t
(
D
)
−
[
3
5
E
n
t
(
D
1
)
+
2
5
E
n
t
(
D
2
)
]
=
c
a
l
E
n
t
(
D
a
t
a
S
e
t
)
−
[
3
5
(
−
2
3
log
2
2
3
−
1
3
log
2
1
3
)
+
2
5
(
−
2
2
log
2
2
2
)
]
=
0.97
−
0.55
=
0.42
\begin{aligned} Gain('NoSurfacing') &= Ent(D) - [\frac{3}{5}Ent(D_1)+\frac{2}{5}Ent(D_2)] \\ & = calEnt(DataSet) - [ \frac{3}{5} (-\frac{2}{3}\log_{2}\frac{2}{3} - \frac{1}{3}\log_{2}\frac{1}{3} ) + \frac{2}{5} ( -\frac{2}{2}\log_{2}\frac{2}{2}) ] \\ & = 0.97-0.55 \\ & = 0.42 \\ \end{aligned}
Gain(′NoSurfacing′)=Ent(D)−[53Ent(D1)+52Ent(D2)]=calEnt(DataSet)−[53(−32log232−31log231)+52(−22log222)]=0.97−0.55=0.42
import numpy as np
import pandas as pd
def createDataset():
# 海洋生物数据集
row_data = {
'no surfacing': [1, 1, 1, 0, 0],
'flippers': [1, 1, 0, 1, 1],
'fish': ['yes', 'yes', 'no', 'no', 'no']
}
dataset = pd.DataFrame(row_data)
return dataset
def calEnt(dataSet):
n = dataSet.shape[0] # 数据集总行数
iset = dataSet.iloc[:,-1].value_counts() # 标签的所有类别
p = iset/n # 每一类标签所占比
ent = (-p*np.log2(p)).sum() # 计算信息熵
return ent
def bestSplit(dataSet):
baseEnt = calEnt(dataSet) # 原始信息熵
axis = {} # 存放对应列的序号,以及它的信息增益
for i in range(dataSet.shape[1]-1): # 对特征的每一列进行循环
levels= dataSet.iloc[:,i].value_counts().index # 提取出当前列的所有取值
ents = 0
for j in levels:
childSet = dataSet[dataSet.iloc[:,i]==j] # 筛选dataframe
ent = calEnt(childSet)
ents += (childSet.shape[0]/dataSet.shape[0])*ent # 计算当前列的信息熵
# print(f'第{i}列的信息熵为{ents}')
infoGain = baseEnt - ents # 计算当前列的信息增益
print(f'第{i}列的信息增益为{infoGain}')
axis["第"+str(i)+"列"] = infoGain
axis = sorted(axis.items(), key=lambda elem:elem[1], reverse=True)
return axis
DataSet = createDataset()
h = calEnt(DataSet)
dit = bestSplit(DataSet)
print(f"样本的信息熵为:{h}")
print(f"信息增益字典:{dit}")
'''
第0列的信息增益为0.4199730940219749
第1列的信息增益为0.17095059445466854
样本的信息熵为:0.9709505944546686
信息增益字典:[('第0列', 0.4199730940219749), ('第1列', 0.17095059445466854)]
'''