본문 바로가기
Python/Data Mining

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

by JKyun 2018. 7. 23.


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


저번 포스팅에 이어서 연관규칙 알고리즘의 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에 올렸습니다.



수고하셨습니다.




댓글0