<jupyter_start><jupyter_text>CF Part 2 - User-based method> Collaborative Filtering on MovieLens Latest-small Part 2 - Finding recommendations using memory based user-user similarity method- toc: true- badges: true- comments: true- categories: [movie, collaborative]- image:  Download 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 sklearn.neighbors import NearestNeighbors
from scipy.sparse import csr_matrix

from recsys.datasets import ml100k
from recsys.preprocessing import ids_encoder

import pandas as pd
import numpy as np
import zipfile<jupyter_output><empty_output><jupyter_text>Load MovieLen ratings<jupyter_code>ratings, movies = ml100k.load()<jupyter_output><empty_output><jupyter_text>userids and itemids encoding<jupyter_code># create the encoder
ratings, uencoder, iencoder = ids_encoder(ratings)<jupyter_output><empty_output><jupyter_text>Transform rating dataframe to matrix<jupyter_code>def ratings_matrix(ratings):    
    return csr_matrix(pd.crosstab(ratings.userid, ratings.itemid, ratings.rating, aggfunc=sum).fillna(0).values)    

R = ratings_matrix(ratings)<jupyter_output><empty_output><jupyter_text>Memory based collaborative filtering (CF) also known as nearest neighbors based CF makes recommendation based on similar behavious of users and items. There are two types of memory based CF : user-based and item-based CF. Both of these algorithm usually proceed in three stages :1. Similarity computation (between users or items)2. Rating prediction (using ratings of similar users or items)3. Top-N recommendation  IdeaLet $u$ be the user for which we plan to make recommendations. 1. Find other users whose past rating behavior is similar to that of $u$2. Use their ratings on other items to predict what the current user will like  Algorithm : user-to-user collaborative filteringThe entire process of user-to-user CF algorithm is described as follow (<NAME> et al. 2013): For an active user $u$,     First identify the set $G_u$ of $k$ most similar users. $G_u$ is the group users similar to the active user $u$. The similarity between two users $u$ and $v$ can be measured by the cosine similarity measure as follows :\begin{equation} w_{u,v}=\frac{\vec{r}_u \cdot \vec{r}_v}{\|\vec{r}_u\|_2 \ast \|\vec{r}_v\|_2} = \frac{\sum_{i\in I}r_{u,i}r_{v,i}}{\sqrt{\sum_{i\in I} (r_{u,i})^2}\sqrt{\sum_{i\in I} (r_{v,i})^2}}\end{equation}$w_{u,v}$ is the degree of similarity between users $u$ and $v$. This term is computed for all $v\in U$, where $U$ is the set of all users. There remains the question of how many neighbors to select. As experimented by (Herlocker et al. 1999), $k\in [20,50]$ is a reasonable starting point in many domains.         Find the set $C$ of candidate items, purchased by the group and not purchased by the active user $u$. Candidate items have to be the most frequent items purchased by the group.        Aggregate ratings of users in $G_u$ to make predictions for user $u$ on items he has not already purchased. Several aggregation approaches are often used such as average, weighted sum, ajusted weighted sum. By using weighted sum, the predicted rating of user $u$ on item $i$ denoted by $\hat{r}_{u,i}$ is computed as follow :\begin{equation} \hat{r}_{u,i}=\bar{r}_u + \frac{\sum_{v\in G_u}(r_{v,i}-\bar{r}_v)\cdot w_{u,v}}{\sum_{v\in G_u}|w_{u,v}|}.\end{equation}Ratings of similar users are weighted by the corresponding similarity with the active user. Summation are made over all the users who have rated item $i$. Subtracting the user’s mean rating $\bar{r}_v$ compensates for differences in users’ use of the rating scale as some users will tend to give higher ratings than others (<NAME>, et al. 2011). This prediction is made for all items $i \in C$ not purchased by user $u$.        The Top-$N$ recommendations are obtained by choosing the $N$ items which provide most satisfaction to the user according to prediction.      Step 1. Identify $G_u$, the set of $k$ users similar to an active user $u$ To find the $k$ most similar users to $u$, we use the cosine similarity and compute $w_{u,v}$ for all $v\in U$. Fortunately, libraries such as scikit-learn (sklearn) are very useful for such tasks :1. First of all, we create a nearest neighbors model with sklearn through the function ```create_model()```. This function creates and fit a nearest neighbors model with user's ratings. We can choose ```cosine``` or ```euclidian``` based similarity metric. ```n_neighbors=21``` define the number of neighbors to return. With $k=20$ neighbors, $|G_u|=21$ as $G_u$ contains $20$ similar users added to the active user $u$. That is why ```n_neighbors=21```. Each row $r_u$ of the rating matrix $R$ represents ratings of user $u$ on all items of the database. Missing ratings are replaced with $0.0$. ```pythonR[u,:]  uth row of the rating matrix R. Ratings of user u on all items in the database```2. Function ```nearest_neighbors()``` returns the knn users for each user.<jupyter_code>def create_model(rating_matrix, metric):
    """
    - create the nearest neighbors model with the corresponding similarity metric
    - fit the model
    """
    model = NearestNeighbors(metric=metric, n_neighbors=21, algorithm='brute')
    model.fit(rating_matrix)    
    return model
