如何进行随机抽样？

正文

请到「今天看啥」查看全文

import random

def SelectRandomK(L, N, k):

    for i in range(0, k):
        # 产生i到N-1间的随机数
        j = random.randint(i, N - 1)
        L[i], L[j] = L[j], L[i]

这个算法实现的缺点就是依赖了数据总数N。如果不知道N有没有办法呢？

那就是蓄水池算法。蓄水池算法是大数据抽样常用的算法，在不知道数据总数目的情况下可以完成随机抽样。

先从最简单的蓄水池抽样算法说起，即蓄水池中数据的数目为1。先把第一个数据以概率1/1放入蓄水池，第二个数据以1/2的概率替换蓄水池中数据，第三个数据以1/3的概率替换蓄水池中数据，第k个数据以1/k的概率替换蓄水池中数据，如此重复，直至遍历完所有的数据。

这样完成后，每个数据被抽中的概率是相等的，即使不知道数据总数目。下面，就用数学归纳法完成证明：

只需要证明当遍历至第k行时，前面k行中的任意一行被抽取的概率均为1/k。

证明:（1）当i=1时，第一行被抽取的概率为1/1，成立。

（2）假设当i=k时成立，则前面k行中的任意一行被抽取的概率为1/k。现证明i=k+1时成立。

请到「今天看啥」查看全文