<jupyter_start><jupyter_text>CF Part 3 - Item-based method> Collaborative Filtering on MovieLens Latest-small Part 3 - Finding recommendations using memory based item-item similarity method- toc: true- badges: true- comments: true- categories: [movie, collaborative]- image:  IdeaLet $u$ be the active user and $i$ the referenced item1. If $u$ liked items similar to $i$, he will probably like item $i$.2. If he hated or disliked items similar to $i$, he will also hate item $i$.The idea is therefore to look at how an active user $u$ rated items similar to $i$ to know how he would have rated item $i$  Advantages over user-based CF1.  Stability  : Items ratings are more stable than users ratings. New ratings on items are unlikely to significantly change the similarity between two items, particularly when the items have many ratings (<NAME>, et al. 2011). 2.  Scalability  : with stable item's ratings, it is reasonable to pre-compute similarities between items in an item-item similarity matrix (similarity between items can be computed offline). This will reduce the scalability concern of the algorithm. (Sarwar et al. 2001), (<NAME>, et al. 2011).  Algorithm : item-to-item collaborative filteringThe algorithm that defines item-based CF is described as follow (B. Sarwar et al. 2001)(<NAME> 2001) :            First identify the $k$ most similar items for each item in the catalogue and record the corresponding similarities. To compute similarity between two items we can user the Adjusted Cosine Similarity that has proven to be more efficient than the basic Cosine similarity measure used for user-based collaborative as described in (B. Sarwar et al. 2001). The Adjusted Cosine distance between two items $i$ and $j$ is computed as follow\begin{equation} w_{i,j}= \frac{\sum_{u\in U}(r_{u,i}-\bar{r}_u)(r_{u,j}-\bar{r}_u)}{\sqrt{\sum_{u\in U} (r_{u,i}-\bar{r}_u)^2}\sqrt{\sum_{u\in U} (r_{u,j}-\bar{r}_u)^2}}\end{equation}$w_{i,j}$ is the degree of similarity between items $i$ and $j$. This term is computed for all users $u\in U$, where $U$ is the set of users that rated both items $i$ and $j$. Let's denote by $S^{(i)}$ the set of the $k$ most similar items to item $i$.             To produce top-N recommendations for a given user $u$ that has already purchased a set $I_u$ of items, do the following :     Find the set $C$ of candidate items by taking the union of all $S^{(i)}, \forall i\in I_u$ and removing each of the items in the set $I_u$.\begin{equation} C = \bigcup_{i\in I_u}\{S^{(i)}\}\smallsetminus I_u\end{equation}                $\forall c\in C$, compute similarity between c and the set $I_u$ as follows:\begin{equation} w_{c,I_u} = \sum_{i\in I_u} w_{c,i}, \forall c \in C\end{equation}                Sort items in $C$ in decreasing order of $w_{c,I_u}, \forall c \in C$, and return the first $N$ items as the Top-N recommendation list.             Before returning the first $N$ items as top-N recommendation list, we can make predictions about what user $u$ would have given to each items in the top-N recommendation list, rearrange the list in descending order of predicted ratings and return the rearranged list as the final recommendation list. Rating prediction for item-based CF is given by the following formular (B. Sarwar et al. 2001):\begin{equation} \hat{r}_{u,i}=\frac{\sum_{i\in S^{(i)}}r_{u,j}\cdot w_{i,j}}{\sum_{j\in S^{(i)}}|w_{i,j}|}\end{equation}  Import useful requirements<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 ml1m, ml100k
from recsys.preprocessing import ids_encoder

import pandas as pd
import numpy as np
import os
import sys<jupyter_output><empty_output><jupyter_text>Load 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>Let's implements the item-based collaborative filtering algorithm described above  Step 1. Find similarities for each of the items To compute similarity between two items $i$ and $j$, we need to :1. find all users who rated both of them,2. Normalize their ratings on items $i$ and $j$3. Apply the cosine metric to the normalized ratings to compute similarity between $i$ and $j$ Function ```normalize()``` process the rating dataframe to normalize ratings of all users<jupyter_code>def normalize():
    # compute mean rating for each user
    mean = ratings.groupby(by='userid', as_index=False)['rating'].mean()
    norm_ratings = pd.merge(ratings, mean, suffixes=('','_mean'), on='userid')
    
    # normalize each rating by substracting the mean rating of the corresponding user
    norm_ratings['norm_rating'] = norm_ratings['rating'] - norm_ratings['rating_mean']
    return mean.to_numpy()[:, 1], norm_ratings
