연관규칙분석(Apriori 알고리즘)

추천시스템에 관심을 가지게 되면서 추천시스템에 배경에 대해 알게되었습니다. 지금은 딥러닝을 이용하는 많은 알고리즘이 나왔지만 오늘은 추천시스템의 1세대라고 할 수 있는 Apriori 알고리즘에 대해서 정리하고자 합니다.

 

우리는 연관규칙을 할때 효율적으로 탐색하는것이 중요합니다. 왜일까요?? 연관규칙의 개수는 Item 개수가 증가함에 따라서 지수적으로 증가하게 됩니다. 우리는 Item 수가 10개만 된다고 해도 규칙은 57002개가 생성이 됩니다. 즉 계산량이 엄청 복잡해지고 많아지게 되며 시간 또한 오래 걸리게 됩니다. 

 

이러한 경우를 대비하여 "평가 측도"를 기준으로 계산량과 속도를 줄일 수 있습니다. 연관규칙에 관한 글은 다음글에서 https://jaaamj.tistory.com/113 확인할 수 있습니다. 

 

그 방법중 하나가 바로 Apriori 알고리즘 입니다. 

 

Apriori 알고리즘

---

Apriori는 빈발항목집합을 추출하는 것이 원리입니다. 여기서 빈발항목집합이란? 최소지지도 이상을 갖는 항목집합을 의미합니다. 모든 항목집합의 대한 복잡한 계산량을 줄이기 위해 최소 지지도를 정해서 그 이상의 값만 찾은 후 연관규칙을 생성하게 됩니다. 

 

그 과정을 그림으로 쉽게 표현해보면 다음과 같습니다.

 

http://blog.skby.net/apriori-%EC%97%B0%EA%B4%80-%EA%B7%9C%EC%B9%99-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

 

다음 그림을 보며 더 자세하게 이해해 보도록 하겠습니다.  

https://ratsgo.github.io/machine%20learning/2017/04/08/apriori/

 

만약 아이템 집합 {A,B}의 지지도가 사용자가 정한 최소 지지도를 넘지 못하게 되면 자동적으로 {A,,B}는 물론이고, {A, B}의 초월집합인 {A,B,C}, {A,B,D} 등 총 8가지 규칙들은 제외되게 됩니다. 이렇게 함으로써 계산량을 줄이게 되는 것입니다.

 

Apriori 알고리즘의 장/단점

---

장점

- 상품간의 많은 연관규칙들을 발견할 수 있습니다.

- 원리가 간단하기 때문에 쉽게 이해할 수 있습니다.

 

단점

- 상품수가 많을수록 그 계산량이 기하급수적으로 늘어난다.

- 비즈니스 측면에서 중요한 현실적인 연관 규칙들이 발견하기에 부족하다.

 

 

참고

---

http://blog.skby.net/apriori-%EC%97%B0%EA%B4%80-%EA%B7%9C%EC%B9%99-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

 

https://ratsgo.github.io/machine%20learning/2017/04/08/apriori/