01. 추천시스템 이해

이번 포스팅부터 추천시스템의 입문자분들을 위한 추천시스템 글을 작성해보도록 하겠습니다. 해당 글은 T-아카데미에서 발표한 추천시스템 - 입문하기의 자료에 딥러닝을 이용한 추천시스템과 추천시스템 대회를 분석한 내용을 추가한 글입니다. 해당 자료보다 더욱더 좋은 자료들이 페이스북 그룹 Recommender System KR에 있으니 많은 관심 부탁합니다.

• [01. 추천시스템 이해]
• [02. 컨텐츠 기반 추천시스템]
  • [02. 유사도 함수 및 평가 함수]
  • [02. TF-IDF를 이용한 추천시스템]
  • [02. Word2Vec을 이용한 추천시스템]
• [03. 협업필터링 기반 추천시스템]
  • [03. KNN을 이용한 추천시스템]
  • [03. SGD을 이용한 추천시스템]
  • [03. ALS을 이용한 추천시스템]
• [04. 딥러닝을 이용한 추천시스템]
  • [04. Deep Neural Networks for YouTube Recommendations]
  • [04. Training Deep AutoEncoders for Collaborative Filtering]
  • [04. Wide & Deep Learning for Recommender Systems]
  • [04. Factorization Machine]
• [05. 추천시스템 실습하기]
• [06. 추천시스템 대회 분석하기]
  • [06. 카카오 아레나 2차 대회]
  • [06. 카카오 아레나 3차 대회]
  • [06. RecSys2020 대회]

추천시스템 개요

추천시스템은 사용자(user)에게 상품(item)을 제안하는 소프트웨어 도구이자 기술입니다. 이러한 제안은 어떤 상품을 구매할지, 어떤 음악을 들을지 또는 어떤 온라인 뉴스를 읽을지와 같은 다양한 의사결정과 연관 있습니다. 이제부터 이러한 도구를 가지고 어떤 사용자에게 어떤 상품을 어떻게 추천할지에 대해 이해하는 과정을 가져보도록 하겠습니다.

기업에서의 추천시스템

백문이 불여일견이라는 말처럼 한번 기업에서는 어떤 식으로 추천시스템을 이용하는지 살펴보도록 하겠습니다. 개인적으로 생각할 때, 국내에서 추천시스템을 가장 잘 활용하는 대기업을 뽑으면 당근마켓, 네이버, 카카오 등이 있는 것 같습니다. 해당 기업들은 블로그나 컨퍼런스를 통해서 추천시스템을 어떤 식으로 활용하는지를 알려주는데 자료를 보면 되게 잘 사용하고 효과도 잘 보는 것 같습니다.

• 당근마켓 : 당근마켓 공식 블로그 링크
• 네이버 : 네이버 추천시스템 컨퍼런스 링크
• 카카오 : 카카오 추천시스템 테크 컨퍼런스 링크

당근마켓 같은 경우에는 아래와 같이 함께 본 상품을 통해서, 같은 지역의 사람들이 어떤 상품을 관심있게 같이 보는지를 알려줍니다. 이후에 언급하겠지만 이러한 방식을 User Based 기반의 추천이라고 합니다.

당근마켓 같은 경우에는 아래와 같이 함께 본 상품을 통해서, 같은 지역의 사람들이 어떤 상품을 관심있게 같이 보는지를 알려줍니다. 이후에 언급하겠지만 이러한 방식을 User Based 기반의 추천이라고 합니다.

카카오에서 운영중인 브런치에서는 읽은 글과 비슷한 내용의 글을 추천해줍니다. 이후에 언급하겠지만 이러한 방식을 Item Based 기반의 추천이라고 하고 최근에 많이 사용하는 방법의 추천방식입니다.

