《大数据算法》一3.4　估算不同元素的数量

本节书摘来华章计算机《大数据算法》一书中的第3章 ，第3.3节，王宏志　编著, 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.4　估算不同元素的数量

顾名思义，估算不同元素的数量就是看数据流中出现了多少不同的元素。
数据流中不同元素数量统计问题
输入：数据流,隐式地定义了一个频率向量f=(f1,…,fn)，中j出现的次数输出：,即出现在σ中不同元素的数量。
估算数据流中不同元素的个数可以用于统计访问某个网站的所有用户个数或者统计某个页面的访问ip数等。由于这些访问量十分巨大，不可能在内存中完全保存所有访问信息，因而需要合理的亚线性算法。
如果这个问题被限定为确定性算法(比如δ=0)或精确算法(比如ε=0)，那么可以证明，这个问题是不可能在亚线性空间内求解的。因此，我们要寻找一个随机化的近似算法，即输出d的(ε,δ)近似。
3.4.1　基本算法
1.算法描述
对于一个整数p>0,令
表示p的二进制表示中末尾0的个数，即该算法的核心思想是，数据流当前不同的元素个数越多，对应不同哈希值的个数就越多，从而其中出现某一个元素对应哈希值末尾0的个数多的概率就越大。具体地，对于d个不同的数来说，我们可以期望其中某一个数j满足。于是，我们在数据流中维护的的最大值(也就是z)给出了一个logd的估计。
我们设计了如下非常简单的算法。算法3-3　数据流中元素数量估计基本算法

初始化:
1　从2-通用哈希函数族中随机选择哈希函数h:［n］→［n］;
2　z←0;
处理j:
3　if zeros(h(j))>z then z←zeros(h(j));
输出:2z+1/2。

针对该算法，对数据流<1,3,3,5,2,2,1,4,4,6,6>的数据流片段给出具体计算示例，如图3-1所示。使用哈希函数h(x)=x mod 23，计算过程如下：
1) 对数据流中第一个数据1，计算h(1)=1,其二进制数为001,zeros(h(x))=0；
2) 对数据流中第二个数据3,计算h(3)=3,其二进制数为011，zeros(h(x))=0；
3) 对数据流中第三个数据3,计算h(3)=3,其二进制数为011，zeros(h(x))=0；
4) 对数据流中第四个数据5,计算h(5)=5,其二进制数为101，zeros(h(x))=0，同时更新z的最大值为2;
5) 对数据流中第五个数据2,计算h(2)=2,其二进制数为010，zeros(h(x))=1。
直到数据流处理完当前数据得到最大的z=2，作为统计不同元素估计的参数，即最终估计值为2z+1/2≈6。

补充知识:通用哈希函数族
对于任意哈希函数，都可以人为构造一些特殊的输入，使得哈希冲突非常高，从而让哈希表的性能大大降低。为了抵御这种攻击，我们可以实现大量哈希函数，然后

在构造哈希表的时候从中任选一个。由于数据输入者并不知道挑选的是哪一个哈希函数(算法设计者其实也不知道)，这样做就达到了避免刻意攻击的目的。这是一种舍伍德算法，即用随机化方法提高算法在最坏情况下的性能，类似用随机化方法来优化快速排序(参见参考文献［12］的7.3节)。下面简单介绍通用哈希函数族，对其细节感兴趣的读者可以阅读参考文献［12］的11.5节和参考文献［13］的第13章。
设集合U是一个全域，U≥n，令集合V={0,1,2,3,…,n-1}，H是一个从U到V的哈希函数集合。如果H满足对于任意的元素x1,x2,x3,…,xk以及从H中均匀随机选取的一个哈希函数h，的概率小于1/nk-1，那么将H称为k-通用哈希函数族。
所以，如果哈希函数h是从2-通用哈希函数族中选取的，那么对于任何两个元素x、y，它们的哈希值满足h(x)=h(y)的概率最多为1/n。
下面给出一个2-通用函数族的例子：

其中p是质数，

2.算法质量分析
定理3-3　算法3-3输出数据流中不同元素数目的估计为d，数据流中真实不同元素数目为d,则
证明　形式上，对于j∈［n］和整数r≥0，令Xr,j作为事件zeros(h(j))≥r的指示随机变量，并令当算法处理完该流时将z的值记作t。如果Yr>0，则表明(3-1)我们可以将上面的公式重新表示为下面的形式：(3-2)由于h(j)为(log n)比特字符串上的均匀分布，所以可以得到现在我们对Yr的期望和方差做如下估算。式(3-3)的第一步使用随机变量Yr的两两独立性，因为h是由2-通用哈希函数族产生的。E［Y(3-3)这样，分别使用马尔可夫不等式和切比雪夫不等式，得到
于是，d=2t+12，令a是满足2a+12≥3d的最小整数，利用式(3-1)和式(3-4)得到同样，令b取得最大的整数，这样有2b+12≤d/3，利用式(3-2)和式(3-5)得到以上证明在以下两方面稍显薄弱。首先，评估d只能和d在同一数量级，并且不是任意好的近似值。其次，算法失效的概率的上界相当大(2/3≈47%)。当然，我们可以通过用更大的常量替代常量“3”来减小这个概率。但更好的方法是用一个不断生成的标准——“中位数技巧”，这个方法不会进一步降低评估d的质量。
补充知识:马尔科夫不等式和切比雪夫不等式
马尔科夫不等式和切比雪夫不等式是概率分析中常用的概率不等式。
马尔科夫不等式：设X为只取非负值的随机变量，则对任意实数t>0有

切比雪夫不等式：设X为随机变量，具有有限均值μ和方差σ2，则对任意实数t>0有

