{"id":1117,"date":"2015-06-04T13:36:45","date_gmt":"2015-06-04T11:36:45","guid":{"rendered":"http:\/\/dan.thoeisen.dk\/hjem\/?p=1117"},"modified":"2015-06-04T13:56:51","modified_gmt":"2015-06-04T11:56:51","slug":"recommendation-system-in-php-using-matrix-factorization","status":"publish","type":"post","link":"https:\/\/dan.thoeisen.dk\/hjem\/recommendation-system-in-php-using-matrix-factorization\/","title":{"rendered":"Recommendation system in PHP using Matrix Factorization"},"content":{"rendered":"

A recommendation system, is a system that can predict a rating for a user-item pair, where this user has never interacted with the item before.<\/p>\n

In other words, is users of a user can give preferences for items\/products in the sense of a star system (1-5 stars like NetFlix) or a thumbs-up\/thumbs-down like YouTube, one can generate a rating matrix consisting of users and items. And each cell then has a rating value if the user has rated this particular item.<\/p>\n\n\n\n\n\n\n\n\n
User\/product matrix<\/td>\nJames<\/td>\nPeter<\/td>\nAnna<\/td>\nVictoria<\/td>\n<\/tr>\n
Blue pants<\/td>\n5<\/td>\n3<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Red hat<\/td>\n4<\/td>\n0<\/td>\n0<\/td>\n1<\/td>\n<\/tr>\n
Black shoes<\/td>\n1<\/td>\n1<\/td>\n0<\/td>\n5<\/td>\n<\/tr>\n
Computer mouse<\/td>\n1<\/td>\n0<\/td>\n0<\/td>\n4<\/td>\n<\/tr>\n
Yellow t-shirt<\/td>\n0<\/td>\n1<\/td>\n5<\/td>\n4<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

The table above, is called a ratings matrix, where a value above 0 is a rating defined by the user. A rating of 0 means the user has never encountered the product before.<\/p>\n

We now wish to calculate all the cells with 0’s – This is where Matrix Factorization is useful.
\nLet’s do some maths’<\/p>\n

We have a set of users \"U\" and a set of items \"D\". Let \"R\" of size \"|U| be the ratings matrix that the users have assigned their items. We want to discover \"K\" latent factors<\/p>\n

We now need to find two matrices \"P(a|U| and \"Q such that their product approximates \"R\":<\/p>\n

\"R<\/p>\n

So each row of \"P\" would represent the strength of the associations between a user and its factors. To get the prediction of a rating of an item \"d_j\" by \"u_i\" we can calculate the dot product of the two vectors corresponding to \"u_i\" and \"d_j\":<\/p>\n

\"\hat{r}_{ij}<\/p>\n

We just need to find \"P\" and \"Q\" – There exist several ways to do this.<\/p>\n

I’m going to use Gradient Descent – initialize the two matrices with some values, and calculate how different their product is to \"M\" and try to minimize the difference iteratively.<\/p>\n

The squared error can be calculated by:<\/p>\n

\"e_{ij}^2<\/p>\n

We want to minimize this error, and we want to know in which direction this error goes.<\/p>\n

\"\frac{d}{d
\n\"\frac{d}{d<\/p>\n

We now know in which direction to go, to minimize the error (i.e. the gradient) for both \"p_{ik}\" and \"q_{kj}\"<\/p>\n

\"p'_{ik}
\n\"q'_{kj}<\/p>\n

Where \"\alpha\" is a constant that determines the rate of approaching the minimum, and should be a small value like \"\alpha. If this value is too large we might step over the minimum, and maybe oscillating around the minimum.<\/p>\n

Using the above update rules we can iteratively perform the operation until a convergence.<\/p>\n

\"E<\/p>\n

Now we have the factorization done, which is fine. – We can although run into a problem with over-fitting the model.
\nTo avoid that, we introduce a regularization step:<\/p>\n

\"e_{ij}^2<\/p>\n

Where \"\beta\" is used to control the magnitudes of the user-factor and item-factor vector such that \"P\" and \"Q\" would give a good approximation of \"R\" without having to contain large numbers. In practice $latex $beta$ is set to some value in the range of \"0.02\"<\/p>\n

So the new update rules are:<\/p>\n

\"p'_{ik}
\n\"q'_{kj}<\/p>\n

<\/p>\n

Implementation in PHP<\/h3>\n