[Data Science] Frequent Pattern Mining - Association and Correlations

Mining Max pattern & Closed pattern

• Frequent itemset을 찾는 것뿐만 아니라 max pattern과 closed pattern도 찾는 것이 중요 정보를 얻는 과정에 속할 수 있다.
• Max pattern과 closed pattern에 대해서는 이전 게시글 참조.

2024.03.28 - [Data Science] - [Data Science] Frequent Pattern Mining

[Data Science] Frequent Pattern Mining

MaxMiner: Mining Max Patterns

• MaxMiner는 기본적으로 Apriori 알고리즘을 사용한다.
  • '모든' frequent pattern을 탐색하지 않으며 max pattern만 탐색한다. (frequent pattern의 일부는 탐색)
  • 그래도 naive한 접근법은 여전히 비효율적이다.. 

Algorithm

• 트랜잭션이 다음과 같고, minimum support가 1이라고 할 때

Transaction ID	Items
1	{A, B, D, E}
2	{B, C, E}
3	{A, B, E}
4	{A, C, E}
5	{B, E}

1. 첫 번째 스캔: frequent item(길이 1)을 찾아 정렬한다. (오름차순)
   • Frequent item = A:3, B:4, C:2, D:1, E:5
   • Ascending order → D, C, A, B, E
2. 두 번째 스캔: potential max pattern을 가진 2-itemset의 support를 찾는다.
   • Potential max pattern: candidate itemset에서 max pattern의 가능성이 있는 최대 크기의 frequent itemset.
   • RED: Category of candidates
   • GREEN: Potential max patterns for each category of candidates
   • DC, DA, DB, DE, DCABE
   • CA, CB, CE, CABE
   • AB, AE, ABE
   • BE
3. Candidates reducing
   • 만약 ABCD가 max pattern이라면 ABC, ABD, BCD에 대해서 support를 확인할 필요가 없다. Max pattern이 아니라면 확인해야한다... ABC가 max pattern이라면 AB, BC, AC의 support를 확인할 필요가 없다.

• 즉, DFS처럼 동작
• 위의 예시를 명확하게 들지 못한 것 같아 다른 예시를...

Set-enumeration Tree

• Frequent item이 A, B, C, D가 있으며 순서 또한 오름차순으로 정렬되어 있다고 가정하자.
• 이때, 4개의 item에 대해 set-enumeration tree를 생성한다면 다음과 같다.

Set-enumeration Tree

• 위 tree에서 ABCD가 max pattern이면 하위 노드에 대해서 max pattern인지 확인하는 과정을 거치지 않아도 된다. 마찬가지로 BCD가 max pattern이라면 하위 노드인 BC, BD에 대해서 max pattern인지 확인하는 과정을 거치지 않아도 된다. 

CLOSET: Mining Closed Patterns

• CLOSET은 FP-growth 실행 중에 closed pattern을 확인할 수 있다.
• FP-growth에 대해서는 이전 게시글 참조.

2024.04.01 - [Data Science] - [Data Science ] Frequent Pattern Mining - FP-Growth

[Data Science ] Frequent Pattern Mining - FP-Growth

• CLOSET을 요약하면 다음과 같다.
  • A를 가지고 있는 모든 트랜잭션이 B를 가지고 있으면 AB는 frequent closed pattern이다.
• 예를 들어, conditional pattern base 표가 다음과 같고 minimum support=3이라 했을 때,

Item	Conditional Pattern base	Frequent
A	{  }	4
B	A:3	4
C	AB:3	3
D	ABC:1, A:1, B:1	3
E	ABC:2, ABCD:1	3
F	ABCE:2, BD:1	3

• E-conditional pattern base의 FP-tree는 다음과 같다.

E-conditional FP-tree

• 여기서 E의 frequent는 3이고 ABC의 수도 3으로 frequent 하면서 동일하므로 ABCE는 closed pattern이라 할 수 있다.
• F의 경우 F만 closed pattern이 된다.
• D의 경우 D만 closed pattern이 된다.
• C의 경우 ABC가 closed pattern이 된다.
• B의 경우 B와 AB가 closed pattern이 된다. B는 frequency가 4이며, AB의 경우 3이기 때문에 frequency가 달라 둘 다 closed pattern이라고 할 수 있다.
• A의 경우 A가 closed patten이 된다.
• 즉, 모든 closed pattern은 {A:4, B:4, D:3, F:3, ABC:3, ABCE:3}이다.
  • 여기서 ABC는 AB의 super-pattern이므로 {A:4, B:4, D:3, F:3, AB:3, ABC:3, ABCE:3}에서 AB를 제외한다.

CHARM: Mining by Exploring Vertical Data Format

• 트랜잭션에 따라 itemset을 스캔하려니 비용이 많이든다.
  → Item에 대해 스캔하자..!
• 트랜잭션이 다음과 같다고 하자.

  Transaction ID	Items
  1	{A, B, D, E}
  2	{B, C, E}
  3	{A, B, E}
  4	{A, C, E}
  5	{B, E}

• 이를 vertical format으로 바꾼다면 다음과 같이 바꿀 수 있다.
  • t(A) = {T1, T3, T4}
  • t(B) = {T1, T2, T3, T5}
  • t(C) = {T2, T4}
  • t(D) = {T1}
  • t(E) = {T1, T2, T3, T4, T5}

