- 논문 링크 (8143회 인용)
Summary
- user based CF, Clustering method의 한계를 극복하고자 item-based CF를 개발하였다.
- 아마존과 같이 수많은 유저와 아이템을 가지고 있는 온라인 상점에게 scalability 문제는 중요하고 item-based CF을 통해 이 문제를 풀 수 있다.
- 유사한 유저를 먼저 찾는 것이 아니라, 유사한 아이템을 먼저 찾는다.
Motivation
- 전통 cf는 다음의 한계를 가진다.
- 고객의 수와 아이템의 수를 각각 $M,N$이라고 할 때, 최악의 경우 시간 복잡도는 $O(MN)$이다. 물론, 보통의 경우에 $O(M+N)$의 복잡도를 가지지만, 여전히 computationally expensive하다.
- 이렇게 시간이 오래 걸리는 문제를 $M,N$ 중 하나의 크기를 줄임으로써 해결할 수 있다. 그렇지만 이는 부정확한 결과를 야기한다.
- cluster models은 다음의 한계를 가진다.
- 하나의 세그먼트에 속한 유저들은 누가 누구에게 더 '유사한' 개념이 없이, 모두 유사한 유저로 묶인다.
- 이런 이유로 정확한 추천을 하기가 어렵다.
- search based methods은 다음의 한계를 가진다.
- 유저가 소비한 제품의 동일한 author, artist, director 등의 제품을 검색하여 추천해준다.
- 하지만 만약 유저의 구매 이력이 많다면, 매우 많은 아이템에서 이를 찾는 것은 비효율적이다.
- 결국 item-based CF는 더 빠르게 추천을 하면서, 동시에 정확도도 확보하고자 연구된 방법론이다.
Approach
Making similar items table
하나의 아이템에 대해 가장 유사한 아이템을 판별하기 위해서, similar-items table을 만든다. 이때, product-to-product matrix을 만들어서 모든 아이템 pairs에 대해 이터레이션을 돌 수 있지만, 대부분의 product pairs는 공통의 소비자가 존재하지 않기 때문에 이는 비효율적인 방법이다. 이에 대한 대안으로 논문에서는 아래의 알고리즘을 제안한다.
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
아이템1과 아이템2간의 유사도를 계산할 때, 모든 아이템간에 계산하는게 아니라 한명의 유저가 두 아이템을 구매한 이력이 있는 경우에 한해서, 아이템1과 아이템2간의 유사도를 계산한다.
위의 pseudo code를 보면 최악의 경우, 시간 복잡도가 $O(N^2M)$인 것을 확인할 수 있다. 하지만 대부분의 유저들은 매우 적은 구매 이력을 가지고 있기 때문에 세번째 줄의 복잡도 $O(N)$은 무시할만하다. 따라서 최종 시간 복잡도는 $O(NM)$ 정도이다. (전통 cf와 똑같은 것 아닌가?!)
Recommendation
similar table을 완성했으면, 유저가 구매한 제품과 가장 유사한 제품을 유사도에 따라 나열하고 이를 추천해준다.
Results
Conclusion
- pseudo code을 아무리 쳐다봐도 100% 이해를 못하겠다.. 차라리 이 포스트 글의 item-based cf가 더 이해하기 쉬운 것 같다.
- 여하튼 item-based cf가 나오게된 배경, 풀고자 하는 문제는 확실하게 알게 된 것 같다. (scalability, accuracy 두 마리 토끼 잡기)
- 아직까지는 '알고리즘'이라기 보다 간단한 방법에 의한 추천이라는 느낌이 드는데 다른 추천 알고리즘을 더 살펴봐야할 것 같다.
댓글