Menu Sidebar
Menu

Reservoir Sampling

Very Fast Reservoir Sampling by Erik Erlandson

今天正式的把这个抽样算法加到Apache Flink里了, 这个算法是Erik Erlandson在他的博客上公布的大概是迄今为止最快速的抽样算法的. 这个算法采用了流行的gap distribution的方法抽样, 有效的在减少cpu使用的情况下, 减少了内存的占用, 通过生成抽样之间的gap, 进行近似随机抽样. 在他的博客http://erikerlandson.github.io/blog/2015/08/17/the-reservoir-sampling-gap-distribution/中,  证明了抽样可以通过生成gap实现随机抽样, 大大减少了随机数的生成时间和占用的内存, 实际应用下, 可以大大增加整体系统的运行效率. 他的博客中, 有基于Bernoulli Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/BernoulliSampler.java)和Poisson Distribution(https://github.com/apache/flink/blob/master/flink-java/src/main/java/org/apache/flink/api/java/sampling/PoissonSampler.java)的两种实现, 在Apache Flink中, Bernoulli分布实现了非replacement的抽样, 而Poisson分布实现了replacement的抽样. 这个新的优化算法, 使用了几何分布(https://en.wikipedia.org/wiki/Geometric_distribution)的思想, 对于样品大小远远小于数据大小 (1000000倍以上)的情况下, 样品的抽样率近似于P = R/j, R是样品集合大小, j是当前数据的总数. 这个算法有两部分组成. 作者定义了一个阈值T, T=4R, R是样品集合的大小. 这里的4是由随机数的好坏确定的. 确定的方法很复杂. 如果数据量小于阈值T, 则使用传统的水塘抽样. 这里使用水塘抽样的原因是, 如果当前的数据量小, 则生成gap会大大影响抽样结果的分布. 因为这个算法的gap是通过累计分布最后达到均匀分布的, 少量的gap会产生极大的误差. 通过实验表明, KS-test下, 如果样品大小是100,数据量是100000, 那么与随机抽样比较, 误差远远超过了 KS-test的容忍值D. 在数据量小的情况下, 生成少量随机数并不会对系统产生太大的负担, 这种trade-off是可以接受的. 水塘抽样的分布和数据量无关, 所以即使抽样大小和数据量很接近, […]

Reservoir Sampling 水塘抽样

水塘抽样是一组解决数据流取样的方法, 有很多的变种. 它适用的问题有如下特点: 对象为无法在内存中放下的数据, 如不间断数据流, 或者巨大的文件, 数组等. 样本集的大小为k, 并且要求每个样本的取样概率相等. 取样概率可以通过添加权重(weight)来改变取样概率. 一般(无weight)水塘抽样的每个样本的取样概率为: k/(n+1) 水塘抽样的算法实现非常简单, 而且证明简练. 算法如下: 预设数组A, 大小为k. 先取样k个元素. 放入A中. 从k+1元素开始, 每次取得随机数r, 范围为(0,k+1). 如果r <= k, A[r] = S[k+1], S是当前数据流.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

December 2024
M T W T F S S
 1
2345678
9101112131415
16171819202122
23242526272829
3031