streaming中常用的随机抽样问题(reservoir sampling)

作者:luozhipeng   发表日期:2015-6-22  浏览:705次

最近看mahout的KMeans聚类算法时发现了如下一段代码:


   if (currentSize < k) {
        chosenTexts.add(newText);
        ClusterWritable clusterWritable = new ClusterWritable();
        clusterWritable.setValue(newCluster);
        chosenClusters.add(clusterWritable);
   } else {
        int j = random.nextInt(index);
        if (j < k) {
             chosenTexts.set(j, newText);
             ClusterWritable clusterWritable = new ClusterWritable();
             clusterWritable.setValue(newCluster);
             chosenClusters.set(j, clusterWritable);
         }
    }
    index++;

这段代码是在选取随机种子的类中(RandomSeedGenerator.java),之前我并没了解过随机抽样问题,看到这段代码感觉有点纳闷,按常用的方法,如果在L个种子中要选k个的话,直接在L内生成随机数就能解决。而这段代码的含义是把先读到前k个种子就作为临时选中的种子,在读k+1个后都会生成一个随机数,int j = random.nextInt(index); 即生成0<=j<=index-1随机数,然后当j<k时,就把下标为j(从0开始标)替换成当前的种子。

大致介绍了下代码,大家觉得每个种子被选中的概率是一样吗?答案是一样的(伪随机数可信下)。那么这种随机取法又有什么好处呢?如果我们要处理的数据事先不知道有多少条,然而数据量又非常大无法全部加载,若要等概率的选取k条数据,那么这个方法就派上用场了。

 

问题描述:对于n(n>=k),先临时选取前k个,对于k+1<=i<=n,如果每次以s1的概率的决定是否选取第i个元素,那么最后每个元素被选中的概率都相等,即为s2

 

证明一:

对于某个元素x,且x<=n,那么它最终被选中的概率是:

P(x) = 访问x时被选中的概率*Π(后面的元素没被选中的概率+后面的元素被选中的概率*但是没有替换x的概率)

s3

 

 

证明二:

可以使用数学归纳法。

假设当x=n时成立,即每个元素被选中的概率都是s2,下面来证明x=n+1时。

对于最后一个元素,即第n+1个,它被选中的概率直接是s5 ,不会被后面的覆盖。

对于1<= t <=n,设

P(t)表示第t个元素被选中的概率

P(发生替换)表示有元素被替换的概率

P(不发生替换)表示没有元素被替换的概率

P(t|发生替换)表示发生替换的情况下,第t个元素没有被替换

P(t|不发生替换)表示不发生替换,t没有被替换

P(发生替换) = s5          P(t|发生替换) = s6   (前一项表示之前被选中的概率,后一项表示k个中替换的不是t)

P(不发生替换) = s7    P(t|不发生替换)=s2

s8

 

标签:

本文固定链接: http://www.luozhipeng.com/?p=297
转载请注明: luozhipeng 2015-6-22 于 罗志鹏的BLOG 发表

上一篇: :下一篇
返回顶部