用Python写算法 | 蓄水池算法实现随机抽样

现在有一组数,不知道这组数的总量有多少,请描述一种算法能够在这组数据中随机抽取k个数,使得每个数被取出来的概率相等。

如果这组数有n个,那么每个数字取到的概率就是k/n,但是这个问题的难点在于不知道这组数的总数,也就是不知道n,那么该怎么计算每个数取到的概率呢?

01

蓄水池算法

游泳池(蓄水池)大家都不陌生,有些游泳池中的水是活的,有入水管也有出水管,那么和泳池体积相当的水流过之后,是不是泳池中所有的水都会被替换呢?当然不是,有的水在泳池中可能会存留很久,有的可能刚进去就流走了。仿照这种现象,蓄水池抽样算法诞生了,蓄水池算法的关键在于保证流入蓄水池的水和已经在池中的水以相同的概率留存在蓄水池中。并且蓄水池算法可以在不预先知道总量的情况下,在时间复杂度O(N)的情况下,来解决这类采样问题。

02

核心原理

这一部分涉及公式,为了保证效果直接贴了图过来。

03

Python实现

接下来尝试用Python实现一下蓄水池算法,由于蓄水池算法是在事先不知道总量的情况下抽样的,所以定义一个方法来接收单个元素,并且把这个方法放在类中,以持有采样后的数据。

 1import random
 2
 3
 4class ReservoirSample(object):
 5
 6    def __init__(self, size):
 7        self._size = size
 8        self._counter = 0
 9        self._sample = []
10
11    def feed(self, item):
12        self._counter += 1
13        # 第i个元素(i <= k),直接进入池中
14        if len(self._sample) < self._size:
15            self._sample.append(item)
16            return self._sample
17        # 第i个元素(i > k),以k / i的概率进入池中
18        rand_int = random.randint(1, self._counter)
19        if rand_int <= self._size:
20            self._sample[rand_int - 1] = item
21        return self._sample

04

测试代码

接下来实现一个测试用例验证实现的算法是否正确,既然是随机抽样,无法通过单词测试来验证是否正确,所以通过多次执行的方式来验证,比如从1-10里随机取样3个数,然后执行10000次取样,如果算法正确,最后结果中1-10被取样的次数应该是相同的,都是3000上下。

 1import unittest
 2from collections import Counter
 3
 4from reservoir_sample import ReservoirSample
 5
 6
 7class TestMain(unittest.TestCase):
 8
 9    def test_reservoir_sample(self):
10        samples = []
11        for i in range(10000):
12            sample = []
13            rs = ReservoirSample(3)
14            for item in range(1, 11):
15                sample = rs.feed(item)
16            samples.extend(sample)
17        r = Counter(samples)
18        print(r)
19
20if __name__ == '__main__':
21    unittest.main()

输出的结果如下

1Counter({7: 3084, 6: 3042, 10: 3033, 3: 3020, 8: 3016, 5: 2997, 4: 2986, 2: 2972, 9: 2932, 1: 2918})

上面输出了每个数字被取样到的次数,通过图表可以清晰的看到分布情况

可以看出蓄水池算法对于随机抽样还是非常适合的,每个元素的抽样概率都相同。

05

代码

上述的算法和测试代码已经放在Github,地址是https://github.com/python-fan/reservoir-sample,可以直接下载使用。

原文发布于微信公众号 - Python私房菜(python-fans)

原文发表时间:2018-08-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

图像处理中任意核卷积(matlab中conv2函数)的快速实现。

     卷积其实是图像处理中最基本的操作,我们常见的一些算法比如:均值模糊、高斯模糊、锐化、Sobel、拉普拉斯、prewitt边缘检测等等一些和领域相关的算...

9708
来自专栏大壮

iOS transform(2D仿射)

1525
来自专栏大数据风控

Python中的交叉分析pivot_table

交叉分析 通常用于分析两个或两个以上,分组变量之间的关系,以交叉表形式进行变量间关系的对比分析; 从数据的不同维度,综合进行分组细分,进一步了解数据的构成、分...

3188
来自专栏风口上的猪的文章

机器学习(2) - KNN识别MNIST

 https://github.com/s055523/MNISTTensorFlowSharp

2242
来自专栏Bay的专栏

如何使用 scikit-learn 为机器学习准备文本数据

文本数据需要特殊处理,然后才能开始将其用于预测建模。

2295
来自专栏机器之心

教程 | 在Python和TensorFlow上构建Word2Vec词嵌入模型

选自adventuresinmachinelearning 机器之心编译 参与:李诗萌、刘晓坤 本文详细介绍了 word2vector 模型的模型架构,以及 T...

4867
来自专栏码云1024

a-start寻路算法

在英雄联盟之中,当你和你的队友都苦苦修炼到十八级的时候,仍然与敌方阵营不分胜负,就在你刚买好装备已经神装的时候,你看见信息框中一条队友的消息:“大龙集合”,这个...

3562
来自专栏zingpLiu

机器学习之线性代数

  完整内容已上传到github:https://github.com/ZingP/machine-learning/tree/master/linear_al...

1961
来自专栏计算机视觉与深度学习基础

【深度学习】写诗机器人tensorflow实现

代码地址:https://github.com/hjptriplebee/Chinese_poem_generator, 欢迎fork, star 机器人命名M...

2.7K6
来自专栏PaddlePaddle

【进阶篇】Recurrent Group教程

导语 PaddlePaddle 高度支持灵活和高效的循环神经网络配置。接下来的进阶篇推文将围绕RNN模型展开,指导你如何在 PaddlePaddle 中配置和使...

3655

扫码关注云+社区

领取腾讯云代金券