Association Rule Mining

본 포스팅은 충남대 이종률 교수님의 강의자료를 바탕으로 작성한 글입니다.

 

이 글은, item Set들에 대한 내용이다.

우리가 다루려는 모든 데이터가 들어있는 set을 U라고 하자. Universal set을 말한다.

그럼 이 U에서 item들을 뽑을 수 있을 텐데, 그 뽑힌 애들을 I라고 할 것이다.

그 I라는 set안에 담긴 item의 개수가 k일 때, 우리는 I를 k-itemset이라고 한다.

만약 우리가 6개의 I를 만들었다면, 6 transitions의 dataset이라고 한다.

예를 들어 I = {bread, beer}라 한다면, support(I)는 6개의 transitions 중 I가 포함된 것이 몇 개인지를 의미한다.

 

association Rule R

R : I1->I2 의 형태인 규칙이다.

I1과 I2의 교집합은 공집합이다.

만약 sup(R)을 구하려고 한다면, 이는 I1과 I2를 둘 다 가지고 있는 I의 개수를 구하는 것이다.

그리고 confidence(R)을 구하려 한다면, sup(I1 + I2)/sup(I1) 의 식으로 구할 수 있다.

예를 들어, R : {beer} -> {bread} 라면, sup(R)은 beer와 bread를 포함한 I의 개수, conf(R)은 sup(R)/sup(beer)이다.

 

이걸 어떻게 사용하냐 하면, 우리는 threshold로 minsup과 minconf를 설정한다.

sup(R)과 conf(R)을 구했을 때 minsup과 minconf이상인 R들을 찾고 싶은 것이다.

그런데 우선.. 만약 item이 d개라면, itemset의 수는 2^d이고, R의 개수는 3^d-2*(d+1)+1이다.

즉, 구할 수 있는 R이 엄청나게 많다는 것이다..

이걸 다 계산하려면 엄청나게 오랜 시간이 걸린다.

그래서 Apriori라는 알고리즘을 사용할 것이다.

 

Apriori

이 알고리즘은 두 단계로 진행되는데,

Frequent itemset를 찾고, 그 Frequent한 itemset에 association rule를 생성할 것이다.

 

1. Frequent itemset 찾기

일단, sup(I1+I2)는 sup(I1), sup(I2)보다 항상 작거나 같다.

왜냐면 sup(I1+I2)는 I1, I2 모두가 있는 I의 개수를 찾는 것이기 때문!

 

그리고 만약 I2가 I1을 포함하고 있는 상태라면,

I2가 frequent하면 당연히 I1도 frequent하다.

그리고 I1이 frequent하지 않다면 어쩔 수 없이 I2도 frequent하지 않다.

I2 = {bread, beer}, I1 = {bread} 라고 생각해보면 이해가 갈 것이다.

 

그럼 이제 이런 관계성을 알았다면, 우리는 itemset들을 가지고 lattice, 격자를 만들 수 있다.

만약 n개의 item이 있다면 lattice에는 2^n-1개의 itemset들을 가지고 있다.

그리고 lattice에선, 하위에 있는 set들이 상위 set에 포함된 관계이다.

 

그럼 이걸 갑자기 왜 만들었냐, 하면은

아까 말했듯 item set들로 만들 수 있는 모든 R을 따지려면 시간이 오래 걸리기 때문에 편법(?)을 쓴 것이다.

item이 a, b, c, d가 있다고 하자.

lattice에서 하위부터 따져보면, 우선 a를 볼 것이다.

근데 위에서 말한 관계 처럼, 만약 a가 frequent하지 않다면, a를 포함한, a의 상위 관계들은 모두 non-frequent할 것이다.

그럼 그 lattice에서 a를 포함하는 8개의 set을 지워버릴 수가 있는 것이다!

 

그럼 이제 더 나아가서, 위의 방식을 일반화시켜볼 것이다.

k개의 item을 가진 set들을 생각해보자.

이를 Fk라고 할 것이다.

모든 Fk의 합집합(F1+F2+F3..)은 전체 집합과 같다.

다음의 단계를 따르면 된다.

 

1) k=1

2) Fk를 찾는데, 만약 Fk가 공집합이면 멈춘다.

2) Fk가 공집합이 아니라면 k를 1 증가시키고 다시 step 2로 간다.

 

그럼 이제 대충 틀을 알겠으니, Apriori의 단계를 하나씩 봐보겠다.

 

1. 우선, F1을 찾는다. 

여기서 말하는 F1은 item의 수가 1이면서 support값이 minsup보다 큰 set들을 말한다.

그러려면 우선 item 수가 1인 집합, C1을 찾는다. ex) {{beer}, {bread}, {butter}, {milk}}

그리고 C1 중 minsup보다 support가 큰 집합을 찾아 F1으로 명명한다. ex) {{beer}, {bread}}

 

