精华内容
下载资源
问答
  • 蓄水池算法

    2018-01-26 22:24:07
    最近有个需求,需要从不固定大小的数据集中取固定数量的数据作为样本,有个同学提到了蓄水池算法,于是了解了一下。 蓄水池算法,本身是为了解决海量数据的随机抽样问题,在算法领域应用还是挺广泛的,由于数据本身...

    最近有个需求,需要从不固定大小的数据集中取固定数量的数据作为样本,有个同学提到了蓄水池算法,于是了解了一下。

    蓄水池算法,本身是为了解决海量数据的随机抽样问题,在算法领域应用还是挺广泛的,由于数据本身是有权重,又出现了加权蓄水池算法。

    蓄水池算法

    问题描述: 给定一个不固定长度的数据集合 sequence,从中等概率地抽取 k 个元素作为样本返回

    问题思路: 先把样本填满,然后不断往样本里面等概率替换元素

    算法实现

    def reservior_sampling(sequence, k):
        n = len(sequence)
        if k > n:
            return sequence
    
        sample = list()
        for i in range(k):
            sample.append(sequence[i])
    
        for i in range(k, n):
            j = random.randint(0, i)
            if j >= k:
                continue
            sample[j] = sequence[i]
    
        return sample

    这里需要注意的是往样本里面替换元素的时候,第 i 个元素能被选中用来替换的概率是 k / i + 1,这样就能保证每个元素被选中的机会都是均等的

    加权蓄水池算法

    问题描述: 给定一个不固定长度的非常大的数据集合 sequence,集合中每个元素包含一个权重 weight,按照权重从集合中抽取 k 个元素返回

    问题思路: 和蓄水池算法的思路一样,先把样本填满,然后不断地按照权重替换元素

    算法实现

    def weighted_reservior_sampling_achao(sequence, k):
        n = len(sequence)
        if k > n:
            return sequence
    
        wsum = 0
        sample = list()
        for i in range(k):
            sample.append(sequence[i])
            wsum += sequence[i]['weight'] / k
    
        for i in range(k, n):
            wsum += sequence[i]['weight'] / k
            p = sequence[i]['weight'] / wsum
            j = random.random()
            if j <= p:
                sample[random.randint(0, k-1)] = sequence[i]
    
        return sample

    这里第 i 个元素被选中用来替换的概率是 sequence[i].weight * k / sum(sequence[0:i+1].weight),当所有权重都一致的时候,就和蓄水池算法是一致的了。

    这里面有个小问题,就是一开始用来填充样本的数据,其实是等概率的,这样会导致,填充样本的数据权重失效,但是这个问题只在数据集合较小(准确地说 klen(sequence) 比较接近)的情况下才会有比较明显的缺陷,在海量数据集的情况下,这种影响是微乎其微的。

    完整代码: https://github.com/hatlonely/algorithm/blob/master/reservoir_sampling.py

    参考链接

    Reservoir sampling: https://en.wikipedia.org/wiki/Reservoir_sampling

    转载请注明出处
    本文链接:http://hatlonely.github.io/2018/01/26/蓄水池算法/

    展开全文
  • 蓄水池算法 leetcode 算法学习笔记 排序 快排:com.monkey.sort.Code01_QuickSort 链表 倒序单链表:com.monkey.linkedlist.Code01_ReverseLinkedList 字符串 KMP算法: 二叉树 前序,中序,后序遍历: 按层遍历: ...
  • 蓄水池算法 leetcode leetcode practice 动态规划 DynamicProgramming 贪心算法 GreedyAlgorithm 分治算法 DivideAndConquer 头脑风暴 Brainteaser 堆 Heap 栈 Stack 数学 Math 队列 Queue 排序 Sort Random Trie ...
  • 蓄水池算法证明

    2018-10-27 20:57:16
    蓄水池算法 蓄水池算法是一种大数据随机抽样算法,对于海量流式数据,在未知数据规模(N)的情况下.对数据样本进行随机选取k个样本,来达到均匀抽样的目的:对于每个样本被选择的概率都是Pxi被选择=knP_{x_i被选择}=\frac{...

    蓄水池算法

    蓄水池算法是一种大数据随机抽样算法,对于海量流式数据,在未知数据规模(N)的情况下.对数据样本进行随机选取k个样本,来达到均匀抽样的目的:对于每个样本被选择的概率都是Pxi=knP_{x_i被选择}=\frac{k}{n}.

    算法

    int a[k]={x1,x2,....,xk}  //用数据流中的前k个数来初始化一个容量为k的数组
    for i = k to N:
        m=random(0,i)  //在[0,i] 之间随机
        if m < k:
            exchange a[m] and a[i] 
    

    证明

    对于第i个数(i>k)来说,它被选择的概率是ki+1\frac{k}{i+1},如果它被选择替换蓄水池中的一个数,那么,对于第i+1个数来说如果要替换第i个数那么概率为ki+11k=1i+1\frac{k}{i+1}*\frac{1}{k}=\frac{1}{i+1},保留第i个数的概率为11i+11-\frac{1}{i+1}.以此类推,直到第N个数替换第i个数:

    ki(11i+1)(11i+2)...(11N)=kN\frac{k}{i} *(1-\frac{1}{i+1})* (1-\frac{1}{i+2}) *...(1-\frac{1}{N})=\frac{k}{N}

    对于第1~k个数,也可以使用类似的方式来证明具有相等的概率. 证明完毕.

    展开全文
  • 蓄水池算法 leetcode MyLeetCodeSummary 引言: 刷题总结,不想只是机械性刷题,想把刷过的题尽可能都琢磨明白,这样才能融会贯通,真正掌握算法,随心所欲的运用于实践。 推荐的Repo: 争取定期更新题目类型的总结 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,778
精华内容 711
关键字:

蓄水池算法