Association Analysis Basic Concepts and Algorithms

Association Analysis Basic Concepts and Algorithms

보통 비지니스에서 거래의 결과를 분석하기 위해서 많이 쓴다.

가장 성공적인 사례가, 아기 기저귀 옆에 맥주이다.

기저귀를 사고 맥주를 많이사는 연관 관계를 찾아낸 것이다.

위와 같이 거대한 데이터 셋에 숨어 있는 재미있는 관계가 존재할 수 있다.

Bioinformatics, medical diagnosis, Web Mining, 그리고 Scientific data analysis.

Earth science data의 경우 ocean, land 그리고 atmosphere processes간의 재미 있는 관계를 파악할 수 있다.

각각의 Earth system element들이 서로 어떻게 상호 작용하는지을 알아 낼 수 있기 때문이다.

비록 이겨서는 market basket data를 가지고 설명하지만, 다양한 분야에 적용할 수 있음을 염두 해야 한다.

Association analysis를 market basket data에 적용하려 할때 생기는 큰 2가지 이슈가 있다.

1) pattern을 거대한 거래 데이터로 부터 찾아내는것은 많은 컴퓨팅 파워를 필요로 한다.

2) 발결된 패턴이 거짓일 수도 있다.

따라서, 어떻게 효과적으로 마이닝을 할 것인가와

어떻게 이러한 생성한 연관 규칙을 평가해서 거짓을 찾아낼 것인가에 대한 것으로 나눠서 설명 한다.

Apriori Algorithm

---

Association Rule이라고 하면 가장 기본적으로 배우는 알고리즘이 Apriori Algorithm이다.

Association Rule은 원인과 결과의 개념이 아니다.

이것은 의미는 2개의 사전이 같이 발생할 가능성이 높다는 의미를 나타낸다.

위의 요소로 했을 때 Support와 Confidence를 계산해 보자.

X->Y 라는 규칙이 있다고 할 때

Support(s)의 경우 X와 Y가 존재하는 transaction의 수를 의미한다.

Confidence(c)의 경우 X를 포함하는 Transaction중에서 Y를 포함하는 것의 수를 의미 한다.

각각에 대해서 계산 하면 아래와 같다. 

Confidence는 당연히 생성괸 규칙의 신뢰성을 의미하므로 높을 수록 좋다고 할 수 있다.

X->Y 일때의 가능성의 1이면 가장 좋은 것이다.

그러면 Support의 의미는 무엇일까?

가량 support가 낮다면 그것은 어떠한 문제점을 내포하고 있을까?

그것은 support가 낮을 경우 confidence가 아무리 높다고해도 그것이 가지는 의미가 약할 수 밖에 없다.

가량 1만개의 Transaction에 대해서 단 10개 정도의 Transaction에서만 나오는 Confidence 1 짜리 규칙이 있다고 하자.

이러한 규칙은 일반적인 사살이라고 보기 어렵다. 왜나하면 10만개중 단 10개의 support 값만을 가지기 때문이다.

이러한 관점에서 Support는 중요하다고 할 수 있다.

Rule Mining Task

최소 support와 최소 confidence를 지원하기 위해서 그것을 데이터 셋속에서 찾아내는 것이 중요하다.

가장 기본적인 알고리즘은 Brute-force approach 이다.

하지만 이 방법은 계산 복잡도가.

이므로 실제 사용하기가 어렵다.

위 같은 예제를 Brute-force approach로 계산할 경우 602번의 계산 연산을 필요로 한다.

모든 support 값이 0.4 이다.

결국 Itemset이 같기 때문이 발생하는 문제점 이다.

따라서 support와 confidence를 decouple하여 계산하면 계산의 복잡도를 줄일 수 있다.

4개의 원소에 대한 부분집합의 갯수는 2^4으로 16개이다.

각각은 아래와 같다.

Brute force approach를 계산하는 복잡도는

O(NMw) 인데 여기서 M이 2^d므로 그 복잡도를 무시할 수가 없다.

Apriori Algorithm

Mining Association Rule은 크게 2단계로 이뤄 지며 각각에 대해서 최적화를 하는 방법을 다루겠다.

1) Frequent itemset generation

- generate all itemsets whose support >= minsup

2) Rule Generation

- Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset

1) Frequent itemset generation

원칙

