内容简介:如果你去参加音乐会,你排在队尾,如何估计你的前面还有多少个人?如下图,整个队伍的长度是已知的为
介绍
KMV Sketch
是 Theta Sketch
算法的一种,简单来说, KMV Sketch
是用来估算大数据中不重复元素的个数,例如某个网站的唯一身份访客数。本文简单翻译自 datasketches
的 文档 ,用以说明该算法是如何进行估算的。
案例1
如果你去参加音乐会,你排在队尾,如何估计你的前面还有多少个人?如下图,整个队伍的长度是已知的为 1000Ft
,你与前一个人的距离为 2Ft
,那么可以简单的估算,整个队伍共有 1000Ft/2Ft=500
人,此时你用于计算的样本包含的人数为 1
人。
再次观察这个队伍,你发现人与人之间的距离并不是均匀的,你看到队尾的 11
个人一共占据了 30Ft
的长度,那么再次估算人数为 1000Ft/30Ft*11=11/(30Ft/1000Ft)=366
人,由于此次你用了 11
个人作为样本,估算值应该比之前更精确。
案例2
现在我们有一份大数据样本,包含的是访客的唯一 id
,为了简单说明原理,假设只有 10
个不同的 id
, 我们还需要一个特殊的 hash
函数,它能将 id
映射成 0~1
之间的值, 并且映射后的值是有序的,如下图所示:
如果选取最小的那个值作为估算样本,那么整体数量的估算值为 1/0.008=125
,如果选第 4
个数,即 0.386
作为样本,那么估算值为 1/(0.386-0.195)=5
。可以看到,在只有一个样本的情况下,估算值与真实值 10
差距较大。
参考估算排队人数的做法,我们同样选择多个样本来估算,例如选择最小的 0.008/0.145/0.195
这 3
个样本,此时估计值的计算方式为 (3-1)/0.195=10.26
,可以看到,距离真实值已经很接近了。
KMV
估算法的计算原理就是这样,虽然很简单,但数学上可以严格证明该估计量是整体的无偏估计。
相关链接: 什么是无偏估计?
以上所述就是小编给大家介绍的《简单认识KMV Sketch估算算法》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 【火炉炼AI】机器学习025-自动估算集群数量-DBSCAN算法
- 说说鸡蛋估算法
- 干货 | 用跳跃—扩散模型估算市场隐含价值
- 软件工程造价估算标准》编制工作全面展开
- 项目管理 – 如何估算新技术的工作时间?
- 使用 TensorFlow Hub 和估算器构建文本分类模型
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
软件人才管理的艺术
Michael Lopp / 罗小平 / 人民邮电出版社 / 201008 / 35.00元
本书作者具有15年的硅谷人才管理经验,他在博客上发表了大量探讨软件人才的管理之道的文章,深受读者欢迎。本书素材取自他的博客文章,用深入浅出的语言,讲述发人深思的道理,具有很强的现实操作性。 本书分为三大部分:“管理的箭袋”、“过程就是产品”、“你的其他版本”。前两部分分别讲述了人员与产品的管理,第三部分除了讨论管理之外,还讲述了如何有针对性地准备简历和电话面试,来提高自己面试成功的几率。书中......一起来看看 《软件人才管理的艺术》 这本书的介绍吧!
HTML 压缩/解压工具
在线压缩/解压 HTML 代码
随机密码生成器
多种字符组合密码