Algorithm

• CHARM을 이용하여 frequent itemset 구하기

1. 전체 DB를 한 번 스캔하여 vertical format으로 변환한다. (Item의 수가 트랜잭션의 수보다 훨씬 적다.)
2. k=1(Itemset의 길이)부터 시작해서 k+1 크기의 frequent itemset을 찾아나간다. (Intersection operation, Apriori property를 사용한다.)
3. Frequent itemset이 나오지 않을 때까지 반복한다.

Association Rules

• 다량의 데이터 사이에서 항목 간의 관계 정리

Multi-level association rule

• 특정 항목이 추상화 수준에서 분류(hierarchy 존재)될 수 있을 때 사용되는 규칙이다. 예를 들어, '과일'이라는 추상적인 카테고리에서 '사과', '바나나'와 같은 구체적인 항목이 존재할 수 있다.
• Flexible minimum support setting이 필요하다.
  • Lower level에 있는 항목들은 lower support를 가진다.
  • Lower level의 항목과 high level의 항목이 frequent pattern에 포함될 확률을 최대한 유사하게 만든다.
  • 과일이라는 상위 항목의 minimum support를 5%로 설정한다면, 사과나 바나나와 같은 하위 항목의 minimum support는 3%로 설정할 수 있다. 상위 항목과 동일하게 설정한다면 uniform setting이라고 한다. Uniform setting의 경우 minimum support의 차등을 두지않아 unfair하므로 association rule을 제대로 확인하지 못할 가능성이 있다.
•  Redundancy Filtering
  • 일부 규칙이 ancestor로 인해 중복될 수 있다.
  • 예를 들어, 과일 → 오렌지 주스 (support = 8%, confidence = 70%)인데, 사과 → 오렌지 주스 (support= 2%, confidence = 72%)와 같이 첫 번째 규칙이 두 번째 규칙의 ancestor인 경우가 존재할 수 있다.
  •  Confidence에 의한 필터링: descendent rule의 confidence가 ancestor rule의 confidence와 비슷한 경우 중복으러 처리하여 필터링한다. 위의 예시에서 두 rule의 support가 비슷하므로 (arbitrary) 중복으로 볼 수 있다.
  • Expected value에 의한 필터링: ancestor rule의 support value에 대해 descendent rule의 support가 expected value에 가까우면 중복으로 처리하여 필터링한다.
    - Expected value = Expected Support(X ∪ Y) = Support(X) * Support(Y)

Multi-dimensional association rule

• 항목 간 뿐만 아니라 다양한 속성(시간, 장소 등)을 포함하는 규칙이다. 예를 들어, "주말에 런던에서 판매된 우유는 빵과 함께 구매될 가능성이 높다."와 같은 규칙이 해당한다.
• Single-dimensional rules: buys(X, “milk”) → buys(X, “bread”): milk → bread
• Multi-dimensional rules: >= 2 dimensions
  • Inter-dimension association rules (no repeated dimensions)
    age(X,”19-25”) ∧ occupation(X, “student”) → buys(X, “coke”)
  • Hybrid-dimension association rules (repeated dimensions)
    age(X,”19-25”) ∧ buys(X, “popcorn”) → buys(X, “coke”)

Quantitative association rule

• 숫자로 표현되는 데이터 속성이 포함된 규칙이다. 예를 들어, "매출이 100만 달러를 초과하는 매장에서는 고가의 와인이 치즈와 함께 자주 판매된다."와 같은 규칙이 해당한다. 일반적으로 discretization이 필요하다.
• Skeleton of association rules
  A_quan1 ∧ A_quan2 → A_cat
• 필요한 경우, 인접한 연관 규칙을 군집화하여 일반적인 규칙으로 만들 수 있다.(If needed, we cluster adjacent association rules to form general rules.)
• age(X,”34-35”) ∧ income(X,”30-50K”) → buys( X,”high resolution TV”)

Interesting correlation patterns

• 데이터 세트 내에서 변수 간의 상관 관계를 탐사하여 유의미한 패턴을 찾아내는 것에 중점을 둔다. 예를 들어, "저녁 시간에 피트니스 앱 사용이 증가하면, 음악 스트리밍 서비스 사용도 증가한다."와 같은 패턴이 해당된다.
• 유의미한 패턴(interestingness)을 찾아내기 위해 lift라는 것을 사용한다.
• Lift(A→B) = P(A and B)/P(A)*P(B)
  • Lift > 1: A와 B가 함께 발생할 확률이 독립적일 때 예상되는 것보다 높음을 의미하며, 두 항목 간에 양의 관계가 있다고 볼 수 있다.
  • Lift == 1: A와 B가 서로 독립적임을 의미한다.
  • Lift < 1: A와 B가 함께 발생할 확률이 독립적일 때 예상되는 것보다 낮음을 의미하며, 두 항목 간에 음의 관계가 있다고 볼 수 있다.
• Lift의 계산을 통해 특정 association rule이 우연에 의한 것인지, 아니면 통계적으로 유의미한 패턴을 나타내는 것인지 판단하는데 기준이 될 수 있다.