[데이터 마이닝] Pattern Mining: Basic Concepts

<Pattern 마이닝의 기본 개념>

1. 패턴이란?

- 데이터셋 안에서 빈번하게 발생하는 item들의 집합(set of items), 순서에 의미가 있는 것(subsequences), substructure 

ex) sequence의 예시: 코로나 감염 단계

- 패턴은 datasets의 본질적이고 중요한 특성을 나타낸다.

 

 

2. 패턴 발견(pattern discovery)이란?

- pattern discovery: 방대한 데이터 세트들로부터 패턴을 알아내는 것

- 사람들이 종종 무슨 물건을 세트로 많이 구매하는지?, 아이패드를 산 후에 어떤 것을 구매하는 결과가 일어나는지? (subsequence) 

에 대한 답을 할 수 있음.

 

 

3. 패턴 발견이 중요한 이유

- 본질적인 데이터 마이닝 과제에 대한 기초가 됨.

 : association(연관성), correlation(상관관계), casuality analysis(인과관계 분석) /  Mining sequential(순차적 마이닝), structural patterns(구조적 패턴) /  Classification-범죄 패턴 분석 /Cluster analysis-패턴 기반 집합 클러스터링

- 여러 어플리케이션에 쓰임.

 : 장바구니 분석, 크로스-마케팅(물건 묶어팔기), 카테고리 디자인, 웹 접속 분석 / 많은 데이터 타입: 시계열, 스트림 데이터, 시공간 데이터, 멀티미디어 데이터 등

 

 

4. 기본 개념: Trasactional Database 

- TDB(Transactional Database)

- 각 *트랜잭션은 식별자, 즉 TID와 관련되어있다.

- 각 품목의 판매된 횟수와 관련이 있을 수 있다. (예시를 들 건가..)

TID	구매한 아이템
1	Beer, Nuts, Diaper
2	Beer, Coffee, Diaper
3	Beer, Diaper, Eggs
4	Nuts, Eggs, Milk
5	Nuts, Coffee, Diaper, Eggs, Milk

 

- TBD에서 frequent item에 집중. 

- support: 집합에서 item이 얼마나 발견되는지 (빈도)

- frequent: support를 많이 받은 것

- 최소한 3개 이상의 support를 가지는 것은 frequent item set

- 우리는 frequent pattern의 집합을 찾아내는 효율적인 방법을 고안해야 함.

 

* 트랜잭션(transaction): TID로 구분되는 데이터의 집합. (각 행을 의미)

 

 

5. 기본 개념: k-Itemsets and Their Supports 

• Itemsets: 하나 혹은 그 이상 아이템의 집합 
  ex) 아이템 6개의 Itemsets: 2^6=64개 
• k-itemset: k개의 items을 포함하는 itemsets
  ex) {Beer, Nuts, Diaper}은 3-itemset
• Absolute support (count, 절대 support): sup{X}=itemset X의 발생 횟수 (동시에)
  ex) sup{Beer}=3 , sup{Diaper}=4, sup{Beer, Diaper}=3 

* minsup: support 값의 최소 기준(=threshold)

• Relative support (상대 support): s{X} = X를 포함한 트랜잭션의 부분 (각 트랜잭션이 X를 포함할 확률)
  ex) s{Beer} = 3/5 = 60%     (beer을 포함하는 트랜잭션=3, 전체 트랜잭션=5)

 

6. 기본 개념: Frequent Itemsets(=Patterns)

• minsup threshold는 frequent 판단에 하나의 기준이 된다.
• X의 itemset가 support 최솟값의 한계점(minsup threshold) 보다 더 큰 support를 가지면 --> itemset X는 frequent 하다.

ex) 5-transaction에서 minsup threshold(한계점) = 50% 

모든 frequent 1-itemsets: Beer(3/5, 60%); Nuts(3/5, 60%); Diaper(4/5, 80%); Eggs(3/5, 60%)

