Apriori 알고리즘
APriori 알고리즘은 연관규칙 탐색을 위한 Transcaction 데이터가 있어야 하고, 최소지지도(Min support)를 설정해 줘야 한다. 여기서 트렌젝션 데이터란 아이템들의 집합이나 아이템 세트이며, 최소지지도는 해당 아이템셋의 지지도가 최소한 이정도는 넘어야 한다는것을 설정해 두는것이다.
Apriori알고리즘 예시
| 구매자 | 구매 아이템 |
| M1 | A,B,C,D |
| M2 | B,E |
| M3 | C,D |
| M4 | D,E |
| M5 | C,D,E |
| M6 | A,B,C,D,E |
트렌젝션 데이터가 위 테이블 처럼 주어지고 최소지지도를 3으로 설정한다. 구매 아이템은 대형 마트의 구매 데이터로 가정한다. {A},{B},{C},{D},{E}는 각각 다른 항목집합(Itemset)으로 보면된다.
1단계
위 테이블 데이터를 스캔하여 항목이 1개인 빈발항목집합을 찾는다. 빈발항목집합은 지지도를 기준으로 판단되며 해당 항목집합의 지지도가 설정한 최소지지도 3보다 높다면 빈발항목집합이 되고 낮다면 비빈발항목집합이 된다.
| Item | 지지도(Support) |
| A | 2 |
| B | 3 |
| C | 4 |
| D | 5 |
| E | 4 |
{A},{B},{C},{D},{E}각각 아이템들의 구매가 2,4,4,5,4 만큼 구매되었고 이는 지지도이다. 최소 지지도 3을 넘지 못하는 {A}는 비빈발 항목집합이므로 항목집합에서 제외한다.(가지치기,Pruning) 여기서 Apriori알고리즘의 원리를 알 수 있다. {A}는 다음 단계의 빈발항목집합 분석에 더 이상 이용되지 않는다. 그 이유는 한 항목집합이 비빈발하다면 그 항목을 포함한 모든 집합 또한 비빈발 하기 때문이다.(규칙 1) 반대로 생각해서 한 항목집합이 빈발하다면 그 항목을 포함한 모든 집합 또한 빈발 하다.(규칙 2)
2단계
항목이 1개인 항목집합중 {A}가 제외되고 남은 {B},{C},{D},{E}로 항목이 2개인 모든 후보 항목집합을 만들어야 한다.
{B,C},{B,D},{B,E},{C,D},{C,E},{D,E}로 총 6개의 후보 항복집합이 만들어진다.
이제 만들어진 6개의 후보 항목집합의 지지도를 조사하고 1단계와 같이 빈발항목집합과 비빈발항목집합을 구분해 비빈발항목집합은 가지치기 하는과정을 반복한다. (이때 지지도는 항목 2개를 모두 구매한것이어야 한다.)
| Item | 지지도(Support) |
| {B,C} | 2 |
| {B,D} | 2 |
| {B,E} | 2 |
| {C,D} | 4 |
| {C,E} | 2 |
| {D,E} | 3 |
최소 지지도를 넘지 못하는 {B,C},{B,D},{B,E},{C,E}는 후보항목집합에서 제외하고 {C,D},{D,E} 만 남게된다.
3단계
2단계에서 걸러진 빈발항목집합을 가지고 항목이 3개인 항목집합을 만든다.
{C,D,E} 가 만들어 진다.
| Item | 지지도(Support) |
| {C,D,E} | 2 |
다음 단계로 넘어가야 하지만 지지도가 3을 넘는 항목이 없으므로 여기서 Apriori알고리즘은 종료된다.
일반화
1. 데이터 베이스를 스캔해 항목이 1개인 빈발항목집합을 구한다.
2. K빈발항목집합을 대상으로 (K+1)빈발항목집합을 구한다.
-빈발 항목집합으로 후보 항목집합을 구하고, 데이터 베이스를 다시한번 스캔해 최소지지도 조건을 만족하는 빈발항목집합을 구한다.
3. 더 이상 (K+1) 빈발항목집합이 만들어 지지 않을 때 까지 2번 과정을 반복한다.
이상으로 Apriori 알고리즘 포스팅을 마치겠습니다.
'알고리즘 공부 > 연관 규칙 분석' 카테고리의 다른 글
| Apriori 알고리즘 (1) (0) | 2020.01.12 |
|---|