mean, norm_ratings = normalize()
np_ratings = norm_ratings.to_numpy()
norm_ratings.head()<jupyter_output><empty_output><jupyter_text>now that each rating has been normalized, we can represent each item by a vector of its normalized ratings<jupyter_code>def item_representation(ratings):    
    return csr_matrix(
        pd.crosstab(ratings.itemid, ratings.userid, ratings.norm_rating, aggfunc=sum).fillna(0).values
    )
R = item_representation(norm_ratings)<jupyter_output><empty_output><jupyter_text>Let's build and fit our $k$-NN model using sklearn<jupyter_code>def create_model(rating_matrix, k=20, metric="cosine"):
    """
    :param R : numpy array of item representations
    :param k : number of nearest neighbors to return    
    :return model : our knn model
    """    
    model = NearestNeighbors(metric=metric, n_neighbors=k+1, algorithm='brute')
    model.fit(rating_matrix)    
    return model<jupyter_output><empty_output><jupyter_text>Similarities computation Similarities between items can be measured with the *Cosine* or *Eucliedian* distance. The ***NearestNeighbors*** class from the sklearn library simplifies the computation of neighbors. We just need to specify the metric (e.g. cosine or euclidian) that will be used to compute similarities.The above method, ```create_model```, creates the kNN model and the following ```nearest_neighbors``` method uses the created model to kNN items. It returns nearest neighbors as well as similarities measures for each items.```nearest_neighbors``` returns :- ```similarities``` : numpy array of shape $(n,k)$- ```neighbors``` : numpy array of shape $(n,k)$where $n$ is the total number of items and $k$ is the number of neighbors to return, specified when creating the kNN model.<jupyter_code>def nearest_neighbors(rating_matrix, model):
    """
    compute the top n similar items for each item.    
    :param rating_matrix : items representations
    :param model : nearest neighbors model    
    :return similarities, neighbors
    """    
    similarities, neighbors = model.kneighbors(rating_matrix)    
    return similarities[:,1:], neighbors[:,1:]<jupyter_output><empty_output><jupyter_text>Ajusted Cosine SimilarityIn the context of item-based collaborative filtering, the adjusted cosine similarity has shown to be more efficient that the cosine or the euclidian distance. Here is the formular to compute the adjusted cosine weight between two items $i$ and $j$ : \begin{equation} w_{i,j}= \frac{\sum_{u\in U}(r_{u,i}-\bar{r}_u)(r_{u,j}-\bar{r}_u)}{\sqrt{\sum_{u\in U} (r_{u,i}-\bar{r}_u)^2}\sqrt{\sum_{u\in U} (r_{u,j}-\bar{r}_u)^2}}.\end{equation} This term is computed for all users $u\in U$, where $U$ is the set of users that rated both items $i$ and $j$. Since the *sklearn* library do not directly implement the adjusted cosine similarity metric, we will implement it with the method ```adjusted_cosine```, with some helper function :- ```save_similarities``` : since the computation of the adjusted cosine similarity is time consuming, around 5 mins for the ml100k dataset, we use this method to save the computed similarities for lated usage.- ```load_similarities``` : load the saved similarities- ```cosine``` : cosine distance between two vectors.<jupyter_code>def save_similarities(similarities, neighbors, dataset_name):    
    base_dir = 'recsys/weights/item2item'
    save_dir = os.path.join(base_dir, dataset_name)
    os.makedirs(save_dir, exist_ok=True)    
    similarities_file_name = os.path.join(save_dir, 'similarities.npy')
    neighbors_file_name = os.path.join(save_dir, 'neighbors.npy')    
    try:
        np.save(similarities_file_name, similarities)
        np.save(neighbors_file_name, neighbors)        
    except ValueError as error:
        print(f"An error occured when saving similarities, due to : \n ValueError : {error}")

        
def load_similarities(dataset_name, k=20):
    base_dir = 'recsys/weights/item2item'
    save_dir = os.path.join(base_dir, dataset_name)    
    similiraties_file = os.path.join(save_dir, 'similarities.npy')
    neighbors_file = os.path.join(save_dir, 'neighbors.npy')    
    similarities = np.load(similiraties_file)
    neighbors = np.load(neighbors_file)    
    return similarities[:,:k], neighbors[:,:k]


