[Data Science] Association Rule Mining (6) Interesting Measures

 

 

Table 1. Cereal and Basketball Relation

Basketball과 Cereal을 각각 $B$, $C$라고 표기하자. 이때 rule의 sup과 conf를 튜플로 표기하면

$B \to C$ = [40%, 66.7%] 이다. 그러나 실제 시리얼을 먹는 학생의 비율은 3750/5000=75%로 confidence보다 크다. 

심지어 $B$ 없이도 $C$의 비율은 $P(C)=0.75$로 rule $B \to C$는 informative하지 않는다.

 

심지어 rule $B \to \neg C$ = [20%, 33.3%]는 sup과 conf 모두 낮지만, $P(\neg C | B) = 1750/2000$으로 확률의 측면에서 도 정확하다고 할 수 있다. (more informative)

 

즉, support와 confidence는 association에는 유용하지만, correlation은 설명하지 못한다.

따라서 $lift$라는 지표를 새로 도입한다. (아래 Table 5에 다양한 평가 지표가 존재한다.)

 

\[ lift(A, B) = \cfrac{P(B|A)}{P(B)} = \cfrac{conf(A \to B)}{sup(B)} = \cfrac{P(A, B)}{P(A)P(B)} \]

$lift=1$이면, $A$와 $B$는 독립임을 알 수 있다. $lift > 1$이면 $A \to B$일 확률이 높다고 해석할 수 있고, $lift < 1$이면 $A \to B$일 확률이 낮다고 해석할 수 있다.

 

Table 1에서 rule $B \to C$와 $B \to \neg C$를 $lift$의 측면에서 바라보자.

$lift(B, C) = \cfrac{2000/5000}{(3000/5000) \cdot (3750/5000)} = 0.89$

$lift(B, \neg C) = \cfrac{1000/5000}{(3000/5000) \cdot (1250/5000)} = 1.33$

따라서 rule $B \to \neg C$가 더 정확한 정보(많이 나타날 확률)를 갖고 있다고 볼 수 있다.

 

Interestingness Measures

Selecting the Right Interestingness Measures for Association Patterns. by Tan, Kumar, Srivastava

위의 표는 다양한 평가지표들이다. 그리고 다양한 성질(property)를 만족하거나 만족하지 않을 수 있는데, 이중에서 Null-invariance에 대하여 중요하게 살펴볼 것이다.

 

Null invariance는 null-transactions가 영향을 주지 않는 값을 말한다. 

null-transaction은 두 item 모두 없는 데이터를 말한다. 

아래 표에서는 $\neg coffee, \neg milk (\neg m, \neg c)$가 null-transaction에 해당된다. 

milk vs coffee contingency table

null-transaction은 실제 데이터에서 굉장히 많이 차지하고 있으면서 correlation analysis에 매우 큰 영향을 주기 때문에, 여러 연구자들은 null-invariant한 평가지표를 유용한 지표로 생각하고 있다.

 

그러나 대부분의 평가 지표들은 null-invariant하지 않다. 대표적으로 $lift$와 $\chi^2$은 null-invariant가 아니다.

 

Null-invariant한 지표들은 $AllConf(a, b)$, $Coherence(a, b)$, $Cosine(a, b)$, $Kulc(a, b)$, $MaxConf(a, b)$ 이렇게 5개가 있다. (모두 값의 범위는 $[0, 1]$이다.)

 

\[ AllConf(a, b) = \cfrac{sup(ab)}{\max(sup(a), sup(b))} \]

\[ Coherence(a, b) = \cfrac{sup(ab)}{sup(a) + sup(b) - sup(ab)} \]

\[ Cosine(a, b) = \cfrac{sup(ab)}{\sqrt{\sup(a) sup(b)}} \]

\[ Kulc(a, b) = \cfrac{sup(ab)}{2}\left( \cfrac{1}{sup(a)} + \cfrac{1}{sup(b)} \right) \]

\[ MaxConf(a, b) = \max \Big\{ \cfrac{sup(ab)}{sup(a)}, \cfrac{sup(ab)}{sup(b)} \Big\} \]

Comparison of Null-Invariant Measures

이제 여러 데이터셋에 대하여 5개 지표를 비교해보자.

우선 $D_1, D_2$는 $mc$가 $\neg mc$, $m \neg c$보다 많으므로 positively correlated하다. 반면에 $D_3$는 negatively correlated하다. $D_4$는 $mc \ : \ \neg mc$의 비율과 $mc \ : \ m \neg c$의 비율이 같으므로 neutrally correlated하다. 

 

$D_1$과 $D_2$는 null-transaction만 다르다. 그러나 5개 지표 모두 null-invariant하므로 $D_1$과 $D_2$ 모두 같은 결과값을 갖는다.

 

$D_1$과 $D_3$를 비교해보자. 이들은 $mc$ 데이터의 수가 다르다. 특히 $D_3$는 $mc$의 데이터가 $\neg m \neg c$ 에 비해 매우 적다. 이 경우 5개 지표 모두 매우 작은 값을 나타내는 것을 볼 수 있다.

 

$D_4 ~ D_6$을 살펴보자. 이들은 같은 null-transaction을 갖는다. $Kulc$는 $D_4 ~ D_6$에 대하여 모두 $0.5$로, neutral한 결과를 갖는다. 

 

IR, Imbalance Ratio

IR은 두 itemset $A$, $B$의 imbalance를 측정하는 지표이다. 범위는 $[0, 1]$이고 $0$에 가까울 수록 balance하고, $1$에 가까울 수록 imbalance하다고 해석한다.

\[ IR(A, B) = \cfrac{|sup(A) - sup(B)|}{sup(A) + sup(B) - sup(A \cup B)} \]

 

$IR$을 이용하여 위의 neutral했던 데이터셋 $D_4 ~ D_6$을 살펴보자.

$D_4$의 경우, $IR(m, c) = 0$으로 완벽히 balance하다. 

$D_5$의 경우, $IR(m, c) = 0.89$로 매우 imbalance하다고 할 수 있다.

$D_6$의 경우, $IR(m, c) = 0.99$로, $D_5$보다도 훨씬 imbalance하다.

 

따라서, $Kulc$와 $IR$을 같이 활용하면, interestingness를 잘 판단할 수 있다.