大数据计数原理1+0=1这你都不会算No.77

完结篇。

这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 T_T。有兴趣的小伙伴可以在菜单看看整个系列。

好啦,开始今天的主题,今天主要呢,聊最后两个基数估计算法,一个是 Adaptive Counting ,一个是 HyperLogLog Counting 。话不多说,直接简单粗暴从 Adaptive Counting 开始吧。

Adaptive Counting 其实就是一个组合算法。原始论文是 《 Fast and accurate traffic matrix measurement using adaptive cardinality counting 》 。思路很简单粗暴,就是将 LC 和 LLC 组合起来使用,我们假设 LC 与 LLC 在同样的条件下,在总统计值 m 等于 M 的时候误差达到一致,那么当 m 小于 M 的时候使用 LC ,当 m 远大于 M 的时候使用 LLC。

为什么呢?我们都知道 LC 其实只是 BitMap 的进化版,如果基数太大的话,那么会占用非常多非常多的内存,如果桶设置得太小的话所有的桶基本都满了,那么这样子误差会很大。而 LLC 则非常稀疏,如果 m 太小的话,那么会出现非常多的空桶,这样子误差也非常大。所以总结起来就是,组合起来用,总统计量小的话用 LC , 统计量太大的话用 LLC 。

HyperLogLog Counting 其实就是 LC 基数估计法从算术平均数换成调和平均数。先补充一下小学算术,什么叫算术平均数什么叫调和平均数哈。首先是算术平均数,其实就是加起来求和。

第二是调和平均数,其实就是倒数求和除n的倒数。

呐,这样就可以解释清楚了。LC 里边是对 m 个桶里边的值进行求算术平均数然后直接进行基数估计,而 LLC 则是使用调和平均数。那么,这样做有什么道理呢?对比一下,LLC 是第一个,HyperLogLog Counting 是第二个。

看得出差别了吗?一个是直接求和平均,一个是倒数平均。其中 LLC 使用算术平均数,那么如果数值比较稀疏的时候,也即是有一些偏离值的时候,整个数据的求和会变得很偏远。用人话来说就是,我跟姚明平均身高两米。。。非常容易受到异常值的影响。而 HyperLogLog Counting 使用调和平均数则可以有效降低偏离值的影响。虽然来说也有一点影响但是影响程度没有算术平均数那么大。

最后放出各大算法的空间占用及误差率,看时机使用吧,别什么东西都直接丢一个 HyperLogLog ,有些场景下可能直接丢一个 HashSet 更靠谱喔。

好了这个系列到此结束,总得来说基数估计算法的套路都差不了太多,基本都输基于 BitMap 的思想,然后进行分桶,接着对桶进行统计这样的思路来进行超大数据量的基数估计。

谢谢大家支持 ~ 大家有什么想知道或者想看的可以留言或者私信找我,我会看心情写的。

元旦快乐么么哒

本文来自企鹅号 - 一名叫大蕉的程序员媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习与数据挖掘实战

【今日热门&优秀资源】深度学习&Kaggle竞赛

17130
来自专栏机器学习算法工程师

LightGBM大战XGBoost,谁将夺得桂冠?

如果你是一个机器学习社区的活跃成员,你一定知道 **提升机器**(Boosting Machine)以及它们的能力。提升机器从AdaBoost发展到目前最流行的...

18430
来自专栏鸿的学习笔记

写给开发者的机器学习指南(七)

Classifying email as spam or ham (NaiveBayes)

12510
来自专栏大数据挖掘DT机器学习

R语言vs Python:数据分析哪家强?

本文章旨在更客观地看待这两门语言。我们会平行使用Python和R分析一个数据集,展示两种语言在实现相同结果时需要使用什么样的代码。这让我们了解每种语言的优缺点,...

1.2K110
来自专栏Coding迪斯尼

神经网络实战:快速构建一个基于神经网络的手写数字识别系统

12920
来自专栏专知

【专知-PyTorch手把手深度学习教程07】NLP-基于字符级RNN的姓名分类

【导读】主题链路知识是我们专知的核心功能之一,为用户提供AI领域系统性的知识学习服务,一站式学习人工智能的知识,包含人工智能( 机器学习、自然语言处理、计算机视...

735130
来自专栏杨熹的专栏

使聊天机器人具有个性

本文结构: 模型效果 模型的三个模块 模块细节 ---- 今天的论文是 《Assigning Personality/Identity to a Chattin...

35780
来自专栏一名叫大蕉的程序员

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

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

207100
来自专栏数据科学与人工智能

【Python环境】R vs Python:硬碰硬的数据分析

我们将在已有的数十篇从主观角度对比Python和R的文章中加入自己的观点,但是这篇文章旨在更客观地看待这两门语言。我们会平行使用Python和R分析一个数据集,...

30990
来自专栏Petrichor的专栏

深度学习: 局部响应归一化 (Local Response Normalization,LRN)

局部响应归一化(Local Response Normalization,LRN):

94340

扫码关注云+社区

领取腾讯云代金券