만약 어떤 아이템셋이 빈번한 빈도를 가진다면 그것의 부분집합들은 반드시 빈번한 빈도를 가진다.

이 말의 의미는 당현이 ABC의 support가 50이 넘었어서 frequent itemset으로 정해졌다면,

그것의 부분집합인 AB와 BC 같은 것들의 support는 당연히 50을 넘는 다는 의미이다.

이것을 다시 정리하면 아래와 같은 수식을 얻는다.

어떤 item-set의 support 값은 절대로 그것의 subset들의 support 값을 초과할 수 없다는 의미를 가진다.

이러한 특성은 anti-monotone이라는 특성으로 잘 알려져 있다.

이러한 특성을 통해서 pruning을 할 수 있다.

만약 AB가 infrequent 하다면 그것의 subset은 모두 계산할 필요도 없다.

Algorithm

2) Candidate Generation

1단계: Candidate Generation

새료운 후보 아이템 셋 k개를 빈도 아이템 셋 k-1개에서 뽑아낸다.

2단계: Candidate Pruning

support-based pruning 전략을 사용해서 

후보 k-itemset을 제거 한다.

support 값에 기반해서 pruning은 할 수 있는데 추가로 중복값을 제거하는 것도 중요 하다.

Candidate 생성 방법

Brute force method

모든 k 아이템에 대해서 생성할수 있는 Candidate로 고려 한다.

레벨 3으로해서 즉 k=3

d가 6개라고 하면, Brute force method로 할 경우

 의 조합으로 계산을 해야 한다. 20개가 후보가 되고 아래와 같이 많은 후보군이 생성 된다.

후보군을 생성하는 것 자체는 복잡한 일이 아니지만, 그것을 pruning 하는것은 복잡한일 이다. 그래서 이방법은 좋지 않다.

F_k-1 X F_1 Method

3) Rule Generation

만약 4개의 속성이 있다면 그것에 대한 rule은 아래와 같다.

그리고 |L|의 숫자는 k이고 이것은 2^k 이다.

어떻게하면 효율적으로 rule을 frequent itemset으로 부터 생성할 수 있을까?

일반적으로 confidence는 anti-monotone한 성질이 없다.

c(ABC->D)는 c(AB->D)보다 클수도 잇고 작을 수도 있다.

하지만, 같은 itemset으로 부터 생성된 rule의 confidence는 anti-monotone한 성징을 가진다.

Confidence는 오른쪽의 아이템 숫자에 관해서 anti-monotone한 성질을 가진다.

약간 반대의 개념이 된다. support pruning일 때와

왜냐하면 support가 크다면, confidence 계산은 분모가 커지므로 값이 작아 지기 떄문이다.

위 처럼 subset이 high confidence를 가지지 않을 경우 그것의 superset은 그것보다 작은 confidence를 가지기 때문에 pruning의 대상이 된다.

앞선 support와 반대의 개념을 가지는 것을 알 수 있다.

핵심은 RHS의 super와 sub의 관계를 봐야한다는 것이다. 왼쪽이 아니라 오른쪽이다.

Apriori Algorithm의 Complexity

Choice of minimum support threshold

- lowering support threshold results in more frequent itemsets

- this may increase number of candidates and max length of frequent itemsets

Dimensionality (number of items) of the data set

- more space is needed to store support count of each item

- If number of frequent items also increases, both computation and I/O costs may also increase

Size of database

- since apriori makes multiple passes, run time of algorithm may increase with number of transactions

Average transaction width

- Transaction width increases with denser data sets

- This may increase max length of frequent itemsets and traversals of hash tree (number of subsets in a transaction increases with its width)

연습문제 (exercise)

 

min-support = 2/10 일때 Frequent itemset을 구하라.

 {e} = 8 / 10

 {b,d} = 2 / 10

 {b,d,e} = 2 / 10

계산해 본결과 subset들이 당연히 support 값이 더 높거나 같았다.

위와 같은 공식을 가지고 아래 계산을 수행해 보자.

{b,d,e} 총 6개가 생성 된다.

{b,d,e}의 support는 2/10으로 minsup를 만족하기 때문에 frequent itemset으로 고려 한다.

b,e -> d  2/5

d,e -> b 2/5

e -> b,d x  2/8  (b의 superset)

d -> b,e x  2/6  (b의 superset)

b->d,e 2/6 (e의 superset)

b,d->e  2/2

FP-growth Algorithm