def nearest_neighbors(rating_matrix, model):
    """    
    :param rating_matrix : rating matrix of shape (nb_users, nb_items)
    :param model : nearest neighbors model    
    :return
        - similarities : distances of the neighbors from the referenced user
        - neighbors : neighbors of the referenced user in decreasing order of similarities
    """    
    similarities, neighbors = model.kneighbors(rating_matrix)        
    return similarities[:, 1:], neighbors[:, 1:]<jupyter_output><empty_output><jupyter_text>Let's call functions ```create_model()``` and ```nearest_neighbors()``` to respectively create the $k$-NN model and compute the nearest neighbors for a given user<jupyter_code>model = create_model(rating_matrix=R, metric='cosine') # we can also use the 'euclidian' distance
similarities, neighbors = nearest_neighbors(R, model)<jupyter_output><empty_output><jupyter_text>Step 2. Find candidate items The set $C$ of candidate items are the most frequent ones purchased by users in $G_u$ for an active user $u$ and not purchased by $u$. Function ```find_candidate_items()``` : find items purchased by these similar users as well as their frequency. Note that the frequency of the items in the set $C$ can be computed by just counting the actual occurrence frequency of that items.1. ```Gu_items``` : frequent items of $G_u$ in decreasing order of frequency.2. ```active_items``` : items already purchased by the active user3. ```candidates``` : frequent items of $G_u$ not purchased by the active user $u$<jupyter_code>def find_candidate_items(userid):
    """
    Find candidate items for an active user
    
    :param userid : active user
    :param neighbors : users similar to the active user        
    :return candidates : top 30 of candidate items
    """
    user_neighbors = neighbors[userid]
    activities = ratings.loc[ratings.userid.isin(user_neighbors)]
    
    # sort items in decreasing order of frequency
    frequency = activities.groupby('itemid')['rating'].count().reset_index(name='count').sort_values(['count'],ascending=False)
    Gu_items = frequency.itemid
    active_items = ratings.loc[ratings.userid == userid].itemid.to_list()
    candidates = np.setdiff1d(Gu_items, active_items, assume_unique=True)[:30]
        
    return candidates<jupyter_output><empty_output><jupyter_text>Step 3. Rating prediction Now it's time to predict what score the active user $u$ would have given to each of the top-30 candidate items.To predict the score of $u$ on a candidate item $i$ ,we need :1. Similarities between $u$ and all his neighbors $v \in G_u$ who rated item $i$ : function ```nearest_neighbors()``` returns similar users of a user as well as their corresponding similarities.2. Normalized ratings of all $v \in G_u$ on item $i$. The normalized rating of user $v$ on item $i$ is defined by $r_{v,i}-\bar{r}_v$. Next, let's compute the mean rating of each user and the normalized ratings for each item. The DataFrame ```mean``` contains mean rating for each user. With the mean rating of each user, we can add an extra column ```norm_rating``` to the ```ratings```'s DataFrame which can be accessed to make predictions.<jupyter_code># mean ratings for each user
