信息
I
(
X
=
x
i
)
=
−
log
2
p
(
x
i
)
I(X=x_i)=-\log_2{p(x_i)}
I(X=xi)=−log2p(xi)
公式中的负号是为了确保信息为0/正；
底数只需满足大概率事件X对应于高的信息量即可。
I(x)：表示随机变量的信息；
p(xi)：当xi发生时的概率。
一个具体事件的信息量应该是随着其发生概率而递减的，且不能为负。
熵
在信息论和概率论中，熵度量随机变量的不确定性。信息熵考虑随机变量的所有可能取值，即所有可能发生事件所带来的信息量的期望，计算公式：
H
(
X
)
=
∑
i
=
1
n
p
(
x
i
)
I
(
x
i
)
=
−
∑
i
=
1
n
p
(
x
i
)
log
b
p
(
x
i
)
H(X)=\sum_{i=1}^np(x_i)I(x_i)=-\sum_{i=1}^np(x_i)\log_bp(x_i)
H(X)=∑i=1np(xi)I(xi)=−∑i=1np(xi)logbp(xi)
如果n表示X变量取值种类，那么p(xi)表示X变量取xi值占总体样本的比例。
熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性。熵越大，表明X=xi的不确定性越大。反之亦然。在机器学习分类中，熵越大表明这个类别的不确定性更大，反之越小。当随机变量的取值为两个时，熵随概率的变化曲线如图：
当p=0/1时，H§=0，随机变量完全没有不确定性；
当p=0.5时，H§=1，此时随机变量的不确定性最大。
示例：
X = [1 0 1 1 0] Y = [1 1 1 0 0]
p(X=0)=2/5 p(X=1)=3/5
p(Y=0)=2/5 p(Y=1)=3/5
H
(
X
)
=
−
2
/
5
×
log
(
2
/
5
)
−
3
/
5
×
log
(
3
/
5
)
=
0.292
H(X)=-2/5\times\log(2/5)-3/5\times\log(3/5)=0.292
H(X)=−2/5×log(2/5)−3/5×log(3/5)=0.292
H
(
Y
)
=
−
2
/
5
×
log
(
2
/
5
)
−
3
/
5
×
log
(
3
/
5
)
=
0.292
H(Y)=-2/5\times\log(2/5)-3/5\times\log(3/5)=0.292
H(Y)=−2/5×log(2/5)−3/5×log(3/5)=0.292
联合熵
随机变量X和Y的联合熵：
H
(
X
,
Y
)
=
∑
x
i
∈
X
∑
y
i
∈
Y
p
(
x
i
,
y
i
)
I
(
x
i
,
y
i
)
=
∑
x
i
∈
X
∑
y
i
∈
Y
p
(
x
i
,
y
i
)
log
1
p
(
x
i
,
y
i
)
H(X,Y)=\sum_{x_i\in X }\sum_{y_i\in Y}p(x_i, y_i)I(x_i, y_i)=\sum_{x_i\in X }\sum_{y_i\in Y}p(x_i, y_i)\log\frac{1}{p(x_i,y_i)}
H(X,Y)=∑xi∈X∑yi∈Yp(xi,yi)I(xi,yi)=∑xi∈X∑yi∈Yp(xi,yi)logp(xi,yi)1
可简写为：
H
(
X
,
Y
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
H(X,Y)=-\sum_{x, y}p(x, y)\log p(x, y)
H(X,Y)=−∑x,yp(x,y)logp(x,y)
联合熵
H
(
X
,
Y
)
H(X,Y)
H(X,Y)表示随机变量X和Y一起发生时的信息熵，即X和Y一起发生时的确定度，产生的信息量。
上例中：
p(X=0, Y=0)=1/5 p(X=0, Y=1)=1/5
p(X=1, Y=1)=1/5 p(X=1, Y=1)=2/5
H
(
X
,
Y
)
=
−
1
/
5
×
log
(
1
/
5
)
−
1
/
5
×
log
(
1
/
5
)
−
1
/
5
×
log
(
1
/
5
)
−
2
/
5
×
log
(
2
/
5
)
=
0.579
H(X, Y)=-1/5\times\log(1/5)-1/5\times\log(1/5)-1/5\times\log(1/5)-2/5\times\log(2/5)=0.579
H(X,Y)=−1/5×log(1/5)−1/5×log(1/5)−1/5×log(1/5)−2/5×log(2/5)=0.579
注：若有两个不相关的事件X和Y，即
p
(
x
,
y
)
=
p
(
x
)
×
p
(
y
)
p(x, y)=p(x)\times p(y)
p(x,y)=p(x)×p(y)，则两个事件同时发生时获得的信息量应该等于两者各自发生时获得的信息之和，即
H
(
X
,
Y
)
=
H
(
X
)
+
H
(
Y
)
H(X, Y)=H(X)+H(Y)
H(X,Y)=H(X)+H(Y)。
条件熵
随机变量X在给定条件下随机变量Y的条件熵，定义描述为：X给定条件下Y的条件概率分布的熵，公式：
H
(
Y
∣
X
)
=
∑
x
i
∈
X
p
(
x
i
)
H
(
Y
∣
X
=
x
i
)
=
∑
x
i
∈
X
p
(
x
i
)
∑
y
j
∈
Y
p
(
y
i
∣
x
i
)
log
1
p
(
y
j
∣
x
i
)
=
∑
x
i
∈
X
∑
y
j
∈
Y
p
(
x
i
)
p
(
y
j
∣
x
i
)
log
1
p
(
y
j
∣
x
i
)
=
∑
x
i
,
y
j
p
(
x
i
,
y
j
)
log
1
p
(
y
j
∣
x
i
)
\begin{aligned} H(Y|X) &=\sum_{x_i\in X }p(x_i)H(Y|X=x_i) \\ &=\sum_{x_i\in X }p(x_i)\sum_{y_j\in Y }p(y_i|x_i)\log\frac{1}{p(y_j|x_i)} \\ &=\sum_{x_i\in X }\sum_{y_j\in Y }p(x_i)p(y_j|x_i)\log\frac{1}{p(y_j|x_i)} \\ &=\sum_{x_i, y_j }p(x_i, y_j)\log\frac{1}{p(y_j|x_i)} \end{aligned}
H(Y∣X)=xi∈X∑p(xi)H(Y∣X=xi)=xi∈X∑p(xi)yj∈Y∑p(yi∣xi)logp(yj∣xi)1=xi∈X∑yj∈Y∑p(xi)p(yj∣xi)logp(yj∣xi)1=xi,yj∑p(xi,yj)logp(yj∣xi)1
可简写为：
H
(
Y
∣
X
)
=
∑
x
,
y
p
(
x
,
y
)
log
1
p
(
y
∣
x
)
H(Y|X)=\sum_{x, y}p(x, y)\log\frac{1}{p(y|x)}
H(Y∣X)=∑x,yp(x,y)logp(y∣x)1
条件熵与联合熵的关系
H
(
Y
∣
X
)
=
H
(
X
,
Y
)
−
H
(
X
)
H(Y|X)=H(X,Y)-H(X)
H(Y∣X)=H(X,Y)−H(X)
推导过程：
H
(
Y
∣
X
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
y
∣
x
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
p
(
x
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
+
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
+
∑
x
(
∑
y
p
(
x
,
y
)
)
log
p
(
x
)
=
−
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
,
y
)
+
∑
x
(
p
(
x
)
)
log
p
(
x
)
=
H
(
X
,
Y
)
−
H
(
X
)
\begin{aligned} H(Y|X) &=-\sum_{x,y}p(x, y)\log p(y|x) \\ &=-\sum_{x,y}p(x, y)\log \frac{p(x, y)}{p(x)} \\ &=-\sum_{x,y}p(x, y)\log p(x, y)+\sum_{x,y}p(x, y)\log p(x) \\ &=-\sum_{x,y}p(x, y)\log p(x, y)+\sum_{x}(\sum_yp(x, y))\log p(x) \\ &=-\sum_{x,y}p(x, y)\log p(x, y)+\sum_{x}(p(x))\log p(x) \\ &=H(X, Y)-H(X) \end{aligned}
H(Y∣X)=−x,y∑p(x,y)logp(y∣x)=−x,y∑p(x,y)logp(x)p(x,y)=−x,y∑p(x,y)logp(x,y)+x,y∑p(x,y)logp(x)=−x,y∑p(x,y)logp(x,y)+x∑(y∑p(x,y))logp(x)=−x,y∑p(x,y)logp(x,y)+x∑(p(x))logp(x)=H(X,Y)−H(X)
互信息
互信息量定义为后验概率和先验概率比值的对数：
I
(
x
i
;
y
i
)
=
log
p
(
x
i
∣
y
i
)
p
(
x
i
)
I(x_i; y_i)=\log\frac{p(x_i|y_i)}{p(x_i)}
I(xi;yi)=logp(xi)p(xi∣yi)
互信息（平均互信息量）：
I
(
X
;
Y
)
=
∑
x
i
∈
X
∑
y
i
∈
Y
p
(
x
i
,
y
i
)
log
p
(
x
i
∣
y
i
)
p
(
x
i
)
I(X; Y)=\sum_{x_i \in X}\sum_{y_i \in Y}p(x_i, y_i)\log\frac{p(x_i|y_i)}{p(x_i)}
I(X;Y)=∑xi∈X∑yi∈Yp(xi,yi)logp(xi)p(xi∣yi)
可简写为：
I
(
X
;
Y
)
=
∑
x
,
y
p
(
x
,
y
)
log
p
(
x
∣
y
)
p
(
x
)
I(X; Y)=\sum_{x, y}p(x, y)\log\frac{p(x|y)}{p(x)}
I(X;Y)=∑x,yp(x,y)logp(x)p(x∣y)
互信息的性质：
I
(
X
;
Y
)
=
H
(
X
)
−
H
(
X
∣
Y
)
=
H
(
Y
)
−
H
(
Y
∣
X
)
=
I
(
Y
;
X
)
I(X; Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=I(Y; X)
I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)=I(Y;X)
互信息的理解：
H
(
X
)
H(X)
H(X)是X的不确定度，
H
(
X
∣
Y
)
H(X|Y)
H(X∣Y)是Y已知时，X的不确定度，则
I
(
X
;
Y
)
=
H
(
X
)
−
H
(
X
∣
Y
)
I(X; Y)=H(X)-H(X|Y)
I(X;Y)=H(X)−H(X∣Y)表示Y已知，使得X的不确定度减少了
I
(
X
;
Y
)
I(X; Y)
I(X;Y)。Y已知时，X的不确定度为
H
(
X
∣
Y
)
=
H
(
X
)
−
I
(
X
;
Y
)
H(X|Y)=H(X)-I(X; Y)
H(X∣Y)=H(X)−I(X;Y)。
决策树 - 信息增益，信息增益率，基尼系数
决策树是表示基于特征对实例进行分类的树形结构。从给定的训练数据集中 ，依据特征选择的准则，递归的选择最优划分特征，并根据此特征将训练数据进行分割，使得各子数据集有一个最好的分类的过程。决策树算法的三要素：特征选择；决策树生成；决策树剪枝。
构建决策树的基本思想：随着树的深度的增加，结点的熵迅速地降低，熵降低的速度越快越好，就能得到一颗较矮的树。
信息增益（ID3算法）
信息增益在决策树算法中理解为使用划分前后集合熵的差值，来衡量使用当前特征对于样本集合划分效果的好坏，是用来选择特征的指标，信息增益越大，则这个特征的选择性越好。在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差（信息熵-条件熵），即：
I
G
(
Y
∣
X
)
=
H
(
Y
)
−
H
(
Y
∣
X
)
IG(Y|X)=H(Y)-H(Y|X)
IG(Y∣X)=H(Y)−H(Y∣X)
示例：
随机变量X - [矮 矮 矮 高 矮 矮 高 中 中 高 矮 矮 ]
随机变量Y - [不嫁 不嫁 嫁 嫁 不嫁 不嫁 嫁 嫁 嫁 嫁 不嫁 不嫁]
H
(
Y
)
=
−
6
/
12
×
log
(
6
/
12
)
−
6
/
12
×
log
(
6
/
12
)
=
0.301
H(Y)=-6/12\times\log(6/12)-6/12\times\log(6/12)=0.301
H(Y)=−6/12×log(6/12)−6/12×log(6/12)=0.301
H
(
Y
∣
X
=
矮
)
=
−
1
/
7
×
log
(
1
/
7
)
−
6
/
7
×
log
(
6
/
7
)
=
0.178
H(Y|X=矮)=-1/7\times\log(1/7)-6/7\times\log(6/7)=0.178
H(Y∣X=矮)=−1/7×log(1/7)−6/7×log(6/7)=0.178
H
(
Y
∣
X
=
中
)
=
−
1
×
log
(
1
)
−
0
=
0
H(Y|X=中)=-1\times\log(1)-0=0
H(Y∣X=中)=−1×log(1)−0=0
H
(
Y
∣
X
=
高
)
=
−
1
×
log
(
1
)
−
0
=
0
H(Y|X=高)=-1\times\log(1)-0=0
H(Y∣X=高)=−1×log(1)−0=0
p
(
X
=
矮
)
=
7
/
12
p(X=矮)=7/12
p(X=矮)=7/12
p
(
X
=
中
)
=
2
/
12
p(X=中)=2/12
p(X=中)=2/12
p
(
X
=
高
)
=
3
/
12
p(X=高)=3/12
p(X=高)=3/12
可得：
H
(
Y
∣
X
)
=
∑
x
i
∈
X
p
(
x
i
)
H
(
Y
∣
X
=
x
i
)
=
7
/
12
×
0.178
+
2
/
12
×
0
+
3
/
12
×
0
=
0.103
H(Y|X)=\sum_{x_i\in X }p(x_i)H(Y|X=x_i)=7/12\times0.178+2/12\times0+3/12\times0=0.103
H(Y∣X)=∑xi∈Xp(xi)H(Y∣X=xi)=7/12×0.178+2/12×0+3/12×0=0.103
那么信息增益为0.301-0.103=0.198，即表示在知道了身高信息后，嫁/不嫁的不确定度由0.301降为了0.198
缺点：信息增益偏向取值较多的特征。
信息增益率（C4.5算法）
信息增益率 = 惩罚参数 * 信息增益，本质是在信息增益的基础之上乘上一个惩罚参数。特征个数越多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
惩罚参数的计算公式：
惩
罚
参
数
=
1
H
(
X
)
惩罚参数=\frac{1}{H(X)}
惩罚参数=H(X)1，即数据集Y以特征X作为随机变量的熵的倒数，换句话说是将特征X取值相同的样本划分到同一个子集中。
I
G
R
(
Y
∣
X
)
=
H
(
Y
)
−
H
(
Y
∣
X
)
H
(
X
)
IG_R(Y|X)=\frac{H(Y)-H(Y|X)}{H(X)}
IGR(Y∣X)=H(X)H(Y)−H(Y∣X)
缺点：信息增益率偏向取值较少的特征。因此，C4.5并不是直接选择信息增益率最大的属性作为划分属性，而是之前先通过一遍筛选，先把信息增益低于平均水平的属性剔除掉，之后从剩下的属性中选择信息增益率最高的，这样就兼顾了两个方面。
基尼系数（CART算法-分类树）
基尼系数表示在样本集合中一个随机选中的样本被分错的概率。基尼系数越小表示集合中被选中的样本被分错的概率越小，即集合的纯度越高，反之集合纯度越低。计算公式为：基尼系数=样本被选中的概率*样本被分错的概率。表示为：
G
i
n
i
(
p
)
=
∑
k
=
1
K
p
k
(
1
−
p
k
)
=
1
−
∑
k
=
1
K
p
k
2
Gini(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2
Gini(p)=∑k=1Kpk(1−pk)=1−∑k=1Kpk2，
p
k
p_k
pk表示选中的样本属于
k
k
k类别的概率，则这个样本被分错的概率是
1
−
p
k
1-p_k
1−pk；
样本集合中有
K
K
K个类别，一个随机选中的样本可以属于这
K
K
K个类别中的任意一个，因此对类别就加起来求和；
当目标是二分类的时候，
G
i
n
i
(
p
)
=
2
p
(
1
−
p
)
Gini(p)=2p(1-p)
Gini(p)=2p(1−p)。
文字说明：CART是二叉树，即当使用某个特征划分样本集合时，只有两个集合，一个是等于给定的特征值的样本集合，另一个是不等于给定的特征值的样本集合。实质上是对拥有多个取值的特征的二值处理。
公式说明：
D
1
=
{
D
∣
A
=
a
}
D_1=\{D|A=a\}
D1={D∣A=a}
D
2
=
{
D
∣
A
≠
a
}
D_2=\{D|A\neq a\}
D2={D∣A=a}
那么
G
i
n
i
(
D
,
A
)
=
∣
D
1
∣
∣
D
∣
G
i
n
i
(
D
1
)
+
∣
D
2
∣
∣
D
∣
G
i
n
i
(
D
2
)
Gini(D, A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)
Gini(D,A)=∣D∣∣D1∣Gini(D1)+∣D∣∣D2∣Gini(D2)
最优划分属性，即对一个具有超过2个取值的特征，需要计算以每一个取值为划分点，对样本集D划分之后子集的基尼系数，其中使得基尼系数最小的划分点就是使用特征A对样本集合D进行划分的最佳划分点。
示例：
| label=0 | label=1 | 总计 | |
|---|---|---|---|
| <36.5 | 127 | 14 | 141 |
| >36.5 | 103 | 56 | 159 |
| 总计 | 230 | 70 |
a
=
G
i
n
i
(
l
e
f
t
[
a
g
e
<
36.5
]
)
=
1
−
(
127
141
)
2
−
(
14
141
)
2
=
0.178864
a=Gini(left[age<36.5])=1-(\frac{127}{141})^2-(\frac{14}{141})^2=0.178864
a=Gini(left[age<36.5])=1−(141127)2−(14114)2=0.178864
b
=
G
i
n
i
(
r
i
g
h
t
[
a
g
e
>
36.5
]
)
=
1
−
(
103
159
)
2
−
(
56
159
)
2
=
0.456311
b=Gini(right[age>36.5])=1-(\frac{103}{159})^2-(\frac{56}{159})^2=0.456311
b=Gini(right[age>36.5])=1−(159103)2−(15956)2=0.456311
G
i
n
i
(
36.5
)
=
141
300
×
a
+
159
300
×
b
=
0.358
Gini(36.5)=\frac{141}{300}\times a+\frac{159}{300}\times b=0.358
Gini(36.5)=300141×a+300159×b=0.358
参考链接：
信息熵、信息增益、信息增益率、gini、woe、iv、VIF
决策树–信息增益，信息增益比，Geni指数的理解