蓄水池抽样算法的问题

  统计/机器学习 抽样方法    浏览次数:5734        分享
3

不是很明白蓄水池抽样算法是如何做到在流动的数据中保证独立、均匀抽样的。

 

道画师   2017-04-12 22:18



   1个回答 
12

蓄水池抽样、或者水库抽样(reservoir sampling)是一种online算法,实现等概率随机抽样。


问题描述

情形 1,你需要从海量样本(总数量未知)中等概率抽取k个数据。


情形 2,当前时刻数据库里没有数据,此后每秒中都会一个新数据进入数据库,k+1秒之后,你需要从数据库中等概率抽取k个数据,并且保证每时每刻这k个数据都是从数据库中等概率抽取的。


一般解决方法

情形 1,先把数据数一遍,得到个数之后,再开始等概率抽取。


情形 2,从第k+1秒开始,每一秒都从整个数据中重新抽取k个。


蓄水池抽样算法

情形 1, 先取出数据库中的前k个数据,然后开始读取下一个数据,我们以k/(k+1)的概率保留这个数据,并且从之前的k个数据中随机挑选一个丢弃,以1/(k+1)的概率不做任务操作。我们继续读取下一个数据,我们以k/(k+2)的概率保留这个数据,并且从之前保留的k个数据中随机挑选一个丢弃,以2/(k+2)的概率不做任何操作。归纳起来,对于第j个数据,我们以k/j的概率保留这个数据,并且从之前保留的k个数据中随机挑选一个丢弃,以(j-k)/j的概率不做任何操作。反复进行,直到遍历完整个数据库。


情形 2, 类似地,一开始我们先保留前k秒产生的数据,此后,第j秒的时候(j > k),我们以k/j的概率保留这个数据,并且从之前保留的k个数据中随机挑选一个丢弃,以(j-k)/j的概率不做任何操作。



相比于一般解决方法,蓄水池的优势显而易见!时间上少了,不用不停地遍历整个数据库来随机抽取,更重要的时候,不用保存历史数据,只需要保存k个已经被选择的数据。省时间、省空间!


SofaSofa数据科学社区DS面试题库 DS面经

可爱多   2017-04-14 13:11



  相关讨论

两阶段抽样和分层抽样是一回事吗?

parametric bootstrap和nonparametric bootstrap的区别是什么?

bootstrap 一般用在哪些方面

Jackknife vs Bootstrap

滚雪球抽样算法的实现

自助法(bootstrap)的0.632是怎么来的?

python产生一个随机置换?

python对给定的集合进行有放回抽样?

把训练集分成n份,用同种算法在每个子训练集上训练再把预测平均,效果如何?

什么是SMOTE sampling方法?

  随便看看

numpy.array转换为图片并显示出来

推荐系统有哪些常用的评价标准

'str' object has no attribute 'decode' 代码运行时有错误呢?请高手帮忙解决

二元分类问题中经常提到的TP,TN,FN,FP都是什么意思?

怎么按照设定概率产生不重复的随机排序?