def cosine(x, y):
    return np.dot(x, y) / (np.linalg.norm(x) * np.linalg.norm(y))


def adjusted_cosine(np_ratings, nb_items, dataset_name):
    similarities = np.zeros(shape=(nb_items, nb_items))
    similarities.fill(-1)
    
    def _progress(count):
        sys.stdout.write('\rComputing similarities. Progress status : %.1f%%' % (float(count / nb_items)*100.0))
        sys.stdout.flush()
        
    items = sorted(ratings.itemid.unique())    
    for i in items[:-1]:
        for j in items[i+1:]:            
            scores = np_ratings[(np_ratings[:, 1] == i) | (np_ratings[:, 1] == j), :]
            vals, count = np.unique(scores[:,0], return_counts = True)
            scores = scores[np.isin(scores[:,0], vals[count > 1]),:]

            if scores.shape[0] > 2:
                x = scores[scores[:, 1].astype('int') == i, 4]
                y = scores[scores[:, 1].astype('int') == j, 4]
                w = cosine(x, y)

                similarities[i, j] = w
                similarities[j, i] = w
        _progress(i)
    _progress(nb_items)
    
    # get neighbors by their neighbors in decreasing order of similarities
    neighbors = np.flip(np.argsort(similarities), axis=1)
    
    # sort similarities in decreasing order
    similarities = np.flip(np.sort(similarities), axis=1)
    
    # save similarities to disk
    save_similarities(similarities, neighbors, dataset_name=dataset_name) 
    
    return similarities, neighbors<jupyter_output><empty_output><jupyter_text>now, we can call the ```adjusted_cosine``` function to compute and save items similarities and neighbors based on the adjusted cosine metric. uncomment the two lines of the following cell to compute the adjusted cosine between all items. As we have already run the next cell before, we will just load the precomputed similarities for further use.<jupyter_code># nb_items = ratings.itemid.nunique()
# similarities, neighbors = adjusted_cosine(np_ratings, nb_items=nb_items, dataset_name='ml100k')<jupyter_output><empty_output><jupyter_text>Among the following similarity metrics, choose the one you wish to use for the item-based collaborative filtering :- **euclidian** or **cosine** : choose *euclidian* or *cosine* to initialise the similarity model through the sklearn library.- **adjusted_cosine** : choose the *adjusted_cosine* metric to load similarities computed and saved through the ```adjusted_cosine``` function.In this case, we will use the *adjusted_cosine* metric.<jupyter_code># metric : choose among [cosine, euclidean, adjusted_cosine]

metric = 'adjusted_cosine'

if metric == 'adjusted_cosine':
    similarities, neighbors = load_similarities('ml100k')
else:
    model = create_model(R, k=21, metric=metric)
    similarities, neighbors = nearest_neighbors(R, model)
print('neighbors shape : ', neighbors.shape)
print('similarities shape : ', similarities.shape)<jupyter_output>neighbors shape :  (1682, 20)
similarities shape :  (1682, 20)<jupyter_text>```neighbors``` and ```similarities``` are numpy array, were each entries are list of 20 neighbors with their corresponding similarities  Step 2. Top N recommendation for a given user Top-N recommendations are made for example for a user $u$ who has already rated a set of items $I_u$  2.a- Finding candidate itemsTo find candidate items for user $u$, we need to :1. Find the set $I_u$ of items already rated by user $u$,2. Take the union of similar items as $C$ for all items in $I_u$3. exclude from the set $C$ all items in $I_u$, to avoid recommend to a user items he has already purchased.These are done in function ```candidate_items()```<jupyter_code>def candidate_items(userid):
    """
    :param userid : user id for which we wish to find candidate items    
    :return : I_u, candidates
    """
    
    # 1. Finding the set I_u of items already rated by user userid
    I_u = np_ratings[np_ratings[:, 0] == userid]
    I_u = I_u[:, 1].astype('int')
    
    # 2. Taking the union of similar items for all items in I_u to form the set of candidate items
    c = set()
        
    for iid in I_u:    
        # add the neighbors of item iid in the set of candidate items
        c.update(neighbors[iid])
        
    c = list(c)
    # 3. exclude from the set C all items in I_u.
    candidates = np.setdiff1d(c, I_u, assume_unique=True)
    
    return I_u, candidates
