Frequent Pattern, Association Rules

Frequent Pattern, Association Rules

Minimum support를 만족하는 pattern을 frequent pattern이라 한다.

Frequent pattern들 간의 관계를 rule이라 한다.

 

Rule 중에서 minimum confidence를 만족하는 rule을 association rule이라 한다.

 

Support

Itemset X의 support는 전체 transaction DB에서 X가 얼마나 나타났는지를 의미한다.

비율이 될 수도 있고 카운팅 횟수가 될 수 있다. 이는 정하는 마음이다.

 

Minimum support를 threshold로 삼아서 이보다 큰 support를 가져야만 frequent pattern이 될 수 있다.

frquent pattern = $support \geq min\_support$

 

Itemset의 size가 1인 itemset의 support는 아래와 같이 구할 수 있다.

따라서 크기가 1인 frequent pattern은 $\{ A, B, D, E \}$가 된다.

 

Confidence

Itemset X와 Y가 있을 때 $X \rightarrow Y$의 X를 살 때 Y도 같이 살 확률이다.

조건부 확률 $P(Y \vert X)$을 의미한다.

confidence = $\frac{P(X \cup Y)}{P(X)}$

 

Itemset 입장에서는 X와 Y의 합집합에 대한 확률이므로 $\cup$으로 표기하였다.

확률적인 관점에서는 $\cap$으로 볼 수 있다.

 

$X \rightarrow Y$와 $Y \rightarrow X$의 confidence가 다름에 주의해야 한다.

 

Association Rule

Rule $X \rightarrow Y$가 association rule이 되기 위해서는 아래 2가지 조건을 만족해야 한다.

• Itemset $X \cup Y$의 support $\geq$ min_support
• Rule $X \rightarrow Y$의 confidence $\geq$ min_confidnece

 

---

Closed Pattern, Max-Pattern

Frequent pattern의 sub-pattern은 모두 frequent pattern이 된다.

때문에 매우 긴 frequent pattern의 sub-pattern이 모두 frequent pattern이 되며 이 수는 매우 많아지게 된다.

총 개수 = $_nC_1 + _nC_2 + ... _nC_n \; = \; 2^{n} - 1$ ($n$ : frequent pattern의 최대 길이)

 

이러한 redundant한 성질로 인해 모든 frequent pattern을 찾기 힘들어서 closed pattern이나 max pattern의 개념을 도입하여 뽑아내는 pattern의 수를 줄일 수 있다.

Closed pattern으로만 frequent pattern을 정의하면 손실없이 rule과 pattern의 수를 줄일 수 있다.

 

Closed Pattern

Frequent pattern X를 포함하고 X의 support와 같은 support를 가진 frequent pattern Y가 없을 때 X는 closed pattern이다.

즉, 아래 조건을 만족하는 Y가 존재하지 않아야 한다.

• Y : X의 superset
• Y의 support = X의 support

 

Max-Pattern

Frequent pattern X를 포함하는 frequent pattern Y가 존재하지 않을 때 X는 max-pattern이다.

• Y : X의 superset
• Y : frequent patterh $\Rightarrow$ Y의 support $\geq$ min\_support

 

개수 비교

DB에 $\{ \{ a_1, ..., a_{100} \}, \{ a_1, ..., a_{50} \} \}$로 있고 min_sup = 1이라고 하자.

• 모든 frequent pattern의 수 = $2^{100} - 1$
  • 각 100가지 item들이 있고/없고 - 공집합
• closed pattern의 수 = 2
  • $\{a_1, ..., a_{100}\}$ : sup = 1
  • $\{a_1, ..., a_{50} \}$ : sup = 2
• max-pattern의 수 = 1
  • $\{a_1, ..., a_{100} \}$ : sup = 1