东莞网站建设图表,做a 视频在线观看网站,商场设计图平面图,wordpress切换中文转载自 浅谈流处理算法 (1) – 蓄水池采样
前言 现如今#xff0c;“大数据 ”已经不是什么新概念#xff0c;“一千个人眼中有一千个大数据”。社交网络#xff0c;智能穿戴设备#xff0c;智能家居#xff0c;传感器#xff0c;机器人等每一个热门的词汇背后都是大量…转载自 浅谈流处理算法 (1) – 蓄水池采样
前言 现如今“大数据 ”已经不是什么新概念“一千个人眼中有一千个大数据”。社交网络智能穿戴设备智能家居传感器机器人等每一个热门的词汇背后都是大量的数据。抛开各种噱头和概念相信每个人都能看到数据的价值且能感受到数据规模的爆炸式增长。大规模的数据本身并不产生什么价值只有通过理解数据发现知识避免“Garbage In Garbage Out” 才能发挥数据的价值。
在形式多样的大数据问题中有一类问题输入以数据流的方式提供。我们需要在有限空间内通过若干遍访问数据流(很多时候可能仅仅允许访问一遍)完成数据处理并提取有价值的信息。我们称处理这类问题的算法为“流处理算法”(Streaming Algorithm)
Wikipedia定义 In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes (typically just one). These algorithms have limited memory available to them (much less than the input size) and also limited processing time per item.
一些典型的例子
根据用户访问日志统计用户来源分布根据用户访问日志统计新增用户数目根据用户访问日志统计Unique User数目根据用户访问日志统计某个页面访问次数……
这些问题在数据规模并不大且事先确定的情况下采取直接的统计方案并不难实现。但在数据流场景下直接的方案并不能满足实际需求。
数据流问题有以下特点
数据规模大存储空间有限。保存完整的数据集合并不现实。分发速度快。如果处理不及时没有足够资源保存数据。允许数据遍历极少次数一般仅支持遍历一次。空间复杂度sub-linear时间复杂度linear可以接受近似解
曾几何时拜摩尔定律和硬件技术所赐软件开发脱离在64k内存中扣扣索索的日子进入没事开个大数组的印度模式时代(道听途说如有雷同概不负责)。软件体量一个比一个吓人。然而面对上述特点的数据流问题时我们再一次深刻地体会到日新月异的计算机技术背后总有一个背景音 - “New Wine In Old Bottles”。
数据库大牛Jim Gray多年前就指示我们Tape is Dead, Disk is Tape, Flash is Disk, RAM locality is King. TalkingData的Bitmap引擎这不又在扣扣索索了嘛
这个小系列就是跟大家一起品尝一下“新酒” 以酒会友:-)
言归正传针对上述数据流问题特点流处理算法的一般模式有
采样/过滤 – 减少规模 如蓄水池采样 Reservoir Sampling随机映射(Random Projection) – 降维 Hash/SimHash概要 (Sketch)统计直方图(Histogram) 滑动窗口
这些算法模式都是希望通过样本采样或者特征采样使用有限数据保持原整体数据的某些特性。
后续我们计划聊聊蓄水池采样 存在性查询基数估计频率估计频繁项估计等问题的流处理方法。
蓄水池采样
蓄水池采样是一类采样算法的总称广泛使用在从数据流中按一定需求抽样出部分样本的场景中。蓄水池可以看作小段缓存协助存储数据流的部分信息。
下面我们从三个具体例子看看什么是蓄水池采样。
问题1. 年度大奖将从参加年会的同事中随机选择如何维护一个获奖者名字不管何时老大宣布获奖者所有参会者获奖概率一致
假如老大宣布获奖者时参会同事人数为N我们需要保证每个参会者获奖概率为1/N。
蓄水池采样算法是这样的
记录第一个到达的同学到获奖者名单上 (早起的鸟儿有虫吃 :-) )当第i位同学到达年会会场的时候(i1): 以1/i的概率使用第i位同学替换获奖者名单上的同学以1-1/i的概率保持获奖者名单不变 (Yeah!守擂成功!)
看起来很简单我们来看看是否能满足问题的需求
第一个同学P_1到达时获奖者必定是P_1。(获奖概率 1⁄1 100%满足)第二个同学P_2到达时1/2概率获奖者替换为P_2, 也1/2概率保持为P_1 (满足)当第i位同学到达时1/i的概率获奖者替换为P_i。而的1-1/i概率保持获奖者不变也就是P_1, P2, …, P(i-1)获奖的概率为 1/(i-1) * (1-1/i) 1/i (满足)
综上所述根据归纳法蓄水池采样搞掂了。
问题2. 项目进展很好老大很高兴决定年度大奖有k名如何维护一个k个获奖者名单保证不管何时老大宣布获奖者所有参会者获奖概率一致
假如老大宣布获奖者时参会同事人数为N我们需要保证每个参会者获奖概率为k/N。
蓄水池采样算法是这样的 记录前k位到达的同学到获奖者名单上 (早起总没错的) 当第i位同学到达年会会场的时候(ik): - 以k/i的概率使用第i位同学替换获奖者名单上的随机一位同学(某位同学杯具了) - 以1-k/i的概率保持获奖者名单不变 (集体守擂成功!)
看起来跟上一个问题差不多应该是正确的吧
前k位同学到达时获奖者必定是P_1, P_2, …, P_k。(获奖概率 k/k 100%满足)当第i位同学到达时( i k) [Condition 1] k/i概率获奖者替换为P_i (满足)[Condition 2] 1 - k/i的概率保持获奖者名单不变对于P_x (x i), 在第i位同学尚未到达时获奖概率为k/(i-1)。她能保留在获奖名单中的概率由两部分组成 k/(i-1) * [k/i * (1 - 1/k) 1 - k/i] k/i(满足) [Condition 1]没有被P_i踢掉 k/i * (1 - 1/k)[Condition 2]P_i直接出局了1 - k/i
综上所述根据归纳法蓄水池采样又搞掂了。
问题3.为了激励绩效好的同学每个参会同学都有一个权重如何维护一个k个获奖者名单保证不管何时老大宣布获奖者所有参会者获奖概率与权重成比例
假如老大宣布获奖者时参会同事人数为N我们需要保证参会者(P, 绩效权重W)获奖概率为W_i/(W_1 W_2 … W_N)。
蓄水池采样算法是这样的
记录前k位到达的同学到获奖者名单上 (嗯早起永远没错的) 每位同学的分值S_i random(0, 1) ^ (1/W_i)当第i位同学到达年会会场的时候(ik): 计算第位同学的分值 S_i random(0, 1) ^ (1/W_i)如果获奖者名单中分值最小的同学P_x的分值S_x比S_i小P_x被S_i替换了否则获奖者名单不变 (集体守擂成功!)
怎么证明这样可以满足要求呢额“这里空白太小我写不下了” (自己看论文去吧)
年会一年也就一次很快来了又走了。各种各样的数据流每天都在产生这些蓄水池采样方法可以帮忙我们获得数据流的一个样本。对于小规模样本可以保持大规模数据信息的场景蓄水池采样帮忙我们把“大数据”的“大”给去掉了。
参考文献
https://en.wikipedia.org/wiki/Streaming_algorithmhttps://en.wikipedia.org/wiki/Reservoir_samplingVitter, Jeffrey S. (1 March 1985). “Random sampling with a reservoir”Efraimidis, Pavlos S.; Spirakis, Paul G. (2006-03-16). “Weighted random sampling with a reservoir”
