중첩 정보를 이용한 효율적인 협업 필터링 프레임워크

Abstract

전자상거래의 사용자들이 시스템 내에 존재하는 모든 상품들을 보는 것은 사실상 불가능하기 때문에 대부분의 전자상거래에는 사용자 개인에 맞는 상품들을 소개해주는 추천 시스템이 존재한다. 추천 시스템에서 상품을 추천하기 위한 방법 중 가장 널리 사용되는 것이 유저 기반 협업 필터링이다. 유저 기반 협업 필터링을 사용하는 추천 시스템의 사용자와 아이템의 수가 많아짐에 따라 검색 시간 내에 유사한 성향의 사용자를 정확하게 계산하는 방안이 요구된다. 일반적으로 대용량 데이터를 이용하는 시스템들은 빠른 검색을 위하여 인덱싱을 사용한다. 그러나 추천 시스템 환경에서는 (1)고차원 데이터 (2)sparse한 데이터 (3)metric space를 만족하지 않는 객체 간의 유사도의 세 가지 특성으로 인하여 인덱싱을 사용하기 어렵다. 다양한 사전 실험을 통해 추천 시스템에서 인덱싱 적용이 어려움을 보인다. 본 논문에서는 유저 기반 협업 필터링 추천 시스템에서 효과적으로 유사한 성향을 갖는 사용자를 검색하는 두 가지 프레임워크를 제안한다. 첫 번째 프레임워크는 질의 유저가 점수를 부여한 아이템들 중 하나 이상의 아이템에 점수를 부여한 유저들만을 대상으로 질의 유저와의 유사도를 계산하는 방법이다. 질의 유저와 모든 다른 유저간의 유사도를 계산하는 대신 일부 유저에 대해서만 유사도를 계산하기 때문에 효율적이다. 두 번째 프레임워크는 첫 번째 프레임워크의 성능을 개선한 방법으로써 두 유저 사이에 유사도를 계산할 때 시스템에 존재하는 모든 아이템의 점수를 이용하지 않고 두 유저가 동시에 점수를 부여한 아이템의 점수만을 이용하여 계산하는 방법이다. 계산할 필요가 없는 유저를 필터링한 후 유저가 아이템에 부여한 점수 중 의미 없는 부분을 한번 더 필터링 하기 때문에 질의 유저와 유사한 유저를 더욱 효율적으로 찾을 수 있다. 제안하는 프레임워크가 정확하게 유사한 유저를 계산함과 기존 방안보다 공간 사용이 많지 않음을 수학적으로 증명한다. 또한, 다양한 실험을 통해 제안하는 프레임워크를 이용했을 때 최대 33배의 성능 향상이 있음을 보이고 동적 상황에서도 실시간으로 계산 가능함을 보인다. |There are recommender systems which introduce the products personalized for a certain user in most of the e-commerce because it is practically impossible for a user to look at all the products. The user-based collaborative filtering is a way to recommend products that one of the most widely used. In recommender system, the user-based CF have been required to calculate similarities between users with their taste in query time, even though the number of users and items are exploded. Typically systems that handle large amounts of data use indexing for efficient retrieval. However, indexing is difficult to use in recommender systems, because of (1)high dimensional data, (2)sparse data, (3)similarity that does not satisfy the metric space between objects. Through preliminary experiments, we show that it is difficult to apply the indexing in recommender system. This paper proposes two frameworks to retrieve users similar to a query user for user-based collaborative filtering. The first framework calculates similarity between a given query user and others which give scores to one or more items in which given ratings by query user. This framework is efficient because it calculates similarities between some of users instead of all users. The second framework calculates similarity between a given query user and others with only their common item ratings instead of whole item ratings of each user and the constraint of our first framework. It can compute the similarity more efficient than our first framework because it filters out the meaningless part of scores again after filtering out users by our first framework. It is proved that the both frameworks can accurately calculate user-similarities without any storage overhead. Finally, we verify that the second framework can significantly improve at most 33 times the performance compared with previous methods in a dynamic situation in real time via extensive experiments.; There are recommender systems which introduce the products personalized for a certain user in most of the e-commerce because it is practically impossible for a user to look at all the products. The user-based collaborative filtering is a way to recommend products that one of the most widely used. In recommender system, the user-based CF have been required to calculate similarities between users with their taste in query time, even though the number of users and items are exploded. Typically systems that handle large amounts of data use indexing for efficient retrieval. However, indexing is difficult to use in recommender systems, because of (1)high dimensional data, (2)sparse data, (3)similarity that does not satisfy the metric space between objects. Through preliminary experiments, we show that it is difficult to apply the indexing in recommender system. This paper proposes two frameworks to retrieve users similar to a query user for user-based collaborative filtering. The first framework calculates similarity between a given query user and others which give scores to one or more items in which given ratings by query user. This framework is efficient because it calculates similarities between some of users instead of all users. The second framework calculates similarity between a given query user and others with only their common item ratings instead of whole item ratings of each user and the constraint of our first framework. It can compute the similarity more efficient than our first framework because it filters out the meaningless part of scores again after filtering out users by our first framework. It is proved that the both frameworks can accurately calculate user-similarities without any storage overhead. Finally, we verify that the second framework can significantly improve at most 33 times the performance compared with previous methods in a dynamic situation in real time via extensive experiments.