Apriori 알고리즘

R로 배우는 Market Basket Analysis

Christopher Bruffaerts

Statistician

연관규칙 마이닝

연관규칙 마이닝은 대규모 거래 데이터베이스에서 항목 간 흥미로운 관계를 찾습니다.

이 작업은 두 하위 작업으로 나뉩니다:

빈발 아이템집합 생성: 대규모 거래 데이터에서 모든 빈발 아이템집합을 찾습니다. 아이템집합은 최소 지지도 임계값을 만족하면 빈발입니다.
규칙 생성: 위 빈발 아이템집합에서 최소 신뢰도 임계값을 넘는 연관규칙을 생성합니다.

Apriori 알고리즘은 연관규칙 마이닝 알고리즘 중 고전적이고 빠른 방법입니다.

Apriori 알고리즘의 핵심 아이디어

Apriori 알고리즘:

바텀업 접근
Apriori 원리를 이용해 후보 아이템집합 생성

Apriori 원리:

아이템집합이 빈발이면, 그 모든 부분집합도 빈발입니다.
- _예:_ {A,B}가 빈발이면 {A}, {B}도 빈발
아이템집합이 비빈발이면, 그 모든 상위집합은 비빈발입니다.
- _예:_ {A}가 비빈발이면 {A,B}, {A,C}, {A,B,C}도 비빈발

¹ Agrawal and Srikant (1994)

예시: 1-아이템집합

아이템 집합 격자2

TID	거래
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 최소 지지도 임계값 = 3/7 = 0.42

예시: 2-아이템집합

아이템 집합 격자3

TID	거래
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 최소 지지도 임계값 = 3/7 = 0.42

예시: 3-아이템집합

모든 아이템집합

TID	거래
1	{A, B, C, D}
2	{A, B, D}
3	{A, B}
4	{B, C, D}
5	{B, C}
6	{C, D}
7	{B, D}

¹ 최소 지지도 임계값 = 3/7 = 0.42

예시: 빈발 아이템집합

아이템 집합 격자3

아이템집합	개수	지지도
{A}	3	0.42
{B}	6	0.85
{C}	4	0.57
{D}	5	0.71
{A,B}	3	0.42
{B,C}	3	0.42
{B,D}	4	0.57
{C,D}	3	0.42

¹ 최소 지지도 임계값 = 3/7 = 0.42

Apriori: 규칙 생성

연산 비용이 큰 빈발 아이템집합 생성을 마치면, apriori는 규칙을 생성합니다:

단일 선행항으로 고신뢰 규칙부터 시작
- _예:_ {A,C} $\rightarrow$ {B}
우변 항목을 늘려 더 복잡한 규칙 구성
- _예:_ {A,C} $\rightarrow$ {B, D}

요령: 연관규칙 가지치기

_예:_ {B,C,D} $\rightarrow$ {A}의 신뢰도가 낮으면, 결론에 A가 포함된 모든 규칙을 버립니다(예: {B,D} $\rightarrow$ {A, C}, {D} $\rightarrow$ {A,B, C}).

Apriori 첫 시도

거래 데이터

inspect(head(trans,2))

    items     transactionID
[1] {A,B,C,D} 1            
[2] {A,B,D}   2

apriori 함수 첫 호출 - 빈발 아이템집합

support.all = apriori(trans, 
                      parameter = list(supp = 3/7, target="frequent itemsets"))

Apriori 출력 - 빈발 아이템집합

빈발 아이템집합

inspect(support.all)

    items support   count
[1] {A}   0.4285714 3    
[2] {C}   0.5714286 4    
[3] {D}   0.7142857 5    
[4] {B}   0.8571429 6    
[5] {A,B} 0.4285714 3    
[6] {C,D} 0.4285714 3    
[7] {B,C} 0.4285714 3    
[8] {B,D} 0.5714286 4

아이템 집합 격자3

Apriori로 규칙 추출

파라미터: 채굴 파라미터는 추출되는 아이템집합/규칙의 특성을 바꿉니다.

지지도 = 3/7
신뢰도 = 60%
규칙 최소 길이 = 2

특정 인자로 apriori 호출하여 규칙 추출

rules.all = apriori(trans,
                parameter = list(supp=3/7, conf=0.6, minlen=2),
                control = list(verbose=F)
                   )

규칙 추출: 출력

규칙 확인

inspect(rules.all)

    lhs    rhs support   confidence lift      count
[1] {A} => {B} 0.4285714 1.0000000  1.1666667 3    
[2] {C} => {D} 0.4285714 0.7500000  1.0500000 3    
[3] {D} => {C} 0.4285714 0.6000000  1.0500000 3    
[4] {C} => {B} 0.4285714 0.7500000  0.8750000 3    
[5] {D} => {B} 0.5714286 0.8000000  0.9333333 4    
[6] {B} => {D} 0.5714286 0.6666667  0.9333333 4

Ayo berlatih!

R로 배우는 Market Basket Analysis