[AI] Association Mining

1. Association Mining

주어진 트랜잭션 집합으로부터, 어떤 아이템들이 나타날지를 다른 아이템들의 발생으로부터 예측하는 규칙을 찾는 작업이다.

 

 

위의 그림은 장바구니 분석의 예시인데,

{Diaper} → {Beer},

{Milk, Bread} → {Eggs, Coke},

{Beer, Bread} → {Milk}

기저귀를 사는 사람이 맥주를 산다, 우유와 빵을 사는 사람이 계란과 콜라를 산다, 맥주와 빵을 사는 사람이 우유를 산다 처럼 분석하는 것이다. 

 

1) 항목 집합(Itemset)

- 한 개 이상의 항목(들)의 집합

ex. {Eggs}, {Milk, Bread, Diaper}

- k-항목집합(k-itemset) : k개 항목을 가지는 항목 집합

 

2) 지지도 카운트(Support Count) : σ

- 항목집합이 나타난 횟수

ex. σ{Eggs} = 1, σ{Milk, Bread, Diaper} = 2

 

3) 지지도(Support) : s

- 항목집합이 나타나는 트랜잭션의 비율

ex. s{Eggs} = 1/5 = 0.2, s{Milk, Bread, Diaper} = 2/5 = 0.4

 

4) 빈발 항목집합(Frequent Itemset)

- 지지도가 주어진 임계치 minsup(최소지지도)보다 큰 항목집합

ex. minsup = 0.3이라면, {Eggs}은 빈발하지 않으며, {Milk, Bread, Diaper}은 빈발

 

5) 연관규칙

- X와 Y가 항목집합이라 할 때, X → Y 형태로 나타나는 함축 표현

ex. {Milk, Diaper} → {Bread}

 

6) 연관규칙의 평가척도

- 지지도(Support) : s

X와 Y를 함께 포함하는 트랜잭션 비율규칙이 얼마나 중요한가?- 신뢰도(Confidence) : cX를 포함한 트랜잭션 중에 Y가 나타나는 비율 규칙이 얼마나 믿을만 한가?

 

7) 연관규칙 마이닝

- 트랜잭션들의 집합이 주어졌을 때, 다음 조건을 만족하는 모든 규칙을 찾는 작업

Support ≥ minsup

Confidence ≥ minconf

 

 

 

연관규칙의 예

{Milk,Diaper}→{Beer} (s=0.4, c=0.67)
{Milk,Beer}→{Diaper} (s=0.4, c=1.0)

{Diaper,Beer}→{Milk} (s=0.4, c=0.67)

{Beer}→{Milk,Diaper} (s=0.4, c=0.67)
{Diaper}→{Milk,Beer} (s=0.4, c=0.5)

{Milk}→{Diaper,Beer} (s=0.4, c=0.5)

 

8) 관찰 결과

- 모든 규칙은 {Milk, Diaper, Beer}의 동일한 항목집합에서 나옴

- 동일한 항목집합에서 나온 규칙들은 지지도는 동일하나 신뢰도는 다를 수 있음

- 지지도와 신뢰도를 분리하여 규칙을 결정할 필요성