모든 frequent 2-itemsets: {Beer, Diaper}:3/5 (60%)

모든 frequent 3-itemsets: None

•  k에 대한 높은 빈도 집합을 이루는 것: minsup threshold가 frequent 측정의 기준이 된다.
  → frequent k-itemsets를 얻기 위한 더 효율적인 방법 고안

 

7. Frequent Itemsets에서 Association Rules까지

• itemsets을 비교할 때, Association Rules는 더 명확해진다. 

ex) Diaper --> Beer : Diaper 구매는 beer 구매를 발생시킴.

 {Beer} ∪ {Diaper} = {Beer, Diaper} ({Beer}과 {Diaper}의 합집합은 {Beer, Diaper}이다.)

 

8. Association Rule

• X->Y의 연관성의 세기를 어떻게 계산할까? 

1. support와 confidence를 계산

: X∪Y의 support  ex) s{Diper, Beer} = 3/5 = 0.6 (60%)  (5는 트랜잭션 개수에서 비롯됨, X와 Y가 일어날 확률)

: X∪Y의 confidence = sup(X, Y) / sup(X)   (X가 일어나면 Y가 일어날 확률)

  ex) c = sup{Diaper, Beer} / sup{Diaper} = 3/4 = 0.75 (Diaper 사면 Beer 살 확률 75%)

* sup: 절대 absolute support (개수로 구하기), s: 상대 relative support(확률로 구하기)

• 패턴 분석에서, 우리는 데이터베이스를 지배하는 규칙(rules)에 관심이 있다. 그리고 support와 confidence는 X,Y의 발생 빈도와 상관관계를 어느정도 보장한다. 

 

9. Frequent Itemsets와 Association Rules Mining

- Association Rule: 어떤 itemsets가 얼마나 자주 함께 발생하는지, 서로 얼마나 연관되어 있는지를 표시하는 것

, minsup, minconf 이라는 두 가지 한계점(threshold)이 있음. 

 

- Association Rule Mining:

1. 2가지 threshold인 minsup, minsconf 확인 

2. s ≥ minsup, c ≥ minsconf 인 X → Y (s,c) 인 rules(집합)를 찾기

 

ex) minsup = 50% 일때,  2.5 이상인 Absolute support 찾기 

Freq. 1-itemsets: Beer:3, Nuts: 3, Diaper: 4, Eggs: 3 

Freq. 2-itemsets: {Beer, Diaper}: 3 

 

minconf = 50% 일 때, 

Beer → Diaper (60%, 100%)  (beer,diaper 짝은 3번 나타남 3/5 =60%, beer, diaper짝 3번, beer도 3번 나타나므로 3/3=100%)

Diaper → Beer (60%, 75%) (beer, diaper 짝은 3번 나타남 3/5=60%, diaper은 4번 나타남. 3/4=75%)

- {Beer, Diaper}이 Association Rule 만족함. 

 

- 결론: mining association rules와 mining frequent patterns는 매우 가까운 문제이다 (비슷?)

          대규모 데이터셋을 마이닝하려면 확장 가능한 방법이 필요하다. ( support와 confidence를 하나하나 다 셀 수 없다.)

 

 

Challenge: 너무 많은 Frequent Pattern이 있다면 ?

• long pattern은 조합 갯수만큼의 sub-pattern을 포함한다. ex) {a1, a2, ... a10} 은 (2^10-1)개의 sub-patterns가 있음.
• (minsup=1)인 TDB1에 frequent itemsets는 얼마나 있는가?
  
  • TDB1:  T1:{a1, ... ,a50},  T2:{a1,...,a100}, minsup=1
  • 1-itemsets: {a1}:2, {a2}:2, ..., {a50}:2, {a51}: 1, ..., {a100}: 1
  • 2-itemsets: {a1, a2}: 2, ..., {a1, a50}: 2, {a1, a51}: 1, ...., {a99, a100}: 1
  • ....
  • 99-itemsets: {a1, a2, ..., a99}:1, ..., {a2, a3, ... , a100}: 1
  • 100-itemsets: {a1, a2, ...., a100}: 1
  • The total number of frequent itemsets: 2^100 - 1  (minsup=1 이므로 공집합 제외 모든 부분집합이  frequent itemsets)  계산하고 저장하기에 너무 크다.

 

 이런 challenge 같은 것을 어떻게 처리할까?..

 