mean = ratings.groupby(by='userid', as_index=False)['rating'].mean()
mean_ratings = pd.merge(ratings, mean, suffixes=('','_mean'), on='userid')

# normalized ratings for each items
mean_ratings['norm_rating'] = mean_ratings['rating'] - mean_ratings['rating_mean']

mean = mean.to_numpy()[:, 1]
np_ratings = mean_ratings.to_numpy()<jupyter_output><empty_output><jupyter_text>Let us define function ```predict``` that predict rating between user $u$ and item $i$. Recall that the prediction formula is defined as follow :\begin{equation} \hat{r}_{u,i}=\bar{r}_u + \frac{\sum_{v\in G_u}(r_{v,i}-\bar{r}_v)\cdot w_{u,v}}{\sum_{v\in G_u}|w_{u,v}|}.\end{equation}<jupyter_code>def predict(userid, itemid):
    """
    predict what score userid would have given to itemid.
    
    :param
        - userid : user id for which we want to make prediction
        - itemid : item id on which we want to make prediction
        
    :return
        - r_hat : predicted rating of user userid on item itemid
    """
    user_similarities = similarities[userid]
    user_neighbors = neighbors[userid]
    # get mean rating of user userid
    user_mean = mean[userid]
    
    # find users who rated item 'itemid'
    iratings = np_ratings[np_ratings[:, 1].astype('int') == itemid]
    
    # find similar users to 'userid' who rated item 'itemid'
    suri = iratings[np.isin(iratings[:, 0], user_neighbors)]
    
    # similar users who rated current item (surci)
    normalized_ratings = suri[:,4]
    indexes = [np.where(user_neighbors == uid)[0][0] for uid in suri[:, 0].astype('int')]
    sims = user_similarities[indexes]
    
    num = np.dot(normalized_ratings, sims)
    den = np.sum(np.abs(sims))
    
    if num == 0 or den == 0:
        return user_mean
    
    r_hat = user_mean + np.dot(normalized_ratings, sims) / np.sum(np.abs(sims))
    
    return r_hat<jupyter_output><empty_output><jupyter_text>Now, we can make rating prediction for a given user on each item in his set of candidate items.<jupyter_code>def user2userPredictions(userid, pred_path):
    """
    Make rating prediction for the active user on each candidate item and save in file prediction.csv
    
    :param
        - userid : id of the active user
        - pred_path : where to save predictions
    """    
    # find candidate items for the active user
    candidates = find_candidate_items(userid)
    
    # loop over candidates items to make predictions
    for itemid in candidates:
        
        # prediction for userid on itemid
        r_hat = predict(userid, itemid)
        
        # save predictions
        with open(pred_path, 'a+') as file:
            line = '{},{},{}\n'.format(userid, itemid, r_hat)
            file.write(line)
import sys

def user2userCF():
    """
    Make predictions for each user in the database.    
    """
    # get list of users in the database
    users = ratings.userid.unique()
    
    def _progress(count):
        sys.stdout.write('\rRating predictions. Progress status : %.1f%%' % (float(count/len(users))*100.0))
        sys.stdout.flush()
    
    saved_predictions = 'predictions.csv'    
    if os.path.exists(saved_predictions):
        os.remove(saved_predictions)
    
    for count, userid in enumerate(users):        
        # make rating predictions for the current user
        user2userPredictions(userid, saved_predictions)
        _progress(count)
user2userCF()<jupyter_output>Rating predictions. Progress status : 99.9%<jupyter_text>Step 4. Top-N recommendationFunction ```user2userRecommendation()``` reads predictions for a given user and return the list of items in decreasing order of predicted rating.<jupyter_code>def user2userRecommendation(userid):
    """
    """
    # encode the userid
    uid = uencoder.transform([userid])[0]
    saved_predictions = 'predictions.csv'
    
    predictions = pd.read_csv(saved_predictions, sep=',', names=['userid', 'itemid', 'predicted_rating'])
    predictions = predictions[predictions.userid==uid]
    List = predictions.sort_values(by=['predicted_rating'], ascending=False)
    
    List.userid = uencoder.inverse_transform(List.userid.tolist())
    List.itemid = iencoder.inverse_transform(List.itemid.tolist())
    
    List = pd.merge(List, movies, on='itemid', how='inner')
    
    return List