test_user = uencoder.transform([1])[0]
i_u, u_candidates = candidate_items(test_user)
print('number of items purchased by user 1 : ', len(i_u))
print('number of candidate items for user 1 : ', len(u_candidates))<jupyter_output>number of items purchased by user 1 :  272
number of candidate items for user 1 :  893<jupyter_text>2.b- Find similarity between each candidate item and the set $I_u$<jupyter_code>def similarity_with_Iu(c, I_u):
    """
    compute similarity between an item c and a set of items I_u. For each item i in I_u, get similarity between 
    i and c, if c exists in the set of items similar to itemid.    
    :param c : itemid of a candidate item
    :param I_u : set of items already purchased by a given user    
    :return w : similarity between c and I_u
    """
    w = 0    
    for iid in I_u :        
        # get similarity between itemid and c, if c is one of the k nearest neighbors of itemid
        if c in neighbors[iid] :
            w = w + similarities[iid, neighbors[iid] == c][0]    
    return w<jupyter_output><empty_output><jupyter_text>2.c- Rank candidate items according to their similarities to $I_u$<jupyter_code>def rank_candidates(candidates, I_u):
    """
    rank candidate items according to their similarities with i_u    
    :param candidates : list of candidate items
    :param I_u : list of items purchased by the user    
    :return ranked_candidates : dataframe of candidate items, ranked in descending order of similarities with I_u
    """
    
    # list of candidate items mapped to their corresponding similarities to I_u
    sims = [similarity_with_Iu(c, I_u) for c in candidates]
    candidates = iencoder.inverse_transform(candidates)    
    mapping = list(zip(candidates, sims))
    
    ranked_candidates = sorted(mapping, key=lambda couple:couple[1], reverse=True)    
    return ranked_candidates<jupyter_output><empty_output><jupyter_text>Putting all together Now that we defined all functions necessary to build our item to item top-N recommendation, let's define function ```item2item_topN()``` that makes top-$N$ recommendations for a given user<jupyter_code>def topn_recommendation(userid, N=30):
    """
    Produce top-N recommendation for a given user    
    :param userid : user for which we produce top-N recommendation
    :param n : length of the top-N recommendation list    
    :return topn
    """
    # find candidate items
    I_u, candidates = candidate_items(userid)
    
    # rank candidate items according to their similarities with I_u
    ranked_candidates = rank_candidates(candidates, I_u)
    
    # get the first N row of ranked_candidates to build the top N recommendation list
    topn = pd.DataFrame(ranked_candidates[:N], columns=['itemid','similarity_with_Iu'])    
    topn = pd.merge(topn, movies, on='itemid', how='inner')    
    return topn
topn_recommendation(test_user)<jupyter_output><empty_output><jupyter_text>This dataframe represents the top N recommendation list a user. These items are sorted in decreasing order of similarities with $I_u$.**Observation** : The recommended items are the most similar to the set $I_u$ of items already purchased by the user.  Top N recommendation with predictions Before recommending the previous list to the user, we can go further and predict the ratings the user would have given to each of these items, sort them in descending order of prediction and return the reordered list as the new top N recommendation list.  Rating predictionAs stated earlier, the predicted rating $\hat{r}_{u,i}$ for a given user $u$ on an item $i$ is obtained by aggregating ratings given by $u$ on items similar to $i$ as follows:\begin{equation} \hat{r}_{u,i}=\frac{\sum_{j\in S^{(i)}}r_{u,j}\cdot w_{i,j}}{\sum_{j\in S^{(i)}}|w_{i,j}|}\end{equation}<jupyter_code>def predict(userid, itemid):
    """
    Make rating prediction for user userid on item itemid    
    :param userid : id of the active user
    :param itemid : id of the item for which we are making prediction        
    :return r_hat : predicted rating
    """
    
    # Get items similar to item itemid with their corresponding similarities
    item_neighbors = neighbors[itemid]
    item_similarities = similarities[itemid]
    
    # get ratings of user with id userid
    uratings = np_ratings[np_ratings[:, 0].astype('int') == userid]
    
    # similar items rated by item the user of i
    siru = uratings[np.isin(uratings[:, 1], item_neighbors)]
    scores = siru[:, 2]
    indexes = [np.where(item_neighbors == iid)[0][0] for iid in siru[:,1].astype('int')]    
    sims = item_similarities[indexes]
    
    dot = np.dot(scores, sims)
    som = np.sum(np.abs(sims))

    if dot == 0 or som == 0:
        return mean[userid]
    
    return dot / som<jupyter_output><empty_output><jupyter_text>Now let's use our ```predict()``` function to predict what ratings the user would have given to the previous top-$N$ list and return the reorganised list (in decreasing order of predictions) as the new top-$N$ list<jupyter_code>def topn_prediction(userid):
    """
    :param userid : id of the active user    
    :return topn : initial topN recommendations returned by the function item2item_topN
    :return topn_predict : topN recommendations reordered according to rating predictions
    """
    # make top N recommendation for the active user
    topn = topn_recommendation(userid)
    
    # get list of items of the top N list
    itemids = topn.itemid.to_list()
    
    predictions = []
    
    # make prediction for each item in the top N list
    for itemid in itemids:
        r = predict(userid, itemid)
        
        predictions.append((itemid,r))
    
    predictions = pd.DataFrame(predictions, columns=['itemid','prediction'])
    
    # merge the predictions to topN_list and rearrange the list according to predictions
    topn_predict = pd.merge(topn, predictions, on='itemid', how='inner')
    topn_predict = topn_predict.sort_values(by=['prediction'], ascending=False)
    
    return topn, topn_predict<jupyter_output><empty_output><jupyter_text>Now, let's make recommendation for user 1 and compare the two list<jupyter_code>topn, topn_predict = topn_prediction(userid=test_user)