전제 조건: A⊂B,  S{A} >= S{B} : A가 B의 부분집합이라면, A의 support는 B의 support보다 크다. (A가 더 frequent 하다)

B가 frequent 하다 = B의 모든 부분집합은 frequent 하다.

A가 frequent 하지 않다 = A의 모든 부분집합은 frequent 하지 않다. 

frequent 하지 않은 itemset 찾으면 그것에 대한 superset 볼 필요 없음.

1. Closed Patterns: 압축된 형태의 pattern 표현하기

• solution 1: Closed patterns
  • 패턴(itemset) X가 frequent 하고, X와 같은 support를 가진 super pattern(set, 수퍼셋)이 존재하지 않으면  X는 Closed pattern 이다.
  • = X의 support > 수퍼셋의 support 면, X는 Clossed pattern
  • 트랜잭션 DB인 TDB1: T1: {a1, ..., a50};  T2: {a1,..., a100}, minsup = 1 
  • TDB1는 Closed patterns가 얼마나 있나?
    • 2개: P1: "{a1, ..., a50}"; P2: "{a1, ..., a100}"
    • s{a1, ..., a50}:2, super set은 모두 support가 1이다.  "s{a,.... a100}:1", "s{a1,....,a51}: 1" 수퍼셋에서 본인보다 큰 support가 존재하지 않음. 따라서 closed pattern
    • s{a1, ...., a100}:1 이고 더이상 수퍼셋이 존재하지 않음. 그래서 본인이 가장 큰 서포트를 가짐. closed pattern
• Closed pattern은 frequent patterns의 무손실 압축(lossless compression)이다.
  • pattern의 갯수를 줄여주고, support 정보도 잃지 않는다.
  • "{a2, ..., a40}: 2", "{a5, a51}: 1" 처럼 모든 subsets의 support 정보를 얻을 수 있다.

 

2. Max Patterns: 압축된 형태의 pattern 표현하기

• solution 2: Max patterns
  • pattern X가 frequent하고, frequent한 수퍼셋(super pattern)이 존재하지 않으면 X는 max-pattern이다.
•  closed patterns와 차이점
  • max pattern의 서브셋(sub patterns)의 real support를 상관하지 않음. 
  • 트랜잭션 DB TDB1: T1: {a1, ..., a50}; T2: {a1, ... a100} / minsup = 1 이라고 가정
  • max pattern은 1개:  P: "{a1, ..., a100}: 1"
  • {a1, ..., a100}: 1 은 minsup=1 이므로 일단 frequent, 더이상 frequent한 수퍼셋이 존재하지 않음. (여기의 부분집합은 어쨌든 frequent할 것이라는 보장..)
  • {a1, ..., a50}: 2 인데, frequent한 수퍼셋이 더 존재 {a1, ..., a100} 같은 수퍼셋
• max-pattern은 손실 압축(lossy compression)이다! (정보를 좀 버리고 압축)
  • frequent pattern이라는 것은 알지만, real support 정보는 얻을 수 없음.
  • {a1, ..., a40}이 frequent라는 것은 안다.

 

→ Closed pattern은 단계 별로 frequent pattern을 하나씩 찾아주는 느낌이라면, Max pattern은 딱 봤을 때 최대 frequent한 pattern만을 단순하게 찾아줌. 그래서 Closed가 real support 정보를 알 수 있는 것! 

→ 많은 Application 에서 max pattern Minig보다 Closed Pattern Mining이 더 바람직하다.