보통 이전의 기업에서는 파레토의 법칙을 이용한 전략을 많이 취해왔습니다. 해당 법칙은 이탈리아의 경제 학자가 찾아낸 법칙으로 완도콩의 80%는 20%의 콩깍지에서 열리는 사실입니다. 이러한 법칙은 많은 부분에서 통했는데, 기업에서는 상위 20%가 전체 매출의 80%의 가치를 창출하니 해당 고객에 역량을 집중해야한다는 의미입니다.

 

하지만, 인터넷 발전에 힘입어 넷플릭스와 아마존과 같은 회사들은 파레토의 법칙이 아닌 롱테일의 법칙에 집중을 하기 시작했습니다. 파레토의 법칙과는 반대로 롱테일의 법칙은 하위 80%가 상위 20%의 가치보다 크다는 법칙입니다. 아마존의 경우 서점에서 팔지 않는 책을 온라인에서 추천해줘서 판매하는 전략을 취했고, 넷플릭스는 개개인의 맞는 영화를 추천해줌으로서 하위80%의 매출을 끌어올렸습니다.

 

과거의 추천시스템

참고자료 : HoonDongKim, 추천시스템 - 알고리즘 Trend 정리

추천시스템의 알고리즘을 본격적으로 살펴보기 전에 과거에는 어떤 방식으로 추천했는지, 현재에는 어떤 방식으로 추천하는지에 대해 살펴보도록 하겠습니다. 초창기의 추천시스템은 연관분석과 관련된 알고리즘을 많이 사용했습니다. 말 그대로 해당 상품과 연관있는 상품을 찾는 방법인데 자세한 내용은 조금 있다가 설명하겠습니다. 이후, 넷플릭스에서 영화추천 관련 대회를 3년 동안 열었는데 해당 대회에서 SVD를 이용한 Matrix Factorization 기법이 우승을 차지했고 현재까지도 협업 필터링 방법의 알고리즘을 많이 사용하고 있습니다. 이후에는 딥러닝의 발달에 힘입어 딥러닝 모델, 강화학습 모델, 그래프 모델 등 여러 가지 형태의 최신 모델들이 사용되고 있습니다.

그중에서도 이번 포스팅에서는 대표적으로 과거에 많이 사용했던 알고리즘인 연관분석, Apriori, FP-Growth를 통해서 추천시스템의 알고리즘이 어떤 식으로 작동하는지 알아보도록 하겠습니다.

연관분석

연관분석이란?

룰기반의 모델로서 상품과 상품사이에 어떤 연관이 있는지 찾아내는 알고리즘입니다. 이러한 연관은 2가지 형태로 존재합니다.

연관의 정의?

• 첫번째, 얼마나(frequent) 같이 구매가 되는가?
• 두번째, A아이템을 구매하는 사람이 B아이템을 구매하는가?

연관분석은 위와 같은 규칙을 찾아내는 형태입니다. 어떤 상품들이 한 장바구니 안에 담기는 지 살피는 모습과 비슷하기 때매 장바구니 분석이라고 표현하기도 합니다.

대표적인 예시로는 아래의 같은 이미지(출처: lifeindigital.org)가 있습니다. 해당 이미지는 월마트에서 맥주를 구매할 때 기저귀를 같이 구매하는 경향이 크다는 것을 밝혀서 둘을 함께 진열하는 전략으로 매출을 향상했다는 내용입니다. 이러한 방식으로 특정 상품(맥주)과 특정 상품(기저귀)간의 연관성을 파악해서 같이 구매하도록 유도(함께 진열)하는 것이 추천시스템의 기본적인 전략이라고 할 수 있습니다.

그렇다면, 이러한 연관분석을 어떻게 사용하는지에 대해 알아보도록 하겠습니다. 먼저, 연관분석을 사용하기에 앞서서 연관분석에 사용하는 평가지표를 살펴보겠습니다. 연관분석에 사용되는 지표는 3가지가 있습니다. 각각의 지표의 의미와 수식을 함께 살펴보면, 아래와 같이 3개의 지표가 있고 연관분석의 효용을 평가하기 위해 3가지 지표를 함께 비교합니다.

