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

2021-09-23

完结篇。
这个系列写到这里算是结束了,真是不容易说实话,查了好多好多的资料,真的很难相信懒得要命的我能写完这个系列 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 的思想,然后进行分桶,接着对桶进行统计这样的思路来进行超大数据量的基数估计。

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




元旦快乐么么哒


相关文章

智能的本质好像不是数据算法算力和知识

2021-09-23
也许能够对计算、感知、认知、洞察机制机理会有更多更新的认识吧!新闻需要联系起来看,记得最清楚的阮次山先生说的一句话:”...

11.18 | 科技论文数据分析原理与实践——以计量语言学为例(19:00)

2021-09-23
【主题】科技论文数据分析原理与实践——以计量语言学为例【时间】2020年11月18日(周三)19:00-21:00【主讲】李杰(辽宁工程...

CSS计数器+伪类实现数值动态计算与呈现

2021-09-23
其实原理跟上面的计算选中个数是一样的,不过这里呢,每个复选框计数值这里都是具体值(不是默认的1),最后,通过相邻兄弟选...

每日一题:Excel有计量单位数据的计算方法!

2021-09-23
首先说,这种表格是不规范的,正确的表格应该如下表.如果想直接计算,使用=LEFT(C2,2*LEN(C2)-LENB(C2)),提取单价.然后再和数量相乘就可以了,公式=(LEFT(C2,2*LEN(C2)-LENB(C2)))*D2.

投加计算中氮(N)源数值的选择​​!

2021-09-23
营养投加计算N源数值的选择在污水处理中营养的投加很重要,投加量的计算为营养的投加提供了参考,所以计算的正确性尤为重要!...

送你38个常用的Python库,数值计算、可视化、机器学习等8大领域都有了

2021-09-23
NumPy 支持多维数组与矩阵运算...SciPy 在NumPy库的基础上增加了众多的数学、科学及工程计算中常用的库函数...Pandas 基于NumPy的一种工具,为解决数据分析任务而生.纳入大量库和一些标准的数据模型...

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

2021-09-23
使用算术平均数,那么如果数值比较稀疏的时候,也即是有一些偏离值的时候,整个数据的求和会变得很偏远.用人话来说就是,我跟...

光圈数值是怎么算出来?不必完全理解,但起码要了解原理

2021-09-23
就更别提光圈的数值是怎么计算出来的这种看似很深奥的问题了.接下来好机友摄影就和大家一起看看光圈的那些事儿.光圈数值怎样...

Nat Bio | 单细胞数据集成的计算原理与挑战

2021-09-23
包括基于不同原理和假设的各种不同计算策略.有必要为这些数据集成任务定义统一的概念,根据输入数据结构和具体集成任务,将现...

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

2021-09-23
这篇呢,又是开坑之作,这是一个系列,主要会将大数据下的计数原理.说到计数,不知道大家会第一印象想到什么,我估计会是.....

随机推荐

【校友动态】祝贺!我校1988级计算机及应用专业欧阳瑜校友当选澳门社会文化司司长

2021-09-25
欧阳瑜,女,1968年出生于广东,毕业于华南理工大学1992届计算机及应用专业.1994年,欧阳瑜任司法警察局高级技术员;2000年...

如何构建出色的Vue组件?

2021-06-02
SCSS partial,让使用者能够按照其意愿进行自定义.不过,如果仅仅提供一个 SCSS 文件,这种方式仍然有一个缺陷.组件的使用者...

工作坊 | 品牌全案IMC 林展贤创意实战营

2021-05-12
顶尖品牌高手-林教头教你如何做品牌新鲜的体验,奇妙的联想观看视频,了解课程详情《品牌全案IMC十八铜人创意实战营》由林展贤...

AJAX基础知识与简单的操作示例

2021-05-05
AJAX基础知识与简单的操作示例什么是AJAX?步骤1 –如何发出HTTP请求步骤2 –处理服务器响应步骤3 – 一个简单的例子步骤4 –使用...

这可能是史上最全的CSS自适应布局总结

2021-04-09
大体上,布局中会用到的有:尺寸相关的盒子模型,普通流、浮动、绝对定位三种定位机制,CSS3中的transform、弹性盒子模块、试...

UC浏览器海外版、就是刺激

2021-01-01
共享软件被关小黑屋一个月,大多文件关注我回复:软件合集UC浏览器海外版、就是刺激UC Turbo和夸克最初确实是从同一个项目分...

php 微信公众号接入支付宝支付

2020-05-17
assign('goto',$goto); $this->view->engine->layout(false); return view... 课题:PHP开发商城秒杀抢购并发解决方案知识点:redis并发处...

007-面向对象三大特性

2017-07-16
007-面向对象三大特性(1)面向对象的三大特性(2)封装(3)实例方法与静态方法(4)this和static(5)继承(6)方法覆盖(方法重写,...

光圈数值是怎么算出来?不必完全理解,但起码要了解原理

2016-07-23
就更别提光圈的数值是怎么计算出来的这种看似很深奥的问题了.接下来好机友摄影就和大家一起看看光圈的那些事儿.光圈数值怎样...

千万别用设计模式?

2015-08-17
面向对象的设计模式(以下简称DP)是22年前GoF四位大师共同著述的,今天依然在设计中发挥重要的指导作用.但是如果没有一定...