大数据计数原理1+0=1这你都不会算(九)No.64

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet

大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap

大数据计数原理1+0=1这你都不会算(三)No.51 <- BloomFilter

大数据计数原理1+0=1这你都不会算(四)No.52 <- B-Tree

大数据计数原理1+0=1这你都不会算(五)No.55 <- B+Tree

大数据计数原理1+0=1这你都不会算(六)No.57 <- LinearCounting(一)

大数据计数原理1+0=1这你都不会算(七)No.59 <- LinearCounting(二)

大数据计数原理1+0=1这你都不会算(八)No.60 <- RoaringBitMaps

啦啦啦~有小伙伴说我最近怎么不更新,其实最近真的很忙,而且有很多新的东西要去学,连论文都只能抽时间看。今天这个算法说实话很难理解,但是确实是一个很好很好巨好的基数估计算法。叫做LogLogCounting,出自论文《Loglog Counting of Large Cardinalities》,人称LLC。

这么举例子吧,跟你聊聊这个算法有多节省内存。假如我们有1亿数据基数,使用HashSet可能需要2G内存,使用BitMap需要大概12.5M,使用LinearCounting需要1.25M,使用LLC只需要640字节,连1K都不需要。

我们都知道,基数统计的前提就是hash函数要足够好。什么叫足够好?分布均匀、长度一致、碰撞可忽略。怎么取?主流加密算法基本都可以。

好了牛逼吹完了,想了解到这个程度的可以左上角退出了嗷。下面是严肃的数学时间,我尽量讲得不那么数学。

首先,这个算法的第一要义是什么?靠猜。

比如我们Hash完的串为0100,1000,0010。等,我们发现这些串第一个1出现的位置在第3位上(按1、2、3、4这样从左往右数),那我们就猜,总共有2^3这么多个数。主要算法思路就是上面这样,取第一个1出现的位置,然后靠猜。

那么问题来了,我们为什么可以这样猜呢?这就需要概率论的知识了。

我们假设字符串"Banana"(简称为B),通过hash之后得到了一大堆的01的比特串,因为我们的hash算法非常好,所以每一个bit位为0和为1的概率就是五五开,都是50%这样。

那我们就把他当成是薛定谔的猫了,我完全不知道这个bit位有没有猫,只有谜底揭晓的时候才知道。我们把所有装着盒子的猫一字排排开,从头开始找。第一个盒子找不到猫(标记bit位为0)的概率为1/2,第二个盒子就找到猫的概率为1/(2^2),第k个盒子就找到猫的概率为1/(2^k)。

好,接下来假设我们总共要找n次,也就是有n个B进行hash。

考虑第一个问题。第一个B进行Hash后,在第k个位置第一次找到猫的概率为1-1/(2^k),那么明显,进行n次的结果后,所有的寻找次数加起来,都最多在第k个位置第一次找到猫的概率P( X <= k )= (1-1/(2^k))^n。当n远大于2^k的时候,P( X <= k )的概率几乎为0,好了我们找到了一个上限。

接下来我们考虑第二个问题。那么如果考虑每一次的结果都大于k呢?概率P( X >= k) = 1 - (1-1/(2^k))^n。由极限定理可以得到,当n远小于2^k的时候,P( X >= k )的概率几乎为0。

那么我们就得到说,无论是n远大于2^k 时,P的概率很小。无论是n远小于2^k 时,P的概率也很小。那既然这样,我们就直接拍脑袋取2^k了嘛。

所以LLC的基本思想就是。我们先拍一个大概的数据范围,也就是统计的上限,比如你的数据量是大概1亿,1百亿还是1千亿,这样拍一个,然后选hash算法均匀分配到他们身上。意思就是,如果我们的基数是1千亿,那么我们致至少要有足够多的bit位空间来保存这上限也就是一千亿。在实际进行统计的时候,我们进行n次hash之后,如果第一个找到1的位置是k,那么就可以估计这个基数是2^k。

