연관 분석 추천

연관 규칙 분석 (Association Rule Analysis, Association Rule Mining)

 

 

예를 들면 우유, 빵이 등장했을 때 계란과 콜라가 등장하면 연관 관계를 표기한다. 

다만, 해당 연관관계가 인과관계를 의미하지는 않는다. 

연관 규칙은 다음과 같다. 

IF (antecedent) $\rightarrow$ THEN (consequent)

특정 사건이 발생시 빈번하게 발생하는 또다른 사건 규칙 

 

itemset: antecedent와 consequent 각각을 구성하는 상품들의 집합

위 사진을 참고하면 꼭 itemset이 {antecedent, consequent} 이러한 형태로 될 것 같지만 오해하지말자. 

antecedent와 consequent에 등장한 모든 상품들을 모아놓은 집합이다. 

 

antecedent와 consequent의 각 원소는 서로 겹치지 않는다. 

support count: 전체 내역에서 특정 itemset 등장 횟수 

support: support count의 비율 

frequent itemset: 유저 지정 threshold 를 넘는 itemset 

 

support는 위 언급처럼 단일 itemset에 대해서 등장 비율을 찾을 수도 있지만, X $\rightarrow$ Y 즉, 연관관계가 있는 두 데이터셋을 포함하는 비율을 찾을 때도 사용된다. 

Confidence 는 조건부 확률이다. 사진에 나타난 설명이 좀 부실하기도 하고 했갈리는데, 전체 데이터가 아니라 X 집합 중에서 Y 집합을 포함하는 X 집합의 비율이다. 즉 X 가 등장했을 때 Y가 등장할 확률이다.

lift는 [X가 등장했을 때 Y가 등장할 확률] / [Y가 등장할 확률] 즉 조건부 확률을 Y가 등장할 확률로 나눈 것이다. 

lift 결과값으로 독립, 양의 상관 관계, 음의 상관 관계를 알 수 있다. 

즉 X가 등장했을 때 Y 의 등장 동향을 살필 수 있다. 

 

 

예시를 통해 살펴보자. 

근데 수식적으로 lift = 1이면 X, Y가 독립이라고는 하지만 

P(Y|X)/ P(Y) 애초에 P(Y|X) 가 X 가 등장할 때의 Y가 등장할 확률이다. 따라서 X 가 등장하지 않았을 때도 고려한 Y 의 등장 확률이 분모로 왔을 때 결과값이 1 이 되려면 sample의 크기가 굉장히 커야할 것으로 보인다. (혹시 이와 관련해서 아시는 내용이 있으시면 알려주시면 감사하겠습니다.)

 

하지만 수식을 풀어서 보면 P(X 교집합 Y) / ( P(X) P(Y) ) 가 되어 의미가 직관적으로 다가온다. 각각 독립적으로 등장할 확률분의 X와 Y가 같이 등장한 확률을 보면 독립 여부를 알 수 있다.  

 

이렇게 알게 된 

Support, Confidence, Iift 을 어디에 사용하는지 살펴보자. 

 

item 개수가 많아서 데이터를 보기 어려울 때, 위 방법을 사용한다. 

 

최종 추천을 제공하기 위한 척도는 lift 이다. 

이는 lift를 사용했을 때 질적으로 만족스러운 추천 결과를 얻을 수 있기 때문이다. 

예를 들어보자. 

와인, 오프너, 생수를 산다고 하자. 

조건부 확률만 살펴보았을 때, 오프너를 사는 경우는 빈번하지 않기 때문에 오히려 와인과 물을 같이 살 확률이 더 높다. 

그러나 물을 살 경우, 오프너를 살 경우를 각각 고려하고 이를 통해 리프트를 구하면 

l(Y $\rightarrow$ X) : 10 

l(Z $\rightarrow$ X) : 1

로 와인과 오프너의 상관관계가 훨씬 높다는 것을 알 수 있다. 

 

이를 통해 와인을 샀을 때 추천 품목을 '물' 이 아닌 '오프너' 를 제안할 수 있다. 

 

 

주어진 transaction 에서 모든 연관 규칙을 찾아내야 한다. 

가장 간단한 방법은 Brute-force 로 다 해보는 것이다. 

하지만 당연히 위 과정은 너무 많은 계산량이 요구된다. 

M은 아이템 셋의 가능한 개수이다. 아이템 개수가 10개만 되어도 M = $2^d$ 이므로 1024 개 가량이 된다. 

이에 따라서도 감당이 안되는데 모든 연관 규칙의 개수는 한술 더 떠 $3^d$ 이다. 

1 번과정이 방금 brute force로 살펴봤듯이 오래걸린다. 이에 따라 이 부분을 효율적으로 하는 알고리즘은 다음등이 있다. 

각각의 알고리즘이 복잡하므로 Apriori 알고리즘만 살펴보자. 

 

해당 글이 내가 정리 할 수 있는 것보다 더 잘 정리한 듯 하여 링크를 첨부한다. 

https://ordo.tistory.com/89

[Python] Apriori algorithm:: 연관규칙분석 (1)

https://ordo.tistory.com/93?category=751589 

[Python] Apriori algorithm:; 연관규칙분석 (2)

해당 블로그에는 Apriori algorithm 을 직접 구현한 예시도 있으니, 추후 살펴보자.