[Data Mining] 2 - Frequent Itemset

연관 규칙 찾기

 

많은 transaction이 존재한다고 하자.

각 transaction에는 아이템들의 부분집합이 있을 때 연관규칙을 찾아보자.

 

Q1 : transaction들에서 빈번하게 등장하는 아이템 부분집합을 찾자

 

Support 란?

부분집합 I를 모두 포함하는 transaction의 수

또는

부분집합 I를 모두 포함하는 transaction의 비율

 

다음 표는 각 transaction에 해당하는 Item들을 나타낸 표이다.

Transaction ID	Items
1	Bread, Coke, Milk
2	Beer, Bread
3	Beer, Coke, Diaper, Milk
4	Beer, Bread, Diaper, Milk
5	Coke, Diaper, Milk

위 표에 따르면 부분집합 {Beer, Bread} 의 Support 는 2이다. (2, 4 transaction에 포함되어있음.)

 

support threshold s 는 아이템 부분집합의 빈번함 척도이다.

s이상의 support 를 갖는 부분집합은 빈번하게 등장하는 부분집합이라는 뜻이다.

 

연관 규칙(Association rules) 이란

transaction에 대해 if - then 으로 표현되는 규칙

연관규칙 {i_1, i_2, ... i_k} -> j  의 의미는 "어떤 transaction에서 아이템 부분집합 {i_1, i_2, ... i_k} 을 포함할 때 아이템 j를 포함할 가능성이 높다."이다.

 

많은 연관 규칙 중에서 significant/interesting 한 규칙을 찾아야 한다.

"포함할 가능성이 높다."에 대한 척도를 정의한 것이 confidence 이다.

 

 

confidence

confidence(I->j) = support(I U j) / support(I)

아이템 부분집합 I를 포함하는 transaction들 중에 I와 아이템 j를 모두 포함하는 transaction들의 비율

 

 

Interesting 연관 규칙

confidence 가 높은 연관 규칙이라도 interesing 하지 않을 수 있다.

 

연관 규칙 I->j 에 대한 Interest

Interest(I->j) = |conf(I->j) - Pr[j]|

confidence(I->j)에서 j에 대한 비율을 뺀 값을 의미한다.

Pr[j] = (number of transactions that contain j) / (number of transactions)

모든 transaction들 중 j를 포함하는 transaction들에 대한 비율

보통 0.5 이상의 수를 threshold로 사용.

 

Transaction ID	Basket
1	milk, coke, beer
2	milk, pepsi, juice
3	milk, beer
4	coke, juice
5	milk, pepsi, beer
6	milk, coke, beer, juice
7	coke, beer, juice
8	beer, coke

위 표에 대해 연관 규칙 {milk, beer} -> coke 가 있다고 하자.

support = 2

confidence = 2/4 = 0.5

Interest = 0.5 - 5/8 = -1/8

해당 규칙은 intereting 하지 않음을 알 수 있다.

 

 

Q2 : Support >= s 이고 Confidence >= c 인 모든 연관 규칙을 찾아라

s와 c는 사용자에 의해 주어진다.

 

빈번하게 등장하는 아이템 부분집합(frequent itemsets)을 찾는 것이 어렵다.

 

연관 규칙 찾기

 

step 1 : 모든 frequent itemset I를 찾는다.

step 2 : 연관 규칙을 만든다.

2-1 : frequent itemset I의 부분집합 A를 추출한다. (I가 frequent 하기 때문에 부분집합인 A도 frequent 하다.)

2-2 :  single pass to compute the rule confidence (confidence(A, B->C, D) = support(A, B, C, D) / support(A, B))

2-3 : 만약 A, B, C -> D의 confidence가 c보다 낮으면, A, B -> C, D의 confidence도 c보다 낮다.

support(A, B, C, D) / support(A, B, C) >= support(A, B, C, D)/support(A, B)

support(A, B, C) 가 support(A, B)보다 작거나 같기 때문.

step 3 : 연관 규칙들 중 조건을 만족하는 (Support >= s and Confidence >= c) 규칙들을 출력한다.

 

 

 

Finding Frequent Itensets

 

naive way: Frequent Itemsets 을 구하기 위해서는 모든 Itemset을 만들어서 Frequent 한지 계산해야한다.

1. transaction을 1개 읽을 때, 해당 transaction에 포함된 item 수 n만큼 읽어야 한다.

2. 이 때 부분집합 I를 2^n 개 생성해서 카운팅 해야한다.

3. 다시 1로 돌아가서 n중첩 loop를 돌아야한다.

 

dataset이 너무 커서 memory에 모두 올릴 수 없다.

결국 disk I/O 횟수가 시간에 중요하다.

disk I/O를 줄이는 것이 최선!

 

메인 메모리 병목현상

많은 frequent-itemset 알고리즘에서 메인 메모리는 critical resource이다.

frequent item pair를 찾는것이 어렵다. (frequent item pair 가 많기 때문...)

 

frequent item pair를 찾아보자.

접근 1 : matrix를 사용해 모든 pair를 센다.

접근 2 : map[(i, j)] = c 로 저장

 

접근 1은 pair 당 4byte 저장공간 필요

접근 2는 pair당 12byte 저장공간 필요하지만 count가 1이상인 pair만 저장함.

 

이 마저도 메모리에 저장할 수 없다면?

다음 글인 A-Priori algorithm에서 메모리를 줄일 수 있는 방법을 제시한다.