Data Science 2.Frequent Pattern Mining

이번 포스트는 Pattern Mining 중에 Frequent Pattern Mining (FP)에 대해 다룬다.

Frequent Pattern Mining

Basic Concepts of FP Mining

1. Frequent Pattern Mining은 무엇일까?

• 큰 데이터에서 자주 나타나는 패턴을 찾는 것
  • 데이터를 많이 모아놓고 보면 어떤 것들이 우연이 아니라 반복적으로 같이 나타난다.
  • 그 반복되는 구조를 찾는 것이 FP 이다.
  • 단순히 많이 나오는 것이 아닌 빈도 + 관계성이 중요

2. Frequent Patterns는 무엇인가?

• 데이터 안에서 자주 등장하는 패턴
  • 같이 자주 등장하는 아이템 집합
  • 순서가 있는 패턴
  • 구조 안에서 반복되는 패턴

3. 왜 Frequent Pattern Mining이 중요한가?

• 여러 산업에서는 큰 데이터베이스로부터 의미 있는 패턴을 뽑아내는 데 관심이 많다.
  • Interesting Pattern = 의사결정에 도움이 되는 패턴
  • 패턴 발견 -> 의사결정 -> 실제 성과로 연결되기 때문

Ex) Market Basket Analysis

• 고객이 장바구니에 함께 담는 상품들 사이의 연관관계를 찾는 것
  • 상품 bundle 설계
  • 진열 전략
  • 마케팅 전략에 적용

Patterns and Supports

• transaction DB : 여러 개의 거래가 모인 데이터
• 각 거래 T는 아이템 집합(item set)

Support : 어떤 itemset이 몇 번 등장했는지

• support(X) = X가 포함된 거래 수

Relative Support : 전체 거래 중에서 얼마나 비율로 등장하는가

• support(X) / 전체 거래 수

Frequent Patterns의 정의

• support ≥ min_sup 이면 frequent
  • min_sup : 최소 지지도 (threshold)
• 아이템이 많아질수록 support는 줄어든다.

Association Rule

형태 : X → Y

• X가 있으면 Y도 같이 나올 가능성이 높다.
• 같이 나온다는 정보보다 방향성과 의미가 있다.
• Strong Rules : 강한 규칙이 필요

Strength of Association Rule

• Support : support(X ∪ Y)
  • X와 Y가 같이 등장한 비율
  • 얼마나 자주 같이 나오는지를 물어봄
• Confidence
  • confidence(X → Y) = support(X ∪ Y) / support(X)
  • X가 있을 때 Y가 나올 확률

support가 높고, confidence가 높은 규칙이 좋다.

Frequent Mining의 문제점

• 패턴 개수가 폭발적으로 증가
• frequent itemset 이면, 모든 subset도 frequent하다.

Closed Frequent Pattern

정의 : X가 closed ⇔ sup(Y) = sup(X)인 Y ⊃ X 존재하지 않음

• X보다 큰 집합이 있는데 support가 같으면 X는 정보 없음.
• 정보 손실 없이 압축이 가능하다.

두 가지 경우

• sup(Y) = sup(X)
  • 정보가 동일, X를 저장할 필요가 없다.
• sup(Y) < sup(X)
  • X가 더 중요한 정보, X를 유지한다.

Closed pattern = Complete Information

• 모든 frequent pattern은 복원이 가능하다.

Maximal Frequent Pattern

정의 : X가 maximal ⇔ sup(Y) ≥ min_sup인 Y ⊃ X 존재하지 않음

• 더 이상 확장 불가능한 가장 큰 frequent pattern
• 확장 가능한 더 큰 frequent set이 없다.
  • 끝까지 키운 패턴
• 가장 큰 frequent pattern만 남기기에 개수가 매우 적지만
  • support 정보 손실이 있다.

포함관계

Frequent ⊃ Closed ⊃ Maximal

• Frequent : 전체
• Closed : 압축 (정보는 유지)
• Maximal : 더 압축 (정보 일부 손실)

---

FP Mining Method : Apriori

Apriori Algorithm

가능성 있는 애들만 만들고, 나머지는 아예 보지 않는다.

• 후보를 제한적으로 생성 (confined candidate generation)
• frequent itemset의 모든 subset은 반드시 frequent
  • 어떤 subset이 infrequent -> superset은 절대 frequent 불가

Purning Principle

• infrequent itemset이 하나라도 있으면 그 superset은 생성하지도 않는다.

Overall Process (Join & Prune)

1. DB scan -> F1 (frequent 1-itemsets)
2. 반복:
	(1) Join -> 후보 생성 (Ck)
	(2) Prune -> infrequent 제거 -> Fk
3. 더 이상 없으면 종료 

Apriori 는 작은 것부터 시작해서, 불가능한 후보는 미리 제거하며 점점 키운다.

Candidate Generation

1. Self-Join

• 길이 k인 frequent itemset들끼리 서로 붙여서
• 길이가 k+1인 후보를 만든다.
• Join 조건
  • 길이 k-1인 두 itemset p,q를 붙여서 길이 k 후보를 만들기 위해서는 앞의 k-2개의 아이템이 같아야 함.
  • 앞의 두 개가 같아야 뒤에걸 합칠 수 있는 abcd의 예시

2. Pruning

• 만든 후보들 중에서 Apriori property를 이용
• 절대 frequent일 수 없는 후보를 미리 제거한다.

핵심 흐름

Join -> infrequent subset 검사 -> 없으면 candidate 추가

Limitation of Apriori Algorithm

