计算离散随机变量的信息熵可以直接使用如下公式进行计算。
H
(
x
)
=
−
∑
i
=
1
N
p
(
x
i
)
l
o
g
(
p
(
x
i
)
)
H(x)=-\sum_{i=1}^{N}{p(x_i)log(p(x_i))}
H(x)=−i=1∑Np(xi)log(p(xi))
其中
N
N
N是变量
x
x
x在数据集中的样本数量,
p
(
x
i
)
p(x_i)
p(xi)是
x
i
x_i
xi值在整个数据集中出现的频率。
1.该方法最早由Kozachenko & Leonenko[1]在1987年提出的,基于该方法的一系列改进公式称为经典k-近邻(classical k-NN)。可以参考网站:Kozachenko-Leonenko estimator。在
D
D
D维空间中的经典k-近邻估计计算公式[2]为:
H
(
x
)
≈
ψ
(
N
)
−
ψ
(
k
)
+
l
o
g
(
c
D
)
+
D
N
∑
i
=
1
N
l
o
g
(
ε
i
)
H(x)\approx\psi(N)-\psi(k)+log(c_D)+\frac{D}{N}\sum_{i=1}^{N}log(\varepsilon_i)
H(x)≈ψ(N)−ψ(k)+log(cD)+NDi=1∑Nlog(εi)
其中,
ψ
\psi
ψ是Digamma函数,
ε
i
\varepsilon_i
εi是
x
i
x_i
xi到它第
k
k
k个邻居的欧式距离(Euclidean distance),
x
i
x_i
xi是变量
x
x
x的一个采样点,
c
D
=
π
D
2
Γ
(
1
+
D
2
)
c_D=\frac{\pi\frac{D}{2}}{\Gamma(1+\frac{D}{2})}
cD=Γ(1+2D)π2D,而
Γ
\Gamma
Γ是Gamma函数。其他关于该公式的详细描述可以参考原文:https://homepages.tuni.fi/jaakko.peltonen/online-papers/lu2020aaai.pdf。
2.Gamma函数是阶乘函数 x ! x! x!在实数范围上的拓展,而Digamma函数是Gamma函数的对数的导数。其具体的定义式可以自行搜索。Gamma函数和Digamma函数虽然定义比较复杂,但是它们的特殊值可以很方便地使用递推公式来计算。
互信息是基于熵来计算的,用来表示两个随机变量的熵的重叠部分。当两个变量独立的时候,它们的互信息为0。两个离散随机变量的互信息计算公式为:
I
(
x
;
y
)
=
∑
i
,
j
p
(
i
,
j
)
l
o
g
p
(
i
,
j
)
p
x
(
i
)
p
y
(
j
)
I(x;y)=\sum_{i,j}p(i,j)log\frac{p(i,j)}{p_{x}(i)p_y(j)}
I(x;y)=i,j∑p(i,j)logpx(i)py(j)p(i,j)
其中,
p
(
i
,
j
)
p(i,j)
p(i,j)是
x
=
x
i
x=x_i
x=xi和
y
=
y
j
y=y_j
y=yj同时在整个数据集中出现的频率,
p
x
(
i
)
p_{x}(i)
px(i)是
x
=
x
i
x=x_i
x=xi在整个数据集中出现的频率,
p
y
(
j
)
p_{y}(j)
py(j)是
y
=
y
j
y=y_j
y=yj在整个数据集中出现的频率。
两个连续随机变量的互信息计算也是基于k-近邻估计,由Kraskov等人[3]在2004年提出。其中提出了两种基于k-近邻的计算的方法,此处仅给出第一种方法的公式:
I
(
x
;
y
)
≈
ψ
(
k
)
−
<
ψ
(
n
x
+
1
)
+
ψ
(
n
y
+
1
)
>
+
ψ
(
N
)
I(x;y)\approx\psi(k)-<\psi(n_x+1)+\psi(n_y+1)>+\psi(N)
I(x;y)≈ψ(k)−<ψ(nx+1)+ψ(ny+1)>+ψ(N)
其中,
<
.
.
.
>
<...>
<...>意为求
N
N
N个点的均值。该公式的更详细描述可以参见[3]或者博客:机器学习特征选择:传统互信息、k-nearest neighbor互信息。
from sklearn.feature_selection import mutual_info_regression
该方法是基于k-近邻的两个连续随机变量互信息估计的拓展,由Ross[4]在2014年提出,该计算方法也在python的sklearn.feature_selection库的源码中使用,详细的实现可以参考其源码。其计算公式为:
I
(
x
;
y
)
≈
ψ
(
N
)
−
<
ψ
(
N
x
)
>
+
ψ
(
k
)
−
<
ψ
(
m
)
>
I(x;y)\approx\psi(N)-<\psi(N_x)>+\psi(k)-<\psi(m)>
I(x;y)≈ψ(N)−<ψ(Nx)>+ψ(k)−<ψ(m)>
其中,
N
x
i
N_{x_i}
Nxi是和
x
i
x_i
xi有相同离散值的点数,
m
i
m_i
mi是在
N
x
i
N_{x_i}
Nxi个点中确定了第k个邻居后,在该邻居之内的点数。
一般来说,k越小,统计误差越大,系统误差越小,k越大则相反。通常k取3,这个也是sklearn.feature_selection库中默认的k值。
但值得注意的是,如果x和y一个是在离散域上定义,一个是在连续域上定义,那么它们虽然可以用上面给的公式计算,但是由于它们的计算原理不同,可能效果会没有那么理想。但也不失为一种在信息领域的度量方式吧。
[1]Kozachenko L F, Leonenko N N. Sample estimate of the entropy of a random vector[J]. Problemy Peredachi Informatsii, 1987, 23(2): 9-16.
[2]Lu C, Peltonen J. Enhancing Nearest Neighbor Based Entropy Estimator for High Dimensional Distributions via Bootstrapping Local Ellipsoid[C]. Proceedings of the AAAI Conference on Artificial Intelligence. 2020, 34(04): 5013-5020.
[3]Kraskov A, Stögbauer H, Grassberger P. Estimating mutual information[J]. Physical review E, 2004, 69(6): 066138.
[4]Ross B C. Mutual information between discrete and continuous data sets[J]. PloS one, 2014, 9(2): e87357.
联系客服