개요

Amazon.com Recommendations Item-to-Item Collaborative Filtering 논문을 읽고 요약하는 포스팅이다. 해당 논문은 아마존에서 직접 production에까지 적용하여 효과를 입증한 논문으로써 item-item CF의 교과서적인 논문이라는 생각이다. 내용은 어디까지나 필자의 이해수준과 배경지식에 따른 자의적 해석이기 때문에 비판적 참고가 필요하다.

출처 : Amazon.com
Recommendations
Item-to-Item Collaborative Filtering

추천 알고리즘이란?

추천 알고리즘은 사용자가 관심가지는 아이템들을 입력으로 받아 e-커머스 사이트에서 제공해주는 것으로 잘 알려져있다. 세계 최대의 커머스 업체인 아마존에서도 당연히 관심을 가지고 연구를 진행하는 분야이다.

출처 : Amazon.com
Recommendations
Item-to-Item Collaborative Filtering

추천의 도전과제

그런 추천 알고리즘에 있어 아래와 같은 도전 과제들이 존재한다.

  • 대용량 데이터
  • 실시간 response(0.5초 미만을 권장)
  • 새로운 고객들은 매우 제한적인 정보만 존재
  • 오래된 고객은 정보 과잉 우려가 있음

추천 문제 접근방식

추천 문제를 해결하기 위해 보통 3가지의 접근방식이 있다.

  • 전통적인 협업 필터링(Collaborative Filtering)
  • 클러스터 모델(cluster model)
  • 검색 기반 모델(search-based model)

논문에서는 3가지 모델을 Item-to-Item Collaborative Filtering 모델과 비교해보았다. 논문에서 제시한 알고리즘은 실시간으로 대용량 데이터 기반에서 높은 품질의 추천을 제공한다고 한다.

Recommendation Algorithms

대부분의 추천 알고리즘들은 고객이 구매하고 평가한 아이템들을 다른 유저들의 그것과 오버랩해서 찾는 방식을 취한다. 즉, 알고리즘이 유사한 고객들의 아이템을 집계해서 사용자가 이미 구매하거나 평가한 아이템을 제거하고 남은 아이템을 사용자에게 추천하는 방식이다. 이 방식의 2가지 유명한 버전은 CF와 cluster model이다. 다른 검색 기반 방법이나 Item-to-Item CF는 고객이 아닌 비슷한 아이템을 찾는데 집중한다는 것이 차이점이다.

Traditional Collaborative Filtering

전통적인 CF에서는 전체 카탈로그 N개에 대해 사용자마다 N차원의 벡터를 만들고 그벡터의 값은 평점으로 채운다.(넷플릭스 영화의 경우 1~5점) 그런데 문제는 대부분의 고격은 이 벡터가 매우 Sparse하다는 것이다. 알고리즘은 사용자와 비슷한 몇몇 고객 기반으로 추천을 생성한다. 고객 A와 고객 B의 유사도를 구하는 방법은 여러가지가 있는데 일반적인 방법은 두 벡터의 코사인 유사도를 보는 것이다.

$$ similarity(\overrightarrow{A},\overrightarrow{B}) = cos(\overrightarrow{A},\overrightarrow{B}) = \frac {\overrightarrow{A} \bullet \overrightarrow{B}}{||\overrightarrow{A}||*||\overrightarrow{B}||} $$

이어서 알고리즘은 유사한 고객들의 아이템 사이에서 아이템을 고르는데 다양한 방법을 사용한다. 일반적인 방법은 유사한 고객들 끼리 얼마나 많이 구매를 했는지(평점을 잘 매겼는지) 순위를 매긴다. (이 순위대로 iterate하면서 사용자의 이력에 없는 아이템을 추천해주면 될 것이다.) CF를 사용하여 추천을 제공하는 것은 계산량이 많다. worst case에서 $O(MN)$이기 때문이다. 하지만 실제로는 사용자 벡터들이 평균적으로 Sparse하기 때문에 알고리즘의 성능은 $O(M+N)$에 가까운 경향이 있다. 그렇다고 하더라도 매우 큰 대용량 데이터셋(예: 천만 고객, 백만 이상의 아이템)에서는 알고리즘이 성능 이슈를 맞닥드릴수 있다. 성능 이슈를 해결하는 방법으로 데이터 사이즈를 줄이는 것을 생각해 볼 수 있다. 사용자는 샘플링해서 제거하고 아이템은 매우 있기있거나 매우 인기 없는 아이템을 제거하는 것이다. 또한 카테고리나 주제별로 아이템을 나누어 놓고 이 아이템에서만 추천을 하는 것도 방법이다. 혹은 차원 축소 테크닉(클러스터링이나 PCA)도 있을 수 있다. 하지만 불행히도 이 방법들은 모두 추천의 품질을 몇가지 이유로 저하시킨다. 첫째, 만약 사용자가 줄어든다면 유사한 사용자 자체가 누락 될 가능성이 있다. 둘째, 아이템 벡터 공간을 파티셔닝 해놓고 추천을 한다면 추천하는 아이템이 제한적일 수 있다. 셋째, 알고리즘이 매우 유명하거나 매우 유명하지 않은 아이템을 폐기해버리면 추천에 등장할 가능성이 없고 이런 아이템만 구매한 사용자는 추천을 받지 못한다. 차원 축소 테크닉은 마찬가지로 낮은 빈도의 아이템들을 제거하는 효과가 있어 회의적이다. 하지만 사용자 공간을 차원 축소 하는 것은 비슷한 사용자를 클러스터링하는 효과가 있다. 나중에 기술하겠지만 이런 클러스터링도 추천 품질을 저하시킬 수 있다.