• 지지도 : 특정 상품 A를 구매할 확률
• 신뢰도 : 특정 상품 A를 구매했을 경우에, B도 구매할 확률
• 향상도 : 특정 상품 A와 B를 동시에 구매할 확률 (두 사건이 동시에 얼마나 발생하는지 비율)

위의 신뢰도랑 향상도는 의미가 비슷한데 무슨 차이가 있을까요? 신뢰도 같은 때는 A 상품이 구매되었을 때 B 상품이 구매할 확률입니다. 즉, 특정 조건(A 상품 구매)을 줬을 때 결과(B 상품 구매)가 발생하는 조건부확률로 생각할 수 있습니다. 하지만 향상도 같은 때는 A를 구매했을 때 B의 구매 정도를 보는 것이 아니라 B를 구매 시에 A도 구매를 어느 정도 하는지? A를 구매 시에 B도 어느 정도 구매하는지? 를 동시에 측정합니다. 즉, A와 B를 각각 구매한다고 했을 때, A와 B 상품의 구매가 얼마나 같이 일어나는 정도를 측정하는 것으로 해석할 수 있고 만일 A 상품과 B 상품이 독립인 때는 P(A, B) = P(A) ∙ P(B)가 되어서 향상도는 1이 됩니다. 만일, 1보다 크다면 어느 정도 향상도를 하고 있다고 해석할 수 있습니다.

이제 이러한 정보를 바탕으로 연관분석을 해보도록 하겠습니다. 먼저, 상품 간의 연관성을 파악하기 위해 어떤 규칙이 있는지 만들어보도록 하겠습니다. 상품이 4개 있을 때의 규칙은 상품을 구매하지 않는 경우를 제외하면, 총 15가지가 있습니다. 고등학교 수학에서 순열과 조합을 통해서 상품이 4개일 때 2개를 선택하는 경우의 수는 4C2로 6이 되는 것을 배웠습니다. 이제, 이를 이용해서 모든 경우의 수를 계산하면 1개만 선택한 경우의 수 + 2개만 선택한 경우의 수 + 3개만 선택한 경우의 수 + 4개만 선택한 경우의 수 = 15개의 경우의 수가 있음을 알 수 있습니다. (전체 경우의 수 16 - 0개만 선택하는 경우의 수를 통해서 15를 계산할 수도 있습니다.)

하지만 이처럼 모든 규칙의 경우의 수를 계산하고 3가지 지표를 비교해가면서 좋은 규칙을 찾기에는 문제점이 있습니다. 어떤 문제점이 있을까요? 바로 시간과 메모리가 너무 많이 차지한다는 점입니다. 아래의 그래프는 아이템의 수가 증가함에 따라서 규칙의 수가 얼마나 증가하는지에 대한 그래프입니다. 10개의 아이템까지만 해도 크지 않았던 규칙의 수가 15를 기점으로 기하급수적으로 상승하는 것을 볼 수 있습니다. 당연하게도, 아이템의 수는 2의 n 제곱에서 1을 뺀 값으로 아이템이 하나 늘어날 때마다 지수분포 형태로 증가해서 50개의 상품만 되어도 약 10^15으로 1경에 조금 못 미치는 것을 볼 수 있습니다.

이러한 문제점을 사람들이 어떻게 해결했느냐? 바로 불필요한 규칙은 애초에 제거하는 형식으로 알고리즘을 만들었고 이게 Apriori 알고리즘의 시작입니다.

Apriori 알고리즘

Apriori 알고리즘이란?

