2015年10月 的存档

蓄水池抽样浅说 (3)

2015年10月23日 没有评论

加个权吧

前面说的是均匀抽样,要是想加个权怎么办呢?先说加权有什么用呢?比如我们已经统计好了搜索的关键字和词频,那么有了加权就可以直接用这个数据来抽样而无需把关键字重复好多遍了。

我们先来看看这个抽样应该是怎么样的。假设这总共 $n$ 项都摆在你面前了,设第 $i$ 项的权值为 $w_i$,那么我们抽到这一项概率应该是

$$P_i = \frac{w_i}{w_1 + w_2 + \cdots + w_n}$$

我们现在来看看,如果把这 $n$ 项按照第 $n$ 项、第 $n-1$ 项、…… 第 $2$ 项、第 $1$ 项的顺序抽出来,这个概率是多少。因为这 $n$ 项的顺序是可以随便摆的,所以它求出来是有一定普遍意义的。

第一次抽出第 $n$ 项的概率是

$$P_n(1) = \frac{w_n}{w_1 + w_2 + \cdots + w_n}$$

第 $n$ 项已经被抽走了,那第二次抽到第 $n-1$ 项的概率是

$$P_{n-1}(2) = \frac{w_{n-1}}{w_1 + w_2 + \cdots + w_{n-1}}$$

以此类推,按照这个顺序抽出所有元素的概率就是

$$P(S) = \prod_{i=1}^n \frac{w_i}{w_1+w_2+\cdots w_i} $$

这有什么用呢?别着急,先记下这个结果,我们下面来说说算法怎么做。

阅读全文…

蓄水池抽样浅说 (2)

2015年10月22日 没有评论

没有看过前一篇的同学请看这里:蓄水池抽样浅说 (1)

跳跳跳!—— Algorithm X

前面介绍的方法都很好,但是要计算 $n-k$ 个随机数实在是有点浪费时间…… 有兴趣的同学可以把那个调用函数换成比如 reservoirSample(range(10**8), 10**5),就知道这东西还是要算上一会儿的了。

再来看看这个过程吧——把前 $k$ 个元素放进去之后,随机决定接下来的元素要不要放进去,但是每次决定时都需要产生一个随机数。要是我们能够确定应该跳过多少个元素,不就可以省掉很多生成随机数的工夫了吗?每一步过程就变成了

  • 确定该跳过多少个元素 $S(k, n)$
  • 跳过 $S(k, n)$ 个元素
  • 从前 $k$ 个元素中随机产生一个要替换的元素,用下一个元素替换

阅读全文…

蓄水池抽样浅说 (1)

2015年10月21日 没有评论

jar_of_marbles

我们有时候会有进行数据抽样的需要,比如要从文件中随机取出若干行,或从数据集中随机取出若干数据进行分析。通常情况下这并不是什么难事,比如 Python 中直接提供了 random.sample() 来做这件事,Numpy 中更提供了功能更为强大的 numpy.random.choice()。然而这些东西都有一个问题,就是你必须把整个数据集读到内存里。如果数据集超出了内存的限制,或者要对一个持续的输入流做抽样,即从包含 $n$ 个项目的集合中(等概率)选取 $k$ 个样本,其中 $n$ 为很大或未知,又该怎么做呢?

阅读全文…