Cluster Model

유사한 사용자를 찾기 위해서 클러스터 모델은 고객을 많은 세그먼트로 나누고 작업을 분류 문제로 다룬다. 알고리즘의 목적은 같은 세그먼트안에 유사한 고객을 모으는 것이다. 그리고 이 세그먼트 안에서 사용자의 구매이력과 평점을 사용하여 아이템을 추천한다. 세그먼트는 일반적으로 클러스터링이나 다른 비지도 학습 알고리즘을 통해 생성된다. 일부 회사에서는 이미 마이닝 된 결과로 세그먼트를 나누는 경우도 있으나 대부분의 회사에서는 greedy cluster generation을 통해 다양한 형태를 생성한다.(랜덤한 사용자를 각 세그먼트의 대표로 등록하고 이 사용자들과 비슷한 사용자를 모은다.) 매우 큰 데이터셋은 샘플링이나 차원 축소가 또한 필요하다. 알고리즘이 세그먼트를 생성하고 난 뒤 사용자를 각 세그먼트 벡터와 유사도를 구해 가장 적합한 세그먼트로 배정한다. 몇몇 알고리즘은 사용자를 복수의 세그먼트로 배중하고 각 세그먼트와의 관계를 strength로 제공한다. 클러스터 모델은 더 나은 온라인 scalibiltiy와 성능을 cf대비 보이는데 이유는 사용자의 아이템 계산이 전체 사용자가 아닌 세그먼트 안에서 일어나기 때문이다. 클러스터 모델은 많은 고객을 각각의 세그먼트로 배정하고 각 세그먼트의 사용자를 유사한 사용자로 간주한다. 하지만 클러스터에서 찾을 수 있는 사용자가 가장 유사한 사용자가 아닐 수 있기 때문에 추천되는 아이템이 연관성이 떨어 질 수 있다. 이에 대한 보완책으로 세그먼트 수 자체를 정교하게 늘릴수 있지만 이는 cluster model의 성능이 거의 cf와 같아지게 된다.(이부분은 필자의 생각엔 미리 segment를 계산해 놓고 서비스를 제공하면 보완이 가능할 듯 하다.)

Search-Based Method

검색 또는 컨텐츠 베이스 방법은 추천 문제를 연관된 아이템을 검색하는 문제로 다룬다. 주어진 사용자의 구매기록이나 평점을 기반으로 같은 저자나 아티스트 혹은 감독, 유사한 키워드나 주제의 아이템을 찾는다. 만약 고객이 갓파더 DVD컬렉션을 샀다면 말론 브란도 주연의 다른 영화나 느와르장르 등의 영화를 추천하는 식이다. 만약 특정 사용자의 구매기록이나 평점 데이터가 적어도 검색 기반 추천 알고리즘은 잘 동작한다. 하지만 데이터가 많이 쌓인 사용자의 경우 알고리즘이 전체 데이터를 탐색할 여지가 있다. 따라서 알고리즘은 데이터를 줄이기 위해 데이터셋의 부분집합을 활용해야 되는데 이부분이 추천의 품질을 저하시킬 여지가 있다.

Item-to-Item Collaborative Filtering

아마존은 많은 이메일 캠페인과 사이트 내 메인 페이즈를 포함한 다양한 페이지에서 추천을 타겟 마케팅 도구로 사용한다. 논문의 알고리즘에서 Item-to-Item CF는 대용량 데이터에서 높은 품질을 실시간으로 제공한다.

How It Works

비슷한 사용자를 매칭하는것 대신 Item-to-Item CF는 사용자의 구매하거나 평가한 아이템들의 유사성을 찾고 비슷한 아이템을 추천 리스트로 생성한다. 가장 유사한 아이템을 정의하기 위해 알고리즘은 유사한 아이템 테이블을 만들어 사용자들이 함께 구매하는 경향이 있는 아이템을 찾는다. 그러나 구매한 아이템 Pair와 정확히 일치하는 공통의 고객은 흔하지 않으므로 계산에 있어 시간이나 메모리 사용이 비효율적이다. 따라서 더 나은 접근법은 각 단일 아이템을 모든 연관있는 아이템들로 유사도를 계산하는 것이다. 수도 코드는 아래와 같다.

For each item in product catalog, I1
  For each customer C who purchased I1
    For each item I2 purchased by customer C
      Record that a customer purchased I1 and I2
    For each item I2 Compute the similarity between I1 and I2

