Apriori
- Apriori 알고리즘은 여러 itemset에 대해 frequent한지를 파악하거나 association rule을 파악하기 위한 알고리즘이다.
- Frequent itemset의 subset은 반드시 frequent하다는 사실을 기반으로 만들어졌다.
- 즉, infrequent한 itemset이 존재한다면 해당 itemset의 superset은 생성하거나 테스트할 필요 없다는 것이다.
Algorithm
- Init: DB를 한 번 스캔하여 frequent 1-itemset(item의 개수가 1인 itemset)을 구한다.
- 일련의 k에 대해 아래 3~5단계를 반복한다 (k=1 부터 반복).
- Generate Candidate: Frequent k-itemset으로부터 (k+1)-itemset 후보를 생성한다.
- Test: 만들어진 후보 itemset에 대해 DB를 스캔하여 frequent인지 확인한다.
- 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
Challenges
- Transaction database scan이 여러 번 발생한다.
→ Scan 횟수를 줄여 효율을 높인다. - Itemset join 시, 후보 (k+1)-itemset이 많이 나온다.
→ 후보 itemset 수를 줄여 효율을 높인다. - 후보 itemset의 support를 계산하는 양이 많다.
→ 계산하는 알고리즘을 효율 좋은 알고리즘으로 바꿔 효율을 높인다.