探索HyperLogLog算法(含Java实现)(2)

到这里,你大概已经理解了LogLog算法的基本思想,LogLog算法是在HyperLogLog算法之前提出的一个基数估计算法,HyperLogLog算法其实就是LogLog算法的一个改进版。

LogLog算法完整的基数计算公式如下:


LogLog算法

其中m代表分桶数,R头上一道横杠的记号就代表每个桶的结果(其实就是桶中数据的最长前导零+1)的均值,相比我之前举的简单的例子,LogLog算法还乘了一个常数constant进行修正,这个constant具体是多少等我讲到Java实现的时候再说。

调和平均数

前面的LogLog算法中我们是使用的是平均数来将每个桶的结果汇总起来,但是平均数有一个广为人知的缺点,就是容易受到大的数值的影响,一个常见的例子是,假如我的工资是1000元一个月,我老板的工资是100000元一个月,那么我和老板的平均工资就是(100000 + 1000)/2,即50500元,显然这离我的工资相差甚远,我肯定不服这个平均工资。
用调和平均数就可以解决这一问题,调和平均数的结果会倾向于集合中比较小的数,x1到xn的调和平均数的公式如下:


探索HyperLogLog算法(含Java实现)

调和平均数

再用这个公式算一下我和老板的平均工资:


使用调和平均数计算平均工资

最后的结果是1980元,这和我的工资水平还比较接近,这样的平均工资水平我才比较信服。

再回到前面的LogLog算法,从前面的举的例子可以看出,
影响LogLog算法精度的一个重要因素就是,hash值的前导零的数量显然是有很大的偶然性的,经常会出现一两数据前导零的数目比较多的情况,所以HyperLogLog算法相比LogLog算法一个重要的改进就是使用调和平均数而不是平均数来聚合每个桶中的结果,HyperLogLog算法的公式如下:


探索HyperLogLog算法(含Java实现)

HyperLogLog算法

其中constant常数和m的含义和之前的LogLog算法公式中的含义一致,Rj代表(第j个桶中的数据的最大前导零数目+1),为了方便理解,我将公式再拆解一下:


探索HyperLogLog算法(含Java实现)

HyperLogLog公式的理解

其实从算术平均数改成调和平均数这个优化是很容易想到的,但是为什么LogLog算法没有直接使用调和平均数吗?网上看到一篇英文文章里说大概是因为使用算术平均数的话证明比较容易一些,毕竟科学家们出论文每一步都是要证明的,不像我们这里简单理解一下,猜一猜就可以了。

细节微调

关于HyperLogLog算法的大体思想到这里你就已经全部理解了。
不过算法中还有一些细微的校正,在数据总量比较小的时候,很容易就预测偏大,所以我们做如下校正:
(DV代表估计的基数值,m代表桶的数量,V代表结果为0的桶的数目,log表示自然对数)

if DV < (5 / 2) * m: DV = m * log(m/V)

我再详细解释一下V的含义,假设我分配了64个桶(即m=64),当数据量很小时(比方说只有两三个),那肯定有大量桶中没有数据,也就说他们的估计值是0,V就代表这样的桶的数目。
事实证明,这个校正的效果是非常好,在数据量小的时,估计得非常准确,有兴趣可以去玩一下外国大佬制作的一个HyperLogLog算法的仿真:

constant常数的选择

constant常数的选择与分桶的数目有关,具体的数学证明请看论文,这里就直接给出结论:
假设:m为分桶数,p是m的以2为底的对数


p

则按如下的规则计算constant

switch (p) { case 4: constant = 0.673 * m * m; case 5: constant = 0.697 * m * m; case 6: constant = 0.709 * m * m; default: constant = (0.7213 / (1 + 1.079 / m)) * m * m; } 分桶数m的选择

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/035f6a8d33d76629d8ff96ebb891297b.html