user2userRecommendation(212)<jupyter_output><empty_output><jupyter_text>Let us make top n recommendation for a given user.  Evaluation with Mean Absolute Error (MAE)<jupyter_code>from recsys.preprocessing import train_test_split, get_examples

# get examples as tuples of userids and itemids and labels from normalize ratings
raw_examples, raw_labels = get_examples(ratings, labels_column='rating')

# train test split
(x_train, x_test), (y_train, y_test) = train_test_split(examples=raw_examples, labels=raw_labels)

def evaluate(x_test, y_test):
    print('Evaluate the model on {} test data ...'.format(x_test.shape[0]))
    preds = list(predict(u,i) for (u,i) in x_test)
    mae = np.sum(np.absolute(y_test - np.array(preds))) / x_test.shape[0]
    print('\nMAE :', mae)
    return mae
evaluate(x_test, y_test)<jupyter_output>Evaluate the model on 10000 test data ...

MAE : 0.7505910931068639<jupyter_text>SummaryWe have summarised all the steps of building the user-based collaborative filtering into a python class for further user. Click [UserToUser.py](https://github.com/nzhinusoftcm/review-on-collaborative-filtering/blob/master/recsys/memories/UserToUser.py) for more details on the **UserToUser** class definition.<jupyter_code>from recsys.memories.UserToUser import UserToUser

# load ml100k ratings
ratings, movies = ml100k.load()

# prepare data
ratings, uencoder, iencoder = ids_encoder(ratings)

# get examples as tuples of userids and itemids and labels from normalize ratings
raw_examples, raw_labels = get_examples(ratings, labels_column='rating')

# train test split
(x_train, x_test), (y_train, y_test) = train_test_split(examples=raw_examples, labels=raw_labels)
# create the user-based CF
usertouser = UserToUser(ratings, movies, metric='cosine')
# evaluate the user-based CF on the ml100k test data
usertouser.evaluate(x_test, y_test)<jupyter_output>Evaluate the model on 10000 test data ...

MAE : 0.7505910931068639<jupyter_text>Evaluation on the ML-1M dataset (this may take some time)<jupyter_code>from recsys.datasets import ml1m
from recsys.preprocessing import ids_encoder, get_examples, train_test_split
from recsys.memories.UserToUser import UserToUser

# load ml100k ratings
ratings, movies = ml1m.load()

# prepare data
ratings, uencoder, iencoder = ids_encoder(ratings)

# get examples as tuples of userids and itemids and labels from normalize ratings
raw_examples, raw_labels = get_examples(ratings, labels_column='rating')

# train test split
(x_train, x_test), (y_train, y_test) = train_test_split(examples=raw_examples, labels=raw_labels)

# create the user-based CF
usertouser = UserToUser(ratings, movies, k=20, metric='cosine')

# evaluate the user-based CF on the ml1m test data
print("==========================")
usertouser.evaluate(x_test, y_test)<jupyter_output>Normalize users ratings ...
Initialize the similarity model ...
Compute nearest neighbors ...
User to user recommendation model created with success ...
==========================
Evaluate the model on 100021 test data ...

MAE : 0.732267005840993
{'fraction_non_alphanumeric': 0.1061252240558749, 'fraction_numerical': 0.012608937511589096, 'mean_word_length': 4.455158462575859, 'pattern_counts': {'":': 0, '<': 59, '<?xml version=': 0, '>': 60, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '398274', 'license': 'Apache-2.0', 'n_tokens_mistral': 5096, 'n_tokens_neox': 4866, 'n_words': 1703, 'path': '_notebooks/2021-06-23-collaborative-filtering-movielens-latest-small-02.ipynb', 'repo_name': 'recohut/notebook', 'size': '16198'}