A priori Algorithm을 이용한 상관관계 분석

데이터들의 상관 관계를 분석하는데 사용하는 알고리즘 중 하나인 A priori Alogrithm에 대해 공부한 내용을 복습해보자.

정의

이 알고리즘은 빈발항목집합(Frequent Itemsets)의 연관규칙분석을 위한 알고리즘으로, 컨텐츠를 기반한 항목 추천의 기본이 되는 방법론이다.

이 알고리즘을 실행하기 위한 항목들은 탐색을 위한 Transaction Data와 최소 지지도(Minimum Support)가 있다. 최소 지지도가 필요한 이유는 최소 지지도를 기반으로 Itemsets들을 걸러내기 때문이다. 이 지지도는 전체 아이템에 대한 대략적인 탐색이 끝나고 난 뒤에 설정해줘야 정확도가 올라갈 것이다.

과정

대략적인 과정은 이러하다.

1. Minimum Support를 설정하고 Database를 스캔하면서 빈번항목집합을 찾는다. 이 때, 집합의 Support 값은 Minimum Supoort보다 커야 한다.

2. 위에서 구한 집합을 기반으로 다시 한번 빈번항목집합을 생성한다. 이 때, 생성한 후보들 중에 위에 있는 빈번항목집합에 없는 Item이 있으면, 반드시 제외한다.
   집합을 Minimum Support 기준으로 없애기 때문에 분석 초반에는 이러한 항목들이 생성될 확률이 거의 없지만, 반복 횟수가 커질수록 이런 경우가 많아지기 때문에 꼭 제외해줘야 한다.

3. 더 이상 집합이 만들어지지 않거나, 내가 원하는 횟수만큼 반복할 때까지 이 과정을 반복한다.

계산되는 지표

A priori 알고리즘에 대한 대략적인 설명은 ratsgo's blog 에서 쉬운 예를 들어서 설명해 주신다. 쉽게 말하면 마트에서 데이터들을 받았는데, 라면과 계란, 대파에 대한 구매 데이터가 있다. 그러면 라면, 라면과 계란, 라면과 대파, 라면과 계란과 대파를 같이 살 확률과 관계 이런 것들을 분석하는 것이다.

그래서 알아야 할 지표들이 5가지가 있다.

기본적으로 알아야 할 용어

• Antecedent : 조건절. '만약 ~라면'에 해당 되는 것이다.
• Consequent : 결과절. 조건절 뒷부분에 해당되는 내용이다.

조건절과 결과절은 무조건 상호배반관계(서로 겹치는 요소가 없는 것)여야 한다.

지표 해석

사용한 Apriori Alogorithm API Doucments : mlxtend

• Support(지지도) : $support(A) = P(A), range:[0,1]$
  이 지표는 Association Rule에 밀접한 관련이 있기보다는 itemset에 큰 영향을 끼치는 좌표인데, 앞서 말한 과정에서 처럼 데이터를 골라내는 작업에 가장 큰 영향을 끼친다.
  원문 : The support metric is defined for itemsets, not assocication rules.

• Confidence(신뢰도) : $confidence(A->B)=$ $P(A,B) \over P(A)$$,range[0,1]$
  A가 주어졌을 때 B가 일어날 확률.

• Lift(향상도) : $Lift(A->B) =$$P(A,B)\over P(A) P(B)$$,range[0,\infty]$
  조건절과 결과절이 서로 독립일 때, 동시에 두 사건이 발생하는 비율을 얘기한다. A,B가 독립이면 이 값은 1이다.
  여기서 말하는 조건절 결과절의 독립은 if they were statistically independent. 이 얘기다.

• Conviction : $Conviction(A->C) =$$1-support(C)\over1-confidence(A->C)$$,range[0,\infty]$
  이 값이 클수록 결과절과 조건절이 관련이 있다는 것이다. 왜냐하면 신뢰도가 커질수록 값은 무한대에 까까워지기 때문.
  Lift와 비슷하게 두 값이 독립이면 이 값도 1이다.

• leverage : $leverage(A->C) =$$support(A->C) - support(A) * support(C), range [-1,1]$
  이 값이 0이면 독립이고, 0에서 멀어질 수록 독립이지 않는 수치를 나타내는 것 같다.
  원문 : Leverage computes the difference between the observed frequency of A and C appearing together and the frequency that would be expected if A and C were independent. An leverage value of 0 indicates independence.

