[CS246] Frequent Itemsets Mining & Association Rules

 

Market-Basket Model

우리는 association rule을 찾고 싶다. Amazon과 같은 곳에서 어떤 사람이 $\{ x,y,z \}$를 샀다면, $\{ v,w \}$ 도 사는 경향을 찾고 싶을 것이다. 

Example 1 (Stanford CS246)

위 그림을 예시로 할 때, 2개의 rule을 찾을 수 있다. {milk} -> {coke}, {diaper, milk} -> {beer}

Applications 

item과 basket은 반드시 상품과 바구니일 필요가 없다. 추상화된 데이터 형태라고 생각하면 다양한 응용이 가능하다.

 

Supermarket

items=상품, basket=상품 집합

 

Topic discovery

items=단어(word), basket=문서(document)

 

Plagiarism

item=문서(documents), basket=문장(sentences)

 

Biomarkers

item=신약, 부작용 (drugs & side-effects)

basket=환자

 

더 일반화 하면, association은 item과 basket의 many-to-many mapping으로 간주할 수 있다.

Finding communities in graphs (Stanford CS246)

트위터(이제는 X로 불리는) 커뮤니티를 찾을 때에도 market-basket 모델이 적절하다. 

item=node, basket=outgoing neighbors

 

Frequent Itemsets

basket에 자주 같이 등장하는(appear together frequently) itemset을 찾아보자.

 

Support

support for itemset $I$: 전체 itemset에서 $I$를 포함하는 basket의 개수

Example 1 (Stanford CS246)

예시 데이터에서 {Beer, Bread}의 support는 2이다. (TID=2, 4에서 등장)

support threshold $s$가 주어졌을 때, 최소 $s$개의 basket을 frequent itemset이라 부른다.

 

Example: Frequent Itemsets

아래와 같이 5개 item에 대한 8개의 basket에 대하여, support thresdhold=3일때의 frequent itemset을 구해보자.

Example 2 (Stanford CS246)

이때 frequent itemsets은 {m}, {c}, {b}, {j}, {m, b}, {b, c}, {c, j} 이다.

(예: {m, b}는 B1, B3, B5, B6에 등장하므로 support=4이다.)

반응형

Association Rules

$I \to j$: 어떤 basket이 $I$의 모든 item을 가지고 있을 때, $j$ 역시 포함하고 있을 가능성(likely)

위의 예시에서 $\{ m, b \} \to c$ 라는 association rule을 작성할 수 있다. 

그렇다면 association rule이 얼마나 좋은 rule인가?

 

Confidence

$I$가 주어졌을 때 item $j$일 확률, 즉

\[ \text{conf}(I \to j) = \cfrac{\text{support}(I \cup j)}{\text{support}(I)} \]

 

Interest

그러나 confidence가 높다고 해서 우리가 관심있는 association rule이 아닐 수 있다.

예를 들어 milk는 너무 잘 팔려서 거의 모든 거래 데이터에 포함된다고 하자. 이때 association rule $X \to \text{milk}$는 confidence는 높지만 (데이터 발견이라는 의미에서) 전혀 의미가 없다.

그래서 새로운 지표 interest를 도입한다.

\[ \text{Interest}(I \to j) = \text{conf}(I \to j) - \Pr(j) \]

 

Example: Confidence and Interest

 

Example 2 (Stanford CS246)

Association rule $\{ m,b \} \to c$ 에 대하여 confidence와 interest를 구해보자.

$\text{conf}(\{ m, b \} \to c) = \cfrac{\text{support}(\{ m, b, c \})}{\text{support}(\{ m,b \})} = \cfrac{2}{4}=0.5$

$\text{Interest}(\{ m,b \} \to c) = \text{conf}(\{ m, b \} \to c) - \Pr(\{ c \}) = 0.5 - 5/8 = -1/8$

$c$는 전체 basket 중 $5/8$에 포함되어 있어서 그렇게 interesting 하지 않는 rule이 된다.

 

Mining Association Rules

이제 본격적으로 association rule을 찾아보자.

문제를 정의하자면 $\text{support} \ge s,\ \text{confidence} \ge c$ 2가지 모두 만족하는 association rule을 찾는 것이다.

Hard part: frequent itemsets을 찾으면 association rule을 만드는 것은 쉽다. 그러나 frequent itemsets을 찾는 것이 어렵다!!

 

Rule Generation

일단 frequent itemset $I$를 구했다고 하자. (Apriori algorithm 등으로 구할 수 있다. 이전 포스팅에서도 설명했지만, 다음 포스팅에서 보다 구체적으로 설명할 것이다.)

이렇게 구한 frequent itemset $I$의 모든 부분집합 $A$에 대하여, $I$가 frequent하다면 $A$ 역시 frequent하다는 사실을 이용하여 rule을 만들 수 있다.(support threshold 만족) 그리고 이렇게 구한 rule들의 confidence를 계산하여 association rule을 구한다. (confidence threshold 만족)

 

 

Observation

$I = \{ a,b,c,d \}$가 frequent itemsets이라 하자. 그렇다면 $\{ a,b,c \} \to \{d\},\ \{ a,b \} \to \{c, d\}$ 등의 rule마다 confidence를 계산하여 confidence threshold를 넘지못하면 탈락시킨다. confidence를 구해보면

\[ \text{conf}(\{a, b, c\} \to d) = \cfrac{\text{support}(\{ a, b, c,d \})}{\text{support}(\{a,b,c\})}, \quad \text{conf}(\{a, b\} \to \{c, d\}) = \cfrac{\text{support}(\{ a, b, c,d \})}{\text{support}(\{a,b\})} \]

즉 같은 frequent itemset $I$에서 생성된 (일종의 후보) rule의 confidence의 분자는 같다. $\text{support}(\{ a,b,c \}) \le \text{support}(\{ a,b \})$이므로 $\{a,b,c\} \to d$는 weak rule이고 $\{ a,b \} \to \{c, d\}$는 stronger rule이 된다. 

즉, weak rule에서 confidence threshold를 넘지 못하면 더이상 rule을 생성하지 않아도 된다.

 

Example: Rule Generation

Example 2 (Stanford CS246)

support threshold = 3, confidence threshold = 0.75에서 association rule을 구해보자.

Step 1. Find frequent itemsets

{b, m}, {b, c}, {c, m}, {c, j}, {m, c, b}

 

Step 2. Generate rules

$\text{conf}(bc \to m) = 3/5 < 0.75$ 이므로 탈락. 그리고 더 weak rule인 $b \to cm$ 역시 자동 탈락.

 

Compacting the Output

그럼에도 불구하고 수백만개의 rule을 확인해야만 한다. rule의 개수를 줄이기 위해 support를 이용한 후처리(post-process) 기법을 활용할 수 있다. 

 

Maximal frequent itemsets

상위집합(superset)이 더이상 frequent하지 않을 때 현재의 frequent itemsets이 maximul frequent itemsets이다.

더 많은 pruning 가능

 

Closed itemsets

상위집합(superset)의 support가 더 작을때 자신이 closed itemset이다. (support > 0)

frequent information 뿐 아니라 정확한 support(count) 정보를 제공한다.

Example: Maximal/Closed itemsets