Code Sprint 2015 Round 2 – 협업 필터링으로 유저 기호 예측하기

안녕하세요. SK플래닛 Code Sprint 2015 Round 2에서 3위로 입상한 김재겸이라고 합니다. 제가 이번 라운드에서 문제를 풀기 위해 접근한 방식을 공유해 보겠습니다.

문제 개요

컨텐츠 정보와 6개월 간 고객들의 컨텐츠 구매 기록이 주어지고, 그 뒤 한 달 동안 이루어질 고객들의 컨텐츠 구매를 예측하는 문제입니다. 과거 구매 기록은 영화, 국내 드라마, 해외 드라마, 애니메이션의 4가지 카테고리에 대해 제공이 되지만, 예측은 영화에 대해서만 하도록 되어 있습니다.

알려진 추천 알고리즘들

이번 라운드의 문제를 보고 역시 먼저 떠올리게 된 것은, 넷플릭스, 구글 플레이 스토어 등 많은 컨텐츠 판매 서비스들이 갖추고 있는 추천 시스템(Recommender system)이었습니다.

사실 이번 라운드에서 풀어야 했던 문제는 실제로 유저들이 구매한 내역을 예측하는 것이기 때문에, 유저들에게 아이템을 추천하고 유저들이 그 추천 받은 아이템들을 구매하는 비율을 높이는 것을 목표로 하는 추천 시스템의 목적과는 약간 차이가 있습니다. 주어진 데이터의 출처가 되는 서비스에도 자체적인 추천 시스템이 있어 영향을 미쳤을 것이고, 그 외에도 여러 변수들이 있을 것이었습니다. 하지만 추천 시스템은 기본적으로 유저들의 기호를 예측하는 것이 목적이므로 그에 사용되는 알고리즘들이 이 문제에도 효과적일 것이라는 결론을 내리게 되었습니다.

그래서 검색을 통해, 추천 시스템에 사용되는 몇 가지 알고리즘에 대해 공부를 해 보았습니다. 구현을 위한 시간이 그리 많지 않고, 문제 규정 상 학습에 사용할 수 있는 자원과 시간도 제한돼 있어 일정 수준 이상으로 복잡한 알고리즘은 택하지 않았습니다.

제가 우선 선택한 방법은 비교적 전통적인 방식이지만 잘 동작한다고 평가 받는 두 가지 알고리즘이었습니다. 하나는 협업 필터링(collaborative filtering)이고, 다른 하나는 내용 기반 필터링(content-based filtering)입니다.

협업 필터링의 기본적인 아이디어는, 유저의 구매 패턴이 있다고 가정하는 것입니다. 협업 필터링은 주로 유저 기반 방식과 아이템 기반 방식이 사용됩니다. 유저 기반 협업 필터링(user-based collaborative filtering)은 구매 기록에 따른 유저 사이의 유사도를 구해 타겟 유저와 유사한 유저들의 구매 기록을 기반으로 예측을 하는 것이고, 아이템 기반 협업 필터링(item-based collaborative filtering)은 피구매 기록에 따른 아이템 사이의 유사도를 구해 타겟 유저가 구매했던 아이템들과 유사한 아이템으로 예측을 하는 것입니다.

내용 기반 필터링은 아이템의 각 속성마다 유저의 구매 빈도가 가장 높았던 값들의 집합들을 구해, 그에 가장 부합하는 아이템을 우선으로 예측하는 알고리즘입니다.

알고리즘 적합성 판단

한편, 학습을 위해 주어진 전체 데이터를 간단히 살펴본 결과는 아래와 같았습니다.

  • 컨텐츠(아이템) 수: 41,759개
  • 유저 수: 91,223명
  • 구매 내역 건수: 5,978,953건

그리고 위 데이터로 계산을 해 보면, 다음과 같은 수치가 구해집니다.

  • 1인당 평균 구매 건수: 약 65.5건
  • 1 컨텐츠(아이템)당 평균 피구매 건수: 약 143.2건

이를 통해, 저 계산에 사용된 컨텐츠의 수는 구매 내역이 제공된 기간 이후에 등록된 것들도 포함하는 수임에도, 두 유저 사이의 유사도를 구하기 위한 데이터의 양보다 두 아이템 사이의 유사도를 구하기 위한 데이터의 양이 평균적으로 훨씬 더 많다는 것을 알 수 있습니다. 저는 많은 양의 데이터가 정확도를 높이는데 도움이 된다고 판단하여 아이템 기반 협업 필터링을 사용하기로 하였습니다.

한편 컨텐츠 정보에 각 아이템 별 시리즈 정보, 감독, 배우, 관람 등급 등 다양한 속성 값들이 제공되기 때문에 내용 기반 필터링도 적용이 가능하지 않을까 생각했습니다. 그런데 구현을 하다 보니, 결과가 잘 나오도록 하기 위해서는 조정 및 시험해 봐야 하는 것이 많아 대회 기간 내에 최적화시키기는 어려울 것으로 판단되었습니다. 일단 아이템의 각 속성 별로 가능한 값의 개수가 매우 차이가 나서, 각각 몇 개까지를 유저의 기호 집합에 받아들일지를 정해야 했습니다. 각 속성 별로 유저의 선택에 영향을 미치는 정도가 다를 텐데, 그 가중치도 쉽게 정할 수 없었습니다. 또한 협업 필터링과 함께 사용하는 하이브리드 방식을 위해 두 알고리즘 사이의 가중치를 정하는 것도 매우 애매한 부분이었습니다. 저는 이러한 여러 가지 이유들로 내용 기반 필터링 사용을 중단하게 되었습니다. 물론 어느 정도 조정을 하며 출력을 해 보기도 했지만, 역시 결과는 그리 좋지 않았습니다.