분석 예제

mlxtend references에서 친절하기 예제까지 주었다. 예제를 보면서 지표를 해석해보자.

import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori, fpmax, fpgrowth


dataset = [['Milk', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Dill', 'Onion', 'Nutmeg', 'Kidney Beans', 'Eggs', 'Yogurt'],
           ['Milk', 'Apple', 'Kidney Beans', 'Eggs'],
           ['Milk', 'Unicorn', 'Corn', 'Kidney Beans', 'Yogurt'],
           ['Corn', 'Onion', 'Onion', 'Kidney Beans', 'Ice cream', 'Eggs']]

te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

frequent_itemsets = fpgrowth(df, min_support=0.6, use_colnames=True)
### alternatively:
#frequent_itemsets = apriori(df, min_support=0.6, use_colnames=True)
#frequent_itemsets = fpmax(df, min_support=0.6, use_colnames=True)

frequent_itemsets

Dataset이 저렇게 생겼다고 가정을하고, 빈번항목집합을 만드는데에는 F/P Growth 알고리즘을 사용하든, Apriori 알고리즘을 사용하든 상관이 없기 때문에, 크게 중요하지 않다.
아무튼 min_support=0.6으로 한 데이터셋들은

	support	itemsets
0	1	frozenset({'Kidney Beans'})
1	0.8	frozenset({'Eggs'})
2	0.6	frozenset({'Yogurt'})
3	0.6	frozenset({'Onion'})
4	0.6	frozenset({'Milk'})
5	0.8	frozenset({'Kidney Beans', 'Eggs'})
6	0.6	frozenset({'Kidney Beans', 'Yogurt'})
7	0.6	frozenset({'Eggs', 'Onion'})
8	0.6	frozenset({'Kidney Beans', 'Onion'})
9	0.6	frozenset({'Kidney Beans', 'Eggs', 'Onion'})
10	0.6	frozenset({'Milk', 'Kidney Beans'})

이렇게 생겼다. 데이터들은 frozenset으로 선언되어있는데, 아마도 중복 항목을 없애고 데이터의 수정을 불가하게 만들기 위해 이렇게 설정한 것 같다.

이 데이터셋들에 Association Rule을 적용해보면,

	antecedents	consequents	antecedent support	consequent support	support	confidence	lift	leverage	conviction
0	frozenset({'Kidney Beans'})	frozenset({'Eggs'})	1	0.8	0.8	0.8	1	0	1
1	frozenset({'Eggs'})	frozenset({'Kidney Beans'})	0.8	1	0.8	1	1	0	inf
2	frozenset({'Yogurt'})	frozenset({'Kidney Beans'})	0.6	1	0.6	1	1	0	inf
3	frozenset({'Eggs'})	frozenset({'Onion'})	0.8	0.6	0.6	0.75	1.25	0.12	1.6
4	frozenset({'Onion'})	frozenset({'Eggs'})	0.6	0.8	0.6	1	1.25	0.12	inf
5	frozenset({'Onion'})	frozenset({'Kidney Beans'})	0.6	1	0.6	1	1	0	inf
6	frozenset({'Kidney Beans', 'Eggs'})	frozenset({'Onion'})	0.8	0.6	0.6	0.75	1.25	0.12	1.6
7	frozenset({'Kidney Beans', 'Onion'})	frozenset({'Eggs'})	0.6	0.8	0.6	1	1.25	0.12	inf
8	frozenset({'Eggs', 'Onion'})	frozenset({'Kidney Beans'})	0.6	1	0.6	1	1	0	inf
9	frozenset({'Eggs'})	frozenset({'Kidney Beans', 'Onion'})	0.8	0.6	0.6	0.75	1.25	0.12	1.6
10	frozenset({'Onion'})	frozenset({'Kidney Beans', 'Eggs'})	0.6	0.8	0.6	1	1.25	0.12	inf
11	frozenset({'Milk'})	frozenset({'Kidney Beans'})	0.6	1	0.6	1	1	0	inf

이렇게 나온다.
여기서 보니까 confidence가 1이면 A,B가 독립이어도 conviction이 무조건 inf가 나오는 것을 알 수 있다.

아직까지도 눈에 완전히 확 익지는 않지만, 그래도 어느정도 보이기 시작은 한다.