[CS246] Counting Frequent Elements in a stream

Exponentially Decaying Window: Finding Frequent Recent Items from Stream

Motivation

이번 포스팅에서는 2가지 문제에 관심을 갖는다.

(1) Finding most common elements

(2) Finding most common recent elements

 

Example

최근 영화 중에서 가장 많이 예매된 것은?

(Amazon과 같은) 전자상거래의 stream data 중에서 최근 판매된 인기 상품은?

(Twitter, 이제는 X) SNS에서 최근 가장 활발한 유저는?

 

Sliding Window: What is "recent"?

어떤 기준으로 최근(recent) 정보를 반영할 수 있을까?

가장 기본적으로 떠오르는 생각은 sliding window이다.

window 안에 들어오면 recent item이고, window에서 벗어나면 더이상 최근 정보가 아닌 것이다.

이 방법의 문제점은 recent 기준이 너무 날카롭다는 것이다.

단 한 칸의 window 차이로 최근이 되고 안된다? window_size=5일땐 최신인데 window_size=4면 최신이 아니다?

이거는 좀 불합리하다고 생각된다.

Sliding Window (Stanford CS246)

Exponentially Decaying Window

sliding window(파란 박스)에 비해 다음의 장점을 갖는다.

• stream의 모든 데이터를 저장한다
• 최근(recent) item에 대하여 더 높은 가중치(weight)를 갖는다.

Exponentially Decaying Window (Stanford CS246)

 

stream 데이터가 $a_1, a_2, \dots, a_t$가 들어왔다고 하자. 그렇다면 $t$에서의 exponentially decaying window는

\[ a_t + a_{t-1}(1-c) + a_{t-2}(1-c)^2 + \dots = \sum_{i=0}^{t-1}a_{t-i}(1-c)^i \]

로 나타낼 수 있다.

이때 $c=10^{-6}$ or $10^{-9}$와 같이 매우 작은 숫자이다.

만일 새로운 stream data $a_{t+1}$이 들어오면 current sum에 $1-c$를 곱하고 $a_{t+1}$을 더하면 된다. (계산도 간단하다!)

 

이제 exponentially decaying window를 이용하여 most-frequent item을 찾아보자.

• Counting recent items
• Counting recent individual items
• Counting frequent recent itemsets

 

Task 1: Counting items

stream of items를 binary stream으로 바꾼다. 이때 원하는 item이라면 1, 아니라면 0으로 binary stream으로 정의한다.

아래는 $b$에 대한 binary stream을 만드는 과정이다.

Binary stream (Stanford CS246)

 

임의의 item $x$에 대하여 exponentially decaying window를 계산해보자.

각 $i \in \{1, 2, \dots, t\}$마다 $a_i=x$이면 weight를 계산하고 그렇지 않으면 0으로 간주한다. 

수식으로 쓰면 다음과 같다.

\[ \sum_{t=1}^T \delta_t (1-c)^{T-t} \text{ where } \delta_t=1 \text{ if } a_t=x \text{ otherwise } 0 \]

 

새로운 stream data가 들어와도 계산은 똑같다. new data가 들어오면 우선 current sum에 $(1-c)$를 곱한다. 그리고 new data가 $x$라면 $+1$을 하면 된다. 

 

이렇게 구한 sum을 "weight of item $x$"라 한다.

 

Importance Property: 전체 weight의 합은 $1/c$ 이다.

proof) (무한)등비수열의 합을 이용한다. $\sum_t 1 \cdot (1-c)^t = 1/(1-(1-c))=1/c$

 

Task 2: Counting Individual Items

(정의하기 나름이겠지만 여기서는) weight > 1/2 인 item들을 찾아보자.

위에서 보았듯이 weighted sum = $1/c$ 이다.

이는 달리 말하면 어떤 item도 weight가 $1/c$를 초과하는 것은 없다는 의미이다. 

모든 item이 $[1, 1, \dots, 1]$인 경우에 $1/c$ 이다.

여기서 얻을 수 있는 사실은 weight가 $1/2$이상인 item의 개수는 $2/c$개를 넘지 않는다는 것이다.

$(1/2) \cdot n < 1/c \Rightarrow n < 2/c$

 

 

1. $2/c$개의 counter를 만들고 $0$으로 초기화한다.
2. stream으로부터 $a_t$가 도착할때마다
   
   1. 모든 counter(Python의 dict를 생각하면 된다)에 $(1-c)$를 곱한다. 
   2. count < $1/2$ 인 counter는 drop한다.
   3. new item이 counter에 있다면, 해당 counter += 1
   4. new item이 counter에 없다면, 새로운 item에 대한 counter를 만들고 $1$로 초기화한다.
3. 매 순간마다, counter에 존재하는 item은 "most common recent item"이다.

 

Task 3: Extension to itemsets

모든 가능한 itemset을 저장하기에는 메모리가 부족하다. 

위의 아이디어를 그대로 이용한다.

 

basket $B$가 stream으로부터 들어오면

1. 모든 counter에 $(1-c)$를 곱한다.
2. $B$의 item 중에서 uncounted된 것들은 새 counter를 만든다.
3. $B$의 item들에 대하여 count+=1를 하고
4. count < $1/2$인 counter는 drop한다.
5. initiate new conunt (detail in next)

 

Initiation New Counts

$S \subseteq B$인 $S$에 대하여, 모든 $S$의 부분집합이 counter가 있다면 시작한다.

$S$의 부분집합이 모두 frequent하다면, $S$도 frequent할 가능성이 높다는 휴리스틱을 이용한 것이다.

 

예1) $S = \{ i, j \}$의 경우, $i$, $j$ 모두 counter에 있을 때 $\{ i, j \}$도 counting한다.

예2) $S= \{ i,j,k \}$의 경우, $\{ i,j \}$, $\{ i,k \}$, $\{ j,k \}$ 모두 counter에 있을 때, $\{ i,j,k \}$도 counting한다.