IPSJ-TOM

Size: px

Start display at page:

Download "IPSJ-TOM"

さやなさわなか
6 years ago
Views:

1 Vol. 2 No (Mar. 2009) 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 c 2009 Information Processing Society of Japan

2 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) 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 ).

3 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 α = 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 ) 2 ( <s i,j ) = 3 ( <s i,j ), (2) 4 ( <s i,j ) 5 ( <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 = A D 1 N user N item p i v i A B 1 C

4 50 1 Fig. 1 Simulation process. utility average D C t t A 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 Σ μ 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, Σ v j p i

5 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

6 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 CF CF 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 t = r t = r (a) CF CF N user 3(b) N user

7 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 CF CF N user =500 N item =500 p i 4 4 t CF 4 CF CF CF

8 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 (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 CF CF N item = 500 p i N user = {100, 500, 1000, 2000} 5 CF

9 N user 5(b) (d) CF 2 CF N user CF CF 2 2 CF CF t =30 2 CF CF t =10 2 CF CF 6 CF t =30 CF % CF CF t = p i N user = 500 N item = 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 = t =30 CF

10 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 (1997). 2) Schafer, J.B., et al.: E-Commerce recommendation applications, Data Mining and Knowledge Discovery, Vol.5, No.1-2, pp (2001). 3) Linden, G., et al.: Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, Vol.7, No.1, pp (2003). 4) Goldberg, D., et al.: Using Collaborative Filtering to Weave an Information Tapestry, Comm. ACM, Vol.35, No.12, pp (1992). 5) Resnick, P., et al.: GroupLens: An Open Architecture for Collaborative Filtering of Netnews, Proc. CSCW 94, ACM, pp (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 (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 (2005). 9) Vol.J90-D, No.2, pp (2007). 10) Breese, J.S., et al.: Empirical Analysis of Predictive Algorithms for Collaborative Filtering, Proc. 14th Conference on UAI 98, pp (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.

2nd ACM conference on Electronic commerce, pp.158 167 (2000). 15) Herlocker, J.L.

: An Empirical Analysis of Design Choices in Neighborhood- Based Collaborative

11 57 13) DEWS2007 (2007). 14) Sarwar, B., et al.: Analysis of Recommendation Algorithms for E-Commerce, Proc. 2nd ACM conference on Electronic commerce, pp (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 (2002). 16) 6 FIT2007 (2007). 17) Sarwar, B., et al.: Item-based Collaborative Filtering Recommendation Algorithms, Proc. WWW 01, pp (2001). ( ) ( ) ( ) DC PD DNA

TA3-4 31st Fuzzy System Symposium (Chofu, September 2-4, 2015) Interactive Recommendation System LeonardoKen Orihara, 1 Tomonori Hashiyama, 1

TA3-4 31st Fuzzy System Symposium (Chofu, September 2-4, 2015) Interactive Recommendation System LeonardoKen Orihara, 1 Tomonori Hashiyama, 1 Interactive Recommendation System 1 1 1 1 LeonardoKen Orihara, 1 Tomonori Hashiyama, 1 Shun ichi Tano 1 1 Graduate School of Information Systems, The University of Electro-Communications Abstract: The