본문 바로가기
Python/Data Mining

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

by JKyun 2018. 7. 18.


안녕하세요. 우주신 입니다.



이번 포스팅에서는 연관규칙 알고리즘 중 가장 먼저 접하게 되는 Apriori 알고리즘에 대해 알아보겠습니다.


Apriori 알고리즘은 빈발항목집합(frequent itemsets) 및 연관규칙분석을 위한 알고리즘이다. 


먼저, 연관규칙분석이란 무엇인가?

우리는 연관규칙 분석을 통해 서로 다른 두 아이템 집합이 얼만큼 빈번히 발생하는지(연관도)를 알 수 있다.

경영학이라면 한번쯤은 들어 봤을만한 "맥주를 구매하는 고객들은 기저귀를 구매할 가능성이 높다." 예시도 연관규칙 탐색을 통해 도출된 결론으로 볼 수 있다.


연관규칙분석의 대표적인 알고리즘으로
 Apriori algorithm
 FP-growth algorithm

 DHP algorithm


등이 있는데, Apriori 알고리즘이 비교적 구현이 간단하고 성능 또한 높은 수준을 보여주어 자주 활용되고 있다.


예시를 통해 Apriori 알고리즘을 자세히 알아보자.

우선, Apriroi 알고리즘의 연관규칙 탐색을 위한 Transaction 데이터가 있어야 하고,

최소지지도(Minimum Support)를 설정해줘야 한다.


Transaction 데이터가 아래와 같이 주어지고, 최소지지도를 3으로 설정하자.


 
[Transaction Database]


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


1. 위 트랜잭션 데이터베이스를 스캔하면서 1-빈번항목집합을 찾는다. 


각각의 아이템들이 3번, 6번, 4번, 5번만큼 구매가 되었고
모두 최소지지도 3보다 높기 때문에 1-빈번항목집합에 포함된다.



2. 1-빈번항목집합을 기반으로 2-빈번항목집합을 구한다.


이 때, Self-Join Prune 과정을 거쳐야 한다.

Self-Join은 {1}, {2}, {3}, {4} 아이템을 바탕으로 생성될 수 있는 길이가 2인 모든 후보를 만드는 과정이다.

{1, 2} {1,3} {1, 4} {2, 3} {2, 4} {3, 4} 가 생성될 것이다.


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

Pruning 대상은 후보들 중 itemset의 item 중 1-빈번항목집합에 없는 item이 있으면 Pruning 할 대상이 된다.

{1, 2} {1,3} {1, 4} {2, 3} {2, 4} {3, 4}의 각 itemset의 item들은 모두 1-빈번항목집합에 포함되므로

여기서는 Pruning 된 후보가 없다.


이제, Self-Join과 Prune 과정을 거친 후보들을 대상으로 트랜잭션 데이터베이스를 스캔하면서 Count 한다.  



Count된 값이 최소지지도 3보다 큰 itemset들로 2-빈번항목집합을 구한다.


즉, {1, 2} {2, 3} {2, 4} {3, 4} itemsets들이 2-빈번항목집합이다.


여기서, Apriori 알고리즘의 원리를 알 수 있다.

{1, 3}과 {1,4}는 다음 단계의 빈번항목집합 분석에 있어 더 이상 이용되지 않는다.

왜냐하면 한 항목집합이 비빈발(infrequent)하다면 그 항목을 포함한 모든 집합(Superset) 또한 비반발하기 때문이다.

"If there is any itemset which is infrequent, its superset should not be generated!"



3. 2-빈번항목집합을 기반으로 3-빈번항목집합을 구한다.


과정은 2번 과정과 똑같다.

2-빈번항목집합을 대상으로 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-빈번항목집합에 {1, 3}이 존재하지 않으므로

{1, 2, 3}은 Pruning이 된다. {1, 2, 4} {1, 3, 4}도 마찬가지 원리로 Pruning 된다. 


길이가 3인 후보 {2, 3, 4}를 대상으로 트랜잭션 데이터베이스를 스캔하며 Count 한다.


Count된 값이 최소지지도 3보다 큰 itemset들로 3-빈번항목집합을 구해야 하지만,

최소지지도를 만족하는 더 이상의 itemset이 없기 때문에 종료한다.



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


1. 트랜잭션 데이터베이스를 스캔하면서 1-빈번항목집합을 구한다.

2. k-빈번항목집합을 대상으로 (k+1)-빈번항목집합을 구한다.

- Self Join과 Prune을 통해 후보(Candidate)를 구하고,
- 트랜잭션 데이터베이스를 스캔하면서 최소지지도 조건을 만족하는 후보만 도출한다.

3. 더 이상 (k+1)-빈번항목집합이 만들어지지 않을 때까지 2번 과정을 반복한다.



자, 그럼 위의 과정을 통해 어떤 아이템들이 빈번하게 묶이는지 알았다면,

각 아이템들 간의 연관도가 얼만큼 있는지를 어떻게 알 수 있는가?


이는 Association Rule을 적용하여 지지도(Support), 신뢰도(Confidence) 그리고 향상도(Lift)를 통해 알 수 있다.

[출처: http://www.saedsayad.com/association_rules.htm]



위 Transaction Database에서 1-item -> 2-item 간의 연관도를 구하면,

Support: 1과 2가 전체 데이터베이스에서 함께 나올 확률:: 4/7

Confidence: 1이 나왔을 때, 2가 나올 확률:: 3/3

Lift: 1, 2 item 간의 독립을 가정했을 때, P(A, B) / P(A) * P(B):: 7/6

위와 같이 계산된다.


식의 자세한 설명은 위키피디아를 참조하자.


내용이 길어진 관계로, 파이썬 코드 설명은 다음 포스팅에서 하겠습니다.

코드를 보면 한층 더 수월하게 이해하는데 도움이 될 것 같네요!




수고하셨습니다





 

댓글3

  • 박혜진 2018.09.22 19:21

    개념을 이해 하는 것에 정말 도움 되었습니다~
    답글

  • 아디오스 2019.04.11 22:56

    감사합니다! 특히 3번째 프룬 과정에서 도움이 많이 되었어요!!
    그런데 마지막에 Support값이 1과 2가 전체 데이터베이스에서 함께 나올 확률이라면 3/7 아닐까요?
    그리고 저는 다른 글에서 Support 값은 조건절의 확률으로 알고있어서 '1이 나올 확률'로 해서 3/7을 구했는데, 어떤 것이 맞는 것인지 부가 설명을 들을 수 있을까요?
    답글