1

母集団内の要素の頻度を表すデータ系列が与えられた場合、それをダウンサンプリングする最も簡単な方法は何ですか?

次の母集団:pop = ['a', 'b', 'a', 'c', 'c', 'd', 'c', 'a', 'a', 'b', 'a']

次のように要約できます。freq = {'a': 5, 'c': 3, 'b': 2, 'd': 1}

シンプルな使用：from collections import Counter; Counter(pop)

その母集団をランダムに 5 人にダウンサンプリングするには、次のようにします。

>>> from random import sample
>>> from collections import Counter
>>> pop = ['a', 'b', 'a', 'c', 'c', 'd', 'c', 'a', 'a', 'b', 'a']
>>> smaller_pop = sample(pop, 5)
>>> smaller_freq = Counter(smaller_pop)
>>> print smaller_freq
Counter({'a': 3, 'c': 1, 'b': 1})

freqしかし、リストを作成せずに情報から直接これを行う方法を探していpopます。あなたは、次のような手順が必要ないことに同意するものとします:

>>> from random import sample
>>> from collections import Counter
>>> flatten = lambda x: [item for sublist in x for item in sublist]
>>> freq = {'a': 5, 'c': 3, 'b': 2, 'd': 1}
>>> pop = flatten([[k]*v for k,v in freq.items()])
>>> smaller_pop = sample(pop, 5)
>>> smaller_freq = Counter(smaller_pop)
>>> print smaller_freq
Counter({'a': 2, 'c': 2, 'd': 1})

メモリの考慮事項と速度要件のために、リストをメモリに配置することは避けたいと思いpopます。これは、ある種の加重乱数発生器を使用して確実に実行できます。

4

1 に答える 1

1

周波数をダウンサンプリングする基本的なアルゴリズムは次のとおりです。

import random
import bisect
import collections

def downsample(freq, n):
    cumsums = []
    total = 0
    choices, weights = zip(*freq.items())
    for weight in weights:
        total += weight
        cumsums.append(total)
    assert 0 <= n <= total
    result = collections.Counter()
    for _ in range(n):
        rnd = random.uniform(0, total)
        i = bisect.bisect(cumsums, rnd)
        result[choices[i]] += 1
        cumsums = [c if idx<i else c-1 for idx, c in enumerate(cumsums)]
        total -= 1
    return result

freq = {'a': 5, 'c': 3, 'b': 2, 'd': 1}
print(downsample(freq, 5))

次のような結果を出力します

Counter({'c': 2, 'a': 1, 'b': 1, 'd': 1})
于 2013-06-13T14:31:57.097 に答える