<jupyter_start><jupyter_text>Movie Recommendations > Today>>- [The MovieLens 1M Dataset](The-MovieLens-1M-Dataset)>>>- [Similarity Measures](Similarity-Measures)>>>- [User-to-user kNN](User-to-user-kNN)>>>- [Item-to-item kNN](Item-to-item-kNN) ---<jupyter_code>import math

from itertools import product, combinations
from operator import itemgetter
from collections import defaultdict

import numpy as np

from scipy.spatial import distance
from sklearn.metrics import mean_absolute_error<jupyter_output><empty_output><jupyter_text>The MovieLens 1M DatasetThe MovieLens 1M dataset has been developed by the members of the [GroupLens](https://grouplens.org/) lab in the Department of Computer Science and Engineering at the University of Minnesota. The MovieLens 1M dataset in brief:- Ratings: 1 million- Users: 6,040- Rated Movies: 3,592- Rating Scale: {1, ... , 5}- Additional information on the users: gender, age range, occupation, zip-code- Additional infomation on the movies: genre (A zipped version of this dataset is available in the data folder, or you can [download it](https://grouplens.org/datasets/movielens/1m/) and unzip it) The dataset is composed by three files:- `movies.dat`, providing information about the rated movies     - it follows the format `MovieID::Title::Genres`    - `users.dat`, providing information about the users    - it follows the format `UserID::Gender::Age::Occupation::Zip-code`    - each user has at least 20 ratings- `ratings.dat`, encoding the ratings    - it follows the format `UserID::MovieID::Rating::Timestamp`<jupyter_code>id2movie = dict()

with open("data/ml-1m/movies.dat", "r", encoding='windows-1252') as infile:
    for line in infile:
        movieId, movie, _ = line.split("::")
        id2movie[int(movieId)] = movie
print("no. of movies:", len(id2movie))
for i in list(id2movie.items())[:3]:
    print(i)
user2movies_ratings = defaultdict(dict)

with open("data/ml-1m/ratings.dat", "r", encoding='utf-8') as infile:
    for line in infile:
        userId, movieId, rating = [int(el) for el in line.split("::")[:3]]
        user2movies_ratings[userId][movieId] = rating
print("no. of users:", len(user2movies_ratings))
print(list(user2movies_ratings.items())[0])
print("no. of ratings:",sum([len(v) for v in user2movies_ratings.values()]))<jupyter_output>no. of ratings: 1000209<jupyter_text>---  ExerciseExplore the dataset:- (optional) Turn the dataset into a Pandas data frames if you prefer.- What is the average rating?- Which are the top-rated movies? And which are the lowest-rated ones?- What are the average ratings for men and women?- Which movies received the highest rates from men? Which ones from women?<jupyter_code># your code here<jupyter_output><empty_output><jupyter_text>---  Use case for k-NNIn the following exercise we will use the **k Nearest Neighbors algorithm** (k-NN)- to model the ratings given by user `4447` (982 ratings)    - .. to the following movies:    - `Silence of the Lambs, The (1991)` : id = `593`    - `Raiders of the Lost Ark (1981)` : id = `1198`    - `Back to the Future (1985)`: id = `1270`<jupyter_code>target_movies = [593, 1198, 1270]
# First, let's remove our target ratings from the dataset
target_ratings = dict([(i, user2movies_ratings[4447].pop(i)) for i in target_movies])
target_ratings<jupyter_output><empty_output><jupyter_text>---  Similarity Measures- Similarity/Distance measures are used in many applications (e.g., clustering, classification, word modeling) to measure how two objects are similar/different.- Distances/Similarities are described by a single scalar, the value of which depends on three factors:    - the properties of the **object**     - the **representation** choosen for the objects    - the properites of the **measure** In order to be qualifies as a **metric**, a distance/similarity measure must satisfy the following four conditions:- The distance between any points is always **nonegative**- The distance between two points equals $0$ iff two objects are **identical**- **Symmetry**, i.e., $d(x,y) = d(y,x)$- **Triangular inequality**, i.e., $d(x, z) \leq d(x, y) + d(y, z)$ **Euclidean similarity**- Euclidean distance is the ordinary straight-line distance between two points- Distance is calculated by using the Pythagorean theorem- Distance can be transformed into a similarity measure by summing 1 to the distance and inverting it $$sim_{\ euclidean} (p,q)=\frac{1}{dist(p,q)} = \frac{1}{1 + \sqrt{\sum_{i = 1}^n (p_i - q_i)^2}}$$<jupyter_code>def euclidean_similarity(p, q):
    dist = math.sqrt(sum((pi-qi)**2 for pi,qi in zip(p, q)))
    sim = 1 / (1+dist)
    return sim<jupyter_output><empty_output><jupyter_text>**Manhattan similarity**- The Manhattan (or taxicab, cityblock, rectilinear, $L_1$) distance between two points is calculated as the sum of the absolute distances of their Cartesian coordinates- Similar to the Euclidean distance, but less influenced by outliers $$sim_{\ manhattan} (p,q) =\frac{1}{dist(p,q)} = \frac{1}{1 + \sum_{i = 1}^n |p_i - q_i|}$$ ---  ExerciseWrite a function called `manhattan_similarity()` that calculates this metric<jupyter_code># your code here<jupyter_output><empty_output><jupyter_text>--- **Cosine similarity**- The normalized dot product of two vectors, i.e., the cosine of the angle between them- **Scale-invariance**: cosine similarity is independent of vector length     - you can multiply your vector for any non-zero constant and the angle won't change    - it should be used when vector length is irrelevant    - in k-NN, this means that it is independent of the absolute number of rating per user/item $$sim_{\ cosine} (\vec{p},\vec{q})=\frac{\vec{p} \cdot \vec{q}}{\lVert \vec{p} \rVert \lVert \vec{q} \rVert} = \frac{\sum_{i = 1}^n p_i q_i}{\sqrt{\sum_{i = 1}^n (p_i)^2} \sqrt{\sum_{i = 1}^n (q_i)^2}}$$<jupyter_code>def cosine_similarity(p,q):
    d = sum(pi * qi for pi,qi in zip(p, q))
    mag_p = math.sqrt(sum([pi**2 for pi in p]))
    mag_q = math.sqrt(sum([qi**2 for qi in q]))
    sim = d / ( mag_p * mag_q)
    return sim<jupyter_output><empty_output><jupyter_text>**Pearson correlation**: - Measure of the strength of linear dependence between two variables- Calculated as the ratio between the variance that is shared between the two variables (covariance) and the product of their standard deviations (i.e., of their variance) $$r(p,q) = \frac{\sum_{i = 1}^n (p_i - \bar{p})(q_i - \bar{q})}{\sqrt{\sum_{i = 1}^n (p_i - \bar{p})^2}\ \sqrt{\sum_{i = 1}^n (q_i - \bar{q})^2}}$$ - The correlation value between two variables is invariant to **scale** and **location** tranformations:    - that is, if $a$, $b$, $c$, $d$ are constants and $a > 0$ and $c > 0$: $$r(p,q) = r(a\cdot p + b, c\cdot q + d)$$<jupyter_code>def pearson_correlation(p,q):
    # this code does not scale well to large datasets. In the following, we rely on 
    # scipy.spatial.distance.correlation() to compute long vectors
    if len(p) > 99:
        return 1 - distance.correlation(p,q)        
    
    p_mean = sum(p) / len(p)
    p_deviations = [(pi-p_mean) for pi in p]
    
    q_mean = sum(q) / len(q)
    q_deviations = [(qi-q_mean) for qi in q]
    
    cov = sum(pd * qd for pd,qd in zip(p_deviations, q_deviations))
        
    sds_product = math.sqrt(sum((pd)**2 for pd in p_deviations) * sum((qd)**2 for qd in q_deviations))
    
    if sds_product != 0:
        r = cov / sds_product
    else:
        r = 0
    return r<jupyter_output><empty_output><jupyter_text>**Pearson correlation** and **cosine similarity**:- The Pearson correlation is equivalent to the cosine similarity if the values of input vectors has been **normalized to their arithmetic means**: $$sim_{\ cosine} (p - \bar{p}, q - \bar{q}) = \frac{\sum_{i = 1}^n (p_i - \bar{p})(q_i - \bar{q})}{\sqrt{\sum_{i = 1}^n (p_i - \bar{p})^2}\ \sqrt{\sum_{i = 1}^n (q_i - \bar{q})^2}} = r(p,q) $$ - That is, the Pearson correlation and the cosine similarity are equivalent when the two vectors have **mean of 0**:    - geometrically, the Pearson correlation can be seen as the angle between the two vectors where the origin of the coordinate system is translated at the arithmetic mean values of the vectors;        - both the cosine similarity and the Pearson correlation are **scale invariant**, while Pearson correlation is also **invariant to constant addition**. **Jaccard similarity** Measured as the ratio of the cardinality of the intersection set (number of items that are in both sets) to that of the union set (number of items in either sets) $$sim_{\ jaccard} (P, Q) = \frac{|P \cap Q|}{|P \cup Q|}$$<jupyter_code>def jaccard_sets(p,q): 
    intersection_cardinality = len(set(p).intersection(set(q)))
    union_cardinality = len(set(p).union(set(q)))
    sim = intersection_cardinality / union_cardinality
    return sim<jupyter_output><empty_output><jupyter_text>- It is particularly useful for **datasets with binary values** (e.g., 1s for a preference and 0s for indifference)    - in these cases, you have two objects $P$ and $Q$ with $n$ attributes,    - and you may use this measure to estimate the **overlap that $P$ and $Q$ share with their attributes**.- If $M_{11}$ represents the number of attributes where both objects have a value of 1 and $M_{10} + M_{01}$ represents the number of attributes where only one object has a value of 1: $$sim_{\ jaccard} = \frac{M_{11}}{M_{01} + M_{10} + M_{11}}$$<jupyter_code>def jaccard_binary(p, q):
    # only works for binary vectors! Binarize your vectors first
    m_11, m_01, m_10 = 0, 0, 0
    for pi, qi in zip(p, q):

        if pi == 1:
            if qi == 1:
                m_11 += 1
            else:
                m_10 += 1
                
        elif qi == 1:
            m_01 += 1
    
    sim = m_11 / (m_10 + m_01 + m_11) 
    return sim<jupyter_output><empty_output><jupyter_text>---  ExerciseApply the above measures on the following two vectors and be sure to understand their properties.<jupyter_code>p = [1, 2, 1, 0, 5, 0, 1, 1, 3, 4, 4, 0, 1, 0, 3, 1, 1, 1, 1, 1]
q = [1, 3, 5, 0, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 4, 1, 0, 0, 5, 0]
# your code here<jupyter_output><empty_output><jupyter_text>---  Which one should I use? This very much depends on your application:- How are we modeling our problem (i.e. are we using binary features)?- How do we want our measure to behave?    - do we want results to be less sensitive to outliers?    - do we want results to be scale-invariant?    - do we want results to be location-invariant? As a **rule of thumb**, the best practice is to try how the similarity measures which make sense and decide on the basis of an **empirical evaluation**. ---  User-to-user kNN Given an active user $a$:- Use a similarity measure to determine the $k$ most-similar users to $a$.- Obtain the prediction on item $i$ for user $a$ by using one of the following aggregation approaches on the ratings from the neighborhood:    - average    - weighted sum    - adjusted weighted aggregation (deviation-from-mean)- Choose the top-$n$ items by selecting the $n$ items with the highest scores calculated by applying the previous steps on the items that haven’t been rated by the user $a$.  STEP 1: Find the top-50 similar usersLet's build the neighborhood for our target user `4447` by calculating his similarity with other users.<jupyter_code>def calculate_similarity(ratings, id1, id2, measure, threshold = 0):
    # get the list of shared rated items
    shared = sorted(set(ratings[id1].keys()).intersection(set(ratings[id2].keys())))

    # ignore comparisons with too few overlapping ratings (default is 0)
    if len(shared) <= threshold:
        return 0
    
    sel_ratings = [np.asarray([v for (k,v) in ratings[i].items() if k in shared]) for i in [id1, id2]]
    
    # compute similarity
    sim = measure(*sel_ratings)
    return sim
# Calculate the similarities (NB: this can take a minute)
measure2function = {"euclidean" : euclidean_similarity, "cosine": cosine_similarity, "correlation": pearson_correlation}

similarities = dict()
for measure, function in measure2function.items():
    similarities[measure] = dict()
    for id1, id2 in product([4447], user2movies_ratings.keys()):
        # do not compare our target user with himself
        if id1 == id2:
            continue
        similarities[measure][id2] = calculate_similarity(user2movies_ratings, id1, id2, function)
# select the most similar users according to each measure

k = 50 # this is the k in k-NN
neighborhood = dict()
for measure in similarities.keys():
    neighborhood[measure] = dict(sorted(similarities[measure].items(), key = itemgetter(1), reverse = True)[:k])
print(neighborhood)<jupyter_output>{'euclidean': {1037: 1.0, 3325: 1.0, 4628: 1.0, 61: 0.5, 782: 0.5, 1615: 0.5, 1838: 0.5, 1918: 0.5, 1979: 0.5, 2245: 0.5, 2584: 0.5, 2992: 0.5, 3133: 0.5, 3245: 0.5, 3264: 0.5, 3495: 0.5, 3542: 0.5, 3893: 0.5, 4008: 0.5, 1270: 0.4142135623730951, 1305: 0.4142135623730951, 1967: 0.4142135623730951, 2357: 0.4142135623730951, 3552: 0.4142135623730951, 3838: 0.4142135623730951, 4500: 0.4142135623730951, 4550: 0.4142135623730951, 4651: 0.4142135623730951, 4749: 0.4142135623730951, 364: 0.36602540378443865, 886: 0.36602540378443865, 1240: 0.36602540378443865, 1844: 0.36602540378443865, 3179: 0.36602540378443865, 3381: 0.36602540378443865, 3883: 0.36602540378443865, 4184: 0.36602540378443865, 4270: 0.36602540378443865, 4548: 0.36602540378443865, 4724: 0.36602540378443865, 5409: 0.36602540378443865, 5439: 0.36602540378443865, 5529: 0.36602540378443865, 653: 0.3333333333333333, 2037: 0.3333333333333333, 2673: 0.3333333333333333, 3122: 0.3333333333333333, 3168: 0.3333333333333333, 3351: 0.333333[...]<jupyter_text>STEP 2: Obtain the predictions for all items of interest - In a real life scenario, we should obtain a predictions for all the items that were not rated by our user.- In this example, we will get predictions for just our three target movies. Let's use the following weighted score to aggregate our ratings: - Take the votes of all other critics and multiply them by their similarity with our target user.- Sum these weighted votes for each item of interest.- In order to handle the sparseness of the dataset (no movie has been rated by all the users), divide this score by the sum of all the similarities for critics that reviewed that movie. ![alt text](images/weighting-users.png)<jupyter_code>def getPredictions(movieId, neighborhood, ratings):
    weigthed_scores = []
    similarities = []

    for user, sim in neighborhood.items():
        if movieId in ratings[user]:
            weigthed_scores.append(sim * ratings[user][movieId])
            similarities.append(sim)
    
    return sum(weigthed_scores) / sum(similarities)
recommendations = defaultdict(dict)

for measure in similarities.keys():
    for movie in target_movies:
        recommendations[measure][movie] = getPredictions(movie, neighborhood[measure], user2movies_ratings)<jupyter_output><empty_output><jupyter_text>STEP 3: Choose the top-items - In a real life scenario, you should choose the top-rated items and recommend them to the user.- In this exercise, we will compare the **rating predictions** produced by our RC against the **actual ratings** given by our user. How do the predicted ratings compare to the actual ones?<jupyter_code>print("# Original ratings")

for movieID in target_ratings:
    print(id2movie[movieID], "-->", target_ratings[movieID])
for measure in similarities.keys():
    print("# ", "Predicted,", measure)
    for movieID in target_ratings:
        print(id2movie[movieID], "-->", recommendations[measure][movieID])
    print()<jupyter_output>#  Predicted, euclidean
Silence of the Lambs, The (1991) --> 4.098217993648402
Raiders of the Lost Ark (1981) --> 5.0
Back to the Future (1985) --> 2.7088761776287287

#  Predicted, cosine
Silence of the Lambs, The (1991) --> 4.144352723486918
Raiders of the Lost Ark (1981) --> 3.7517827670141886
Back to the Future (1985) --> 2.74679603706995

#  Predicted, correlation
Silence of the Lambs, The (1991) --> 3.8862286223113807
Raiders of the Lost Ark (1981) --> 4.614829742977353
Back to the Future (1985) --> 3.2929248770516923<jupyter_text>Let's calculate the **Mean Absolute Error** - The difference between the real ratings and those produced by the RS.- If $\hat{y}_i$ is the predicted value of the $i$-th sample, $y_i$ is the true value and $n$ is the sample size: $$MAE(y, \hat{y}) = \frac{1}{n} \sum_{i = 0}^{n - 1} \left| \ y_i, \hat{y_i}\ \right|$$<jupyter_code>true_ratings = [target_ratings[movieID] for movieID in target_ratings]

for measure in similarities.keys():
    print("#", "Mean Absolute Error,", measure)
    predicted = [recommendations[measure][movieID] for movieID in target_ratings]
    print(mean_absolute_error(true_ratings, predicted))<jupyter_output># Mean Absolute Error, euclidean
1.129780605339891
# Mean Absolute Error, cosine
0.7164464844770522
# Mean Absolute Error, correlation
1.0071753325725548<jupyter_text>---  ExerciseSee what happens if:- we specify a minimum rating overlap threshold (say, 10) in the `calculate_similarity()` function.- We change the size of the neighborhood (say, to 100).<jupyter_code># your code here<jupyter_output><empty_output><jupyter_text>---  Item-to-item kNN Given an active user $a$:- For each item in the database, use a similarity measure to determine its $k$ most-similar items.- For each item $i$ not rated by $a$, predict its rating on the basis of the $a$'s previous ratings of the items in the $i$'s neighborhood.- Choose the top-$n$ items by selecting the $n$ items with the highest scores calculated in the previous step.  STEP 1: Find the top-25 similar itemsRe-arranging the ratings dictionary allows us to use the `calculate_distance()` function to calculate the item-based similarities as well<jupyter_code># let's rearrange the dictionary of ratings 

movies2user_ratings = defaultdict(dict)

for user, user_ratings in user2movies_ratings.items():
    for movie, rating in user_ratings.items():
        movies2user_ratings[movie][user] = rating<jupyter_output><empty_output><jupyter_text>To speed up the process, we will ignore all those movies that has not been rated by at least 1500 users<jupyter_code>filtered_movies2user_ratings = dict()
for movie in movies2user_ratings.keys():
    if len(movies2user_ratings[movie]) < 1500:
        continue
    else:
        filtered_movies2user_ratings[movie] = movies2user_ratings[movie]

print("-", len(movies2user_ratings) - len(filtered_movies2user_ratings), "movies have been discarded")
print("-", len(filtered_movies2user_ratings), "movies have been selected")
# Let's calculate the similarities, this time only using Pearson's correlation
# WARNING: This method is quite inefficient! Can you find the bottleneck, and think of a way to speed it up?

similarities = defaultdict(dict)
for id1, id2 in combinations(filtered_movies2user_ratings.keys(), 2):
    similarities[id1][id2] = calculate_similarity(movies2user_ratings, id1, id2, pearson_correlation)
# select the most similar items
neighborhood = dict()
for movie in similarities.keys():
    neighborhood[movie] = dict(sorted(similarities[movie].items(), key = itemgetter(1), reverse = True)[:25])<jupyter_output><empty_output><jupyter_text>---  ExerciseChoose a movie and explore its immediate neighborhood by printing its most similar movies and using MDS or PCA to plot them in a 2-dimensional space<jupyter_code># your code here<jupyter_output><empty_output><jupyter_text>---  STEP 2: Obtain the predictions for all the items of interest For all the items that the user hasn't rated (here we restrict ourselves to our three target movies), the following weighted score is used to aggregate our ratings:- for each pair of items composed by one item rated by our user and one of our items of interest, we calculate a score by multiplying their pairwise similarity and the rating for the known movie.- For each item of interest we sum all these scores.- The score is normalized by diving this total by the total of the pairwise similarity scores involving a item of interest. ![alt text](images/weighting-item.png)<jupyter_code>def getPredictionsForItems(userId, neighborhood, ratings):
    weigthed_scores = []
    similarities = []

    for item, sim in neighborhood.items():
        if userId in ratings[item]:
            weigthed_scores.append(sim * ratings[item][userId])
            similarities.append(sim)
    
    return sum(weigthed_scores) / sum(similarities)
recommendations = defaultdict(dict)

for movie in target_movies:
    recommendations[movie] = getPredictionsForItems(4447, neighborhood[movie], filtered_movies2user_ratings)<jupyter_output><empty_output><jupyter_text>STEP 3: Choose the top-items - In a real life scenario, you should choose the top-rated items and recommend them to the user.- In this exercise, we will compare the **rating predictions** produced by our RC against those produced by our user. How do the predicted ratings compare to the actual ones?<jupyter_code>print("# Original ratings")

for movieID in target_ratings:
    print(id2movie[movieID], "-->", target_ratings[movieID])
print("# Predicted ratings")
for movieID in target_ratings:
    print(id2movie[movieID], "-->", recommendations[movieID])<jupyter_output># Predicted ratings
Silence of the Lambs, The (1991) --> 3.605898258715225
Raiders of the Lost Ark (1981) --> 3.3224392124831894
Back to the Future (1985) --> 3.0006836869169238<jupyter_text>As before, let's calculate the **Mean Absolute Error** (i.e. the difference between the real ratings and those produced by the RS)<jupyter_code>true_ratings = [target_ratings[movieID] for movieID in target_ratings]
predicted = [recommendations[movieID] for movieID in target_ratings]

print("# Mean Absolute Error")
print(mean_absolute_error(true_ratings, predicted))<jupyter_output># Mean Absolute Error
0.5724082135616294
{'fraction_non_alphanumeric': 0.11261302402045849, 'fraction_numerical': 0.06169513197552288, 'mean_word_length': 4.431299603174603, 'pattern_counts': {'":': 4, '<': 85, '<?xml version=': 0, '>': 114, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 5, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '22', 'dir': 'jupyter-structured-clean-dedup', 'id': '172424', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 7919, 'n_tokens_neox': 6815, 'n_words': 2534, 'path': 'notebooks/10_Recommender_Systems.ipynb', 'repo_name': 'ilaiadaya/AUC_TMCI_2021', 'size': '21898'}