샘플 크기 1은 저수지 샘플링을 고려합니까?

Question

저는 코드가 저수지 표본 추출이라는 것을 알고 싶습니다. 내가 처리하고자하는 페이지 뷰 스트림이 있습니다. 한 번에 한 페이지 뷰를 처리하고 있습니다. 그러나 대부분의 페이지 뷰가 동일하므로 임의로 페이지 뷰를 선택 (한 번에 하나씩 처리)하고 싶습니다. 예를 들어, 페이지 뷰가

인 경우

[www.example.com, www.example.com, www.example1.com, www.example3.com, ...] 

한 번에 하나의 요소 만 처리합니다. 여기 내 코드가있다. 저수지 샘플링 알고리즘에 따라

import random 

def __init__(self): 
    self.counter = 0 

def processable(): 
    self.counter += 1 
    return random.random() < 1.0/self.counter 

Answer 1

(여기에서 찾을 수 있습니다 : https://en.wikipedia.org/wiki/Reservoir_sampling를) 우리가 하나의 페이지 뷰 (저수지의 크기 = 1)를 저장하는 경우, 다음과 같은 구현하는 것이 방법을 보여줍니다 스트리밍 페이지 뷰에서 확률 적 선택의 전략 균일 한 선택 확률로 이어진다

import numpy as np 
import matplotlib.pyplot as plt 
max_num = 10 # maximum number of pageviews we want to consider 
# replicate the experiment ntrials times and find the probability for selection of any pageview 
pageview_indices = [] 
ntrials = 10000 
for _ in range(ntrials): 
    pageview_index = None # index of the single pageview to be kept 
    i = 0 
    while True: # streaming pageviews 
     i += 1 # next pageview 
     if i > max_num: 
      break 
     # keep first pageview and from next pageview onwards discard the old one kept with probability 1 - 1/i 
     pageview_index = 1 if i == 1 else np.random.choice([pageview_index, i], 1, p=[1-1./i, 1./i])[0] 
     #print 'pageview chosen:', pageview_index 
    print 'Final pageview chosen:', pageview_index 
    pageview_indices.append(pageview_index) 
plt.hist(pageview_indices, max_num, normed=1, facecolor='green', alpha=0.75) 
plt.xlabel('Pageview Index') 
plt.ylabel('Probability Chosen') 
plt.title('Reservoir Sampling') 
plt.axis([0, max_num+1, 0, 0.15]) 
plt.xticks(range(1, max_num+1)) 
plt.grid(True) 

위에서 알 수있는 바와 같이

, 선택된 뷰 인덱스의 확률은 각각 거의 균일 (1/10 10 페이지 뷰), 수학적으로 균일 한 것으로 판명 될 수 있습니다.