연관분석
Association Rule Analysis, Association Rule Mining. 흔히 장바구니 분석, 서열 분석이라고도 부른다. 이것은 연속된 거래 속에서의 규칙을 발견하기 위해 적용한다. 유명한 사례로 기저귀를 사는 진열대 근처에 맥주를 비치하며 맥주에 대한 매출을 크게 늘린 마트가 있는데, 아버지들이 기저귀를 사면서 보이는 김에 맥주를 사는 그 연관성을 잘 파악한 것이다.
보다 정확하게 정의를 내리자면 주어진 거래(transaction) 데이터에 대해, 하나의 상품이 등장할 때 다른 상품이 같이 등장하는 규칙을 찾는 것이라고 할 수 있다.
위에서는 맥주와 기저귀가 연관되는 인과를 내가 제시했지만, 연관 규칙은 이런 인과관계가 아니라 상관성과 규칙을 찾는 것에 목적을 두고 있기에 엄밀하게는 구분해서 이해할 필요가 있다.
정의
- 규칙: IF (condition) THEN (result)
어떤 조건이 있을 때 결과가 일어난다. 기저귀를 살 때 맥주도 산다. - 연관 규칙: IF (antecedent) THEN (consequent)
특정 사건에 맞춰 빈번하게 발생하는 규칙을 말한다. 기저귀를 살 때 맥주도 산다는 규칙이 자주 일어난다면, 연관규칙. 즉 상관성이 있을 법한 규칙이라는 것! 빈번함은 우리가 우리가 정해주는 요소라 할 수 있다.
이때 antecedent와 consequent에 해당하는 상품들의 집합을 아이템셋itemset이라고 부른다. 그리고 이러한 아이템셋은 서로소를 만족하도록 하는 것이 기본적인 룰이다.
- support count($\sigma$) : 전체 거래 데이터 중 아이템셋이 등장하는 횟수. 이를 통해 support를 정한다.
- support : 아이템셋이 전체 거래 데이터에서 등장하는 비율. 위의 support count를 전체 거래 데이터 수로 나눈다.
- frequent itemset.(빈발 집합) : 이거 말하려고 위의 개념들이 나오는 것. 우리가 지정한 최소한의 count를 넘기는 아이템셋들을 말한다.
척도
이제 우리는 이러한 빈발 집합들 사이에서 연관 규칙을 만들기 위한 척도를 알아볼 필요가 있다.
- support: 지지도. 방금 위에서 본 것! 규칙으로서는 X,Y를 둘 다 포함하는 거래의 비율이 될 것이다. X 하나에 대해서도 support를 구할 수 있다. 수식을 보면 $n(X \cup Y)$라고 써져 있는데 참 애매한 표현이다. 엄밀하게는 오히려 교집합 꼴로 표현하는 게 정의 상 맞는 것 같지만, n 자체가 무엇인지 정의되지 않았으므로 그런갑다 하고 넘어가자.
- confidence: 신뢰도. X가 포함된 거래 중 Y도 포함하는 거래의 비율. 달리 말해 조건부 확률이다. 이 값이 높다는 것은 그만큼 유용한 규칙이라는 뜻이다.
- lift: confidence에 Y가 등장할 확률을 나눠주는 값. 위의 것들은 확률로 표현이 되지만 이 값은 확률끼리의 나눗셈을 하기 때문에 정확히 말하자면 확률이 아니다. 이 값이 1이라면? X를 고려해도 Y의 확률에 변동이 없었다는 뜻이니까 둘은 서로 독립이 된다. 만약 1보다 높다면 양의 상관관계일 것이고, 아니라면 음의 상관관계일 것이다.
수식이 참 이상해보이지만.. 각 척도가 이런 관계를 가진다는 맥락에서 이해하자.
빵이 있을 때 계란도 있는 연관 규칙의 support 척도는 $\frac{2}{5}$이고, confidence는 조건부확률! 즉 $\frac{2}{3}$이다. 그리고 lift는 그것을 계란만의 확률로 나누는 것이니 $\frac{2}{3}\div \frac{2}{5} = \frac{5}{3}$이다. lift가 1 이상이니 양의 상관관계를 가진다고 볼 수 있겠다.
척도는 세 가지가 있지만, 방금 위에서의 사례만 봐도 대충 감을 잡을 수 있듯이 질적인 면에서 lift가 강점을 가진다.
그럼 support니 confidence니 어디에 쓰는가? 위의 사례는 아이템 수가 굉장히 적지만, 아이템의 수가 많다면, 그것들의 조합으로 이뤄지는 규칙의 수는 기하급수적으로 많아진다. 그렇기에 적절하게 유의미한 연관 규칙만을 거르고 찾아낼 필요가 있는데, 이때 도움이 되는 것이 바로 support와 confidence다. 최소한의 s, c를 만족하는 규칙들을 찾아내고, 그에 맞춰 아이템셋을 거른다. 그리고 그렇게 걸러낸 아이템셋 속에서 lift를 척도로 하여 의미있는 연관 규칙을 고르면 된다.
탐색
사실 방금 넌지시 언급했지만 연관 규칙에서 가장 어려운 것은 주어진 거래 데이터에서 적절한 규칙들을 뽑아내는 것이다. 가능한 조합들을 고려하는 과정은 아무래도 가장 오랜 시간을 요구하는 일이기 때문이다.
이를 위해 가장 간단한 해결방법은? 브루트포스 접근법이다. 진짜 무식하게 완전 탐색하기.
여기에서 모든 support의 수를 계산해보자. 일단 모든 거래 수 N개. 그리고 그 속의 아이템 수 W개(각 거래 속 아이템 말고, pandas로 치자면 nunique()). 그리고 각 거래 별로의 모든 아이템셋의 조합 M. 이 M은 정말 말 그대로 가능한 모든 조합을 고려하는 거라 $2^d$개가 된다(d는 각 거래 별 아이템 수). 이걸 다 곱하면 support 수만 NWM이게 된다.
그리고 한 거래 속에 아이템이 10개만 된다고 생각해봐도 M은 1024가 된다..
그래서 최소 support와 confidence를 넘는 값들만을 고려하는 것이다.
최소 support 이상의 모든 아이템셋을 생성하고, 그 후에 최소 confidence를 만족하는 것들로만 연관 규칙을 생성한다.
여기에서 많은 데이터를 접하게 되는 support 고려 과정이 가장 시간이 오래 걸리기에 이 부분을 잘 처리할 필요가 있다.
그리고 이를 처리하는 방법으로 Apriori 알고리즘, DHP, FP-Growth 알고리즘이 있다.
강의에서는 이를 제대로 다뤄주지 않는데 간략하게만 보자.
- Apriori 알고리즘.
예시로 보자.
가령 내가 지금 아이템셋 A={기저귀, 맥주}을 고려하고 있다고 쳐보자. 이 놈의 support는 어떻게 해도 단일 원소를 가진 집합인 {기저귀}나 {맥주}의 support보다는 작거나 같을 수밖에 없다. 당연하지? 분모는 N으로 똑같은데 제한사항이 늘어나는 꼴이니까.
즉, 만약에 {기저귀}의 support이 최소치를 만족하지 못한다면 A는 고려할 필요도 없이 최소 support를 넘지 못하므로 거르면 된다는 것.
이렇게 구현하면 된다고 하네. 이게 apriori의 첫번째고, confidence에 대해서도 있다.
대충 이런 건데, 이것은 식으로 세워보면 또 직관적이다. 위의 식을 그대로 옮겨보자면,
$\Large \frac{P(A \cap B \cap C \cap D)}{P(A \cap B \cap C)} \geq \frac{P(A \cap B \cap C \cap D)}{P(A \cap B)} \geq \frac{P(A \cap B \cap C \cap D)}{P(A)}$
이런 모양이 나온다. 분모의 값은 당연히 왼쪽이 더 작다. 그러니 왼쪽으로 갈수록 더 크거나 같을 수밖에 없다. 이 뜻은 또 뭐냐? 그 밑으로는 confidence가 다 시원찮으니 버리면 된다는 거!
- Direct Hashing and Pruning(DHP)
각 거래 데이터에서 만들 수 있는 원소 2개의 부분집합을 전부 만든다. 그리고 해시 테이블을 만들어서 부분집합을 다 넣어간다. 그러면 각 부분집합의 수가 각각 파악이 되는데 이때 최소 support가 넘는 것들로 새롭게 집합을 구성한다. 그리고 그것들로 support를 구하는 방식. 아닌 것들은 다 거르고 시작하는 것이다.
- FP-Growth
빈도에 따라 트리를 만들어 support를 구하는 방법. 이렇게 트리를 만들면 쉽게 support를 구할 수 있어 최소를 넘는 것만 골라내기도 쉬워진다.
'인공지능 in 네부캠 AI 4기 > 추천시스템' 카테고리의 다른 글
| 모델 기반 협업 필터링 (0) | 2022.10.23 |
|---|---|
| 협업 필터링 개요 (0) | 2022.10.19 |
| 컨텐츠 기반 추천 (0) | 2022.10.18 |
| 인기도 기반 추천 (0) | 2022.10.11 |
| 추천 시스템 Basic (0) | 2022.10.11 |