[Data Mining] 2 - Frequent Items : A-Priori algorithm

A pirori algorithm

2-pass 접근법으로 메인 메모리 사용을 줄일 수 있다.

 

Key Idea : Monotonicity

만약 아이템 셋 I가 적어도 s번 등장한다면, 집합 I의 모든 부분집합 J 또한 s번 이상 등장한다.

만약 아이템 i가 s 미만으로 등장한다면 i를 포함안 아이템 부분집합이 s 번 미만으로 등장한다.

 

A-priori algorithm 구성

1. pass-1 : 모든 transaction을 1회 읽으면서 메인 메모리에 각각의 아이템의 등장횟수를 저장한다.

item수만큼의 메모리 저장 공간이 필요하다.

items that appear >= s times are frequent items

 

2. pass-2 : 모든 transaction을 다시 읽으면서 각각의 아이템의 등장횟수가 s번 이상인 것들만 pair로 만들어 등장횟수를 메모리에 저장한다.

 

(사진 삽입)

 

Frequent triples

각 k에 대해 k-tuples의 두 셋을 구성한다. (sets of size k)

C_k = k-tuples의 후보 = pass-(k-1)에서 기반한 frequent sets으로 k-tuples를 구성

L_k = frequent k-tuples 집합

 

 

A-priori for all frequent itemsets

pass-1