1. 후보가 너무 많다.

• Apriori는 breadth-first 방식
  • 하나씩 다 확장하면서 간다
• 데이터가 커지고 아이템이 많아지면 candidate가 많이 생긴다.
• pruning을 해도 초기의 조합 수가 너무 많다.

2. DB를 여러 번 스캔해야 한다.

• 각 단계마다 support를 하기 위해 DB를 반복적으로 읽는다.

• candidate generation이 비싸기 때문에 더 좋은 방법이 필요

---

Advanced FP Mining Methods

굳이 horizontal DB로만 mining 하지 말고, vertical format으로 하면 어떻게 될까.?

Vertical Data Format

item -> TID list

• 각 아이템이 어디 거래에 등장했는지를 저장

ECLAT (Equivalence Class Transformation)

• DFS + 집합 교집합 (set intersection)
  • Apriori 처럼 candidate를 만들고 DB를 반복 스캔하는 것이 아니다.
• vertical format에서 TID List끼리 계속 교집합해서 support 계산

왜 좋은가?

• 매번 원본 transaction DB를 전부 다시 읽지 않아도 된다.
• 이미 저장된 TID set끼리 교집합

단점

• TID set이 엄청 길어질 수 있다.
  • water, tissue 처럼 모든 거래에 포함되는 아이템 : TID set 저장 비용이 크다.

FP-Growth

• 비싼 candidate generation 없이 frequent pattern을 찾는 방법
• Apriori와의 차이
  • 후보를 많이 만들지 않는다.
  • 데이터를 압축하여 구조 안에서 패턴을 찾는다.
• DFS 사용
• 어떤 frequent itemset p를 기준으로 탐색할 때, p를 포함하는 transaction들만 보면 된다.

STEP 1 : Data Compression

• FP-Tree 만들기
  • frequent item들의 공통 prefix를 공유하게 해서 DB를 압축 표현하는 트리
    • 많은 트랜잭션들은 비슷한 prefix를 가지고 있다.
  • Step A : DB 1번 스캔
    • 각 item frequency 계산 (infrequent item 제거)
    • frequent item을 내림차순으로 정렬
  • Step B : 각 transaction 재정렬
    • 각 transaction 안에서도 frequent item 순서대로 다시 정렬
  • Step C : 트리에 삽입
    • 각 정렬된 transaction을 트리에 넣는다.
    • 공통 prefix가 있으면 같은 branch를 공유하고 count를 증가

각 Path의 의미

• 하나 이상의 transaction들이 공유하는 prefix itemset
• prefix가 몇번 등장했는지의 수 : node의 count

STEP 2-3 : Mining FP-Tree & Generating Frequent Patterns

• Conditional Pattern Base : 특정 item p를 포함하는 prefix 경로들
  • p가 등장하는 모든 경로에서 p 이전만 모은 것
• Bottom -> Top
  • 빈도가 낮은 것부터 시작해야 탐색 공간이 줄어든다.
  • 작은 것부터 DFS 확장

Apriori vs FP-Growth

• 둘 다 같은 결과를 갖는다.
  • 모든 frequent pattern이 동일
• 차이점 :
  • Apriori
    • BFS
    • candidate generation이 많다.
    • DB를 여러 번 스캔한다.
  • FP-Growth
    • DFS
    • candidate가 없다.
    • DB scan이 적다. (보통 2번)

---

Pattern Evaluation

• Apriori/FP-Growth를 돌리게 되면
  • 수천, 수만 개의 규칙을 확인할 수 있다.
• 패턴이 많이 나온다고 꼭 좋은 건 아니다.

Lift

• A가 있을 때 B가 얼마나 더 잘 발생하는지를 나타내는 척도
  • Confidence 는 확률 / Lift는 진짜 관계

\[lift(A → B) = P(A ∩ B) / (P(A) × P(B))\] \[lift = confidence / support(B)\]

의미

lift 값	의미
= 1	독립 (상관 없음)
> 1	양의 상관
< 1	음의 상관

Chi-Square

• Observed vs Expected 비교
  • 우연이면 이정도 나와야하는데, 실제랑 얼마나 다른가?

\[\chi^2 = \sum \frac{(Observed - Expected)^2}{Expected}\]

• Expected = (row sum × column sum) / total

• 해석 : 값이 크다

  • 독립이 아니고 상관성이 있다.

Kulczynski Measure

Null-Invariance : Null 데이터가 추가되어도 값이 변하지 않는 Metric

왜 사용하는가?

• Null-Transaction

• NULL 데이터가 너무 많으면 Lift, χ² 값이 왜곡됨

  • 실제로 weak 관계여도 misleading의 결과 가능

Kulczynski Measure

• 두 confidence의 평균
  • A -> B, B -> A를 양쪽 다 보기 때문에 한 쪽 Bias 제거

\[Kulc(A,B) = \frac{1}{2} (P(A|B) + P(B|A))\] \[= \frac{1}{2} \left( \frac{s(A∩B)}{s(A)} + \frac{s(A∩B)}{s(B)} \right)\]

• 특징
  • null-invariant
  • imbalance에 강하다.
  • 0~1 사이의 범위를 가지고 있다.

Imbalance Ratio (IR)

• A와 B의 빈도 차이 측정 \(IR(A,B) = \frac{|s(A) - s(B)|}{s(A) + s(B) - s(A∩B)}\)

요약

NULL 데이터가 적은 경우 : Lift, χ² 사용 가능

NULL 데이터가 많은 경우 : Kulc + IR 사용