首页 > 数据可视化 > 信息熵应用随笔4:使用多维直方图进行多种统计量计算
2019
02-17

信息熵应用随笔4:使用多维直方图进行多种统计量计算

上节我们讨论了多维直方图的多维数组压缩存储法。这一节讨论在使用此压缩存储法的情况下,如何高效地计算重要的统计值。

一、计算联合熵

设p(x1, … , xn)是离散型随机变量X, … , Xn的联合概率分布。联合熵的计算公式如下所示:

(1)

设我们已经求出了随机变量X1, … , Xn构成的多维联合直方图,使用多维数组压缩保存法,其字典表记做 Dj=P[x1 … xn] = p(x1, … , xn) !=0, 其中j是字典表的下标,最大等于直方图中所有非零项的个数。 即直方图中所有非零项都用键值对表示了。

按照公式(1)来计算联合熵H(x1, … , xn),显然关键在于 p(x1, … , xn)与log( p(x1, … , xn) )的乘积。对于那些p(x1, … , xn) = 0 的项来说,p(x1, … , xn)log( p(x1, … , xn) )=0,故可以忽略直方图中所有零项。而剩余的非零项,已经以键值对的形式存储在字典表里了。所以只需要将字典表里的每一项,计算该项和它的对数之间的乘积,再累加起来求负数就是了。写作公式即:H(x1, … , xn) = -∑j Dj * log(Dj)

二、计算条件熵

根据新的多维数组压缩存储法,已经可以计算条件概率直方图。在上一篇随笔的三.3节已经有所描述。这里再复习一下:

给定n个变量的变量集V=V0,V1,…,Vn-1,V有一个子集U ⊂ V, 和另一个子集W∈(V-U)。条件直方图的运算,是计算W中的变量在特定的bin范围下在U中的分布。

  1. 计算条件直方图

当用户要研究一组变量U和另一组变量W之间的关系时,条件直方图是非常有用的。计算条件直方图的第一步是为w中的变量选择属于特定bin范围的所有条目。对于此选择步骤,我们需要对w中的变量进行解码,以获得其原始bin索引。然后,对于每个选定的条目,使用位掩码执行逻辑与操作,以将与U中的变量不对应的所有位设置为0。通过对具有相同索引的条目的频率求和来计算最终结果。

也是让我们看一个具体的例子:有一个具体的4维直方图,包含A,B,C,D,四个变量,每个变量有16个bin。其字典表如图7(1)所示。假设U包含两个变量B和C,W包含两个变量A和D。A的数值范围是(minA, maxA),D的数值范围是(minD, maxD),这条件直方图的查询操作定义为:

P(bin(B)=b, bin(C)=c |  minA  ≤ bin(A) ≤ maxA , minD  ≤ bin(D) ≤ maxD ) =  ∑a=minAd=minD P(bin(A)=a, bin(B)=b, bin(C)=c, bin(D)=d)

图7,条件直方图的运算示例

现在要求查询 P(A|11 ≤ bin(C≤ 15) 。我们首先将C的bin索引解码,获得原始的bin索引,然后选定11 ≤ bin(C≤ 15范围内的频率,如图7(2)绿色部分所示。接下来设置掩码,掩码只有要查询的A变量索引位是1,其他不查询的变量对应的索引位都是0,如图7(3)所示。接下来将图7(2)选定的绿色项与掩码按位与,并将相同bin索引的频率求和。最后得到的条件直方图的字典表,如图7(5)所示。在数据空间转换完毕后,每个变量有4个bin。

2.依据条件直方图计算条件熵

给定n个变量的变量集V=V0,V1,…,Vn-1,V有一个子集U ⊂ V, 和另一个子集W∈(V-U)。假设我们已经计算出了P(U|W)的条件直方图,其字典表记做D(U|W)。接下来计算条件熵H(U|W)。它表示在特定值的范围内,给定W中的变量,U的不确定性。条件熵H(U|W)的计算公式如下:

H(U|W) = – ∑ p(V) log (p(U|W))

其中p(V)代表变量集V的中全部变量构成的概率分布。显然V的多变量联合直方图的字典表D(V)已经保存了全部非零的p(V), 将其中每一项D(V)j 取出作为p(V)使用即可。p(U|W)代表的条件概率分布,则保存在已经计算好的P(U|W)的条件直方图中,将其中每一项D(U|W)j取出即可。

最终H(U|W)  =   – ∑j D(V)j log (D(U|W)j), j∈[1, m], m为字典表D(V)的长度,也是字典表D(U|W)的长度

三、计算信息增益

已经能计算联合熵和条件熵的情况下,计算信息增益就水到渠成了。

给定包含n个离散型随机变量的变量集V=V0,V1,…,Vn-1,其中一个变量V的信息增益IG(V)等于:

IG(V) = H(V1, … , Vn) – H(V1, … , Vn | V)

=  -∑j D(V)j * log(D(V)j) – [-  ∑j D(V)j log (D(U|W)j)],

= – ∑j D(V)j [log(D(V)j)  –  log (D(U|W)j],  其中W=Vi, U∈(V-W)

四、子多维直方图计算

现在要求从一个大的多维直方图中,有效地过滤出所选变量限定范围的子多维直方图。例如:

P(200 bin(A) 255,0 bin(B) 50) >70%.

在这个查询中,我们要查询变量A属于bin 200到255,变量B属于bin 0到50的概率大于70%的数据项。使用字典表,可以发现这个工作依然很容易:只要将要查询的变量A和Bbin索引解码后,取A属于bin 200到255,变量B属于bin 0到50的数据项,然后再取频率大于70%的即可。

五、用直方图计算众数、平均数、中位数、方差

设有一个离散型随机变量X,其样本集共包含n个样本x1,x2, …, xn-1,并且已经画出了X的直方图,bin的的尺寸为h,总个数为k。直方图字典表记做D(X)j,直方图中非空的bin总个数=字典表的长度=j。 D(X)j中保存的是键值对bin[X] :f(X)。bin[X]是保存直方图的一维数组的非空条目下标,从0开始,到j-1为止。f(X)是bin[X]对应的频率。直接调用D(X)i,等于取直方图第i个非空条目对应的频率f(X)i的值。那么对应的平均数、中位数、众数、标准差计算如下:
众数: 指的是样本集中出现次数最多的样本值。对应于直方图中频率最大的bin的中点值。设直方图字典表中频率最高项为D(X)max,对应的bin索引为bin[X]max。则众数等于bin[X]max * h + h/2

平均数 = (x1+x2 +… +xn-1)/n , 对应于直方图,等于直方图每个bin面积乘以bin中点值。即平均数 =∑j f(X)i* h * (bin[X]* h + h/2)

中位数:以后再说

方差:以后再说

对于多维联合直方图,要计算其中某个变量的众数、平均数、中位数、方差,则需要先计算该变量对应的边缘直方图(详见上一篇随笔3.1节),然后就可以计算以上统计量。

 

推荐网站:

Stackoverflow是一个编程领域的问答社区,在其之上还有一个母站,叫做[StackExchange],管理着几十个大大小小的问答社区(参见[这里](All Sites – Stack Exchange)),Stackoverflow是其中成立最早、规模最大的一个子站,其他的所有子站在形式上都与Stackoverflow保持一致,它们的主题各异,比如这个Mathematics Stack Exchange 子站,就可以问问数学问题。

https://math.stackexchange.com/search?q=conditional+entropy

参考文献:

[1].   Lu, K. and H.W. Shen. A compact multivariate histogram representation for query-driven visualization. 2015.

 


留下一个回复

你的email不会被公开。