(2012 rev.1.23) Web DVD 1 1 DVD SF DVD ( ) ( ) ( ) DVD 0.2 ( ) ( ) ( ) amazon.com (MovieLens) (Resnick et al., 1994) 1

Size: px

Start display at page:

Download "(2012 rev.1.23) Web DVD 1 1 DVD SF DVD ( ) ( ) ( ) DVD 0.2 ( ) ( ) ( ) amazon.com (MovieLens) (Resnick et al., 1994) 1"

みさえかんけ
4 years ago
Views:

1 (2012 rev.1.23) Web DVD 1 1 DVD SF DVD ( ) ( ) ( ) DVD 0.2 ( ) ( ) ( ) amazon.com (MovieLens) (Resnick et al., 1994) 1

2 0.3 optional 1 ( ) ( ) ( ) java java eclipse javadoc api ( ) 0.4 wiki T-10 PT2012.,. wiki, java. java., java Wiki. ( 1-1, 1-2, 1-3),,,,.,. ( 2 ),,.,. (,,,,,, ). 1 optional 2

3 ( ). /., 0.6 wiki. 1 MovieLens (exp data) movies.dat nuser train Ratings.dat nuser test Ratings.dat n {10, 100, 200,..., 1600} wiki. 10User train Ratings.dat, 10User test Ratings.dat,.,. 1.1 movies.dat movies.dat 3952 MovieID::Title::Genre1 Genre2... GenreK movieid :: Title : ( MovieID=19, Ace Ventura: When Nature Calls (1995)) movieid, , MovieID ( ) 1::Toy Story (1995)::Animation Children s Comedy 2::Jumanji (1995)::Adventure Children s Fantasy 3::Grumpier Old Men (1995)::Comedy Romance ::Two Family House (2000)::Drama 3952::Contender, The (2000)::Drama Thriller 3

4 1.2 nuser train ratings.dat, nuser test ratings.dat nuser train ratings.dat, nuser test ratings.dat (rating) UserID::MovieID::Rating::Timestamp nuser train ratings.dat, nuser test ratings.dat, UserID 1 n Rating 1 5 Timestamp timestamp, 1 1::1193::5::timestamp 1::661::3::timestamp 1::914::3::timestamp 1::3408::4::timestamp... UserID 1 MovideID=1193(One Flew Over the Cuckoo s Nest (1975)) Rating= : Users train ratings.dat 1. UserID MovieID, MovieID UserID Rating 1-2 movies.dat, MovieID. ( ),. movies.dat,, ( ),, (OS, ),. (cput time). 2. MovieID1 10, MovieID Title 4

5 3., ,., movies.dat /,. 1-3 nusers train ratings.dat(n = 100,..., 1600) 1. MovieID UserID Rating ( UserID ) 2. UserID MovieID Rating ( MovieID ) 3. UserID MovieID Rating ( MovieID ) 4. MovieID UserID Rating ( UserID ),. 1-2 nusers-train-ratings.dat, UserID=1 UserID=5 MovieID Title 3. MovieID=1 MovieID=5 UserID Title , N = 100,..., (1-2-5 ) , N, ( ) M,,., nusers train ratings.dat /,. nusers train ratings.dat , UserID=i, MovieID=j Rating S[i][j],., S[i][j] Rating. ( ) for-loop 5

6 2 (Group Lens ) (Resnick et al., 1994)(Herlocker et al., 1999) Group Lens John Riedl 3 GroupLens A B A B A B ( ) A B v A ( ) 2.1 N (i = 1,..., N) M (k = 1,..., M) i k s ik {1, 2, 3, 4, 5} i I i {1,..., M} k U k {1,..., N} (i, k) R i k, s ik ( k I i, s ik ) i s i s i = k I i s ik I i i j ( ).,. r ij = (2.1) k I i I j (s ik s i )(s jk s j ) k Ii Ij (s ik s i ) 2 k Ii Ij (s jk s j ) 2 (2.2), r ij = 0 : 1. I i I j 1 ( ) 2. k I i I j (s ik s i ) 2 = 0 k I i I j (s jk s j ) 2 = 0 ( ) 3 6

