用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 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

写给开发者的机器学习指南(十三)

在我们实际使用支持向量机(SVM)之前,我先简要介绍一下SVM是什么。 基本SVM是一个二元分类器,它通过选取代表数据点之间最大间隔的超平面将数据集分成2部分。...

611
来自专栏SeanCheney的专栏

Numpy和MatplotlibPython科学计算——Numpy线性代数模块(linalg)随机模块(random)Python的可视化包 – Matplotlib2D图表3D图表图像显示

Python科学计算——Numpy Numpy(Numerical Python extensions)是一个第三方的Python包,用于科学计算。这个库的前身...

5744
来自专栏null的专栏

机器学习算法实现解析——word2vec源码解析

在阅读本文之前,建议首先阅读“简单易学的机器学习算法——word2vec的算法原理”(目前还没发布),掌握如下的几个概念: 什么是统计语言模型 神经概率语言模型...

6387
来自专栏zingpLiu

机器学习之线性代数

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

1711
来自专栏大数据风控

Python中的交叉分析pivot_table

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

2798
来自专栏技术随笔

[RNN] Simple LSTM代码实现 & BPTT理论推导

4574
来自专栏贾老师の博客

启发式寻路算法

4803
来自专栏PaddlePaddle

【进阶篇】Recurrent Group教程

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

3515
来自专栏Bay的专栏

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

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

2265
来自专栏ATYUN订阅号

四个用于Keras的很棒的操作(含代码)

Keras是最广泛使用的深度学习框架之一。它在易于使用的同时,在性能方面也与TensorFlow,Caffe和MXNet等更复杂的库相当。除非你的应用程序需要一...

1254

扫码关注云+社区