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

发布于 作者:

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

一、计算联合熵

设p(x1, … , xn)是离散型随机变量X1 , … , 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=minA∑d=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，其中一个变量Vi 的信息增益IG(Vi )等于：

IG(Vi ) = H(V1, … , Vn) - H(V1, … , Vn | Vi )

=  -∑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]i * 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.