基础算法到这里就说完了,我们也说了,我们是靠猜的,那能不能猜得靠谱些?

可以。

我猜几十次几百次取平均,应该大概或许能降低这个误差吧?这就有了分桶的思想,我们只需要每个桶记住自己桶的位置以及桶里边最大的k值,就可以了。

我们假设分桶树为16,也就是2^4。那我们就取hash值的前四个bit来进行分桶,把每个桶的max保留起来即可。为什么可以这样保留?因为我们把它界定在某一个桶之后,那它的第一个1肯定是在桶内的,这时候我们就可以对比一下当前桶内的max值,进行合并。然后最终的时候,直接取一下所有桶值得平均即可。

主线就这样说完了,先消化一下,下一次我们继续聊聊,如何降低误差,如何把LogLogCounting 算法改进成无偏估计,改进完的算法误差率究竟在什么样的范围。棒~~掰掰

原文发布于微信公众号 - 一名叫大蕉的程序员(DaBananaTalk)

原文发表时间:2017-10-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

只需连接电脑摄像头,就能用深度学习进行实时对象检测

实时对象检测是一个非常有趣的话题。 我们应如何可靠地检测视频输入中的人和其他现实生活中的物体? 最近我设法构建了一个非常简单的应用程序,只需连接到用户的电脑网络...

19220
来自专栏ATYUN订阅号

使用LSTM预测比特币价格

本文以“时间序列预测的LSTM神经网络”这篇文章为基础。如果没有阅读,我强烈建议你读一读。 考虑到近期对比特币货币的泡沫的讨论,我写了这篇文章,主要是为了预测比...

39970
来自专栏量子位

AI玩微信跳一跳的正确姿势:跳一跳Auto-Jump算法详解

作者:肖泰洪 安捷 北京大学 | 数学科学学院研究生 量子位 已获授权编辑发布 转载请联系原作者 ? 最近,微信小游戏跳一跳可以说是火遍了全国,从小孩子到大孩子...

37250
来自专栏AI科技评论

业界 | 如期而至!谷歌开源 BERT 模型源代码

AI 科技评论按:自上个月谷歌公开 BERT 模型以来,BERT 模型以其双向、深层等特点,成功在 11 项 NLP 任务中取得 state of the ar...

17440
来自专栏机器学习算法与Python学习

超参数优化,这些策略了解一下!

当然,并非所有变量对模型的学习过程都一样重要,但是,鉴于这种额外的复杂性,在这样一个高维空间中找到这些变量的最佳配置显然是一个不小的挑战。

69630
来自专栏机器之心

教程 | Keras+OpenAI强化学习实践:行为-评判模型

选自Medium 作者:Yash Patel 机器之心编译 参与:乾树、黄小天 本文先给出行为-评判模型(actor-critic model)的基本原理,包括...

48490
来自专栏AI研习社

我用 face-recognition.js 识别出谢耳朵,还做了基于 Node.js 的面部识别库

翻译 | 付腾 整理 | 凡江 ? 已训练模型示范,可以很好的识别 拉贾·谢耳朵(这还能认错?)雷纳德和霍华德 在这篇文章里我要向你们示范一下如何用 f...

44860
来自专栏机器之心

教程 | 如何为时间序列数据优化K-均值聚类速度?

355100
来自专栏AI科技大本营的专栏

NLP通用模型诞生?一个模型搞定十大自然语言常见任务

AI科技大本营按:目前的NLP领域有一个问题:即使是再厉害的算法也只能针对特定的任务,比如适用于机器翻译的模型不一定可以拿来做情感分析或摘要。

12620
来自专栏PPV课数据科学社区

用TensorFlow实现神经网络很难吗?看完这篇详解,「小白」也可秒懂!

图:pixabay 作者:Faizan Shaikh 「机器人圈」编译:嗯~阿童木呀、多啦A亮 本文经公众号「雷克世界」授权转载(微信号:ROBO_AI) 如果...

42050

扫码关注云+社区

领取腾讯云代金券