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


저번 포스팅에 이어서 연관규칙 알고리즘의 Apriori 알고리즘에 대해 글을 쓰겠습니다.


저번 포스팅에서 연관규칙분석 개념 및 Apriori 알고리즘에 대해 알아봤으니,

이번에는 파이썬 코드를 보며 한번 더 복습해보자.

(지난 포스트의 지식을 다 안다는 전제하에 코드만 설명)


내가 테스트한 트랜잭션 데이터베이스(Transaction Database)는 아래와 같은 양식이다.

각 줄이 itemset을 구분하며, 1번 itemset은 7번 item과 14번 item으로 구성되어 있다고 보면 된다.


Apriori 알고리즘은 아래와 같은 순서로 진행된다.

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

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

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

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


[메인함수]부터 보자.

193:: 파일을 실행할 때, Transaction Database(input.txt), 최소지지도(min_sup), 결과출력파일(output.txt)을 인자로 넣는다

198:: input.txt로부터 데이터를 로딩한다

200:: 빈번항목집합을 담을 set을 만들고, generate_first_frequent_set()을 통해 1-빈번항목집합을 만든다

204:: 반복문을 돌며 k-빈번항목집합을 대상으로 (k+1)-빈번항목집합을 구한다

208:: k-빈번항목집합을 대상으로 Self Join을 한다

210:: 더 이상 Self Join이 되지 않을 때는 프로그램을 종료한다

215:: Self Join 이후, Prune 과정을 거친다.

- prune() 함수 안에서 후보를 뽑고 그 후보들을 대상으로 최소지지도를 확인한 후 (k+1)-빈번항목집합까지 구한다

218:: (k+1)-빈번항목집합을 구한 후, Association Rule을 통해 지지도(Support)와 신뢰도(Confidence)를 구한다

220:: (k+1)-빈번항목집합이 생성되지 않았으면 종료하고

224:: (k+1)-빈번항목집합이 생성되었으면, frequent_set에 (k+1)-빈번항목집합을 추가하고 길이를 1 추가한다


[1-빈번항목집합을 생성하는 함수]

33:: 여기서 trxes는 전체 트랜잭션 데이터베이스를 가리킨다

34:: item_set을 딕셔너리 형태로 만들어 key = 아이템, value = 갯수로 저장한다

35:: trxes의 itemset의 item들을 방문하며

37:: item_set의 key에 없으면 value를 1로 추가하고 key가 있다면 value를 1씩 증가하며 count 한다

42:: 최소지지도 조건을 만족하지 않는 후보들은 제거하고 1-빈번항목집합을 반환한다


[최소지지도로 아이템을 거르는 함수]

53:: 인자로 받은 후보(candidate)를 바탕으로 최소지지도보다 큰 key들만 빈번항목집합(frequent_set)에 넣는다

56:: 빈번항목집합의 아이템이 하나도 없으면 종료한다


[Self Join]

78:: Self Join을 하기 위해 k-빈번항목집합을 인자로 받는다

81:: 길이가 1인 1-빈번항목집합의 경우 바로 조합이 가능하기 때문에 케이스를 나누었다

85:: 길이가 2 이상인 빈번항목집합들을 가지고 조합을 만들기 전에 중복되지 않는 모든 item을 뽑는다

92:: itertools 모듈의 combinations 함수를 이용하여 가능한 모든 조합을 만들었다


참고로 set 자료형을 쓰기 위해 아래와 같이 리스트 안의 아이템(element)들을 set으로 바꾸는 함수를 따로 만들었다


[Prune]

106:: 이전 빈번항목집합의 길이가 1일 때와 2 이상일 때 케이스를 나누어 가지치기 하였다

117:: 가지치기 원리는 Self Join한 후보들을 대상으로 각각의 itemset의 item들 중 

126:: 이전 빈번항목집합에 없는 item이 하나라도 있으면 후보에서 제외한다

135:: prune 함수에 트랜잭션 데이터베이스를 스캔하며 Count하는 기능도 함께 넣었다

142:: 최소지지도 조건에 만족하는 후보들을 대상으로 (k+1)-빈번항목집합을 반환한다


[Association Rule]

위 함수는 지지도(Support)와 신뢰도(Confidence)를 반환해준다

162:: 지지도

168:: 신뢰도


[output.txt 출력 결과]

서로 다른 두 아이템 간의 지지도(Support)와 신뢰도(Confidence)를 구하여 output.txt 파일에 저장한 결과이다.


코드를 설명하면서 다시 보니 좀 더 효율적으로 코딩할 수 있는 부분이 보이네요.

미숙한 저의 코드는 참고만 해주시고 조금이나마 도움 됐으면 싶습니다.

Full Code는 git에 올렸습니다.



수고하셨습니다.





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



이번 포스팅에서는 연관규칙 알고리즘 중 가장 먼저 접하게 되는 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

위와 같이 계산된다.


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


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

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




수고하셨습니다





 

  1. 박혜진 2018.09.22 19:21

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

  2. 아디오스 2019.04.11 22:56

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

+ Recent posts