웹 분석과 데이터 마이닝을 위한 확률적 자료구조

Probabilistic Data Structures for Web Analytics and Data Mining

이런 훌륭한 글이 있군요. 위 글은 많은 양의 데이터에서 각 아이템의 출현횟수를 세거나 unique 아이템의 수가 몇개인지 세거나 하는 방법들입니다. 예를들어 integer가 엄청나게 많을때 각 값의 출현횟수 세기같은 경우죠.

간단하게 관심가는 것들, 기본적인 내용으로 정리해봅니다.

1. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Linear Counting
m 비트를 준비합니다. 주어진 입력을 0~(m-1) 사이로 해싱합니다. 그 다음 해당 비트의 값을 1로 셋팅. 결국 1로 셋팅된 비트의 수를 세면 이게 입력에 있는 unique한 숫자의 갯수가 되겠죠.

2. 입력에 몇개의 unique한 수가 있는지 세기(Cardinality Esitmation): Log Log Counting
전에 대량의 데이터에서 대략적으로 UNIQUE ITEM 의 수 세기에서 썼던 내용입니다. 다시 정리하자면, 주어진 입력을 해싱함. 해싱한 수들을 살펴보고 제일 앞자리에 최대 몇개의 0이 연속으로 나오는지 봅니다. 이 때 최대 r자리의 연속된 0을 봤다고 하면 2^r개의 unique item이 있구나 하고 보는 방법입니다.

이유는 간단하죠. 해시값의 제일 앞자리에 0이 나올려면 2개의 unique숫자를 봤어야합니다. 1개만 봤을때는 앞자리가 1일수 있으니까요. 마찬가지로 해시값 앞자리에 연속된 0이 2개, 즉 00이 나오려면 4개의 unique숫자를 봤어야합니다. 예를들어 3개만 봤다면 해시값 앞자리가 11, 10, 01이었을 수 있으까요.

사실 2^r은 너무 거친 추정이므로 여러개의 해시함수를 써서 평균을 내던가 하는 방법을 씁니다.

3. 각 입력의 출현횟수 세기: Count-Min Sketch
대량의 데이터에서 각 입력값이 몇번 나왔나 세는 방법입니다. 예를들어 integer로 구성된 데이터였다면 1은 몇개나왔나, 2는 몇개나왔나 등을 세는 것이죠.

방법은 이렇습니다. 0으로 초기화된 d행 w열의 행렬 m을 준비합니다. 그리고 해시 함수 d개를 준비합니다. 이들을 각각 h_1, h_2, …, h_d 라고 합시다. 이 해시는 각각 0~(w-1)까지의 숫자로 입력을 해싱해 줍니다. 처리할 대량의 데이터에대해 다음을 수행합니다.

for each of datum in input
  for i in 1..d
    m[i, h_i(datum)] += 1
  end for
end for

자 그러면 각 입력에대해 총 d개 셀을 1씩 추가시키는 것이죠.

이게 끝나고나서, 역으로 어떤 숫자 k의 출현횟수를 세고 싶다고 하면 다음과 같이 k의 출현횟수를 찾습니다.

cnt = INT_MAX
for i in 1..d
  cnt = min(cnt, m[i, h_i(k)])
end for

여기서 min이 필요한 이유는 이 방법이 본질적으로 hash collision이 있기 때문에 항상 count를 overestimate하기 때문입니다.

4. Range Query: 다수의 Count-Min Sketch 사용
Count-Min Sketch로 어떤 수 k가 몇회나왔는가는 잘 셀수 있게 되었습니다. 이번엔 range query로 1, 2, 3, .., k 까지의 수가 몇번 나왔나? 혹은 500, 501, …, k까지의 수가 몇회나왔나? 와 같은 질문이 주어졌을때 답하는 방법입니다.

