[Data Science] Apriori 알고리즘

연관성 분석 시 항목이 많아질수록 조합할 수 있는 연관성 규칙은 기하급수적으로 늘어난다.

따라서 모든 연관성 규칙을 찾는다는 것은 많은 시간과 자원(컴퓨터 자원=CPU)을 필요로 한다.

그래서 컴퓨터를 이용해서 연관성 분석을 할 때는 Apriori 알고리즘을 사용해서 연관성 규칙을 도출한다.

원리

한 항목이 자주 발생하지 않는다면 이 항목을 포함하는 집합들도 자주 발생하지 않는다.

즉, 한 항목의 support(지지도)가 일정수준에 미치지 못하다면 이 항목을 포함하는 집합들도 자주 발생하지 않는다.

 

만약 삼겹살에 대한 지지도가 0.4라면 {삼겹살, 생수}, {삼겹살, 사과}에 대한 지지도는 아무리 높아도 0.4를 넘지 못 할 것이다.

규칙

1. transaction을 스캔하면서 1-빈번항목집합을 구한다.

연관성 분석을 할 때 하나의 거래 내역을 transaction이라고 한다.

transaction은 문자열로 이루어져있어야 활용하기 편리하다.

 

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

Self Join과 Prune을 통해 후보(Candidate)를 구한다.

Self Join: k-빈번항목집합의 아이템을 바탕으로 생성될 수 있는 길이가 (k+1)인 후보(Candidate)를 만든다.

Prune: 후보(Candidate)들 중 k-빈번항목집합에 없는 item을 갖고 있는 것이 있으면 삭제한다.

Transaction을 스캔하면서 minimum support 조건을 만족하는 후보(Candidate)만 도출한다.

 

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

 

 

 

참고: ordo.tistory.com/89?category=751589, www.youtube.com/watch?v=hMW7vdeV4bY