1강 - 추천시스템의 이해 (연관분석, Apriori, FP-Growth)

추천시스템의 개요

1) 추천시스템이란? (feat. 정의, 중요성, 목표)

2) 기업에서의 추천시스템

• 당근마켓 ‘이 상품과 함께 봤어요’를 통해 한 상품을 본 다른 사용자들이 어떤 상품을 함께 보았는지 나타내 준다.

• 카카오(브런치) 해당 글과 유사한 글을 모델을 통해 비교하며 관련된 글을 추천해 준다.

• 유튜브 스케일이 크다 보니 굉장히 많은 영상들을 딥러닝 모델을 통해 추천하는데, 특히 최근에는 대부분의 영상이 추천으로 인한 클릭수로 추정된다고 한다.

3) 파레토와 롱테일의 법칙

• 파레토의 법칙 상위 20%가 전체의 80% 가치를 창출한다는 법칙으로, 완두콩 예시로부터 출발하였다. 상위 20%의 완두콩에서 전체 80%의 완두콩이 발화되었다는 내용의 예시를 통해 전개되으며, 현재까지도 기업 경영에 필요한 법칙이다. 기업에서는 주로 매출의 80%는 20%의 핵심 고객 및 주력 상품에서 나오므로 그 핵심 고객 20%를 찾아내 그들에게 역량을 집중할 필요가 있다는 의미로 활용된다.

• 롱테일의 법칙 하위 80%의 가치가 상위 20%의 가치보다 크다는 의미로, 앞에 나온 파레토의 법칙과 정반대인 법칙이다. 즉, 파레토의 법칙에서 소외된 80%의 고객에게서도 상당한 영업기회가 존재한다는 의미이다. 최근 발달한 인터넷은 파레토의 법칙이 적용되는 오프라인과 상황이 다르기에 이러한 법칙이 적용될 수 있었다. 특히 아마존이나 넷플릭스 등에서 잘 활용된 롱테일의 법칙은, 오프라인보다 온라인에서 적용하기 쉬우며 아마존이 오프라인 서점에서 잘 팔리지 않던 책을 온라인 추천을 통해 많이 판매하게 되었다는 것을 일례로 들 수 있다.

4) 추천시스템의 역사

• 2005 ~ 2010년
과거에는 Apriori 연관상품추천 알고리즘으로 출발하였다. Apriori 연관상품추천 알고리즘은 소비자가 같이 구매하는 상품을 추천하는 방식으로, 이를 통해 사람들이 추천시스템을 마케팅에서 어떻게 적용할지에 대해서 고민하는 계기가 되었다고 한다.

• 2010 ~ 2015년 2006 ~ 2009년에 넷플릭스에서 어떤 식으로 컨텐츠를 추천할 수 있을지 이에 대한 모델을 개발하는 대회가 열렸는데, 이때 우승자의 알고리즘이 바로 SVD를 활용하는 협업 필터링 모델이다.

• 2013 ~ 2017년
2013년부터 많은 사람들이 데이터의 중요성을 인식하기 시작했고, DataBase에 데이터를 축적함으로써 데이터가 점점 빅데이터로 변화해 갔다. 이전에 있던 모델들로는 빅데이터를 다루기 어려웠기에 이런 빅데이터들을 어떻게 다룰지에 대한 연구가 활발하게 진행되었으며, 이때 나온 것이 Spark를 이용한 빅데이터 모델이다.

• 2015 ~ 2017년
현재는 딥러닝의 발달에 힘입어 협업 필터링을 딥러닝으로 어떻게 소화할지, 대규모의 데이터 속에서 어떻게 딥러닝을 잘 활용해서 추천할지에 대한 연구가 활발히 진행되고 있다.

• 2017년 ~
2017년 이후로는 강화학습이나 Factorization Machine과 같은 머신러닝 알고리즘, Hierarchical RNN 등으로 초개인화 추천시스템에 대한 연구가 진행되고 있다.

연관분석 (Association Analysis)

1) 연관분석이란? (feat. 정의, 예시)

2) 규칙평가지표

1. 지지도 support
A 상품을 구매했을 때, 이것이 B 상품의 구매로 이어지는 것을 의미하며, 조건절 A에 따라 B가 이어지는 현상을 의미한다.
For the rule A → B, support(A) = P(A)

2. 신뢰도 confidence
A 상품을 구매했을 때, 이것이 B 상품의 구매로 이어지는 확률 지표를 의미한다.

1. 향상도 lift
두 사건이 동시에 얼마나 발생하는지에 관한 비율에 따른 독립성을 측정하는 지표이다.

