Apriori algorithm

https://ordo.tistory.com/89

[Python] Apriori algorithm:: 연관규칙분석 (1)

위 블로그를 필사하여 공부한 글입니다.

 

* 모든 텍스트와 이미지의 출처는 위 블로그입니다.

 

---

 

 

Apriori 알고리즘 

; frequent itemsets 및 association rule 분석을 위한 알고리즘

 

* Association Rule; 서로 다른 두 itemset set이 얼만큼 빈번히 발생하는지 연관도를 알 수 있었음

 

* Association Rule의 대표적인 알고리즘

- Apriori algorithm

- FP-growth algorithm

- DHP algorithm

 

 

 

 

먼저, Apriori 알고리즘의 association rule 탐색을 위한 transaction 데이터가 있어야 하고, minsup을 설정해줘야 함

 

Transaction 데이터가 아래와 같이 주어지고, minsup=3으로 설정하자.

출처: 위 블로그

- 슈퍼마켓 구매 데이터라고 가정하면, {1, 2, 3, 4}는 1번 item, 2번 item, 3번 item, 4번 item이 같이 구매되었고, 이를 하나의 itemset이라고 보면 됨

 

 

1. 위 DB를 스캔하며 1-fp를 찾는다.

출처: 위 블로그

- 각 item들이 3번, 6번, 4번, 5번만큼 구매가 되었고,

  모두 minsup=3보다 크기 때문에 1-fp에 포함됨

 

 

2. 1-fp를 기반으로 2-fp를 찾는다.

- 이 때, self-join과 prune 과정을 거쳐야 한다.

 

* self-join: {1}, {2}, {3}, {4} item을 바탕으로 생성될 수 있는 길이=2인 모든 후보를 만드는 과정

=> {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}가 생성될 것

 

이렇게 생성된 후보들을 대상으로 pruning을 하는데,

pruning 대상은 후보들 중 itemset의 item 중 1-fp에 없는 item이 있으면 pruning 할 대상이 됨

{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}의 각 itemset의 item들은 모두 1-fp에 포함되므로 여기서 pruning 된 후보는 없음

 

 

이제 self-join과 prune 과정을 거친 후보들을 대상으로 DB를 스캔하며 count한다.

출처: 위 블로그

 

- count된 값이 minsup=3보다 큰 itemset들로 2-fp를 구한다.

출처: 위 블로그

즉, {1, 2}, {2, 3}, {2, 4}, {3, 4} itemset들이 2-fp이다.

 

 

* 여기서 알 수 있는 Apriori 알고리즘의 원리는,

{1, 3}과 {1, 4}는 다음 단계의 fp 분석에 있어 더 이상 이용되지 않는다는 것

because 한 itemset이 infrequent하다면, 그 item을 포함한 모든 집합(superset) 또한 infrequent하기 때문!

 

 

 

3. 2-fp를 기반으로 한 3-fp 구하기

(2번과 과정은 똑같다.

2-fp를 대상으로 self-join과 prune을 함)

 

self-join: {1, 2}, {2, 3}, {2, 4}, {3, 4}

-> {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}

 

prune: {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}

({1, 2, 3}의 subset이 {1, 2}, {1, 3}, {2, 3}인데, 2-fp에 존재하지 않으므로.

 나머지 두 {1, 2, 4}, {1, 3, 4}도 마찬가지!)

 

 

길이가 3인 후보 {2, 3, 4}를 대상으로 DB를 스캔하며 count한다.

출처: 위 블로그

- count된 값이 min-sup=3보다 큰 itemset들로 3-fp를 구해야하지만, minsup을 만족하는 더 이상의 itemset이 없으므로 종료!

 

 

 

---

 

위의 예시를 일반화해보면,

 

1. DB를 스캔하며 1-fp를 구함

2. k-fp를 대상으로 (k+1)-fp를 구함

- self join과 prune을 통해 후보를 구하고,

- DB를 스캔하며 minsup 조건을 만족하는 후보들만 도출

3. 더 이상 (k+1)-fp이 만들어지지 않을 때까지 2번 과정을 반복