A priori 원리는 아이템 셋의 증가를 줄이는 방법입니다. 기본적인 아이디어는 “빈번한 아이템 셋은 하위 아이템 셋 또한 빈번할 것이다＂입니다. 즉, “빈번하지 않은 아이템 셋은 하위 아이템 셋 또한 빈번하지 않다＂를 이용해서 아이템 셋의 증가를 줄이는 방법입니다. 아래의 예시를 보면 아이템2와 3을 같이 구매하는 경우가 빈번하지 않습니다. 그렇다면, 2와 3에다가 0번이나 1을 같이 구매하는 때도 빈번할까요? 그렇지 않을 것입니다. 2개의 상품을 동시에 구매하는 확률보다는 3개를 구매하는 확률이 더 낮기 때문이죠. 이를 이용해서 2와 3이 빈번하지 않으면 2와 3을 포함한 모든 경우의 수 (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)까지 모두 제거하는 것이 Apriori 알고리즘입니다.

Apriori 알고리즘

1. k개의 item을 가지고 단일항목집단 생성 (one-item frequent set)
2. 단일항목집단에서 최소 지지도(support) 이상의 항목만 선택
3. 2에서 선택된 항목만을 대상으로 2개항목집단 생성
4. 2개항목집단에서 최소 지지도 혹은 신뢰도 이상의 항목만 선택
5. 위의 과정을 k개의 k-item frequent set을 생성할 때까지 반복

우유, 기저귀, 쥬스, 양상추, 맥주 5개의 상품을 가진 경우에 대해 한번 Apriori 알고리즘을 적용해보도록 하겠습니다. 상품의 개수는 총 5개이고 거래는 4번만 발생했다고 생각하겠습니다. 그러면 아래와 같이 거래 테이블을 생성할 수 있습니다.

거래 번호	상품 목록
0	우유, 기저귀, 쥬스
1	양상추, 기저귀, 맥주
2	우유, 양상추, 기저귀, 맥주
3	양상추, 맥주

이러한 거래테이블을 행렬으로 표현하면 아래와 같은데, 행렬의 대부분의 값이 0을 가지기에 희소행렬(sparse matrix)이라고 표현합니다.

거래번호	우유	양상추	기저귀	쥬스	맥주
0	1	0	1	1	0
1	0	1	1	0	1
2	1	1	1	0	1
3	0	1	0	0	1

알고리즘에서 이제 k개의 item을 가지고 단일항목집단 생성 (one-item frequent set) 하는 과정부터 진행하도록 하겠습니다. 5개의 상품목록이 있으니 단일항목집단을 만들면 아래와 같이 5개에 대해서 생성됩니다.

• 단일항목집단 생성 (one-item frequent set) : 우유, 양상추, 기저귀, 맥주, 쥬스

이제, 위의 단일항목집단에서 최소 지지도(support) 이상의 항목만 선택 (예: 최소지지도 0.5) 해야 합니다. 이 부분이 Apriori 알고리즘의 핵심으로 지지도가 특정 임계값 이하이면 해당 규칙은 별로라고 판단하고 버리는 것입니다. 지지도는 아래와 같이 표현할 수 있는데, 예를 들어 우유의 경우는 4번의 거래 중에서 2번만 발생했기에 2/4 = 0.5의 지지도를 가지는 것입니다. 쥬스의 경우는 4번 중에 1번만 발생해서 1/4 = 0.25의 지지도를 가지고 이 값이 기존에 설정해준 최소 지지도 0.5보다 작기에 쥬스는 버리고 알고리즘이 진행되게 됩니다.

• P(우유) : 0.5
• P(양상추) : 0.75
• P(기저귀) : 0.75
• P(쥬스) : 0.25
• P(맥주) : 0.75

이제 이러한 과정을 k-item frequent set이 생길때 까지 반복해주면 됩니다. k가 2인 경우는 쥬스를 제외한 4가지 상품의 집합에서 2개씩 추출한 경우입니다.

• {우유, 양상추, 기저귀, 맥주}
• 2개항목집단 : {우유, 양상추}, {우유, 기저귀}, {우유, 맥주}, {양상추, 기저귀}, {양상추, 맥주}, {기저귀, 맥주}