3) 규칙 생성

4) 연관분석의 문제점

Apriori 알고리즘

• item set의 증가를 줄이기 위한 방법

• “빈번하지 않은 item set은 하위 item set 또한 빈번하지 않다”라는 아이디어에서 출발한 알고리즘

1. k개의 item을 가지고 단일항목집단 생성(one-item frequent set)

2. 단일항목집단에서 최소 지지도(support) 이상의 항목만 선택

3. 2에서 선택된 항목만을 대상으로 2개항목집단 생성

4. 2개항목집단에서 최소 지지도 혹은 신뢰도 이상의 항목만 선택

5. 위의 과정을 k개의 k-item frequent set을 생성할 때까지 반복

• Implicit Feedback dataset 사용(ex. 상품을 구매 후 고객이 만족했는지, 만족하지 않았는지 피드백이 없는 데이터)

1. 5개의 item을 이용해 단일항목집단 생성(one-item frequent set) 생성

1. 단일항목집단에서 최소 지지도(support) 이상인 항목만 선택(ex. 최소지지도를 0.5로 가정)

1. 2번에서 선택된 항목만을 대상으로 2개항목집단 생성

1. 2개항목집단에서 최소 지지도 이상인 항목만을 선택(ex. 최소지지도를 0.5로 가정)

1. 1~4번의 과정을 k개의 k-item frequent set을 생성할 때까지 반복

• 위 예시는 지지도를 기준으로 진행하며 최소지지도 0.5 이상인 item들만 선택

• Confidence와 Lift를 기준으로도 가능

• 원리가 간단하여 사용자가 쉽게 이해하고 의미 파악이 가능함

• 유의미한 연관성을 가지는 구매 패턴을 찾아줌

• 데이터가 클 경우 속도가 느리고 연산량이 많음

• 실제 적용을 해보면 많은 연관 상품들이 제시됨

FP-Growth 알고리즘

• Apriori 알고리즘의 속도 측면에서의 단점을 개선한 알고리즘

• Apriori 알고리즘과 성능은 비슷하지만 FP Tree 구조를 이용해 속도가 조금 빨라졌음

• frequent itemsets를 찾는것에는 좋지만 아이템간의 연관성을 찾기 어려움

1. 모든 거래를 확인하여, 각 아이템마다의 지지도를 계산하고 최소 지지도 이상의 아이템만 선택(앞선 Apriori 알고리즘과 동일한 단계)

2. 모든 거래에서 빈도가 높은 아이템 순서대로 순서를 정렬

3. 부모 노드를 중심으로 거래를 자식 노드로 추가하면서 tree를 형성

4. 새로운 아이템이 나올 경우 부모노드부터 시작하고 그렇지 않을 경우 기존의 노드에서 확장

5. 1~4번을 모든 거래에 대해 반복하고 FP Tree를 만들고 최소 지지도 이상의 패턴만을 추출

1. 모든 거래를 확인하여, 각 아이템마다의 지지도를 계산하고 최소 지지도 이상의 아이템만 선택(위와 같이 최소지지도는 0.5로 가정)

1. 모든 거래에서 빈도가 높은 아이템 순서대로 순서를 정렬

1. 부모 노드를 중심으로 거래를 자식 노드로 추가하면서 tree를 형성

1. 새로운 아이템이 나올 경우 부모노드부터 시작하고 그렇지 않을 경우 기존의 노드에서 확장

1. 지지도가 낮은 순서부터 시작해 조건부 패턴 생성

1. 모든 아이템에 대해 위 과정 반복

• Apriori 알고리즘 보다 빠르고 2번의 탐색으로 가능

• 후보 itemsets을 생성할 필요 없음

• 대용량의 데이터셋에서 메모리 활용이 효율적이지 않음

• Apriori 알고리즘에 비해 설계가 어려움

• FP Tree가 모두 만들어진 후 지지도 계산을 할 수 있음

Apriori, FP-Growth 코드 구현

pip install mlxtend --upgrade

import numpy as np
import pandas as pd
from mlxtend.preprocessing import TransactionEncoder
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import fpgrowth

data = np.array([
                 ["우유","기저귀","쥬스"],
                  ["양상추","기저귀","맥주"],
                 ["우유","양상추","기저귀","맥주"],
                 ["양상추","맥주"]
])

te = TransactionEncoder()
te_arr = te.fit(data).transform(data)
df = pd.DataFrame(te_arr, columns = te.columns_)

%%time
apriori(df, min_support=0.5, use_colnames=True)

%%time
fpgrowth.fpgrowth(df, min_support = 0.5, use_colnames=True)