7 2.2 Rating i j Rating s ik (k I i ) Rating ŝ ik (k I i ). ŝ ik = s i + j U k \{i} r ij(s jk s j ) j U k \{i} r ij (2.3) j U k \{i} r ij(s jk s j ) j U k \{i} r = 0 (2.4) ij U k \ {i} = 0 (, k i ) j U k \{i} r ij = 0 ( ) 2.3 Rating (nuser train ratings.dat) r ij (nuser test ratings.dat) UserID MovieID Rating ŝ ik,, UserID, MovieID, Rating s ik.,, UserID (i ) MovieID (k ) Rating ( s ik, ). Rating ŝ ik Rating s ik (, mean squared error) MSE(R) = 1 R (s ij ŝ ij ) 2 (2.5) (i,j) R Rating User train ratings.dat (100User similarities.dat) i j User similarities.dat, UserID, MovieID, 2.3, UserID, MovieID Rating 2-3 n = 100,..., nuser train ratings.dat,, 7

8 2. nuser test ratings.dat, UserID MovieID Rating, 3. MSE n n = 10 (Sample ) , UserID 1 10, (test ) Rating ( ). n = 100,..., ,,. MSE 2-3 ŝ ik = s i + j [U k i p ] r ij(s jk s j ) j [U k i p ] r ij (2.6) Rating 1. Rating 2. 8

9 3 2 ( ) 20% ( ) AKB48,, , 4. ( ) movies.dat (Comedy, Romance). 9

10 ( ) (Paterek, 2007) 4.1 N M S K < M, K < N K. U K N, V K M. S U, V. S U T V (4.1) i j (i, j) R., (i, j) R (i, j) R, ŝ ij = u T i v j (4.2). u i U i, v j V j.,,. S R N M S = U T V (U, V ) ( ). LU,. ( ). (N = 1600, M = 4000),,, ( ). 4.1 S, full-rank,, : 4.2, O(K) N = 1600, M = 4000,,. rank,, rank K, 10

11 4.2 U, V 4.1 U, V?. 1. U, V ( ) 2. S U T V U, V, U, V S U T V, (i, j) R (i, j) e ij = s ij ŝ ij = s ij u i T v j (4.3)., S U T V MSE(R, U, V ) = 1 (s ij ŝ ij ) R 2 (4.4). (i,j) R U, V, (U, V ) = arg min MSE(R, U, V ) (4.5) (U,V ). MSE(R, U, V ) U, V. MSE u i MSE 2 u i = u i ( 1 R (i,j) R. (i, j) k u ki. ( u ki (i,j) R v j k v kj. (s ij u i T v j ) 2) (4.6) 1 R (s ij u i T v j ) 2) = (s ij u i T v j )v kj (4.7) = 1 R e ijv kj (4.8) (4.9) = 1 v kj R e iju ki (4.10), MSE(R, U, V ) U, V.. 1 R., η. u ki u ki + ηe ij v kj (4.11) v kj v kj + ηe ij u ki (4.12) 4.3,. 11

12 : N M S, η : K N U K M V 1. ( ) U, V, [0, 1]. t = (i, j) R (a) k = 1,..., K i u ki u ki + ηe ij v kj ii v kj v kj + ηe ij u ki 3. MSE, t t + 1 step 2 4. MSE, U U, V V, U, V 4.4 U, V s ij ŝ ij = u T i v j. (4.13),,, k v j, u T i v j. 4.5, S,, K,., U, V., u i u T i u i v j v T j v j. rmse 2 = 1 2 (s ij u T i v j ) 2 + λσ N i=1u T i u i + λσ M j=1v T j v j (4.14) (i,j) R rmse 2. rmse 2 u ki = e ij v kj + λu ki (4.15) rmse 2 v kj = e ij u ki + λv kj (4.16), rmse U, V. u ki u ki + η(e ij v kj λu ik ) (4.17) v kj v kj + η(e ij u ki λv kj ). (4.18), 4.3 step 2(a), 4.18,

13 User train ratings.dat k S,, U, V U, V 4-2 U, V, UserID, MovieID, 4.13, UserID, MovieID Rating 4 1. η = 0.01, n {100, 200, 400, 800, 1600}, K [2, 50], λ [0.01, 1] test MSE. (λ = 0), (λ > 0) 2., η, η., η. References Herlocker, J., Konstan, J., Borchers, A., & Riedl, J. (1999). An algorithmic framework for performing collaborative filtering. Proceedings of the 1999 ACM conference on Research and development in information retrieval (pp ). Paterek, A. (2007). Improving regularized singular value decomposition for collaborative filtering. Proceedings of KDD Cup and Workshop. Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., & Riedl, J. (1994). GroupLens: an open architecture for collaborative filtering of netnews. Proceedings of the 1994 ACM conference on Computer supported cooperative work (pp ). 13

IPSJ-TOM

IPSJ-TOM 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