topn_predict<jupyter_output><empty_output><jupyter_text>As you will have noticed, the two lists are sorted in different ways. The second list is organized according to the predictions made for the user.Note: When making predictions for user $u$ on item $i$, user $u$ may not have rated any of the $k$ most similar items to i. In this case, we consider the mean rating of $u$ as the predicted value.  Evaluation with Mean Absolute Error<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.672389703640273<jupyter_text>Summary As with the User-based CF, we have also summarised the Item-based CF into the python class [ItemToItem](https://github.com/nzhinusoftcm/review-on-collaborative-filtering/blob/master/recsys/memories/ItemToItem.py).  ItemToItem : usage<jupyter_code>from recsys.memories.ItemToItem import ItemToItem
from recsys.preprocessing import ids_encoder, train_test_split, get_examples
from recsys.datasets import ml100k

# load data
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)<jupyter_output><empty_output><jupyter_text>Instanciate the ItemToItem CFParameters :- ```k``` : number of neighbors to consider for each item- ```metric``` : metric to use when computing similarities : let's use **cosine**- ```dataset_name``` : in this example, we use the ml100k dataset<jupyter_code># create the Item-based CF
item2item = ItemToItem(ratings, movies, k=20, metric='cosine', dataset_name='ml100k')
# evaluate the algorithm on test dataset
item2item.evaluate(x_test, y_test)<jupyter_output>Evaluate the model on 10000 test data ...

MAE : 0.507794195659005<jupyter_text>Evaluate the Item-based CF on the ML-1M dataset<jupyter_code>from recsys.memories.ItemToItem import ItemToItem
from recsys.preprocessing import ids_encoder, train_test_split, get_examples
from recsys.datasets import ml1m

# load data
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 Item-based CF
item2item = ItemToItem(ratings, movies, k=20, metric='cosine', dataset_name='ml1m')

# evaluate the algorithm on test dataset
print("=========================")
item2item.evaluate(x_test, y_test)<jupyter_output>Normalize ratings ...
Create the similarity model ...
Compute nearest neighbors ...
Item to item recommendation model created with success ...
=========================
Evaluate the model on 100021 test data ...

MAE : 0.42514728655396045
{'fraction_non_alphanumeric': 0.10075238535580681, 'fraction_numerical': 0.011012567777731075, 'mean_word_length': 4.2742185768122365, 'pattern_counts': {'":': 0, '<': 87, '<?xml version=': 0, '>': 90, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '572043', 'license': 'Apache-2.0', 'n_tokens_mistral': 7533, 'n_tokens_neox': 7151, 'n_words': 2557, 'path': '_notebooks/2021-06-23-collaborative-filtering-movielens-latest-small-03.ipynb', 'repo_name': 'recohut/notebook', 'size': '23825'}