2. Frequent Itemset Mining & Association Rules

Market-Basket Model

items: 마켓에서 파는 물건들

baskets: 각각의 item들의 부분집합

 

association rules

: 예) 우유를 사면 콜라도 사는 경향이 있다. 

{milk} -> {coke}

 

 

Frequent Itemsets

: 빈번하게 자주 함께 나오는 item들의 집합

 

support for itemset I

: itemset I를 포함하는 basket의 수

-> threshold(임계점) s를 주어, s번 이상 등장해야 frequent itemset이라 부른다.

Confidence of association rule

: {I}-> {j}의 확률

-> 신뢰도가 높을수록 좋은 연관법칙.

conf(I->j) = I와 j를 함께 담고 있는 basket의 수 / I만 담고 있는 basket의 수

 

Interest of an association rule

: 얼마나 자주 발생하는가?를 알아볼 수 있다.

이때 Pr [j]는 j를 포함하는 basket의 비율

-> j를 포함하는 basket의 수 / 전체 basket의 

* interest 값이 보통 0.5 이상은 돼야 interesting 하다 한다.

예) 

 

 

support of an association rule

: 왼쪽과 오른쪽이 함께 나온 support 

 

{I}->{j}가 높은 support와 높은 confidence를 가진다면 

{I}와 {I,J}는 frequent 하다고 할 수 있다.

 

 

Mining Association Rules

1. frequent한 모든 itemsets 찾기

2. Rule 만들기

* 만약 a,b,c -> d가 낮은 신뢰도를 가진다면 a, b->c, d도 낮은 신뢰도를 가진다

-> 분자가 같으므로 분모가 작아야 신로도 가 커지는데 분모가 커지기 때문.

-> 아이템의 종류가 적어질 수록 support값은 당연 커짐.

예)

 

Compacting the output

rule의 개수를 줄이기 위해, 후처리 하고 output으로만

• Maximal frequent itemsets
  : 상위집합이  frequent한것만 찾는다
• Closed itemsets
  : 부모가 같거나 더 frequent하다면 부모 선택, 아니면 자식 선택

예) 

closed에서 AC와 ABC의 support가  같으므로 ABC 선

 

* pass: 처음부터 끝까지 파일을 한번 읽으면 1 pass라고 함.

* frequent pair가 가장 많고 frequent triple이 가장 적음

 

 

Finding Frequent Pairs

 

1. Naive Algorithm

1) 모든 pair의 개수 세기

• 모든 pair들을 만들어서 메모리에 하나씩 할당(4byte씩)
  -> 그 후 몇번씩 등장했는지 찾기
• 등장하지 않은 pair들도 메모리에 할당되는 issue가 발생
• 아이템수가 많아 메인메모리 크기를 초과한다면 실패
  예) 10만개의 아이템이 있다면 pair의 개수만 50만 개,
  -> 50만 * 4Byte= 20GB의 메모리가 필요하게 됨.

2) 등장하는 pair의 개수만 세기

• [i, j, c] 형태로 메모리에 할당하기
  -> [i, j, c]={i, j}가 c번 나왔다는 뜻. 
• 각 pair당 3*4byte=12byte 필요
• 실제 등장 횟수가 전체의 3분의 1 이상이라면 1번 방법에 비해 더 많은 메모리를 잡아먹게 됨

 

 

A-Priori Algorithm

• two pass접근법
  pass 1: 처음 읽을 때 각각의 item이 몇 번 나왔는지 세기
  s번 이상 등장하는 아이템(frequent items)을 찾아서 frequent list에 넣는다
  pass 2: frequent list에 있는 item이 포함된 pair들의 개수만 센다
• key idea: 만약 I아이템이 s번 등장했다면 모든 I의 부분집합은 s번 등장한다.
  -> 만약 I의  부분집합이 s번 등장하지 않았다면 I도 s번 등장하지 않는다.
  -> {b, m}, {b, c}가 frequent 하다면 {b, c, m}도 frequent 하다고 추측 가능

old item IDs: 아이템의 위치를 찾기위해 주소 표시

frequent pair을 토대로 frequent tuple 찾기(점점 확장)

* pair일 때가 가장 많은 메모리가 필요

* itemset의 크기가 커질수록 support의 크기는 작아져야 한다

-> 당연히 큰 itemset일수록 등장할 확률이 낮아질 것이므로 기준을 낮춰야 함.

 

 

 

PCY Algorithm

