헤매어도 한 걸음씩

[논문 리뷰] Amazon.com RecommendationsItem-to-Item Collaborative Filtering 본문

Paper Review

[논문 리뷰] Amazon.com RecommendationsItem-to-Item Collaborative Filtering

ritz 2022. 3. 16. 23:32
원문 : https://www.cs.umd.edu/~samir/498/Amazon-Recommendations.pdf

 

  • 사용자가 선호할만한 아이템을 추천함으로써 여러 가지 항목 중 사용자에게 적합한 특정 항목을 추천하여 제공하는 알고리즘
  • 매출과 직결되는 system이기 때문에 많은 연구가 있음 ex. 넷플릭스, 구글, 아마존
  • Item-to-Item Collaborative Filtering : 1998년 Amazon에서 처음 사용

 

Problems

: E-commerce recommendation algorithms often operate in a challenging environment.

  • 대용량 데이터의 처리
  • half of second 안으로 처리해야하는 real time 추천
  • 새로운 USER가 왔을때 어떻게 추천 해야하는가? ⇒ cold start problem for new user
  • 오래된 USER의 너무 많은 데이터는 noise 로 작용
    • → 이런 USER에게 어떻게 추천해야할까?
  • USER 데이터는 휘발성이다.
    • → 각 USER의 시시각각 변하는 interaction 을 어떻게 알고리즘에 반영할것인가?

 

추천 문제를 해결하기 위한 일반적인 3가지 접근방식

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

논문에서는 상기 3가지 모델을 Item-to-Item Collaborative Filtering 모델과 비교한다.

논문에서 제시한 알고리즘은 실시간으로 대용량 데이터 기반에서 높은 품질의 추천을 제공한다.

대부분의 추천 알고리즘들은 고객이 구매하고 평가한 아이템들을 다른 유저들의 그것과 오버랩해서 찾는 방식을 취한다.

즉, 알고리즘이 유사한 고객들의 아이템을 집계해서 사용자가 이미 구매하거나 평가한 아이템을 제거하고 남은 아이템을 사용자에게 추천하는 방식이다.

이 방식의 2가지 유명한 버전은 CF와 cluster model이다. 다른 검색 기반 방법이나 Item-to-Item CF는 고객이 아닌 비슷한 아이템을 찾는데 집중한다는 것이 차이점이다.

 

1. Traditional Collaborative Filtering

알고리즘은 사용자와 비슷한 몇몇 고객 기반으로 추천을 생성

고객의 유사도를 구하는 일반적인 방법은 두 벡터의 코사인 유사도를 보는 것

Traditional CF 에서는 전체 product catalog N, user M 이 존재한다고 했을때, M * N matrix 생성

 

각 유저가 각 카탈로그에 평점을 매긴다. 이 행위로 user의 profile 을 완성

→ 이때, 유저 한 명의 추천을 만들기 위해서, O(MN) 이라는 끔찍한 시간복잡도가 발생

 

물론 해당 matrix 가 굉장히 sparse 하기 때문에 (유저는 수많은 item 중 정말 일부만 rating을 해둠.)

보통의 경우 O(M + N) 의 시간복잡도가 되는 경향이 있음

 

하지만 굉장히 큰 데이터에서 유저에게 추천을 해야할때마다 이 계산을 하려면 너무 많은 컴퓨팅 자원이 필요

Offline 추천을 하면 되지 않는가? 라고 할 수 있겠지만, User 의 preference 는 굉장히 빨리 변하기 때문에, interactive 하게 추천할 수 없게 되면 타격이 크다.

 

성능 이슈를 해결하는 방법으론 데이터 사이즈를 줄이는 것을 생각해 볼 수 있다.

 

사용자는 샘플링해서 제거하고 아이템은 매우 인기 있거나/매우 인기 없는 아이템을 제거 or 카테고리나 주제별로 아이템을 나누어 놓고 이 아이템에서만 추천

혹은 차원 축소(클러스터링이나 PCA)도 있을 수 있다.

 

하지만 위 방법들은 모두 다음과 같은 문제가 있음

  • random sampling user
    • 유사한 유저가 random sampling으로 인해 추천되지 않을 수 있어 성능 하락
    • 다시말해, 사용자가 줄어든다면 유사한 사용자 자체가 누락될 가능성이 있음
  • reduce item. discard very popular and unpopular items
    • 유저가 해당 item을 추천받는게 최선인 상태에서 해당 아이템들을 추천받을 수 없음. 성능 하락
  • partitioning item space based on product category or subject classification
    • 추천이 specific product or subject area 로 제한되면 추천 성능이 떨어질 수 있음
  • Demensionality reduction techniques. such as clustering or PCA
    • low frequency item들을 지워버림
    • 사용자 공간을 축소하는 것은 비슷한 사용자를 클러스터링하는 효과가 있다.(클러스터링도 마찬가지로 추천 품질을 저하시킬 수 있다.)

 

2. Cluster Model

