<jupyter_start><jupyter_text>CF Part 4 - SVD method> Collaborative Filtering on MovieLens Latest-small Part 4 - Finding recommendations using model based singular value decomposition (SVD) method- toc: true- badges: true- comments: true- categories: [movie, collaborative]- image: Due to the high level sparsity of the rating matrix $R$, **user-based** and **item-based** collaborative filtering suffer from **data sparsity** and **scalability**. These cause user and item-based collaborative filtering to be less effective and highly affect their performences. To address the high level sparsity problem, [Sarwar et al. (2000)](http://files.grouplens.org/papers/webKDD00.pdf) proposed to reduce the dimensionality of the rating $R$ using the *Singular Value Decomposition (SVD)* algorithm.--- How do SVD works ?As described is Figure 1, SVD factors the rating matrix $R$ of size $m\times n$ into three matrices $P$, $\Sigma$ and $Q$ as follows :\begin{equation}R = P\Sigma Q^{\top}.\end{equation}Here, $P$ and $Q$ are two orthogonal matrices of size $m\times \hat{k}$ and $n\times \hat{k}$ respectively and $\Sigma$ is a diagonal matrix of size $ \hat{k}\times \hat{k}$ (with $ \hat{k}$ the rank of matrix $R$) having all singular values of the rating matrix R as its diagonal entries ([Billsus and Pazzani, 1998](https://www.ics.uci.edu/~pazzani/Publications/MLC98.pdf), [Sarwar et al. (2000)](http://files.grouplens.org/papers/webKDD00.pdf)).![](https://github.com/nzhinusoftcm/review-on-collaborative-filtering/blob/master/recsys/img/svd.png?raw=1) Figure 1 : Singular value decomposition of rating matrix $R$ After having choosen $k$, the dimension of factors that will represent users and items, we can truncate matrix $\Sigma$ by only retaining its $k$ largest singular values to yield $\Sigma_k$ and reduce matrices $P$ and $Q$ accordingly to obtain $P_k$ and $Q_k$. The rating matrix will then be estimated as \begin{equation}R_k = P_k\Sigma_k Q_k^{\top}.\end{equation}Once these matrices are known, they can be used for rating predictions ant top-N recommendations. $P_k\Sigma_k^{\frac{1}{2}}$ represents the latent space of users and $\Sigma_k^{\frac{1}{2}}Q_k^{\top}$ the latent space of items. Rating prediction for user $u$ on $i$ is done by the following formular\begin{equation}\hat{R}_{u,i} = \begin{bmatrix}P_k\Sigma_k^{\frac{1}{2}}\end{bmatrix}_u \begin{bmatrix}\Sigma_k^{\frac{1}{2}}Q_k^{\top}\end{bmatrix}_i.\end{equation}Before applying SVD, its important to fill in missing values of the rating matrix $R$. [Sarwar et al. (2000)](http://files.grouplens.org/papers/webKDD00.pdf) found the item’s mean rating to be useful default values. The user's average rating can also be used but the former shown better performances. Adding ratings normalization by subtracting the user mean rating or other baseline predictor can improve accuracy.--- SVD algorithm> 1. Factor the normalize rating matrix $R_{norm}$ to obtain matrices $P$, $\Sigma$ and $Q$> 2. Reduce $\Sigma$ to dimension $k$ to obtain $\Sigma_k$> 3. Compute the square-root of $\Sigma_k$ to obtain $\Sigma_k^{\frac{1}{2}}$> 4. Compute the resultant matrices $P_k\Sigma_k^{\frac{1}{2}}$ and $\Sigma_k^{\frac{1}{2}}Q_k^{\top}$ that will be used to compute recommendation scores for any user and items.--- Implementation detailsSVD can easily be implemented using python library such as ```numpy```, ```scipy``` or ```sklearn```. As described by <NAME> in his [Machine Learning course](https://www.coursera.org/learn/machine-learning/lecture/CEXN0/vectorization-low-rank-matrix-factorization), it's not recommended to implement the standard SVD by ourselves. Instead, we can take advantage of matrix libraries (such as those listed before) that are optimized for matrix computations and vectorization.Now let's implement the SVD collaborative filtering  Download useful tools<jupyter_code>import os

if not (os.path.exists("recsys.zip") or os.path.exists("recsys")):
    !wget https://github.com/nzhinusoftcm/review-on-collaborative-filtering/raw/master/recsys.zip    
    !unzip recsys.zip<jupyter_output><empty_output><jupyter_text>Import requirements```matplotlib==3.2.2numpy==1.19.2pandas==1.0.5python==3.7scikit-learn==0.24.1scikit-surprise==1.1.1scipy==1.6.2```<jupyter_code>from recsys.datasets import mlLastedSmall, ml100k, ml1m
from sklearn.preprocessing import LabelEncoder
from scipy.sparse import csr_matrix

import pandas as pd
import numpy as np
import os<jupyter_output><empty_output><jupyter_text>Loading movielen ratings<jupyter_code>ratings, movies = mlLastedSmall.load()<jupyter_output><empty_output><jupyter_text>Let's see how our rating matrix looks like<jupyter_code>pd.crosstab(ratings.userid, ratings.itemid, ratings.rating, aggfunc=sum)<jupyter_output><empty_output><jupyter_text>We can observe that our rating matrix has many of unobserved value. However, as we described earlier, the SVD algorithm requires that all inputs in the matrix must be defined. Let's initialize the unobserved ratings with item's average that led to better performances compared to the user's average or even a null initialization ([Sarwar et al. (2000)](http://files.grouplens.org/papers/webKDD00.pdf)).We can go further and subtrat from each rating the corresponding user mean to normalize the data. This helps to improve the accuracy of the model.<jupyter_code># get user's mean rating
umean = ratings.groupby(by='userid')['rating'].mean()
def rating_matrix(ratings):
    """
    1. Fill NaN values with item's average ratings
    2. Normalize ratings by subtracting user's mean ratings
    
    :param ratings : DataFrame of ratings data
    :return
        - R : Numpy array of normalized ratings
        - df : DataFrame of normalized ratings
    """
    
    # fill missing values with item's average ratings
    df = pd.crosstab(ratings.userid, ratings.itemid, ratings.rating, aggfunc=sum)
    df = df.fillna(df.mean(axis=0))
    
    # subtract user's mean ratings to normalize data
    df = df.subtract(umean, axis=0)
    
    # convert our dataframe to numpy array
    R = df.to_numpy()
    
    return R, df

# generate rating matrix by calling function rating_matrix
R, df = rating_matrix(ratings)<jupyter_output><empty_output><jupyter_text>$R$ is our final rating matrix. This is how the final rating matrix looks like<jupyter_code>df<jupyter_output><empty_output><jupyter_text>Ids encodingLet's encode users and items ids such that their values range from 0 to 909 (for users) and from 0 to 9723 (for items)<jupyter_code>users = sorted(ratings['userid'].unique())
items = sorted(ratings['itemid'].unique())

# create our id encoders
uencoder = LabelEncoder()
iencoder = LabelEncoder()

# fit our label encoder
uencoder.fit(users)
iencoder.fit(items)<jupyter_output><empty_output><jupyter_text>SVD AlgorithmNow that our rating data has been normalize and that missing values has been filled, we can apply the SVD algorithm. Several libraries may be useful such as ```numpy```, ```scipy```, ```sklearn```, ... Let's try it with ```numpy```.In our SVD class we provide the following function :1. ```fit()``` : compute the svd of the rating matrix and save the resultant matrices P, S and Qh (Q transpose) as attributs of the SVD class.2. ```predict()```: use matrices P, S and Qh to make ratin prediction for a given $u$ user on an item $i$. Computations are made over encoded values of userid and itemid. The predicted value is the dot product between $u^{th}$ row of $P.\sqrt{S}$ and the $i^{th}$ column of $\sqrt{S}.Qh$. **Note** that since we normalized rating before applying SVD, the predicted value will also be normalize. So, to get the final predicted rating, we have to add to the predicted value the mean rating of user $u$.3. ```recommend()```: use matrices P, S and Qh to make recommendations to a given user. The recommended items are those that where not rated by the user and received a high score according to the svd model.<jupyter_code>class SVD:
    
    def __init__(self, umeam):
        """
        :param
            - umean : mean ratings of users
        """
        self.umean = umean.to_numpy()
        
        # init svd resultant matrices
        self.P = np.array([])
        self.S = np.array([])
        self.Qh = np.array([])
        
        # init users and items latent factors
        self.u_factors = np.array([])
        self.i_factors = np.array([])
    
    def fit(self, R):
        """
        Fit the SVD model with rating matrix R
        """
        P, s, Qh = np.linalg.svd(R, full_matrices=False)
        
        self.P = P
        self.S = np.diag(s)
        self.Qh = Qh
        
        # latent factors of users (u_factors) and items (i_factors)
        self.u_factors = np.dot(self.P, np.sqrt(self.S))
        self.i_factors = np.dot(np.sqrt(self.S), self.Qh)
    
    def predict(self, userid, itemid):
        """
        Make rating prediction for a given user on an item
        
        :param
            - userid : user's id
            - itemid : item's id
            
        :return
            - r_hat : predicted rating
        """
        # encode user and item ids
        u = uencoder.transform([userid])[0]
        i = iencoder.transform([itemid])[0]
        
        # the predicted rating is the dot product between the uth row 
        # of u_factors and the ith column of i_factors
        r_hat = np.dot(self.u_factors[u,:], self.i_factors[:,i])
        
        # add the mean rating of user u to the predicted value
        r_hat += self.umean[u]
        
        return r_hat
        
    
    def recommend(self, userid):
        """
        :param
            - userid : user's id
        """
        # encode user
        u = uencoder.transform([userid])[0]
        
        # the dot product between the uth row of u_factors and i_factors returns
        # the predicted value for user u on all items        
        predictions = np.dot(self.u_factors[u,:], self.i_factors) + self.umean[u]
        
        # sort item ids in decreasing order of predictions
        top_idx = np.flip(np.argsort(predictions))

        # decode indices to get their corresponding itemids
        top_items = iencoder.inverse_transform(top_idx)
        
        # sorted predictions
        preds = predictions[top_idx]
        
        return top_items, preds<jupyter_output><empty_output><jupyter_text>Now let's create our SVD model and provide to it user's mean rating; Fit the model with the normalized rating matrix $R$.<jupyter_code># create our svd model
svd = SVD(umean)

# fit our model with normalized ratings
svd.fit(R)<jupyter_output><empty_output><jupyter_text>Rating predictionOur model has been fitted.OK ...Let's make some predictions for users using function ```predict``` of our SVD class. Here are some truth ratings<jupyter_code>ratings.head(10)<jupyter_output><empty_output><jupyter_text>Let's apply our model to make see if our predictions make sens. We will make predictions for user 1 on the 10 items listed above.<jupyter_code># user for which we make predictions
userid = 1

# list of items for which we are making predictions for user 1
items = [1,3,6,47,50,70,101,110,151,157]

# predictions
for itemid in items:
    r = svd.predict(userid=userid, itemid=itemid)
    print('prediction for userid={} and itemid={} : {}'.format(userid, itemid, r))<jupyter_output>prediction for userid=1 and itemid=1 : 4.000000000000007
prediction for userid=1 and itemid=3 : 4.0000000000000036
prediction for userid=1 and itemid=6 : 3.9999999999999885
prediction for userid=1 and itemid=47 : 5.000000000000003
prediction for userid=1 and itemid=50 : 4.9999999999999964
prediction for userid=1 and itemid=70 : 2.9999999999999893
prediction for userid=1 and itemid=101 : 5.000000000000002
prediction for userid=1 and itemid=110 : 3.999999999999993
prediction for userid=1 and itemid=151 : 5.000000000000007
prediction for userid=1 and itemid=157 : 5.000000000000019<jupyter_text>Our prediction error is less than 0.00001  Make recommendationsThe ```recommend``` function makes recommendations for a given user.<jupyter_code>userid = 1

# items sorted in decreasing order of predictions for user 1
sorted_items, preds = svd.recommend(userid=userid)

##
# Now let's exclud from that sorted list items already purchased by the user
##

# list of items rated by the user
uitems = ratings.loc[ratings.userid == userid].itemid.to_list()

# remove from sorted_items items already in uitems and pick the top 30 ones
# as recommendation list
top30 = np.setdiff1d(sorted_items, uitems, assume_unique=True)[:30]

# get corresponding predictions from the top30 items
top30_idx = list(np.where(sorted_items == idx)[0][0] for idx in top30)
top30_predictions = preds[top30_idx]

# find corresponding movie titles
zipped_top30 = list(zip(top30,top30_predictions))
top30 = pd.DataFrame(zipped_top30, columns=['itemid','predictions'])
List = pd.merge(top30, movies, on='itemid', how='inner')

# show the list
List<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10337926256639211, 'fraction_numerical': 0.02778846894003541, 'mean_word_length': 3.932422171602126, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 54, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 10, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '517368', 'license': 'Apache-2.0', 'n_tokens_mistral': 4223, 'n_tokens_neox': 3873, 'n_words': 1411, 'path': '_notebooks/2021-06-23-collaborative-filtering-movielens-latest-small-04.ipynb', 'repo_name': 'recohut/notebook', 'size': '12994'}