蓄水池抽样算法的问题

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

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

 

道画师   2017-04-12 22:18



   1个回答 
8

蓄水池抽样、或者水库抽样(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面经 问答 实战

可爱多   2017-04-14 13:11



  相关主题

滚雪球抽样算法的实现   0回答

bootstrap 一般用在哪些方面   1回答

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

parametric bootstrap和nonparametric bootstrap的区别是什么?   1回答

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

Jackknife vs Bootstrap   1回答

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

python产生一个随机置换?   1回答

什么是SMOTE sampling方法?   3回答

SMOTE对于categorical feature如何处理?   2回答

关于两个正态总体抽样分布的独立性问题   1回答

如何对流数据(stream data)进行无差别抽样   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!