Apriori algorithm을 대체하는 새로운 Algorithm 이다.

이것을 통해서도 frequent itemset을 찾을 수 있다.

이것은 FP tree라고 불리우는 것을 사용 하는 것이다.

FP tree를 생성한 다음에 divide and conquer 방법을 통해서 frequent itemset을 찾을 수 있다.

일단 item 셋들을 아래와 같이 support count가 내림차순으로 정렬 한다.

왜냐하면 맨 첫번째 아이템이 root node가 되므로 가장 빈번한 아이템 셋으로 시작하는것이 tree가 올바르게 그려지게 된다.

그렇지 않으면 root에서 너무 많은 branch들이 생성되서 tree 생성이 복잡하며 해석이 어려워 진다.

이제 각각의 Transaction을 이용해서 tree를 생성하면 아래와 같다.

생성방법

Prefix paths ending in x (특정 노드로 끝나는 트리 생성)

-> frequent itemset 을 찾아서 넣음.

해당노드와 관련없는 것들의 빈도를 줄임

해당 노드 제거

모든 관련 없는 infrequent item제거

-> 새로운 트리 생성됨

-> frquent imtemset 찾아서 넣음

이렇게 만들어진 tree를 이용해서 이제 frequent itemset을 생성 하게 된다.

바닥에서 top으로 점진적으로 올라가면서 그것을 찾게 된다.

recursive divide and conquer 방법을 이용해서 하게 된다.

de, ce, be, ae 로 끝나는 것들에 대해서만 그것을 찾게 된다.

모든 path의 node가 다 처리 될 때까지 반복 한다.

어떤 특정 경우에서는 FP-Growth algorithm이 apriori algorithm보다 성능이 수십배가 좋게 된다.

단점으로는 tree가 메모리에 모두 올라가야 하므로 압축률이 좋아야 한다. 

너무 큰 데이터 사이즈에 대해서는 수행이 쉽지 않다.

예제

minimum support count: 2

우선 e로 시작 한다.

위와 같이 생성된 tree를 가지고 e로 끝나는 포인트들을 찾으면 3개가 있다.

3/10 support를 가지므로 minsup를 만족 한다.

따라서 frequent itemset이다.

트리를 재조정 한다.

1) prefix 노드들을 e를 가지는 것들에 대해서만 고려해서 frequency count를 업데이트 한다. 

-> 그냥 단순히 트리 경로를 계산 하는것이 아니라 가지고 있는 데이터 샘플 중에서 e를 포함한 경로들을 카운트 해줘야 한다.

2) 노드 e를 제거 한다.

3) 모든 infrequent item을 제거 한다.

최종적으로 아래와 같은 모습이 된다.

e를 위한 FP-tree로 부터 prefix path가 d인것들만 다시 수집 해서 tree를 형성 한다. 

여기서 다시 계산을 해보면 d가 frequent itemset인 것을 알 수 있다.

따라서, {d,e}는 frequent itemset이 된다.

빈도수를 d를 포함하는 것들로만으로 재종함.

d를 제거함

infrequent itemset을 제거함. 그럼 c가 제거대고 아래와 같은 FP-tree가 구성됨. 

이 트리를 이용해서는 {a,d,e}를 뽑아 낼 수 있다.

이제 e->d는 모두 했으니,

다른 경로인 e->c를 수행 하자.

c를 시작으로하는 것으로 tree를 구성한다.

c는 frequent itemset이다.

따라서 {c,e}로 설정 된다.

그다음 {c,e}를 가지고 FP-tree를 구성 하게 되면

c에 의해서 발생된 것들에 대해서만 빈도수를 재조정하고

c를 제거한다음

infrequent itemset에 대해서 설정을 하면 null만 아래 처럼 남는 FP-tree가 구성 된다.

마지막으로 a를 prefix path로 고려해서 시작하면

위와 같은 tree를 구성하며 a가 frequent itemset이기 때문에

{a,e}는 frequent imtemset이 된다.

이제 suffix e에 대한 FP-tree를 이용한 Divide and conquer 방식을 모두 수행 했다.

최종적으로 찾아낸 frequent Itemset은

{e}, {d,e}, {a,d,e}, {c,e}, {a,e} 이다.

이러한 과정을 suffix 

d,c,b,a,에 대해서도 모두 수행하면 아래와 같은 표를 얻을 수 있다.