[CS246] A-Priori Algorithm: Finding Frequent Itemsets

 

 

Recap: Frequent Itemsets Mining and Association Rule

frequent itemset, association rule에 대해 이전 포스팅을 참고한다. 

(frequent itemset이 주어졌을 때, association rule을 만드는 방법이다.)

 

https://trivia-starage.tistory.com/181

[CS26] Frequent Itemsets Mining & Association Rules

Itemsets: Computation Model

이제 본격적으로 frequent itemset을 구하는 방법을 생각해보자.

일반적으로 데이터는 DB보다는 파일에 저장되어 있을 것이다. (디스크, 등)

basket의 크기는 작지만, 실제 데이터는 item의 종류와 basket의 수가 많다. 그리고 이런 대용량 데이터는 main memory에 fit하지 않을 것이다.

frequent itemset을 찾기 위해서 우리는 item과 basket의 개수를 세는 작업이 필요한데, 이는 정말 심각한 문제다. naive하게 생각해보면 크기가 $k$인 집합을 만들기 위해서는 $k$개의 loop를 돌아야하기 때문이다.

그리고 disk I/O 역시 시간을 많이 잡아먹는다. 

따라서 association rule algorithm은 데이터를 읽는 pass에 따라 비용이 발생한다.

 

Finding Frequent Pairs

가장 어려운 점은 frequent pairs of items $\{i,\ j \}$를 찾는 것이다. 

frequent pair는 triple보다 더 많이 존재할 것이기 때문이다.

우선 frequent pair를 만들수 있다면 더 큰 itemset으로 확장할 수 있으므로 우선 frequent pair를 만드는 것에 집중해보자.

 

Naive Approach

file을 한번 읽고, 메인 메모리에 각 pair의 등장 횟수를 저장해보자.

각 basket에 $n$개의 item이 있다면, 2중 반복문을 통해 $\binom{n}{2} = \frac{n(n-1)}{2}$ 개의 pair를 만들 수 있다. 

여기서 $(\text{# of items})^2$ 가 메인메모리를 초과할 수 있다. 월마트 데이터의 경우 100K(10만)개, Web scale로 가면 item의 개수는 10B(100억)을 넘어간다. 월마트 데이터에 4바이트 integer 자료형을 쓴다고 하여도 메인메모리는 4bytes * (100K * (100K - 1)) / 2 = 20GB가 필요하다. (not feasible!)

 

Approach 1: Triangular Matrix

행렬을 이용하여 모든 pair의 개수를 세는 방법이다.  pair마다 4바이트만 사용하면 된다. 최대 사용 메모리는 (4바이트 정수를 사용한다고 가정) $4*\frac{n(n-1)}{2} \approx 2n^2$ bytes 이다.

 

Approach 2: Triples

triple $[i,\ j,\ c]$를 테이블의 형태로 저장하는 방법이다. ($i,\ j$는 item, $c$는 $\{ i,j \}$의 개수)

4바이트 정수형 자료를 사용한다면 pair가 존재하는 경우에만 12바이트를 차지한다. 게다가 해시테이블의 오버헤드도 고려해야한다. 그러나 모든 pair 중에서 1/3 이하의 pair만 frequent하다면 ($p < 1/3$) 더 triple을 사용하는 것이 유리하다. 사용 메모리는 $12p \frac{n(n-1)}{2} \approx 6pn^2$ 바이트이다.

Comparing the 2 Approaches (Stanford CS246)

반응형

A-Priori Algorithm

monotonicity를 이용하여 효율적으로 frequent itemsets을 찾는 알고리즘이다.

만약 $\text{support}(I) \ge s$ 라면 $I$의 부분집합 $J$ 역시 $\text{support}(J) \ge s$라는 것을 이용한 것이다. 그리고 contrapositive (대우)를 이용하면 $i$가 $s$ basket에 없다면 $i$를 포함한 pair 역시 존재하지 않는다는 것을 알 수 있다.

 

이 알고리즘은 2-pass로 이루어져있다. 

 

Pass 1: basket 데이터를 읽어 main memory에 item별로 occurence를 저장한다. (해시테이블을 이용하여 문자열 이름을 정수로 매핑하여 저장한다.) 이중 support threshold $s$ 이상인 것만 저장한다.

Pass2: basket을 다시 읽어 frequent pair만 main memory에 저장한다. 이때 trick을 이용하여 frequent item을 다시 1부터 번호를 부여하여 원래 번호와 함께 테이블에 저장할 수 있다.

A-Priori Alrogithm and main-memory using (MMDS textbook)

Left: Picture of A-Priori; Right: Using trick (Stanford CS246)

Frequent Triples, Etc.

이제 frequent paris로부터 크기가 $k(\ge 3)$인 frequent itemsets을 구해보자.

$C_k$와 $L_k$를 각각 candidate k-tuples, truly frequent k-tuples라 하자.

$C_k$로부터 support threshold를 만족하는 frequent items를 필터링하여 $L_k$를 얻는다.

도식화하면 다음과 같다.

Frequent k-tuples (Stanford CS246)

실제 market-basket data에 대하여 적절한 support (보통 1%)를 적용했을 때, $k=2$일 때 가장 많은 메모리를 차지한다고 한다. 그리고 당연하게도 support $s$가 작아질 수록 itemsets은 커진다. 

 

Example: A-Priori Algorithm

support=3일 때 아래 8개의 basket에서 association rule을 찾아보자.

Example baskets

(원래는 $\{ \{a\},\ \{b,c\}, \{a,b,c\} \}$ 등으로 집합으로 나타내야하지만 편의상 문자열을 집합으로 표기한다.)

• $C1=\{ b,c,j,m,p \}$
• support=3가 안되는 item은 제외하여 truly frequent itemset을 구한다. $L_1 = \{ b,c,j,m \}$
• $L_1$의 원소끼리 join하여 $C_2$를 구한다. $C_2=\{ bc, bj, bm, cj, cm, jm \}$
• support=3이 안되는 itemset은 제외한다. $L_2=\{ bc, bm, cj \}$
• $L_2$의 itemset끼리 join하여 $C_3$을 구한다. $C_3=\{bcm, bcj, bmj, cmj\}$
  • monotonicity에 따라 frequent itemset의 부분집합도 frequent itemset이다.
  • 그러나 $bcj$의 경우 부분집합 $bj \notin L_2$이므로 $bcj$ 역시 frequent itemset이 아니다.
  • 마찬가지로 $bmj,\ cmj$ 역시 대우명제에 의해 frequent itemset이 아니다.
  • 경우에 따라 여기서 이미 $C_3=\{ bcm \}$ 으로 간주하기도 한다.
• support=3이 안되는 itemset을 제외하여 $L_3$을 구한다. $L_3=\{ bcm \}$

Summary & Keywords

Frequent Itemsets: market-basket model

Association Rules: confidence, interest, maximal itemsets, closed itemsets

Finding Frequent Pairs: triangular-matrix method, triples method

A-Priori Algorithm: how the 2-pass algorithm works