3.中位数技巧
想象一下，如果并行运行k个该算法的副本，在这些副本中使用互不依赖的随机哈希函数，并且输出k个答案的中位数作为最终结果。如果这个中位数超过3d，那么至少有k/2个答案超过3d，反之，我们仅仅希望k2/3个答案超过3d。通过标准的切尔诺夫界，这个事件的概率是2-Ω(k)。同样，中位数小于d/3的概率也是2-Ω(k)。
选择k=θ(log(1/δ)),我们可以使这两个概率的和最多为δ。这就得到一个(O(1),δ)近似算法。下一节给出一个不同的算法，可得到一个(ε,δ)近似算法。
原来的算法需要O(logn)位空间存储一个哈希函数，并需要多于O(log logn)位的空间以存储z。因此，最终的算法需要的空间为O(log(1/δ)×logn)。当用一个新的算法解决这个问题时，将改善这个空间的界限。
3.4.2　改进算法
针对上述问题，本节给出一个更好的算法。这个算法称为BJKST算法，BJKST是以Bar-Yossef、Jayram、Kumar、Sivakumar和Trevisan五个作者的名字命名的。介绍这个算法的原论文给出了三个算法，我们将要介绍第三个算法（在某种意义上是“最好的”）。下面的函数zeros与3.4.1节中的含义相同。常量的值稍后基于算法分析中的需要确定。算法3-4　数据流中元素数量估计改进算法

初始化:
1　从2-通用函数族中随机选择哈希函数h:\[n\]→\[n\];
2　从2-通用函数族中随机选择哈希函数g:\[n\]→\[bε-4log2n\];
3　z←0;
4　B←;
处理j:
5if zeros(h(j))>z then
6　B←B ∪{ g(j), zeros(h(j))};
7　while B>=c/ε2 do
8　　　z←z+1
9　　　从B中移除所有满足β<z的(α,β);
输出：B2z。

直观地说，这个算法是3.4.1节的算法3-3的改良版。这次，我们不是简单地计算在数据流中zeros(h(j))的最大值，而是要尝试确定由所有满足zeros(h(j))≥z的元素j组成的存储桶B的大小。如果在数据流中包含d个不同元素，我们可以期望d/2z落入桶中。因此B2z应该是对d的很好的估计。
我们的目的是节省空间，因而希望B小一些，这样就能存储足够的信息来精确地追踪B值。同时，我们又希望B足够大，这样我们生成的估计值就足够精确。我们可以证明让B增大到大约O(1/ε2)是个不错的选择。最后，为了节约空间，这个算法没有存储B中实际的数字，而是存储基于g的哈希值和zeros(h(j))的值，当B必须缩小时，这两个值用来删除B中相应的元素。
使用改进算法对数据流<1,3,3,5,2,2,1,4,4,6,6>的数据流片段给出具体示例，如图3-2所示。使用与上文相同的哈希函数h(x)=x mod 23进行完全哈希，结果如图中的统计表所示。
1) 如果不压缩，即保留所有B，B=6,得到完全精确的值6。
2) 如果设定相关的参数ε，使得z=1，即需要删除所有哈希值为1的桶，保留下的B=3，使用公式B2z计算得到的不相同元素数为6。
3) 如果设定参数使得z=2，则得到B=1，使用公式B2z得到最终估计值为4。
所以我们需要平衡B的空间和估计的准确度。
下面我们详细地分析算法，在这里，我们假设1/ε2=O(m)，否则这个算法就没有任何意义。

定理3-4　算法3-4的空间复杂度是
证明　这个算法必须存储h、g、z和B，其中h和B是主要空间需求，根据有限域哈希函数族中哈希函数的性质，h需要位的存储空间。存储桶B的规模限制在每个数据桶中的元组（α，β）需要位来存储哈希值α，这个哈希值大于存储数量β所需的存储空间log logn位。综上所述，算法3-4的空间复杂度是
算法质量分析
整个分析假设在B中存储的是(在g下的)哈希值，而不是元素本身，更没有改变B。不论g在其应用到元素集合时是否发生冲突都是如此。通过选择足够大的常量B，并针对每一个选择的哈希函数h，我们保证估计误差过大的可能性最多为1/6。因此，使用这个假设增加了最多1/6的错误可能性。我们现在在不发生冲突的情况下分析余下的误差。
定理3-5　令d表示算法3-4输出的估计值，d表示数据流中实际的不同元素数量，则
证明　该证明的基本条件与3.4.1节一致。对于每个和整数r≥0，对于，令作为一个指示随机变量，并且令当算法完成数据流的处理后用t表示z的值，然后得到Yt=B当算法结束时d=Yt2t与3.4.1节中的证明过程一致，得到注意到如果t=0，那么算法没有增加z，这就意味着d另外一种情况下，t≥1，如果不等于d，那么我们认为这是个失败的结果。通过对所有可能的t的r值求和我们能估出这个事件的概率。对于小的r，当t=r时错误不会出现，因为错误需要Yt很大的偏差。对于大数值的r，仅仅有t=r是不可能的。下面是将总和分成两部分的一个直观体现，我们需要选择阈值，便于将r的“小”值和“大”值区分开，做法如下。
令s等于一个固定的整数，得到
现在我们用切比雪夫不等式和马尔可夫不等式来约束式(3-8)中的第一项，然后我们用式(3-6)计算得到
(根据式(3-7))其中最后一步的界限通过选择一个足够大的常数c(≥2×24×12)来实现。█
记得我们的初始条件中有一个针对g的没有冲突的假设，则最后错误的可能性最大为1/6+1/6=1/3。因此，上面的算法(ε，1/3)近似为d。与3.4.1节一样，通过使用中位数技巧，我们将算法改为对于任意0<δ≤1/3，有算法(ε，δ)近似为d，其空间复杂度增加了O（log(1/δ）)。