2. 그다음 k!=1인 Fk들을 찾는다.

위처럼 Ck를 구하고 Fk를 구하면 되지만, Ck를 구하는 과정부터가 우선 너무 오래 걸릴 것이다.

그래서 이 Ck의 크기를 줄일 수 있는 방법을 생각해볼 것이다.

단, 크기는 줄어들지만, 모든 k-항목 집합은 포함해야만 한다.

 

그러려면, U의 item들에다가 임의의 순서를 부여하는 것이다.

그리고 여기서 Fk-1을 만든다고 할 때,

I1 = {a1, a2, a3, ..., ak-2, ak-1}와 I2 = {a1, a2, a3, ..., ak-2, ak} 이렇게 두 집합이 생길 수 있을 것이다.

근데 저 두 I는 a1부터 ak-2까지의 원소가 모두 겹치고, ak-1와 ak만 다른 원소이다.

그럼 여기서 겹치는 원소들, {a1, a2, ..., ak-2}를 prefix라고 할 것이다.

 

이걸 이용하면, Fk-1로 Ck를 구할 수 있다.

1) Fk-1의 항목집합을 prefix에 의해 정렬시키고, 같은 prefix를 가진 것들을 그룹으로 여길 것이다.

2) 바로 위의 I1과 I2로 예를 들면, k-2개의 원소가 동일하고 2개의 원소가 다르므로 이를 합치면 총 k개의 원소가 될 것이다.

  그럼 이건 k개의 item을 가진 set이니까 이걸 Ck에 포함시킨다.

 

그니까 우선 F1, Ck, F2는.. 위의 방법대로 구해본다.

이렇게 말이다. 

F1은 minsup을 넘는, 원소가 하나인 set의 집합,

C2는 F1을 두 개씩 모아 만든 set,

F2는 그중 minsup을 넘는, 원소가 두 개인 set의 집합.

 

그 후, 위에서 설명한 방법으로 F2를 이용해 C3를 구해본다.

자, 그럼 이렇게 진행되고, C4부턴 공집합이어서 이 알고리즘이 종료됐다.

 

여기까지 Frequent itemset을 찾는 과정이었다.

 

이제 Rule을 생성하는 과정이다.

 

2. Rule Generation

만약 k>=2인 I가 있다고 하면, I를 교집합이 없는 I1과 I2로 나누면, 합집합은 I, 교집합은 공집합이 된다.

그럼 I1->I2를 후보 연관 규칙이라고 할 수 있다.

 

이제 모든 후보 규칙의 confidence를 계산하고, conf가 minconf를 초과하는 후보규칙을 찾을 것이다.

* I1은 frequent해야한다.

 

근데.. 그러면 우리는 2^k -2개의 후보 연관 규칙의 conf를 계산해야 하는데, 그럼 엄청난 시간이 들 것이다.

그래서 이 규칙의 수를 줄이는 방법을 또 고안해낸 것이다.

 

우선 전처럼 frequent k-itemset인 I를 고정시키고, I1과 I2가 I의 부분집합이라고 할 것이다.

그리고, 또다른 I1'와 I2'도 만들 것이고, 교집합이 공집합이고 합집합이 I라는 점은 위와 같다.

 

우리는 이 R에 대한 Lemma를 하나 생각할 수 있는데, 만약 I1이 I1'에 포함돼있다면,

conf(I1->I2)<=conf(I1'->I2')이다.

왜냐면, 좌변은 sup(I)/sup(I1)이고 우변은 sup(I)/sup(I1')인데, 

I1'이 I1을 포함한, 더 큰 집합이므로 당연히 sup(I1')이 sup(I1)보다 작을 것이다.

따라서 양변의 분자는 같고, 분모는 우변이 작기 때문에, 항상 우변이 크거나 같다는 부등식이 성립하게 된다.

 

예를 들어, I = {{bread}, {beer}, {milk}}라면,

conf({beer, bread} -> {milk}) >= conf({beer} -> {milk, bread}) 이다.

 

그러면 이 R도 위처럼 lattice로 표현할 수 있다. 똑같이 윗부분의 좌변이 아랫부분의 좌변을 포함하고 있다.

근데 여기서는 위의 lattice에서와는 다르게, top-down 방향으로 진행한다.

만약 abc->d라는 R의 conf가 minconf보다 작다면, 우리는 좌변이 abc 중 어떤 것이라도 포함한 R들을 모두 삭제할 수 있다.

이렇게 된다는 말이다.

 

 

이렇게 Apriori 알고리즘을 따르면,

1. 높은 빈도수가 나오는 애들만 남긴 후,

2. 그 애들끼리의 관계인 R을 만들어, 그 중에서도 의미있는 R을 찾아낼 수 있다.