이러한 2개항목집단에서의 지지도를 다시 계산하면, 아래와 같고 {우유, 양상추}와 {우유, 맥주}는 값이 0.25로 최소지지도 보다 낮음을 확인할 수 있습니다.

• {우유, 양상추} : 0.25
• {우유, 기저귀} : 0.5
• {우유, 맥주} : 0.25
• {양상추, 기저귀} : 0.5
• {양상추, 맥주} : 0.75
• {기저귀, 맥주} : 0.5

위의 과정을 k개의 k-item frequent set을 생성할 때까지 반복하면 결과적으로 아래와 같은 규칙들을 얻을 수 있습니다.

• {우유}, {양상추}, {기저귀}, {맥주}
• {우유, 기저귀}, {양상추, 기저귀}, {양상추, 맥주}, {기저귀, 맥주}
• {양상추, 기저귀, 맥주}

지지도만을 기준으로 판단했을 때, {우유, 기저귀}, {양상추, 기저귀}, {양상추, 맥주}, {기저귀, 맥주}, {양상추, 기저귀, 맥주}의 상품집단들이 같이 구매될 확률이 높으니 같이 전시를 하든 행사를 하든 어떤 마케팅 전략이 필요하다는 것입니다. 하지만, 꼭 지지도만으로 이를 계산해야하는 것은 아닙니다. Confidence와 Lift를 통해서 위의 과정을 진행해도 괜찮고 여러가지 지표를 통해서 비교한 다음에 결과를 판단하는 것이 가장 정확합니다.

이러한 Apriori 알고리즘의 장점과 단점은 아래와 같습니다.

장점

• 원리가 간단하여 사용자가 쉽게 이해할 수 있고 의미를 파악할 수 있음
• 유의한 연관성을 갖는 구매패턴을 찾아줌

단점

• 데이터가 클 경우 (item이 많은 경우)에 속도가 느리고 연산량이 많음
• 실제 사용시에 많은 연관상품들이 나타나는 단점이 있음

비록 Apriori 알고리즘이 연관분석의 속도와 연산량을 해결하기 위한 알고리즘이지만 충분한 해결책은 되지 못했습니다. 이를 해결하기 위한 방법이 다음에 나오는 FP-Growth라는 방법입니다.

FP-Growth

FP-Growth란?

FP Growth는 이전에 언급한 A Priori의 속도 측면의 단점을 개선한 알고리즘입니다. Apriori와 비슷한 성능을 내지만 FP Tree라는 구조를 사용해서 따른 속도를 가진다는 게 장점입니다. 하지만 동일하게 발생하는 아이템 셋(frequent itemsets)을 찾는 데는 좋지만 아이템 간의 연관성을 찾는 것은 어렵다는 단점이 있습니다. 아이템 간의 연관성이란 A 아이템을 구매했을 때, B 아이템을 구매하는 식의 연관성입니다. 양상추, 기저귀를 구매한 소비자가 맥주를 구매하는 것과 같은 식입니다. 위의 Apriori 예시에서 Confidence라는 방식을 사용했을 때와 {양상추, 기저귀} -> {맥주}와 같은 결과를 얻기는 힘든 것이 FP-Growth의 한계입니다.

FP-Growth 알고리즘

1. 모든 거래를 확인하여, 각 아이템마다의 지지도(support)를 계산하고 최소 지지도이상의 아이템만 선택
2. 모든 거래에서 빈도가 높은 아이템 순서대로 순서를 정렬
3. 부모 노드를 중심으로 거래를 자식노드로 추가해주면서 tree를 생성
4. 새로운 아이템이 나올 경우에는 부모노드부터 시작하고, 그렇지 않으면 기존의 노드에서 확장
5. 위의 과정을 모든 거래에 대해 반복하여 FP TREE를 만들고 최소 지지도 이상의 패턴만을 추출

