MapReduce 기반 대용량 추천 알고리즘 개발

이번 글에서는 SPADE에서 사용하고 있는 알고리즘 중에 개인화/추천에 가장 기본적으로 사용할 수 있는 CF(Collaborative Filtering) 알고리즘에 대해 살펴보겠습니다.

User-based Collaborative Filtering

새로 개인화/추천 개발 업무에 접하시는 분에게 제가 가장 먼저 추천해드리는 논문 중의 하나가 2007년 IEEE Intelligent Systems에 실린 “A Comparison of Collaborative Filtering Recommendation Algorithms for E-commerce”입니다. 가장 기본적인 내용이 예제와 함께 비교적 쉽게 설명되어 있는데요, 이 중에서도 오늘은 user-based 알고리즘부터 살펴보겠습니다.

user-based CF algorithm의 핵심은 “나와 구매 이력이 비슷한 사용자들을 찾아서, 그 사용자들이 많이 산 아이템을 추천하자“입니다. 이를 좀 더 알기 쉽게 표로 풀어보겠습니다. 아래 표에 보면 상품이 4개 있고, 사용자가 3명 있습니다. 0/1의 값은 특정 사용자가 해당 상품을 샀는지 아닌지에 대한 정보입니다.

상품#1 상품#2 상품#3 상품#4
사용자#1 0 1 0 1
사용자#2 0 1 1 1
사용자#3 1 0 1 0
.

이런 데이터가 있을때, user-based CF에서 가장 먼저 하는 연산은 각 사용자간의 유사도를 구하는 것입니다. 구매 이력을 기반으로 했을때, 각각의 사용자가 서로 얼마나 비슷한 사용자인지를 계산하기 위해 보통 jaccard 유사도cosine 유사도를 이용합니다. jaccard 유사도는 J(userA, userB) = |A∩B|/|A∪B|이고, cosine 유사도는 Cos(userA, userB) =A⋅B/(||A||||B||) 입니다. Jaccard 유사도나 cosine 유사도나 사용자 A와 사용자 B가 산 상품이 겹칠수록 값이 커지는 경향이 있습니다.

사용자 1과 사용자 2의 Jaccard 유사도를 계산하는 경우 |A∪B|, 즉 두사람이 산 상품의 합집합의 개수는 3개 입니다. 그리고 |A∩B| 두 사람이 산 상품의 교집합의 개수는 2개네요. 그래서 jaccard 유사도 값은 ⅔= 0.67이 됩니다. 이렇게 모든 사용자간 계산된 유사도는 아래와 같습니다.

사용자#1 사용자#2 사용자#3
사용자#1 1.0 0.67 0
사용자#2 0.67 1.0 0.25
사용자#3 0 0.25 1.0

 (* 혹시 논문을 찾아서 보시는 분은 논문에 있는 표량 값이 틀리네 하실 텐데, 논문에서는 cosine 유사도로 구했습니다.)

위의 2개의 표만 있으면 우리는 각 사용자별로 어떤 상품에 대한 선호도가 높은지 계산을 할 수 있는데요, 사용자 #1에 대해 계산할 때, 사용자 #2가 산 상품들에 대해서는 0.67의 가중치를 줘서 더해주고, 사용자#3이 산 상품들에 대해서는 0.0의 가중치를 줘서 더해줍니다. 물론 자기가 산 상품에 대해서도 1.0의 가중치를 줘서 더해줍니다. 즉 나와 유사한 사용자(사용자 #2)가 산 상품들이 더 높은 가중치를 받게 되는 구조입니다. 이러한 연산 과정은 사용자간 유사도 매트릭스와 원래의 구매 이력 매트릭스를 곱해주는 것과 동일한데요, 매트릭스 곱셈을 하면 아래와 같은 표가 나옵니다.

상품#1 상품#2 상품#3 상품#4
사용자#1 0 1.67 0.67 1.67
사용자#2 0.25 1.67 1.25 1.67
사용자#3 1.0 0.25 1.25 0.25
.

이제 각 사용자별로 선호도를 기준으로 이미 구매했던 상품은 제외하고 개인별로 추천 상품 목록을 원하는 개수만큼 뽑으면 됩니다. 위 과정에서 사용자간 유사도 대신에 상품간 유사도 매트릭스를 이용해 계산하면 item-based CF가 됩니다. 간단하지요? 정리하면 사용자가 M명, 아이템이 N개인 경우, MxN 구매 매트릭스와, MxM 유사도 매트릭스를 (순서를 바꾸어)곱해주면, MxN의 선호도 매트릭스가 생성되고 이걸 기반으로 추천 등의 후작업이 진행됩니다.

분산 기반 User-based CF

너무 간단해 보이긴 합니다만, 구매 기록만 활용 가능할 때 기본적으로 자주 사용되는 알고리즘이고, 이렇게 계산된 데이터를 이용해 데이터 분석 결과에 따른 후처리들이 들어가기도 합니다. 그런데 앞선 글에서도 언급했듯이 사용자 수가 너무 많아지면 매트릭스 자체가 너무 커져서 연산이 어려워집니다.

