[Data Science] Frequent Pattern Mining - Apriori

Apriori

• Apriori 알고리즘은 여러 itemset에 대해 frequent한지를 파악하거나 association rule을 파악하기 위한 알고리즘이다.
• Frequent itemset의 subset은 반드시 frequent하다는 사실을 기반으로 만들어졌다.
• 즉, infrequent한 itemset이 존재한다면 해당 itemset의 superset은 생성하거나 테스트할 필요 없다는 것이다.

Algorithm

1. Init: DB를 한 번 스캔하여 frequent 1-itemset(item의 개수가 1인 itemset)을 구한다.
2. 일련의 k에 대해 아래 3~5단계를 반복한다 (k=1 부터 반복).
3. Generate Candidate: Frequent k-itemset으로부터 (k+1)-itemset 후보를 생성한다.
4. Test: 만들어진 후보 itemset에 대해 DB를 스캔하여 frequent인지 확인한다.
5. Terminate: Frequent itemset이 없거나 후보 itemset이 만들어지지 않는다면 종료한다.

Pseudo-code

// C_k: Candidate itemset of size k
// L_k: Frequent itemset of size k

L_1 = {frequent items}

for (k = 1; L_k != EMPTY_SET; k++) do begin
	C_k+1 = candidates generated from L_k
    for each transaction t in database do
    	increment the count of all candidates in C_k+1 that are contained in t
    L_k+1 = candidates in C_k+1 with min_support
    end
return L (all frequent sets)

Example

min_sup = 50%

Challenges

• Transaction database scan이 여러 번 발생한다.
  → Scan 횟수를 줄여 효율을 높인다.
• Itemset join 시, 후보 (k+1)-itemset이 많이 나온다. 
  → 후보 itemset 수를 줄여 효율을 높인다.
• 후보 itemset의 support를 계산하는 양이 많다.
  → 계산하는 알고리즘을 효율 좋은 알고리즘으로 바꿔 효율을 높인다.