유사한 사용자를 찾기 위해 여러 segment로 유저를 나누고, 가장 유사한 segment 를 찾는다.

그리고 해당 segment 에 있는 유사한 고객들을 기반으로 추천을 진행한다. (세그먼트 안에서 사용자의 구매 이력과 평점을 사용하여 아이템을 추천)

Clustering 자체는 offline 에서 수행할 수 있고, segment 를 찾는 계산이 모든 user 를 대상으로 유사도를 측정하는것보다 훨씬 계산량이 적기 때문에 확장성이 더 좋다.

하지만, segment 를 대상으로 user 와 유사도를 계산하기 때문에, 명확하게 유저와 가장 유사한 유저를 찾는 동작이 아니므로 성능상 문제가 있다. 즉, 클러스터에서 찾을 수 있는 사용자가 가장 유사한 사용자가 아닐 수 있기 때문에 추천되는 아이템의 연관성이 떨어질 수 있다.

 

이에 대한 보완책으로 세그먼트 수를 정교하게(많이많이) 늘릴 수 있지만, 그럼 결국 traditional CF 와 성능이 거의 비슷해진다.

 

3. Search-Based Methods

검색 또는 컨텐츠 베이스 방법은 추천 문제를 연관된 아이템을 검색하는 문제로 다룬다.

주어진 사용자의 구매기록이나 평점을 기반으로 같은 저자나 아티스트 혹은 감독, 유사한 키워드나 주제의 아이템을 찾는다.

만약 고객이 영화 DVD컬렉션을 샀다면 해당 영화 주연의 다른 영화나 동일한 장르의 영화를 추천하는 식이다.

만약 특정 사용자의 구매기록이나 평점 데이터가 적어도 검색 기반 추천 알고리즘은 잘 동작한다.

하지만 데이터가 많이 쌓인 사용자의 경우 알고리즘이 전체 데이터를 탐색할 여지가 있다. (=너무 많은 데이터에 rating을 했다면 전체 item 에 대해서 키워드나 평점을 통한 탐색을 진행)

따라서 알고리즘은 데이터를 줄이기 위해 데이터셋의 부분집합을 활용해야 되는데 이부분이 추천의 품질을 저하시킬 여지가 있다.

 

Item-to-Item Collaborative Filtering

논문의 알고리즘에서 Item-to-Item CF는 대용량 데이터에서 높은 품질을 실시간으로 제공한다.

 

Item-to-Item CF는 비슷한 사용자를 매칭하는것 대신 사용자가 구매하거나/평가한 아이템들의 유사성을 찾고 비슷한 아이템을 추천 리스트로 생성한다.

가장 유사한 아이템을 정의하기 위해 알고리즘은 유사한 아이템 테이블을 만들어 사용자들이 함께 구매하는 경향이 있는 아이템을 찾는다.

 

그러나 구매한 아이템 Pair와 정확히 일치하는 공통의 고객은 흔하지 않으므로 계산에 있어 시간이나 메모리 사용이 비효율적이다.

따라서 더 나은 접근법은 각 단일 아이템을 모든 연관있는 아이템들로 유사도를 계산하는 것이다. 수도 코드는 아래와 같다.

비슷한 유저를 매칭하지 않고, 유저가 현재 보고있는 아이템이나, 유저가 평가한 아이템들과 유사한 아이템을 추천해주는 방식으로 진행한다.

 

위 알고리즘은 O(N^2 M)이라는 시간복잡도가 발생한다. 하지만 유저의 rating 자체가 sparse(또는 구매 기록이 많지 않다) 하기 때문에 보통 O(NM)이 된다.

또한, item 의 profile 의 경우, 보통의 경우 급격하게 변하지 않는다. 따라서 offline 계산이 가능하므로 inference time에 유저에게 바로 lookup 형식으로 빠르게 serving할 수 있는 장점이 있다.

 

이런 계산은 매우 빠르고 오직 사용자가 구매하거나 평점을 매긴 아이템의 수에만 의존적이다.

 

scalibiltiy: A Comparison

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

 

cluster 의 경우 좋은 성능을 보이지 못했지만, item-item 의 경우 모든 item 간의 similarity 계산을 미리 할 수 있었고, 이러한 특성 덕분에 stable 한 profile 을 가지는 item 의 경우 item-item CF 가 user base 보다 scalability가 좋다고 할 수 있다.

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

따라서 알고리즘은 대용량 데이터 환경에서 학습 및 서비스가 가능하다.

해당 알고리즘이 매우 연관성이 높은 아이템을 추천해주기 때문에 품질이 뛰어나다.

전통적인 CF와 달리 해당 알고리즘은 제한된 사용자 기록을 가지고도 높은 품질의 추천을 제공한다.

 

Conclusion

: 앞으로 개인화 마케팅에 대한 추천 알고리즘을 보다 폭넓게 적용할 것으로 기대

 

References

 

'Paper Review' Related Articles more