内容简介：如果你去参加音乐会，你排在队尾，如何估计你的前面还有多少个人？如下图，整个队伍的长度是已知的为
介绍
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 和估算器构建文本分类模型
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
分布式服务架构：原理、设计与实战
李艳鹏、杨彪 / 电子工业出版社 / 2017-8 / 89.00
《分布式服务架构：原理、设计与实战》全面介绍了分布式服务架构的原理与设计，并结合作者在实施微服务架构过程中的实践经验，总结了保障线上服务健康、可靠的最佳方案，是一本架构级、实战型的重量级著作。 《分布式服务架构：原理、设计与实战》以分布式服务架构的设计与实现为主线，由浅入深地介绍了分布式服务架构的方方面面，主要包括理论和实践两部分。理论上，首先介绍了服务架构的背景，以及从服务化架构到微服务架......一起来看看 《分布式服务架构：原理、设计与实战》 这本书的介绍吧!
