Reservoir Sampling

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

Reservoir sampling은 데이터 스트림에서 임의의 개수의 데이터를 추출하는 방법입니다. 이를 이해하기 위해서는 data stream에 대해 알아야 할 필요가 있습니다.

Data Stream

데이터 스트림은 끊임없이 입력되는 데이터를 얘기합니다. 이 데이터는 외부에서 발생해 하나 이상의 경로를 통해 빠르게 입력이 되고, 발생 속도와 빈도가 외부에서 결정됩니다. 대표적인 예시로 은행 거래 내역, 서버 로그 데이터 등이 있습니다.
데이터 스트림에 하는 질의는 주로 2가지로 분류할 수 있습니다.

• 1회성 질의(Ad-hoc queries)    ex) 지금까지 스트림에서 발견된 최댓값은?
• 지속적 질의(Standing queries)    ex) 스트림에서 새로운 최댓값이 나올 때마다 출력해 줘.

 

이러한 질의들에 대해 수행하기 위해서는 대용량의 데이터 스트림을 저장해야 합니다. 하지만 실질적으로는 메모리가 제한된 상황이 많이 때문에 스트림으로 들어온 모든 데이터를 저장하는 것은 불가능합니다.
이를 해결하는 모델 중 sliding windows가 있습니다. 이는 스트림에서 가장 최근의 N개의 데이터만을 window에 저장하는 아이디어입니다. 이는 최근 N개의 데이터에 대한 질의에 유용합니다. 그러나 N의 값이 너무 커지면 이 또한 메모리에 저장할 수 없는 문제를 해결하지 못합니다.
결국 스트림에서 일부 sampling 해서 sampling 된 데이터들을 통해 원본 스트림의 특징을 파악하는 방법을 사용하게 됩니다. 하지만 데이터 스트림의 끝을 모르는 상황 속에서 각 데이터가 뽑힐 확률을 동일하게 해야 합니다.

Reservoir Sampling

이러한 상황 속에서 사용하는 방법이 reservoir sampling입니다. 과정은 다음과 같습니다.

• 스트림의 처음 k개의 값을 크기 k의 배열에 저장합니다.
• 다음 i번째 데이터 x가 들어올 때마다 0 이상 i 미만의 임의의 정수 r을 뽑습니다.
• r이 k 미만이면, 배열의 r번째 값을 x로 대체합니다.

 

1부터 1씩 커지는 자연수들로 이루어진 데이터 스트림에서 3개의 값을 sampling 하는 상황을 생각해 봅시다. 먼저 1, 2, 3은 배열 안에 모두 저장됩니다.

1

2

3

그리고 4의 값이 들어올 때는 4번째 순서이므로 0부터 3 사이의 정수를 임의로 선택합니다. 만약 선택된 정수가 3이면 4를 배열에 저장하지 않습니다. 선택된 정수가 1이었으면, 첫 번째 위치에 있는 값을 4로 대체합니다.

1

4

3

이와 같은 과정을 스트림을 통해 새로 들어오는 데이터에 대해 매번 시행합니다.

분석

Reservoir sampling의 과정에서 모든 스트림의 데이터가 뽑힐 확률이 동일한지 계산해 봅시다.
N개의 값이 스트림을 통해 입력된 상황에서 어떤 값이 배열에 존재할 확률을 k / n이라 가정합시다. 이를 통해 처음 k개의 데이터가 들어왔을 때는 확률이 k / k = 1로 처음 k개의 데이터의 뽑힐 확률은 동일합니다.
N + 1 번째의 값이 들어올 때 이 새로운 값이 배열에 입력될 확률은 k / (n + 1)입니다.
그리고 배열 안에 있는 값을 기준으로 생각할 때, 새로 들어온 값이 자신의 위치에 오지 않을 확률은 1 - 1 / (n + 1)입니다. 따라서 배열의 값들이 대체되지 않고 살아남을 확률을 아래의 식으로 계산할 수 있습니다.
$$ {k \over n} \times \left( 1 - {1 \over n +1} \right) = {k \over n} \times {n \over n +1}$$
계산 결과 k / (n + 1)로 새로운 값이 선택될 확률과 같음을 확인할 수 있습니다.