Mining Data Streams

빅데이터를 다뤄야 하는 많은 상황들에서, 데이터들은 끊임없이 생산되어 들어오고 이 데이터들을 저장하고 처리하기 위한 메모리는 한정되어 있기 떄문에 이들을 전부 저장할 수 없는 경우가 많다. 따라서 데이터들을 일종의 Stream으로 보고 이들을 관리하는 것이 중요하다.

이를 Stream Management라고 하는데, Stream Management에서는 데이터를 무한히 많고, 정적이지 않은(non-stationary) 즉, 데이터의 분포가 계속해서 바뀌는 성질의 것을 받아들인다. 

 

 

The Stream Model

기본적인 데이터 스트림 모델

데이터를 처리하는 기본적인 모델인 Stream Model은 위와 같이 구성이 된다.

이는 여러 가지 특성을 지니는데, 

• 입력되는 데이터 값들(input elements)은 빠른 속도로 입력이 되고, 이들의 입력속도는 각기 다르며, 여러개의 입력 포트를 통해서 입력된다.
• 시스템은 전체 Data Stream을 메모리에 모두 저장할 수 없다. 그림에서도 볼 수 있듯이 Working Storage, Archival Storage의 크기는 유한하기 때문에 무한한 크기의 스트림을 모두 저장할 수는 없다. 

이 스트림에 입력되는 데이터들은 여러 가지 방향으로 사용되고 있는데 

구글, 네이버와 같은 포털사이트에서 지난 1시간동안 어떤 포스트들이 가장 많이 클릭이 되었는지, SNS에서 어떤 피드들이 지난 일주일동안 많은 사랑을 받았는지 등을 이 Stream Model을 통해서 알아낼 수 있다.

 

Problems on Data Streams

데이터 스트림을 조사하여 얻고자하는 요소, 즉 Problem들은 크게 아래와 같다. 이 문제들을 해결할 수 있는 알고리즘들을 계속되는 포스팅을 통해서 설명하려고 한다.

 

• Filtering a data Stream
• Counting Distict Elements
• Estimating Moments
• Finding frequent Elements

Sampling from a Data Stream 

위의 Stream Model에서 살펴보았듯이 시스템은 데이터 스트림의 전부를 저장할 수가 없다. 그렇기 때문에, 이를 해결할 수 있는 여러 방법 중의 하나는  Sampling이다. 즉, 전체 데이터를 저장하지 않고 들어오는 데이터의 일부분(Sample)을 추출하여 이를 저장하는 식이다.

샘플 데이터를 저장하는 방법도 크게 2가지로 나눌 수 있는데, 비율을 일정하게 추출하는 방법과, 샘플의 크기를 일정하게 추출하는 방법이 있다. 

 

With a Fixed Proportion

예를 들어 Search Engine Query를 스트림으로 받는 경우를 생각해보자. data가 들어오는 방식은 tuple(튜플, 쌍)이며, 형식은 (user, query, time)이다. 해결해야 할 문제는 아래와 같이 주어진다

Problem : How ofen did a user run the same query at least twice?

Fixed Proportion Approach의 경우, 들어오는 query에 랜덤한 정수 (0~9)를 생성하여 집어넣고, 0일 경우에만 메모리에 할당한다. 

이 경우 한 유저의 모든 쿼리를 1/10씩 저장하게 되므로 직관적으로 봤을 때, 이 1/10의 쿼리 데이터만 가지고도 꽤 정확하게 근사된 값을 구할 수 있을 것 같다. 하지만 이 방식을 확률적으로 접근하게 되면 큰 오류가 있는 것을 알 수 있다.

 

 

 

한 유저가 전체적으로 x개의 쿼리를 한번만 날리고 d개의 쿼리를 두번만 날렸다고 하자. 3번 이상 날린 쿼리는 없다고 하자.

이 때 2번 날린 쿼리의 비율은 (d/(x+d))임이 자명하다. 그러나 이를 1/10씩 추출해서 확인해보면 다른 결과를 가져오는 것을 확인할 수 있다. 예를 들어 1번씩 날린 쿼리가 10개고 전체 쿼리가 30개라고 하자.

위의 예에서는 1번씩 날린 쿼리가 10개, 2번씩 날린 쿼리가 20개(이때 똑같은 쿼리를 두번씩 날렸으므로 쿼리의 종류. 즉 d 의 값은 10)

따라서 2번 이상 날린 쿼리의 비율은 1/2 일 것이다. 이를 1/10씩 추출했다고 하면 쿼리는 3개가 추출될 것이고, 통계적으로 x하나, d 2개가 추출될 것이다. 그러나 여기서 문제가 생기는데, 추출된 2개의 d가 서로 같은 쿼리일 수도 있고, 다른 쿼리일 수도 있다는 것이다. 

같은 쿼리인 경우 1/2 가 보존되지만, 다를 경우 2/3의 확률을 내놓는다.

 

이를 수학적으로 조금더 살펴보면 다음과 같다.

x -> x/10

d -> 1/10 * 1/10 * d (같은 쿼리가 추출되는 경우) + 2*(1/10 * 9/10)*d (서로 다른 쿼리가 추출되는 경우)

추출된 값들에서는  d/100 의 경우만을 2번의 쿼리로 인정하기 때문에 

d/(10x+19d)의 결과를 가져오게 되고, 따라서 이 경우 원본의 확률을 보존하지 못한다. 

 

따라서 이러한 경우에는 유저의 쿼리를 샘플링할 것이 아니라, 유저를 샘플링하는 편이 조금 더 나은 정확도를 보인다.

해쉬 함수를 이용해서 유저들을 샘플링하면 된다!

 

with a fixed-size sample

이 경우는 샘플의 비율을 일정하게 해서 추출하는 것이 아니라 샘플의 개수를 일정하게 해서 추출하는 방식이다. 

이 경우는 메인 메모리의 크기가 제한적이기 때문에 비교적 효율적으로 추출하는 방식이 될 수 있다.

n의 시간이 경과하는 동안 n개의 튜플들이 지나갔을 경우, 각각의 n개의 튜플들이 s개의 샘플 안에 속할 확률은 s/n이다.

 

 

이를 확장하면, n개의 원소가 도착했을 때 , n개의 튜플들이 s개의 샘플 안에 속할 확률은 s/n이고, n+1번째 원소가 도착했을때, 그 원소가 샘플에 들어갈 확률은 s/(n+1)이 된다. 이를  Reservoir Sampling이라고 한다.

 

Reservoir Sampling

 

증명은 아래와 같이 할 수 있다. (귀납법을 통해)

Base case :

n=s -> s/n = s/s = 1

Inductive step:

After n elements, sample s contains each element with prob. s/n

when n+1 elements arrives

prob of choosing n+1 elements + prob of not choosing n+1 elements(이 경우에 기존의 n개의 원소에서 s개를 추출)

 

= (1-s/(n+1)) + s/(n+1) * (s-1/s) = n/(n+1)

따라서 이를 적용하면

prob = s/(n+1) 이 된다.