• A-Priori에서 1 pass때 메모리에 많은 부분이 여유롭다
  -> 이 부분을 사용해서 2 pass 때 메모리 사용을 줄일 수 있다.
  -> 빈 메모리에 맞게 많은 bucket을 가진 해쉬테이블을 추가한다.
• pair들을 해쉬함수로 각 bucket에 보관하여 각 bucket을 센다
  -> 실제 pair가 등장한 숫자가 아니라 여러 pair가 등장한 숫자들이 해쉬함수를 통해 저장됨
• bucket의 support가 threshohld를 넘었는지 확인
  -> bucket에 여러 쌍들이 들어왔는데도 threshold를 넘지 못했다면
  그 쌍들은 셀 가치도 없이 frequent 하지 않다.(각각의 support는 알 수 없음)
• 만약 bucket이 frequent pair를 가진다면, bucket의 support는 threshold를 넘었을 것.
  -> 그러나 frequent pair를 가지지 못하더라도, threshold는 넘을 수 있다.
• 2 pass: support threshold를 넘은 bucket안의 pair들만 세면 됨.
• Bitmap:bucket이 support s를 넘었다면 1로 표기, 0은 안 넘은 bucket
  -> 4byte를 bit로 표시하므로 1/32의 메모리만 필요
  
  
• 3개짜리 frequent를 찾으려면 3 pass
  4개짜리 frequent를 찾으려면 4 pass....

 

 

Frequent Itemset in <= 2 passes

• 2 pass와 같거나 적게 하려면 많은 frequent itemsets을 놓칠 것이다.

 

3가지 접근법이 있다
1. Random Sampling: 랜덤으로 샘플들을 수집

• 디스크에서 읽고 쓸 필요가 없다
  -> 크기가 작으므로 1 pass 만에 가능
• 랜덤으로 샘플을 수집하므로 원래크기보다 작다
  그러므로 support threshold를 줄여야 한다.
  만약 샘플이 전체 basket의 1/100이라면 threshold도 1/100으로
• false positive(frequent 하다고 결과가 나왔지만 사실 아님)를 피하고 싶다면 2 pass 하면 된다.
• false negative(frequent 하지 않다고 결과가 나왔지만 사실 frequent)를 피하고 싶다면
  threshold를 더 줄이면 된다. 예) s/125로
  -> 이렇게 하면 메모리를 더 필요로 한다.

 

2. SON Algorithm

: 반복적으로 조금씩 메모리에 올려서 전체 개수를 센다
-> 전체 데이터를 결국 다 메모리에 올려야 함.

 

예) 만약 s=100 이상인 아이템을 찾고 싶다면
1. 전체 아이템을 5묶음으로 나눠서 메모리에 올릴 수 있다 하면
한 묶음에서 s=20 이상 등장하는 아이템을 찾는다(1 pass)

-> 이 아이템들이 후보들이 된다.
2. s=20 이상인 아이템들만 모아서 전체 s=100 이상이 되는지 세기 (2 pass)

 

• false positive, false negative 없다.

 

3. Toivonen's Algorithm

: 1. 처음엔 랜덤 샘플로 시작, 샘플에 대한 threshold를 약간 낮춘다.

예) 샘플이 전체의 1%라면 support threshold를 s/100 대신 s/125로 낮춘다.

 

만약 {a, b}, {a, c}, {b, c}가 모두 frequent 하다고 했는데 {a, b, c}가 frequent 하지 않다고 하면 

이상하므로 {a, b, c}를 negative border에 넣는다. (1 pass)

 

2. 1 pass에서 frequent 하다고 한 후보들을 세고, negative border에 있는 것들 또한 센다.

1) 만약 negative border에 있는 걸 셌을 때 frequent 한 것이 하나도 없다면 

우린 frequent itemset을 다 찾은 것이다.

why?

Theorem: itemset S이 전체 데이터에서는 frequent 하다고 하지만, 샘플에서는 frequent 하지 않다고 하다면, negative border가 frequent 한 itemset을 적어도 하나 포함하고 있다.
-> 따라서 negative border에 하나도 없다면 전체 데이터에서 frequent 하지만

내 sample에서 frequent 하지 않는 건 있을 수 없는 일.

 

2) 만약 negative border에 있던걸 세보았더니 사실 frequent 하다고 판명
-> 다른 샘플로 다시 1 pass부터 진행해야 함(운이 나쁘면 pass 수가 늘어나게 됨.)
(운이 좋다면 sampling 방법 수준으로 짧게 걸림)