즉, 전체 사용자 간의 유사도를 다 계산하는 것은 scalable하지 않기 때문에 SPADE의 CF에서는 Minhash Clustering을 사용합니다. 즉 모든 사용자간 간의 유사도를 계산하는 것이 아니라, clustering을 해서 일단 어느 정도 유사한 사용자들끼리 그룹을 만들고, 이렇게 만들어진 ‘상대적으로’ 소규모인 그룹에 대해서 원래의 CF 알고리즘 등을 적용하는 식으로 문제를 해결합니다.

Google이 2007년에 발표한 “Google News Personalization: Scalable Online Collaborative Filtering” 논문에도 잠깐 설명이 나오는데요, Minhash는 한 사용자의 구매 기록을 0에서 M사이의 값을 가지는 p개의 hash key의 concatenation으로 바꾸고, 이 값을 특정 사용자의 group ID로 사용합니다.  적용 데이터 형태에 따라 사용해야 할 Minhash 함수가 달라지는데, 0/1 구매기록의 경우에는 h(x)=(ax+b)mod M을 사용합니다. p가 커지면 커질수록 Minhash key로 구한 jaccard 유사도와, 원래의 구매 이력으로 계산한 jaccard 유사도가 비슷해집니다. 하지만 Minhash를 해보면 p값이 작으면 전혀 유사성 없는 사용자들만 모인 그룹이 생기거나, p가 커지면 동일 그룹내에 모이는 사용자가 너무 없기도 한데요, 이걸 보완하기 위해 한 명의 사용자에 대해서 q번 만큼 Minhash key를 생성해 한명의 사용자가 최대 q개의 서로 다른 그룹에 속하게 합니다. 이 때 각 그룹은 어느 정도 확률적으로 서로 구매 이력이 비슷한 사용자들이 모여 있게 되고, 이 그룹에서 다시 각 사용자를 key로 해서, 같은 그룹에 있던 모든 사용자들을 value로 해서 내보내면, 마지막으로 한 명의 사용자에 대해 어느 정도 유사한 구매 이력을 가진 사용자들을 모을 수 있습니다.  이렇게 target 사용자 1명과 이 사용자와 유사한 사용자 k명이 모인 데이터가 있으니, sequential하게 각 사용자와의 유사도를 구하면서 동시에 아이템 별로 가중치도 incremental하게 k명까지 죽 계산하면 해당 target 사용자에 대한 선호도 매트릭스 값이 나옵니다.

이 과정을 다시 한번 간단하게 단계별로 설명하면 아래 그림과 같습니다.

그림의 가장 좌측을 보면, 사용자 구매 이력이 있습니다. 굵게 표시된 부분이 사용자 ID이고, 그 뒤 숫자는 구매 상품의 ID입니다. 이 구매 이력에 대해서 4자리 숫자의 hash key를 2번(p=2) 만드는 과정을 3번(q=3)하면 한 사용자에 대해서 group ID가 3번 만들어집니다. ‘10000056’이라는 사용자를 보면 group ID가 3개 생겼는데요, 이제  group ID별로 다시 모으면, ‘10000056’이라는 사용자는 3개의 그룹에 각각 속하는데, 첫번째 그룹에는 4명이, 두번째 그룹에는 외롭게 혼자, 세번째 그룹에는 3명이 모여 있습니다.

이제 이 그룹 데이터에서 다시 사용자 ID를 key로 해서 내보내서 사용자 ID별로 다시 모으면, 가장 오른쪽 <Step 3>에서 볼 수 있듯이 이 사용자와 확률적으로 가장 구매 이력이 유사한(하다고 생각되는) 사용자 4명이 모이게 됩니다. 이제 이 사용자들을 가지고 원래 CF 계산을 하면 되구요, ‘10000056’ 사용자에 대한 계산만 필요하므로 총 4번의 유사도 계산과, 상품 ID에 대한 가중치 계산만 진행됩니다.

이미 충분히 눈치 채셨겠지만 이 모든 과정은 MapReduce의 mapper와 reducer로 너무 간단하게 구현이 가능합니다. map->reduce->map->reduce 면 끝납니다.
– 1st Map: 각 사용자별 구매 로그 기반 Minhash key 계산
– 1st Reduce: Group ID별 사용자 모으기
– 2nd Map: 사용자별 grouping을 위해 다시 각 사용자를 key로 해서 emit.
– 2nd Reduce: 각 사용자별로 유사 사용자 그룹 모으고, CF 계산

SPADE CF 모듈

2008년도에 이렇게 만들었던 SPADE의 CF 모듈은 그래서 아래 그림처럼 만들어 졌습니다. 조정 가능한 p, q, 파라메터 등을 밖으로 빼 놓았구요. 수행 시간 등을 고려해서 group의 size가 너무 크다거나 너무 작은 것들은 임의로 제외할 수 있도록 하는 등의 옵션들이 추가되어 있습니다. 물론 조절할 파라메터가 있다는 사실은, 데이터가 주어지면 결과 값들을 보면서 어느 정도 튜닝에 대한 수고가 필요하다는 말과 같습니다 🙂


