Vol. 2 No. 2 47 57 (Mar. 2009) 1, 2 1 3 1 Web Performance Evaluation of Recommendation Algorithms Based on Rating-recommendation Interaction Akihiro Yamashita, 1, 2 Hidenori Kawamura, 1 Hiroyuki Iizuka 3 and Azuma Ohuchi 1 The problem of information overload spreading across the Internet has been causing serious inefficiency in browsing and searching for information. As a way to overcome the problem, the recommender systems are recently used in many E-commerce sites. Many algorithms have been proposed to improve the accuracy of recommendation based on user ratings. The relation between recommender systems and users is rather interactive in the sense that recommendations decides which items are recommended to users and the results of ratings by users will affect the next recommendations. However, conventional studies have not considered the interactive aspects so much. Therefore, our aim of this paper is to propose a new evaluation model using multiagent modeling where the recommender system and agents (as users) interacts with each other. The properties of typical recommendation algorithms such as user-based and itembased collaborative filtering will be analyzed with our proposed model. Our results also suggest the possibilities to propose a novel and effective recommendation algorithm. 1. Amazon.com 1 MovieFinder.com 2 Ebay 3 1) 2) Amazon.com 3) 1992 Collaborative Filtering CF 4) k-nearest neighbor GroupLens 5) 6) 9) CF CF 1 Graduate School of Information Science and Technology, Hokkaido University 2 JSPS, Japan Society for the Promotion of Science 3 Graduate School of Engineering, Osaka University 1 http://www.amazon.com/ 2 http://www.moviefinder.com/ 3 http://www.half.ebay.com/ 47 c 2009 Information Processing Society of Japan
48 CF CF User-based CF CF Item-based CF CF 2. CF CF 10) GroupLens CF 5) Amazon.com CF 3) 11) 12) CF 6),13) Web 14),15) 16) 3. 3.1 3 N user U = {i i =1, 2,...,N user} N item C = {j j =1, 2,...,N item} p i =(p i1,p i2,...,p id ) v j =(v j1,v j2,...,v jd ) p i v j d [ 1, 1] i j s i,j i s i,j i j r i,j 3.2 s i,j p i v j s i,j = f utility (p i, v j ).
49 p i i p i v j s i,j f utility p i v j s i,j f utility f utility 1 f utility 0 s i,j p i v j 0 s i,j =1 s i,j =0 3.1 p i v j [ 1, 1] 2 d x d f utility (p i, v j ) = exp ( α p i v j ) (1) 0 s i,j < 1 x d f utility α s i,j α =0.5 3.3 Web 5 r i,j i s i,j 5 f rating(s i,j) f rating s i,j 5 r i,j 4 p i v j 5 p i v j d s i,j d (2) d =5 r i,j = f rating(s i,j) 1 (s i,j 0.3358) 2 (0.3358 <s i,j 0.3878) = 3 (0.3878 <s i,j 0.4417), (2) 4 (0.4417 <s i,j 0.5160) 5 (0.5160 <s i,j) p i v j p i 5 d (1) s i,j p i v j d r i,j 5 p i v j d d d s i,j p i v j s i,j d d =5 3.4 1 A D 1 N user N item p i v i A B 1 C
50 1 Fig. 1 Simulation process. utility average D C t t A 4. 4.1 p i p i 3 Uniform distribution p i p i [ 1, 1] Multivariate normal distribution p i x d d z =(z 1,z 2,...,z d ) Σ Σ=LL T L μ x = Lz + μ N(μ, Σ), μ = 0 Σ (3) v 0 Σ v v { σ ij = v where i = j Σ v =. (3) σ ij = 0 otherwise 2 Two-peak distribution 1 2 2 Σ μ 2 2 μ 1 =(0.5, 0.5, 0.5, 0.5, 0.5) T, μ 2 =( 0.5, 0.5, 0.5, 0.5, 0.5) T, Σ 0.04 4.2 v j p i
51 4.3 4 Random Recommendation Popular Recommendation User-based CF CF Resnick 5) a U neighbors neighbors neighbors a simirality n Nearest neighbor 2 5) 10) 10) a i sim(a, i) (4) C i i C a,i a i C i C i (r a,j r a)(r i,j r i) j C a,i sim(a, i) =, (r a,j r a) 2 (r i,j r i) 2 j C a,i j C a,i where r i = 1 C i a C i r i,a, neighbors a j r a,j (4) sim(a, i)(r i,j r i) i U j r a,j = r a +, (4) sim(a, i) i U j r i C i U j j a r a,j Item-based CF CF 17) 2 c j sim(c, j) (5) (r i,c r c)(r i,j r j) i U c,j sim(c, j) =, (r i,c r c) 2 (r i,j r j) 2 i U i,c i U i,c where r j = 1 U j i U j r i,j, (5) U c,j c j
52 r j j sim(c, j) [ 1, 1] i c r i,c (6) sim(c, j)(r i,j) j C i r i,c =. (6) sim(c, j) j C i i r i,c 5. 5.1 5.3 5.5 CF CF 5.1 1 2 N user = 500 N item = 500 p i 4.3 utility average t 10 CF t =0 t =30 t =40 CF t =0 2 p i N user = 500 N item =500 Fig. 2 Changes in utility average obtained using each recommendation algorithm (p i is generated based on uniform distribution, N user = 500, N item = 500). N user N item 4.1 p i 5.2 2 1 1 0.05 2 t = r t = r +30 4.3 3 3(a) CF CF N user 3(b) N user
53 3 (a) (b) N item = 500 p i N user = {100, 500, 1000, 2000} (c) (d) N user = 500 p i N item = {100, 500, 1000, 2000} (e) (f) N user = 500 N item = 500 p i Fig. 3 Peak value of utility average and rising step obtained using each recommendation algorithm. (a) and (b) show the results at N item = 500 and p i is generated based on uniform distribution. (c) and (d) show the results at N user = 500 and p i is generated based on uniform distribution. (e) and (f) show the results at N user = 500, N item = 500 and p i is generated based on each distribution. N item 3(c) (d) N item CF 3(e) (f) 4.1 p i CF CF 3 CF CF CF CF 2 5.2 1 1 CF CF N user =500 N item =500 p i 4 4 t 100 4 CF 4 CF CF CF
54 4 CF CF N user = 500 N item = 500 p i 100 Fig. 4 Changes in the number of ratings to each item at N user = 500, N item = 500, p i is generated based on uniform distribution obtained using user-based CF (left) and item-based CF (right). (This figure shows 100 items chosen at random). 1 CF CF CF CF 3(e) (f) p i 4.1 5 (a) (b) N item = 500 p i N user = {100, 500, 1000, 2000} (c) (d) N user = 500 p i N item = {100, 500, 1000, 2000} Fig. 5 Peak value of utility average and rising step of new agent when ratings are set in our recommender system beforehand. (a) and (b) show the results at N item =500andp i is generated based on uniform distribution. (c) and (d) show the results at N user = 500 and p i is generated based on uniform distribution. 5.3 2 100 CF CF N item = 500 p i N user = {100, 500, 1000, 2000} 5 CF
55 5.4 2 1 N user 5(b) (d) CF 2 CF N user 5 2 5.5 3 1 CF CF 2 2 CF CF t =30 2 CF CF t =10 2 CF CF 6 CF t =30 CF 7 5.3 20% CF CF t =10 6 7 p i N user = 500 N item =500 5.6 3 6 6 t =30 t =10 t =70 6 CF CF p i N user = 500 N item = 500 Fig. 6 Changes in utility average in the case where recommendation algorithm is switched from item-based CF to user-based CF (p i is generated based on uniform distribution, N user = 500, N item = 500). 7 CF CF p i N user = 500 N item = 500 Fig. 7 Changes in utility average in the case where recommendation algorithm is switched from item-based CF to user-based CF when several ratings are set in our recommender system beforehand (p i is generated based on uniform distribution, N user = 500, N item = 500). t =50 4 4 t =30 CF
56 CF 7 10 CF CF 6. CF CF CF CF 1) Resnick, P. and Varian, H.: Recommender Systems, Comm. ACM, Vol.40, No.3, pp.56 58 (1997). 2) Schafer, J.B., et al.: E-Commerce recommendation applications, Data Mining and Knowledge Discovery, Vol.5, No.1-2, pp.115 153 (2001). 3) Linden, G., et al.: Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, Vol.7, No.1, pp.76 80 (2003). 4) Goldberg, D., et al.: Using Collaborative Filtering to Weave an Information Tapestry, Comm. ACM, Vol.35, No.12, pp.61 70 (1992). 5) Resnick, P., et al.: GroupLens: An Open Architecture for Collaborative Filtering of Netnews, Proc. CSCW 94, ACM, pp.175 186 (1994). 6) Herlocker, J.L., et al.: Evaluating Collaborative Filtering Recommender Systems, ACM Trans. Information Systems, Vol.22, No.1, pp.5 53 (2004). 7) Herlocker, J.L., et al.: An algorithmic framework for performing collaborative filtering, Proc. 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pp.230 237 (1999). 8) Adomavicius, G. and Tuzhilin, A.: Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Trans. Knowledge and Data Engineering, Vol.17, No.6, pp.734 749 (2005). 9) Vol.J90-D, No.2, pp.223 232 (2007). 10) Breese, J.S., et al.: Empirical Analysis of Predictive Algorithms for Collaborative Filtering, Proc. 14th Conference on UAI 98, pp.43 52 (1998). 11) Ungar, L.H. and Foster, D.P.: Clustering methods for collaborative filtering, Proc. Workshop on Recommendation System at the 15th National Conf. on Artificial Intelligence (1998). 12) Pennock, D.M., et al.: Collaborative Filtering by Personality Diagnosis: A Hybrid Memory- and Model-Based Approach, Proc. 16th Conference on UAI 00 (2000).
57 13) DEWS2007 (2007). 14) Sarwar, B., et al.: Analysis of Recommendation Algorithms for E-Commerce, Proc. 2nd ACM conference on Electronic commerce, pp.158 167 (2000). 15) Herlocker, J.L., et al.: An Empirical Analysis of Design Choices in Neighborhood- Based Collaborative Filtering Algorithms, Information Retrieval, Vol.5, No.4, pp.287 310 (2002). 16) 6 FIT2007 (2007). 17) Sarwar, B., et al.: Item-based Collaborative Filtering Recommendation Algorithms, Proc. WWW 01, pp.285 295 (2001). ( 20 4 17 ) ( 20 6 20 ) ( 20 7 25 ) 1983 2006 2008 DC1 1977 1999 2001 2004 2005 PD 2005 2007 2008 1945 1968 1974 1989 2004 DNA 1973 1996 2000 2006 2007