유사도 계산

추천 알고리즘에서 자주 쓰이는 연산 중 하나가 두 벡터 사이의 유사도를 구하는 것입니다. 두 벡터 사이의 유사도를 구하는 데에는 여러 가지 방법들이 있고, 저는 그 중 코사인 유사도(cosine similarity)를 사용하였습니다.

cosSimilarity(x, y) = (x · y) / (||x|| * ||y||)

아이템 기반 협업 필터링 구현

상술했듯이 아이템 기반 협업 필터링은, 피구매 기록을 바탕으로 모든 아이템 쌍 사이의 유사도를 구하고 유저가 구매한 아이템들을 바탕으로 다른 아이템을 추천하는 알고리즘입니다. 따라서 알고리즘은 크게 유사도를 구하는 부분과 추천할 아이템을 구하는 부분으로 나눌 수 있습니다.

먼저 두 아이템 사이의 유사도를 구하는 부분에 대해 적어 보겠습니다. 두 아이템 사이의 유사도는 피구매 기록에 기반하므로, 이를 구하기 위해서는 우선 아이템을 구매한 유저의 집합을 벡터로 나타내야 합니다. 어떤 아이템 x를 구매한 유저들을 나타내는 벡터를 buyers(x)라고 하고, bought(x, i)는 i번 유저가 아이템 x를 구매한 경우 1, 아닌 경우 0으로 정한 뒤 buyers(x) = [ bought(x, 1), bought(x, 2), …, bought(x, N) ] 이라 하겠습니다. 그러면 아이템 x와 y에 대해 buyers(x) 및 buyers(y) 사이의 코사인 유사도를 구하면, 두 아이템 사이의 유사도로 사용이 가능합니다.

itemsSimilarity(x, y) = cosSimiilarity(buyers(x), buyers(y))

이를 통해 모든 아이템 쌍에 대해 유사도를 구할 수 있습니다. 참고로 저는 겹치는 피구매 유저 집합이 공집합인 경우에 한하여, 공집합이 아닌 경우의 최저 점수(상수로 정했습니다) 이하 범위 내에서 컨텐츠 정보에 따른 점수를 주도록 약간의 튜닝을 하였습니다. 그럼 이제 특정 유저의 아이템 구매 기록을 보고, 다른 아이템들에 추천 점수를 매길 차례입니다.
유저가 구매했던 아이템은 여러 개일 수 있으므로, 단순히 두 아이템 사이의 유사도만으로 점수를 정할 수는 없습니다. 저는 점수 계산을 위해 가중합(weighted sum)을 사용하였습니다만, 사실상 이 문제에서 사용할 수 있는 건 구매 여부밖에 없기 때문에 곱해지는 가중치는 0 아니면 1로 계산이 간단해집니다.
존재하는 K개의 모든 아이템을 차례로 item(1), item(2), …, item(K)라고 하고, 유저 i가 구매한 M(i)개의 아이템을 차례로 record(i, 1), record(i, 2), …, record(i, M(i))라고 할 때, 유저 i에 대한 아이템 x의 추천 점수 score(i, x)는 아래와 같이 정의 가능합니다.

score(i, x) = (itemsSimilarity(x, record(i, 1)) + … + itemsSimilarity(x, record(i, M(i)))) / (itemsSimilarity(x, item(1)) + … + itemsSimilarity(x, item(K)))
(단, 식 표현 편의를 위해 itemsSimilarity(x, x) = 0 으로 가정한 식입니다.)

모든 아이템 사이의 유사도를 구해서 저장해 두는 것이 실행 시간 단축에 도움이 되고, 저 식의 분모도 동일한 값이 많이 쓰이는 부분이기 때문에 미리 계산해 저장해 두는 것이 좋습니다.

아이템 최종 예측

최종 결과를 정할 때는 유저의 평균 아이템 구매 빈도에 따라 한 달 동안 구매할 아이템의 개수를 계산하여 카테고리 구분 없이 점수가 높은 아이템들을 그만큼 뽑은 뒤, 그 중 영화 카테고리의 아이템만 출력하도록 하였습니다.

자가 평가

이번 문제는 진행 기간 중에 주최측 서버에 자신의 답안을 제출하여 점수를 확인해 볼 수 있었지만, 하루 3회만 가능하다는 제한이 있었습니다. 이 제한은 초반에는 충분할 수 있으나 중후반에 튜닝을 하며 개선해 나갈 때는 부족할 것이라는 생각이 들었습니다. 다행히도 주어진 구매 기록이 6개월치가 있기 때문에, 그 중에 앞의 5개월치 기록으로 마지막 한 달의 구매 기록을 예상해 점수를 구해 보는 것으로 알고리즘의 정확도를 어느 정도 타당하게 평가해 볼 수 있었습니다. 실제로 자가 평가 결과가 높게 나올수록 제출 시의 점수도 더 잘 나오는 것을 확인하였습니다.

후기

추천 알고리즘을 직접 구현하여 실제 데이터를 기준으로 점수도 매겨볼 수 있는 재미있는 기회였고, 상도 타게 되어 참 기쁩니다. 여러 모로 매우 유익한 대회 참가 경험이었습니다. 매년 다른 대회들에서는 보기 힘든 주제들로 흥미로운 대회를 열어 주시는 관계자 분들께 감사 드립니다.

김재겸

KAIST 전산학과 학부 10학번으로, 소프트웨어 엔지니어링을 포함해 전산학의 여러 분야에 관심을 가지고 있습니다.

공유하기