이는 Count-Min Sketch만으로는 부족합니다. 각 숫자의 출현횟수를 매번 구하기가 어려울 수 있으니까요. 이를 위해 Count-Min Sketch를 여러개 쓸 수 있습니다. 예를들어 일단 기본적인 Count-Min Sketch를 만듭니다. 그다음은 1, 2를 하나의 수로 3,4를 하나의 수로, … 과 같이 연속된 2개씩의 숫자들을 카운트를 세는 Count-Min Sketch를 만듭니다. 거기에더해 1~4, 5~8, … 과 같이 연속된 4개의 숫자를 묶어서 세는 Count-Min Sketch를 만듭니다. 이런식으로 계속해서 2배씩 키워나가는 Count-Min Sketch를 많이 만듭니다.

이걸로 range query를 어떻게 처리할지 벌써 감이 오시죠?

예를들어 1, 2, 3, …, 10 의 총 발생횟수는 1~8, 9~10 의 2개의 Count-Min Sketch로 답합니다. 또 다른 예로 1~6의 발생횟수는 1~4, 1~2의 2개로 답하면 되겠죠.

5. 집합에 속해있는지. Bloom Filter.
아주 많은 숫자들의 집합이 있습니다. 어떤 입력이 주어졌을때 그 수가 집합의 원소인지 빠르게 답하는 방법이 바로 bloom filter입니다. 방법은 이렇습니다.

m 비트를 만들고 각 자리를 0으로 초기화합니다. 그리고 n 개 해시 함수 h_1, h_2, …, h_n을 만들어놓습니다. 그 다음 집합에 속해있는 데이터에 대해서 다음을 수행합니다.

for each of datum in input
  for i in 1..n
    m[h_i(datum)] = 1
  end for
end for

결국 각 데이터에 대해 n개의 해시함수를 적용해서 각 자리를 1로 셋팅하는 것이죠. 다 준비가 되면 각 입력에 대해 다음을 수행하면 그 입력이 집합에 속하는지 알 수 있습니다.

is_member = true
for i in 1..n
  is_member = is_member && m[h_i(input)]
  if !is_member
    return false
  end if
end for
return true

물론 hash collision이 있기에 이 방법은 false positive가 있습니다.

앞서의 방법들 모두 오차가 있습니다. 그 오차의 한계를 관리하기위해 m, n, d, w 등의 파라미터를 잘 정해주어야 합니다.

Similar Posts:

Comments 3

  1. minjang wrote:

    흥미롭네요. 재밌는 건 4번 같은 블룸필터는 컴퓨터 구조에서도 많이 쓰입니다. 컴구조도 데이터가 막대하죠. 수행되는 명령어가 수십억, 수백억 단위. 여기서 데이터를 효율적으로 분석하는데 보통 확률 기반의 어느 정도 오류를 가진 방법을 쓰죠. 빅데이터 쪽 처리와 이런식으로도 연관이 되는군요.

    Posted 17 Mar 2013 at 4:10 am
  2. Minkoo Seo wrote:

    블름필터는 웹검색에서도 쓰죠. ms단위의 처리속도가 중요해서 최대한 빨리 많은 요청에 답해야하니까요. 저는 그래서 블름 필터를 알게 됐어요.

    블름필터가 컴퓨터 구조에서 쓰인다니 몰랐네요. 전선과 납땜만 연상되는 하드웨어지만 실제론 소프트웨어의 영역이라고 생각되는 알고리즘이 여러가지로 쓰이는걸 다시 확인하게 되는군요. 그런데 정말 흥미롭네요. 컴퓨터 구조에 확률적 자료구조라니.

    Posted 17 Mar 2013 at 1:42 pm
  3. abraxsus wrote:

    아..블룸필터.. 내가 “이거 SW쪽사람들한텐 익숙하지 않을수있겠다”했더니 아키교수가 그러는데 아키쪽에선 하도 흔해서 식상하다고함..
    흥미로웠음..

    Posted 18 Mar 2013 at 3:54 am

Post a Comment

Your email is never published nor shared.