[Data Science] Association Rule Mining (5) Rule Generation

 

앞서 Apriori 또는 FP-Growth 알고리즘을 이용하여 Frequent Itemset Mining을 할 수 있다. 이제 mining하여 얻은 pattern들로 rule을 생성할 것이다.

 

Rule Generation

frequent itemset $L$의 모든 (공집합이 아닌) 모든 부분집합 $f$을 찾을 것이다. ($f \to L - f$)

Figure 1. 길이가 4인 frequent itemset의 candidate rules

위에서 보듯이, $|L|=k$라면 가능한 모든 candidate association은 $2^k -2$개가 있다. ($L \to \varnothing$ 와 $\varnothing \to L$은 제외)

보다 효과적으로 rule을 생성할 수 없을까?

 

Anti-monotone property of Confidence

일반적으로 서로 다른 rule에 대하여 confidence를 비교할 수 없다. 

그러나 같은 itemset에서 생성된 rule이라면, confidence를 비교할 수 있다. 

예를 들어, $L = \set{A, B, C, D}$에서 생성되는 rule은 다음의 성질을 만족한다.

\[ c(ABC \to D) \ge c(AB \to CD) \to c(A \to BCD) \]

rule의 RHS가 많을 수록 confidence는 당연히 감소한다. 아래 수식을 통해 확인할 수 있다.

\[ \cfrac{\sigma(\set{A,B,C,D})}{\sigma(\set{A,B,C})} \ge \cfrac{\sigma(\set{A, B, C, D})}{\sigma(\set{A})} \]

Figure 2. Lattice of rules

또한 candidate rule은 2개의 rule에서 만들어질 수 있다. 단, 이때 두 rule의 접두사가 공유하고 있는 item이 있어야한다. 

아래 예시의 경우, $\cancel{D}$라는 RHS에서 $A$라는 공통 접두사가 있으므로 rule을 생성할 수 있다. 

Apriori에서는 RHS를 바탕으로 rule generation을 한다.

Figure 3. Generating Candidate rule by Merging

물론, 위의 anti-monoton property에 따라 $AD \to BC$의 confidence가 작다면 이렇게 생성된 $D \to ABC$ 역시 pruning된다.