아이템간의 유사도를 구하는 다양한 방법이 있지만 일반적으로 Cosine유사도를 사용하는데 아이템 벡터는 사용자 M명의 평점을 가진 M차원 벡터이다.

이런 아이템 간의 유사도에 대한 오프라인 계산은 매우 time intensive하다. worst case에서 $O(N^2M)$이 소모되지만 실제로는 대부분 구매기록이 헤비하지 않아서 $O(NM)$에 가깝다. 베스트셀러만 구매하는 고객들의 경우 샘플링을 통해 매우 작은 추천품질 하락 대신 계산시간을 대폭 줄일 수 있다. 주어진 유사 아이템 테이블에서 알고리즘은 각 사용자의 구매기록과 평점과 비슷한 아이템을 찾고 집계하여 가장 인기있거나 연관성 있는 아이템을 추천해준다. 이런 계산은 매우 빠르고 오직 사용자가 구매하거나 평점을 매긴 아이템의 수에만 의존적이다.

위에 대한 필자의 주관적인 이해는(필자가 구현한다면) 모델학습과 서비스 시 아래와 같은 케이스이다. 아마존에서 대다수의 사용자가 킨들을 구매할 때 킨들 커버와 라이트를 같이 구매한다고 가정해보자. 모델학습시에는 아마존에서 I1을 구매할 때 함께 구매한 다른 아이템만 추려서 이를 테이블로 유사도를 계산하여 기록한다. 예를 들어 내가 킨들과 킨들 커버, 휴대용 라이트를 같이 샀을때 킨들이 I1이라면 나머지 2개가 I2, I3가 될것이고 유사도가 계산될 것이다.(다른 사람들도 킨들과 킨들커버, 라이트를 많이들 같이 샀다면 벡터가 비슷할것이다.) 서비스 시에는 예를 들어 킨들만 구매하고 체크아웃을 하려고 하는 사용자가 있다면 I1 미리 계산해놓은 유사도 테이블에서 I1으로 검색하면 가장 유사한 아이템으로 킨들 커버와 라이트가 뜨게 되고 이를 통해 “킨들을 구매한 다른 고객님들이 함께 구매한 상품” 이런식으로 추천을 내보낼 수 있다. 대부분은 계산은 모델 학습시 해두었으므로 실시간으로 I1과 유사한 아이템을 lookup하는 일을 성능을 확보하기 용이하다.

출처 : Amazon.com
Recommendations
Item-to-Item Collaborative Filtering

scalibiltiy: A Comparison

대용량 데이터 기반의 상용 서비스 환경에서는 추천 알고리즘은 반드시 비싼 계산을 오프라인으로 미리 해두어야한다.

  • 전통적인 CF에서는 offline 계산이 없거나 적어서 온라인 계산은 고객수나 아이템 수에 의존적이다.
  • 클러스터 모델은 대부분의 계산을 offline으로 하지만 추천 품질이 낮다. 품질을 높이기 위해 세그먼트 수를 늘리면 성능이 나빠진다.
  • 검색 기반 모델은 키워드를 빌드한다. 카테고리나 저자에 대한 색인은 offline 계산이다. 하지만 추천 자체가 흥미롭지 않다.(필자의 해석은 로직이 단순하기 때문이라 생각한다.) 또한 고객수나 아이템이 늘어나면 검색 성능이 저하된다.

Item-to-Item CF의 scalibiltiy와 성능의 핵심은 대부분의 비싼 계산을 offline으로 해둔다는 것이다. 서비스 시에는 단순히 몇개의 아이템과 유사한 아이템을 lookup하는 수준이고 사용자나 아이템이 많아지더라도 서비스 시 lookup하는 아이템 수는 바뀌지 않으므로 scalibiltiy가 확보된다.(학습 장비를 scale out하면 되기 때문) 따라서 알고리즘은 대용량 데이터 환경에서 학습 및 서비스가 가능하다. 해당 알고리즘이 매우 연관성이 높은 아이템을 추천해주기 때문에 품질이 뛰어나다. 전통적인 CF와 달리 해당 알고리즘은 제한된 사용자 기록을 가지고도 높은 품질의 추천을 제공한다.(이미 다른 사용자들이 아이템 평가를 많이 해두었으므로)

Conclusion

추천 알고리즘은 사용자에게 개인화된 쇼핑 경험을 제공해주는 타겟 마케팅 플랫폼으로써 매우 효과적이다. 이후 논문에서는 앞으로도 추천은 더욱 중요해지고 많은이들이 관심을 가질것이라고 얘기한다.

필자의 생각

논문 자체가 논리적이고 쉽게 설명해주기 위한 노력이 엿보여 CF를 공부하는 초기에 매우 도움이 되는 논문이라고 생각한다. 아마존 기술을 엄청 자랑하지만 실제로도 대단하므로 개인적으로 인정한다. 여담이지만 회사 내에서 대학원생 처럼 이렇게 멋진 연구도 하고 성과도 내는 저런 상황이나 문화가 매우 좋아보이고 부럽다.