저수지 샘플링 (연못 샘플링)

제목 1:
데이터 흐름 을 보 여 줍 니 다. 이 데이터 흐름 의 길이 가 크 거나 알 수 없습니다.또한 이 데이터 흐름 에 한 번 만 접근 할 수 있 습 니 다.데이터 흐름 에서 모든 데이터 가 선 택 될 확률 이 같 도록 무 작위 선택 알고리즘 을 쓰 십시오.
복잡 한 문제 에 대해 서 는 반드시 귀납 적 정 리 를 배 워 야 한다. 즉, 작은 사례 에서 착안 한 다음 에 분석 하고 결론 을 내 린 다음 에 증명 해 야 한다.그렇지 않 으 면 추상 적 인 문제 에 부 딪 히 면 예 를 들 어 이 문 제 를 느끼 지 않 고 직접 풀기 가 비교적 어렵다.
이 문제 의 어려움 은 데이터 흐름 의 길 이 를 알 수 없다 는 것 이다. 이미 알 고 있다 면 so easy.지금 귀납 적 총 결 을 진행한다.
1) 길이 가 1 이 고 하나의 데이터 만 있 으 며 바로 돌아 오 면 됩 니 다. 이 데 이 터 는 돌아 올 확률 이 1 입 니 다.
2) 길이 가 2 입 니 다. 첫 번 째 데 이 터 를 읽 을 때 마지막 데이터 가 아니 라 는 것 을 알 게 되 었 습 니 다. 데이터 흐름 이 아직 끝나 지 않 았 기 때문에 계속 읽 고 두 번 째 데 이 터 를 읽 었 을 때 이미 끝 났 음 을 알 게 되 었 습 니 다.그래서 지금의 문 제 는 확률 이 그 중의 하나 로 돌아 오 기 를 기다 리 는 것 이다. 분명히 확률 은 0.5 이다.그래서 이때 우 리 는 0 에서 1 의 난수 p 를 생 성 할 수 있다. 만약 에 p 가 0.5 보다 작 으 면 두 번 째 로 돌아 가 고 0.5 보다 크 면 첫 번 째 로 돌아 갈 수 있다.분명히 이때 두 데이터 가 되 돌아 올 확률 은 같다.
3) 길이 가 3 이 므 로 우 리 는 사전에 분석 할 수 있 으 며, 주제 의 뜻 을 만족 시 키 기 위해 서 는 모든 데이터 가 돌아 올 확률 이 1 / 3 임 을 보증 해 야 한다.그 다음 에 데이터 흐름 을 분석 하고 먼저 첫 번 째 데 이 터 를 읽 은 다음 에 두 번 째 데 이 터 를 읽 습 니 다. 이 때 는 2) 로 처리 하고 하나의 데 이 터 를 보존 할 수 있 습 니 다. 모든 데 이 터 는 1 / 2 입 니 다.이때 세 번 째 데 이 터 를 읽 고 끝 에 있 는 것 을 발 견 했 습 니 다. 제목 의 뜻 을 만족 시 키 기 위해 서 는 1 / 3 의 확률 로 이 데 이 터 를 가 져 올 지 여 부 를 결정 해 야 합 니 다.현재 앞의 두 숫자 도 1 / 3 의 확률 로 돌아 가 는 지, 그렇다면 전체적으로 만족 하 는 지 분석 하고 있다.데이터 1 과 데이터 2 가 동시에 남 을 확률 은 1 / 2 * (1 - 1 / 3) = 1 / 3 이다.1 / 2 데이터 1 과 데이터 2pk 에 만 남 을 수 있 는 확률, 1 - 1 / 3 은 데이터 3 이 남지 않 을 확률 을 가리킨다.따라서 길이 가 3 인 데이터 흐름 에 대해 세 번 째 데 이 터 를 읽 을 때 0 에서 1 의 난수 p 를 생 성 할 수 있 습 니 다. p 가 1 / 3 보다 작 으 면 세 번 째 데 이 터 를 되 돌려 줍 니 다. 그렇지 않 으 면 앞의 두 pk 가 남 긴 데 이 터 를 되 돌려 줍 니 다.
위의 분석 을 통 해 우 리 는 결론 을 얻 을 수 있다. n 번 째 데 이 터 를 얻 을 때 우 리 는 0 에서 1 번 의 난수 p 를 생 성 하고 p 가 1 / n 보다 작 으 면 n 번 째 수 를 보류한다.1 / n 이상 이면 앞의 수 를 계속 유지 합 니 다.데이터 흐름 이 끝 날 때 까지 이 수 를 되 돌려 줍 니 다.
다음은 수학 귀납법 으로 이 결론 을 증명 한다.
1) n = 1 일 때 첫 번 째 요 소 는 1 / 1 의 확률 로 되 돌아 가 조건 에 부합 한다.
2) n = k 일 때 성립 된다 고 가정 하면 모든 요 소 는 1 / k 의 확률 로 되 돌아 가 n = k + 1 일 때 성립 되 는 지 여 부 를 증명 한다.
마지막 요 소 는 1 / k + 1 의 확률 로 돌아 가 고 조건 에 부합 되 며 앞의 k 개 데이터 에 대해 돌아 갈 확률 은 1 / k * (1 - 1 / k + 1) = 1 / k + 1 로 주제 의 뜻 을 만족시킨다.
위 에서 말 한 바 와 같이 결론 은 성립 된다.
제목
제목 1 의 경우 마지막 으로 돌아 오 는 결과 의 길 이 는 k 로 바 뀌 는데 이것 이 바로 연못 표본 이다.
분명히 문제 1 에 대한 이해 가 생 겼 다. 우 리 는 결론 을 직접 바 꿀 수 있 고 위의 1 / n 을 k / n 으로 바 꾸 면 된다.
n 번 째 데 이 터 를 가 져 올 때, 우 리 는 0 에서 1 의 무 작위 p 를 생 성 합 니 다. 만약 p 가 k / n 보다 작 으 면, 교체 탱크 의 임의의 하 나 는 n 번 째 수 입 니 다.k / n 보다 크 면 앞의 수 를 계속 유지 합 니 다.데이터 흐름 이 끝 날 때 까지 이 k 개 수 를 되 돌려 줍 니 다.그러나 컴퓨터 계산 액수 의 정확성 을 확보 하기 위해 서 는 일반적으로 0 에서 n 의 임 의 수 를 생 성 하 는데 k 에 비해 이 치 는 같다.
같은 방법 으로 증명 할 수 있다.
(1) 초기 상황 k < = n, 저수지 에 나타 난 k 개 원소 의 출현 확률 은 모두 일치 하고 모두 1 (2) 의 첫걸음 이다.첫 번 째 단 계 는 k + 1 개의 요 소 를 처리 하 는 상황 을 말한다.두 가지 상황 으로 나 뉜 다. 요소 가 모두 교체 되 지 않 았 다.그 중 어떤 요 소 는 k + 1 개의 요소 로 교체 되 었 다.우 리 는 먼저 상황 2: k + 1 개 요소 가 선 택 될 확률 이 k / (k + 1) (공식 k / i 에 따라) 이기 때문에 이 새로운 요소 가 저수지 에 나타 날 확률 은 반드시 k / (k + 1) 이다.다음은 저수지 에 남 은 원소 가 나타 날 확률, 즉 1 - P (이 원소 가 교 체 될 확률) 를 살 펴 보 자.저수지 에서 임의의 원소 가 교 체 될 확률 은 (k / k + 1) * (1 / k) = 1 / (k + 1) 이다. 즉, 먼저 k + 1 개의 원소 가 선 택 된 다음 에 자신 이 집 합 된 k 개의 원소 중에서 선 택 된 것 을 의미한다.그것 이 나타 날 확률 은 1 - 1 / (k + 1) = k / (k + 1) 이다.낡은 원소 와 새로운 원소 가 나타 날 확률 이 같다 는 것 을 알 수 있다.상황 1: 요소 가 모두 교체 되 지 않 았 을 때 모든 요소 의 출현 확률 은 똑 같 을 것 이다. 이것 은 분명 하 다.그런데 구체 적 으로 얼마 일 까요?바로 1 - P (k + 1 번 요소 가 선 택 됨) = 1 - k / (k + 1) = 1 / (k + 1) 입 니 다.(3) 귀납법: 위의 과정 을 반복 하고 i 단계 에서 i + 1 단계 까지 모든 요소 가 나타 날 확률 이 같다 는 것 을 증명 하면 된다.
의사 코드 는 다음 과 같 습 니 다:

//stream     
//reservoir       k   

// stream   k   reservoir；
for ( int i = 1; i < k; i++)
    reservoir[i] = stream[i];
for (i = k; stream != null; i++) {
    p = random(0, i);
    if (p < k) reservoir[p] = stream[i];
return reservoir;