2. Frequent Patterns

Mining Frequent Patterns, Association and Correlatons

 

Frequent Pattern Mining

---

데이터 속에서 자주 등장하는 패턴을 분석하는 기술

Frequent Pattern?
: 데이터셋 내에서 자주 등장하는 패턴

예를 들면, 자주 함께 구매되는 상품들

Motivation?
데이터 속에 내재된 패턴들 찾기 위함

• 어떤 상품들이 함께 구매가 되는가? (이게 앞으로 주로 다뤄질 예시)
  • Beers and Diapers
  • 기저귀와 맥주는 함께 구매가 되는 경향이 있다
  • 이 정보를 알면 기저귀와 맥주를 함께 비치하면 판매율이 올라갈 것
• 특정 상품을 구매한 다음 순차적으로 어떤 것을 구매하는 경향이 있는가?
  • 디지털 카메라를 구매한 후에 얼마있다가 SD카드(메모리)를 구매하는 경향이 있다
• 어떤 DNA가 신약에 민감한 반응을 보이는가?
  • 신약에 대해서 특정 증상을 보인 집단에서 공통적으로 특정 DNA를 가지고 있다면, 해당 DNA가 약에 민감한 것으로 생각할 수 있다
• 아무튼 이런 정보들을 얻기 위해서 Frequent Pattern Minining을 하는 것이다

 

Basic Concepts

---

Frequent Pattern Mining을 하기 위해서 기본적으로 알아야 하는 용어들

• Itemset X = {x1, x2, ..., Xk}
  • Frequent Pattern은 이러한 Itemset 중에서 정의된다
  • {A, B, C, D, E} 라는 데이터 집합이 있을 때 이 데이터들로 만들 수 있는 Itemset?
    • 2^5 - 1개의 Itemset이 만들어질 수 있다
    • 빈 집합({})은 Itemset으로 치지 않는다
• Association Rules (X->Y)
  • Association Rules는 2개의 Itemset X, Y로부터 정의된다
  • 이때 X U Y(Union)이 Frequent Pattern 이어야 한다
  • Ex) {Beers, Diapers}라는 Frequent Pattern이 있을 때
    • Beers -> Diapers
    • Diapers -> Beers
    • 2개의 Association Rules를 생각해볼 수 있다
    • 이 중에 의미있는 Rule을 찾는 건 뒤에서
• Support and Confidence
  • Support: Transaction이 Itemset X를 포함할 확률 또는 빈도
    • Minimum Support: Itemset X가 Frequent Pattern인지 아닌지를 결정하는 임계치(Threshold)
      • Itemset X의 Support가 Minimum Support보다 크거나 같으면 X는 Frequent Pattern
  • Confidence: Itemset X를 포함하고 있는 Transaction이 Itemset Y도 포함하고 있을 확률 (조건부 확률)
    • Minimum Confidence: 이것도 역시 임계치로 사용

 

Let min_sup = 50%, min_conf = 50%:

Q. Find all frequent patterns
A. {A:3, B:3, D:4, E:3, AD:3}

Q. Find all association rules
A. A -> D (sup: 60%, conf: 100%), D -> A (sup: 60%, conf: 75%)

A를 산 사람이 D를 살 확률은 100%
D를 산 사람이 A를 살 확률은 75%

 

Closed Patterns and Max-Patterns

---

Frequent Pattern의 하위 개념인 Closed Pattern과 Max-Pattern을 알아보자

• 사실 Pattern이라는 게 엄청나게 많이 만들어질 수 있다
• {A1, A2, A3, ..., A100} 이러한 데이터 집합이 있을 때, 2^100 - 1개의 집합이 만들어질 수 있다
• Subpattern이 너무 많음,,,
• 그래서 Subpattern들을 대표하는 Closed Pattern과 Max Pattern을 마이닝을 한다
• Closed Pattern?
  • Itemset X가 Frequent Pattern이면서, X와 같은 support를 갖는 X의 Superset이 존재하지 않으면, X는 Closed 하다고 한다
• Max Pattern?
  • Itemset X가 Frequent Pattern이면서, X의 Superset인 그러한 Itemset Y가 존재하지 않으면, X를 Max Pattern이라고 한다
  • 즉, Frequent Pattern 중에 본인의 Superset이 존재하지 않으면 해당 패턴을 Max Pattern이라고 한다
• Closed Pattern은 Frequent Pattern들을 압축시켜주는 역할 을 한다
  • 불필요한 Pattern, Rule들을 줄여주는 역할을 한다

 

말로는 뭔가 이해하기 어려울 수도 있으므로, 예시를 들어보자

• Y,Z는 Closed Pattern이지만, X는 Y가 있기 때문에 Closed Pattern이 될 수 없다
  • 사실 Y가 있는 이상, X는 크게 의미없는 Pattern이다. 그렇기 때문에 Closed Pattern이 중요한 거!
• Z는 Max Pattern이지만, Y는 Z가 있기 때문에 Max Pattern은 될 수 없다

 

Quiz

Q1. How many frequent patterns are there?
A1. 2^100 - 1개의 Frequent Pattern 존재
min_sup이 1이기 때문에 모든 조합의 패턴이 Frequent Pattern이 된다

Q2. What is the set of closed patterns?
A2.
<a1, a2, ..., a100>: 1
<a1, a2, ..., a50>: 2

두 패턴은 Frequency가 다르기 때문에 둘다 Closed Pattern이 된다

Q3. What is the set of max patterns?
A3. <a1, a2, ..., a100>: 1
Frequent Pattern들 중에서 가장 Superset이 Max Pattern이 된다

 

Scalable Methods for Mining Frequent Patterns

---

Database에 100개의 Item이 있다고 하면, 2^100 - 1개의 패턴이 생성될 수 있는데, 이건 너무 많다

• Downward closure propery of frequent patterns
  • Frequent Pattern의 Subset은 반드시 Frequent하다
  • 이것을 이용한 방법이 Downward closure
  • Ex) {beer, diaper, nuts}가 Frequent Pattern이면, {beer, diaper}은 당연히 Frequent Pattern
    • 이런 경우에 {beer, diaper}는 굳이 없어도 되는 Redundant한 Pattern이다
• 이걸 이용한 마이닝 방법들에는 어떤 Method 들이 있을까?
  • Apriori
  • FP-growth (Frequent Pattern Growth)
  • Charm (Vertical Data Format)
  • 이 Method들에 대해서는 뒤에서 하나씩 다룰 것