Frequent Patterns, Association Rules, Closed Pattern, Max Pattern (Data Mining)

https://analytics4everything.tistory.com/95

Frequent pattern mining

위 블로그를 필사하여 공부한 글입니다.

 

* 모든 텍스트와 이미지의 출처는 위 블로그입니다.

 

---

 

우유를 자주 사는 고객에게 어떤 아이템을 추천할 수 있을까?

-> 우유를 사는 사람들이 주로 무엇을 더 사는지 알아야 함

-> 우유를 샀던 사람이 어떤 아이템을 더 구매했는지 패턴을 파악해야 함

 

 

* Frequent Pattern(FP; 빈발패턴)이란

데이터 집합에서 자주 발생하는 패턴으로 우유와 시리얼 같이 transaction 데이터 집합에서 빈번하게 발생하는 항목집합

 

- 데이터의 연관관계, 상관관계, 다른 관심대상 관계를 분석하는데 있어, 중요한 역할을 한다.

- 데이터 분류, 군집화 등 다른 데이터마이닝 작업에도 도움이 된다.

 

 

 

---

 

 

Frequent Pattern Data Mining

 

- FP 마이닝이란, 데이터 집합에서 재귀관계를 찾아내는 방법

 

ex. 장바구니 분석

-> 집어 넣는 항목이 많을 때, 항목 간의 연관관계를 파악하여, 구매습관을 분석해내고자 하는 것

 

 

규칙 관심도(interestingness)에 대한 축도

- 지지도(Support)

- 신뢰도(Confidence)

 

- support가 2%라면, 분석 대상 전체 트랜잭션에서 특정 아이템을 구매한 비율이 2%임

- Computer => anti-virus software의 confidence가 60%라면,

  컴퓨터를 구매한 고객 중 S/W를 구매한 비율이 60%임을 의미

 

- 일반적으로, 연관규칙이 최소 지지도의 임계값과 최소 신뢰도의 임계값을 만족하면 '흥미가 있다' 라고 판단한다.

(이 최소 임계값이 minimup support/confidence threshold, 즉 minsup와 minconf 인듯!)

 

출처: 위 블로그

(여기서 왜 교집합이 아니라 합집합으로 나타난지 모르겠다.)

 

 

 

---

 

- itemset(항목 집합): 여러 항목의 집합. 트랜잭션에서 가질 수 있는 요소들의 집합을 의미

출처: 위 블로그

 

- TID(Transaction ID): 각 트랜잭션은 TID라고 하는 식별자를 갖는다.

 

- Association rule(연관 규칙): A=>B

  - itemset A는 공집합이 아니며, B도 공집합이 아니다.

  - itemset A와 B의 공집합은 없으며, 각 itemset이 전체 itemset인 I의 부분집합에 포함된다를 의미

 

- 강한 규칙: minsup과 minconf를 모두 만족하는 규칙

 

- K-itemset(K 항목집합); K개의 항목을 갖는 itemset

  ex) {우유, 빵}: 2-itemset, {우유, 빵, 토마토}: 3-itemset

 

- Frequency(빈도): support 개수

  - K-itemset의 발생 빈도는 K-itemset이 발생한 트랜잭션

 

즉,

1. 지지도: A=>B,

Support(A=>B) = P(AUB)

 

2. 신뢰도: A=>B,

Confidence(A=>B) = P(B|A)

 

 

 

---

 

Association Rule 분석의 2단계

 

1. 모든 FP 발견하기; 정의에 의해 사전에 설정한 minsup보다 많이 발생하는 모든 항목 집합 찾아내기

2. FP에서 강한 연관규칙 생성하기; 정의에 의해 minsup과 minconf를 만족하는 규칙 찾아내기

 

모든 FP의 집합을 발견하는 것은 매우 비용이 큰 작업이다. (= 모든 frequent itemset을 찾는 것은 비효율적)

반면 두 번째 단계는 상대적으로 적은 비용이 든다.

-> 따라서 association rule의 전체 성능은 첫 번째 단계에서 결정됨

 

이러한 첫 단계의 계산에서 애로점은 대규모 항목집단이 발생한다는 것인데, 위에서 말한 재귀적인 패턴을 분석한다는 것과 마찬가지로 모든 항목에 대해 하위패턴도 파악한다.

따라서 상대적으로 짧은 여러 개의 FP 집합도 조합을 갖는다.

ex. 길이가 100인 FP {a1, a2, ..., a100}은 100C1이므로 100개의 항목이,

     2개의 항목 집합은 100C2이므로 점점 많아진다.

-> 100C1 ~ 100C100까지 모두 더하면 약 2^100 - 1

(전체 itemset의 원소의 개수가 많아지면 결국 exponential하게 된다.)

 

따라서, 이러한 비용 문제를 해결하기 위해 고안해낸 방법이 바로 Closed Pattern과 Max Pattern.

 

 

 

---

 

 

* Closed Pattern

: An itemset X is closed if X is fequent & there exists no super-pattern Y⊃X, with the same support as X

- dataset D에서 X와 동일한 support 개수를 갖는 super pattern Y가 없다면, itemset X는 dataset D에서 closed 되었다고 한다.

 

ex)

X: {1, 2} = 60%

Y1: {1, 2, 3} = 50%

Y2: {1, 2, 4} = 50% 인 상황에서 minsup이 50%인 패턴을 frequent-pattern이라고 정의하자.

 

X를 포함하는 더 큰 pattern은 Y1, Y2밖에 없는데,

Y1, Y2가 X와 같은 support인 super-pattern(Y1, Y2)가 없으므로 X를 closed-pattern이라고 한다.

즉, X와 같은 support인 Y1, Y2가 없기 때문에 closed-pattern이라고 함

 

 

 

* Max Pattern

: An itemset X is a max-pattern if X is frequent & there exists no frequent super-pattern Y⊃X

- X가 frequent하고, Y도 fequent하며, Y가 X를 포함하는 super-pattern Y가 존재하지 않는다면, itemset는 집합 D에서 max-pattern이라고 한다.

 

(최외각 집합들의 부분집합을 max-pattern이라고 하자.

 자기는 frequent, but 자기를 포함하는 어떤 superset도 frequent x)

 

ex)

X: {1, 2} = 60%

Y1: {1, 2, 3} = 50%

Y2: {1, 2, 4} = 50%

Y2: {1, 2, 3, 4} = 50% 인 상황에서 minsup이 50%인 pattern을 frequent patter 이라고 정의하자.

 

X가 frequent pattern이고, frequent super pattern이 존재하지 않는 경우, Y3은 max-pattern이다.

 

 

- 모든 max-pattern은 closed-pattern이다.

 

 

<Exercise>

DB = {<a1, a2, ..., a100>; <a1, a2, ..., a50>}

- min_sup = 1

 

* Closed pattern

- <a1, ..., a100>: 1

- <a1, ..., a50>: 2

 

* Max pattern

- <a1, ..., a100>: 1

 

 

 

 

- FP는 최소 지지도(threshold)에 따라 매우 민감하게 변화한다.

- minsup이 매우 낮으면, 굉장히 많은 항목집합이 생성된다.