먼저, 1의 과정에서 쥬스가 삭제되는 것은 Apriori와 동일합니다.

• P(우유) : 0.5
• P(양상추) : 0.75
• P(기저귀) : 0.75
• P(쥬스) : 0.25
• P(맥주) : 0.75

이후, 빈도가 높은 아이템 순서대로 순서를 정렬하는데 지지도가 0.75인 양상추, 기저귀, 맥주에서 원하는 순서대로 맨 앞에 나오도록 정렬하면 됩니다. 아래의 예시에서는 기저귀 - 양상추 순으로 정렬된 값입니다.

이후에, 정렬된 거래의 순서에서 아이템 집합 순서대로 노드를 추가해서 트리를 생성해줍니다.

노드를 추가할 때는 규칙이 있습니다. 기존에 있던 노드인지 아닌지인데, 양상추 같은 경우 처음보는 노드이기에 ROOT에 바로 이어지게 됩니다.

마찬가지로 거래번호 2번 역시, 양상추, 기저귀, 맥주가 거래번호 1번에 존재했기에 우유만 이어주게 됩니다.

이런식으로 모든 거래에 대해서 진행되면 위와 같이 FP-Growth 트리가 생성됩니다. 이렇게 만들어지면 FP-Growth 트리를 분해해서, 연관성이 큰 아이템 목록들을 추출할 수 있습니다. 분해과정을 먼저 천천히 살펴보면, 지지도가 낮은 순서부터 어떤 조건의 패턴을 가지는지 생성합니다. 아래는 우유의 조건부 패턴을 생성한 것인데, 우유를 구매했을 경우에 가질 수 있는 조건부 패턴은 {기저귀 | 우유}, {양상추, 기저귀, 맥주| 우유} 가 있습니다.

위의 과정을 모두 거치면, {기저귀, 양상추 | 맥주}, {양상추 | 맥주}를 얻을 수 있고 {양상추 | 맥주}의 경우는 값이 1로 작아서 제거하고 {기저귀, 양상추 | 맥주}만 사용할 수도 있습니다. 이렇게 진행한 FP-Growth 방식의 장점과 단점을 생각하면 아래와 같습니다.

장점

• Apriori 알고리즘보다 빠르고 2번의 탐색만 필요로 함
• 후보 Itemsets 을 생성할 필요없이 진행 가능

단점

• 대용량의 데이터셋에서 메모리를 효율적으로 사용하지 않음
• Apriori 알고리즘에 비해서 설계하기 어려움
• 지지도의 계산이 FP-Tree가 만들어지고 나서야 가능함

위와 같은 문제점들을 안고 있습니다. 한번 Apriori와 FP-Growth의 코드에 대해 살펴보도록 하겠습니다. numpy로 해당 코드를 작성하는것은 어렵기에 패키지를 mlxtend 를 이용하도록 하겠습니다.

import mlxtend
import numpy as np
import pandas as pd

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

from mlxtend.preprocessing import TransactionEncoder
te = TransactionEncoder()
te_ary = te.fit(data).transform(data)
df = pd.DataFrame(te_ary, columns=te.columns_)
df

 

%%time
# 9.97ms 
from mlxtend.frequent_patterns import apriori
apriori(df, min_support=0.5, use_colnames=True)

 

%%time
# 1.99ms 
from mlxtend.frequent_patterns import fpgrowth
fpgrowth(df, min_support=0.5, use_colnames=True)

 

코드는 되게 간단해서 따로 설명은 드리지 않겠습니다. 주목할 것은 속도의 차이인데, apriori는 9.97ms이고 fpgrowth는 1.99ms으로 약 5배정도 fpgrowth가 빠른 것을 볼 수 있습니다. 다음 포스팅에서는 최근에 많이 사용하는 컨텐츠 기반의 추천시스템에 대해서 알아보도록 하겠습니다.

 

 

커피 선물하기