여기서 더 한가지, MapReduce로 위와 같이 구현할 때, 한 사람의 구매 이력을 게속 그 사람의 ID와 같이 가지고 다녀야 합니다. 하지만 처음 minhash를 계산하고 나면, 2nd Reduce 전에는 구매 이력은 필요 없기 때문에 괜히 network traffic만 발생시키게 됩니다. 이 때문에 당시에 MinHash계산 후에, 구매 이력을 특정 DB에 저장해 놓았다가 2번째 reducer 단게에서 필요할 때 다시 DB에서 읽어서 사용하면 시간이 어떻게 되나 궁금해서 실험을 해본 적이 있습니다. 메모리, MySQL Sharding, Hadoop의 MapFile 파일을 저장소로 이용해서 테스트 했었는데, 당시에 사용했던 구매 이력의 경우에는 아래 그림처럼 MySQL에 저장했다가 읽으면 필요할 때만 다시 읽었을 때 훨씬 시간을 줄일 수 있었습니다.

하지만 T Store와 같이 사용자가 많고 구매 이력 데이터가 많은 경우, 오히려 구매 이력을 DB에 저장하고 읽어오는 시간이 더 걸리기도 하므로, 대상 서비스와 데이터 특성에 따라 저장소 형태를 잘 고르고 입/출력 데이터 형태에 신경쓴다면 더 빠른 작업도 가능할 수 있습니다. 위 CF 모듈의 경우 현재 T Store처럼 천만~천수백만명 수준의 사용자는 DB를 사용하지 않아도 파라메터에 따라 수십대 datanode로 최대 1시간 내에 모든 계산이 끝날 수도 있습니다.

기타 CF 알고리즘

구매 이력이 0/1이 아니라, 영화평과 같이 0~10사이의 평점 데이터를 이용해야 하는 경우가 있습니다. Netfllix Contest에 사용된 데이터나, CF관련 논문에서 주로 사용되는 MovieLens Data같은 데이터가 예인데 이 때에 사용하는 CF 알고리즘은 달라집니다. 사용하는 유사도도 약간 달라지고(예, pearson correlation), 개인별 선호도 계산에 사용하는 수식도 조금 바뀝니다.

하지만 큰 틀은 위와 유사해서, 결국은 사용자간 유사도나 아이템간 유사도를 구하고, 그 유사도를 기반으로 개인별 아이템에 대한 선호도를 계산합니다. 조금 더 찾아보고 싶으신 분은 최근 survey자료인 “A Survey of Collaborative Filtering Techniques”나 netflix prize를 거머쥔 팀의 논문 “The BellKor Solution to the Netflix Grand Prize“을 참조하셔도 좋을 것 같습니다.

SPADE의 경우 Hoppin에서 사용자의 평점을 기반으로 개인별 추천 아이템 목록을 생성하는 데 이런 평점을 기반으로 하는 CF 알고리즘을 사용하였고, 계산 효율성을 위해 아이템간의 유사도를 구하고, 각 사용자별로 전체 아이템에 대한 예측 평점을 계산하는 모듈을 각기 MR로 개발했습니다.

T Store 개인화

알고리즘 하나를 MapReduce로 개발한다고 해서, 추천이나 개인화가 끝나는 건 아닙니다. 현재 T Store를 지원하기 위한 프로세스를 간단하게 그려보면 아래 그림과 같이 여러 단계로 나뉘며 매 단계에는 여러가지 알고리즘이나 ETL 모듈들이 결합되어 사용됩니다. (예, 왼쪽 그림의 1번 단계는 오른쪽의 1번에서처럼 여러가지 모듈들이 사용됩니다.) 이렇게 만들어진 기본적인 추천 결과를 바탕으로 실제로 서비스가 나가기 전에 각종 후처리 로직 및 정제 작업이 수반되어야 품질 좋은 추천 결과를 얻을 수 있습니다.

마치며

지금까지 말씀드린 CF는 2008년에 개발되어, 특정 서비스들의 추천에 가장 기본적인 하부 데이터 생성을 위해 주로 사용되고 있습니다. 이 외에도 연관 규칙을 기반으로 추천 상품을 만들어 낸다거나 데이터 분석을 통한 Insight에 기초한 각종 전/후 처리 과정들이 사용되고 있습니다.

많은 CF 알고리즘 중에 최근에는 ALS-WR(Alternating Least Square Weighted lamda Regularization)이라는 알고리즘이 Mahout에 도입되었는데요. 다음 글에서는 이 알고리즘이 어떤 장단점을 지니고 T Store 개인화에 도입하기 위해 어떤 실험과 노력 등이 필요했었는지 살펴보겠습니다.

읽어주셔서 감사합니다.

김민성 Data platform팀

현재 SK 플래닛에서 빅 데이터 분석 및 추천에 필요한 대용량 알고리즘 개발을 담당하고 있습니다.

공유하기

  • 조효성

    잘 읽었습니다. 덕분에 추천 알고리즘 스터디를 잘 시작할 수 있었습니다^^