In this notebook, we will look at Association Rules and Collaborative Filtering

Association Rules

Also called Market Basket Analysis, or Affinity Analysis

References:
- http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/
- https://pyshark.com/market-basket-analysis-using-association-rule-mining-in-python/
- Data adapted from https://www.kaggle.com/heeraldedhia/groceries-dataset

Association rules help us identify what goes with what. For example in a retail sales context, you may want to know that if a person buys bread, they are also likely to buy jam. In such a case, you can recommend jam to a person who is buying bread, but hasn't brought jam yet. Association rules are the basis for recommender systems, so if a person has watched Star Wars, they may be likely to watch Dune.

The end game for Association Rules is a set of rules where for an antecedent we are able to predict the consequent with some level of confidence. An association rule takes the form A → C, which is a way of saying that given A, what is the likelihood of C co-occurring.

Note that this is not correlation, but expressed as a probability called 'confidence'. A and B are called 'itemsets', which means that they represent one or a combination of multiple items in our data. For example, if we are trying to determine the association rules for purchases of milk, bread and butter, then {milk} would be an 'itemset', and so would be {milk, bread}. So a rule may look like {milk, bread} → {butter} with a confidence of 66%. Or it may be simpler, {bread} → {butter} with a confidence of 50%.

Metrics

Support

Support is calculated at the itemset level. It is the ratio of how often an itemset appears in the dataset, divided by the total number of observations in the dataset.

$support(itemset) = {\text{# of transactions in which }itemset \text{ appears} \over \text{Total # of transactions}}$

Support is used to measure the abundance or frequency (often interpreted as significance or importance) of an itemset in a database. We refer to an itemset as a "frequent itemset" if support is larger than a specified minimum-support threshold. All subsets of a frequent itemset are also frequent.

The support for a rule is calculated as $\text{support}(A\rightarrow C) = \text{support}(A \cup C), \;\;\; \text{range: } [0, 1]$

Confidence

$\text{confidence}(A\rightarrow C) = \frac{\text{support}(A\rightarrow C)}{\text{support}(A)}, \;\;\; \text{range: } [0, 1]$

Lift

Lift tells us how good is the rule at calculating the outcome while taking into account the popularity of itemset Y.

$\text{lift}(A\rightarrow C) = \frac{\text{confidence}(A\rightarrow C)}{\text{support}(C)}, \;\;\; \text{range: } [0, \infty]$

Leverage

$\text{levarage}(A\rightarrow C) = \text{support}(A\rightarrow C) - \text{support}(A) \times \text{support}(C), \;\;\; \text{range: } [-1, 1]$

Leverage computes the difference between the observed frequency of A and C appearing together and the frequency that would be expected if A and C were independent. A leverage value of 0 indicates independence.

Conviction

$\text{conviction}(A\rightarrow C) = \frac{1 - \text{support}(C)}{1 - \text{confidence}(A\rightarrow C)}, \;\;\; \text{range: } [0, \infty]$

A high conviction value means that the consequent is highly depending on the antecedent. For instance, in the case of a perfect confidence score, the denominator becomes 0 (due to 1 - 1) for which the conviction score is defined as 'inf'. Similar to lift, if items are independent, the conviction is 1.

Source: http://rasbt.github.io/mlxtend/user_guide/frequent_patterns/association_rules/

While the above is great to obtain a high level understanding, let us scale up our example and look at larger examples, and have the machine do these calculations for us.

Toy Example

Let us calculate these metrics for {milk} → {butter}

Support
support(milk) = 3/5 = 60%
support(butter) = 3/5 = 60%
support(milk AND butter) = 2/5 = 40%

Confidence
confidence(milk → butter) = 2/3 = 67%
or, support(milk AND butter)/support(milk) = 40%/60% = 67%

Lift
lift(milk → butter) = 67% / 60% = 67% = 1.11

Leverage
leverage(milk → butter) = 40% - (60% * 60%) = 0.04

Conviction
conviction(milk → butter) = (1-60%)/(1-67%) = 1.21

Next, we create and test the above out using a Python library to do these calculations.

# Usual library imports
import numpy as np
import pandas as pd

Create toy dataframe

df = pd.DataFrame(
    {'Milk': {'Customer_1': True,
  'Customer_2': True,
  'Customer_3': False,
  'Customer_4': False,
  'Customer_5': True},
 'Bread': {'Customer_1': False,
  'Customer_2': True,
  'Customer_3': True,
  'Customer_4': True,
  'Customer_5': False},
 'Butter': {'Customer_1': True,
  'Customer_2': True,
  'Customer_3': False,
  'Customer_4': True,
  'Customer_5': False}})
df

List itemsets

from mlxtend.frequent_patterns import apriori

frequent_itemsets_ap = apriori(df, min_support=0.01, use_colnames=True)
frequent_itemsets_ap['length'] = frequent_itemsets_ap['itemsets'].apply(lambda x: len(x))

frequent_itemsets_ap

Generate rules

from mlxtend.frequent_patterns import association_rules

rules_ap = association_rules(frequent_itemsets_ap, metric="confidence", min_threshold=0.1)

rules_ap.sort_values(by='lift', ascending=False)

Example with larger dataset

Load data

df = pd.read_csv('groceries.csv', index_col=0)
df

Change dataframe to boolean

df = df>0
print(df.shape)
df

(3898, 167)

List itemsets

from mlxtend.frequent_patterns import apriori

frequent_itemsets_ap = apriori(df, min_support=0.01, use_colnames=True)
frequent_itemsets_ap['length'] = frequent_itemsets_ap['itemsets'].apply(lambda x: len(x))

frequent_itemsets_ap.sort_values(by='support', ascending=False)

Generate rulesets

Rulesets, sorted by lift

from mlxtend.frequent_patterns import association_rules

rules_ap = association_rules(frequent_itemsets_ap, metric="confidence", min_threshold=0.1)

rules_ap.sort_values(by='lift', ascending=False)

Sorted by confidence

rules_ap.sort_values(by='confidence', ascending=False)

Sorted by support

rules_ap.sort_values(by='support', ascending=False)

---

---

Collaborative Filtering

Collaborative filtering aims to predict the ratings a given user will give to an item that this user has not yet purchased/watched/consumed.

It does so by identifying other users similar to this user, and looking at the ratings they have provided to the item in question. If the predicted rating is high, then it would make sense to recommend that item to the user.

Consider the table below:

There are 5 users, who have rated 12 movies using a rating scale of 1 to 5. Many of the cells are blank, which is because not every user has rated every movie.

Our task is to decide what movie to recommend to a user to watch next. To do this, we use the following approach:

1. Find users similar to a given user. Similarity between users is determined solely based on the ratings they have provided, and not on features outside the ratings matrix (eg, age, location etc). There are many ways to determine which users are similar.

2. Estimate the rating for unwatched movies based on such ‘similar’ users. Again, there are many ways to determine the rating estimate, eg average, median, max, etc.

The accuracy of predicted ratings can be determined using MSE/RMSE, or MAE and such metrics. Once the predictions are known, we can use these to determine the movies to recommend next.

---

The surprise library (pip install scikit-surprise) provides several algorithms to perform collaborative filtering, and predict ratings.

To use the surprise library, data needs to be in a certain format. We need to know the UserID, the ItemID and the Rating, and supply it to the library in exactly that order to create a surprise 'dataset'! No other order will work.

First, the usual library imports

import pandas as pd
import numpy as np

Creating a toy dataset

We create a random dataframe. There are 5 users, who have rated some movies out of 12 movies.

df = pd.DataFrame({'Movie 1': {'User 1': 2.0,   'User 2': 4.0,   'User 3': 3.0,   'User 4': np.nan,   'User 5': np.nan},
 'Movie 2': {'User 1': 3.0,   'User 2': np.nan,   'User 3': np.nan,   'User 4': np.nan,   'User 5': 3.0},
 'Movie 3': {'User 1': 2.0,   'User 2': np.nan,   'User 3': np.nan,   'User 4': np.nan,   'User 5': np.nan},
 'Movie 4': {'User 1': np.nan,   'User 2': 5.0,   'User 3': 3.0,   'User 4': np.nan,   'User 5': 3.0},
 'Movie 5': {'User 1': 2.0,   'User 2': np.nan,   'User 3': np.nan,   'User 4': 3.0,   'User 5': 1.0},
 'Movie 6': {'User 1': np.nan,   'User 2': 4.0,   'User 3': np.nan,   'User 4': 2.0,   'User 5': np.nan},
 'Movie 7': {'User 1': 1.0,   'User 2': np.nan,   'User 3': 5.0,   'User 4': 3.0,   'User 5': 1.0},
 'Movie 8': {'User 1': np.nan,   'User 2': 4.0,   'User 3': np.nan,   'User 4': 4.0,   'User 5': np.nan},
 'Movie 9': {'User 1': 2.0,   'User 2': np.nan,   'User 3': 4.0,   'User 4': 1.0,   'User 5': np.nan},
 'Movie 10': {'User 1': np.nan,   'User 2': 4.0,   'User 3': np.nan,   'User 4': 3.0,   'User 5': np.nan},
 'Movie 11': {'User 1': np.nan,   'User 2': 3.0,   'User 3': 2.0,   'User 4': 4.0,   'User 5': np.nan},
 'Movie 12': {'User 1': 5.0,   'User 2': np.nan,   'User 3': np.nan,   'User 4': 1.0,   'User 5': 5.0}})

df.reset_index()

Now we need to get the ratings matrix in a format that the surprise library can consume. We need to split out the user, item, rating in exactly that order in a dataframe, which we can do by using melt, and then we drop the NaNs.

redesigned_df = pd.melt(df.reset_index(), id_vars='index', value_vars=[col for col in df if col.startswith('M')])
redesigned_df.dropna(inplace=True)
redesigned_df.reset_index(drop=True, inplace=True)
redesigned_df

The surprise library

Next, we import the surprise library and convert our dataframe to a Dataset that the surprise library can consume. More information on the library is available at https://surprise.readthedocs.io/

from surprise import Dataset
from surprise import Reader
reader = Reader(rating_scale=(1, 5))
# each line needs to respect the following structure: user ; item ; rating ; [timestamp]
data = Dataset.load_from_df(redesigned_df[['index', 'variable', 'value']], reader)

# let us look at the data
data.raw_ratings

[('User 1', 'Movie 1', 2.0, None),
 ('User 2', 'Movie 1', 4.0, None),
 ('User 3', 'Movie 1', 3.0, None),
 ('User 1', 'Movie 2', 3.0, None),
 ('User 5', 'Movie 2', 3.0, None),
 ('User 1', 'Movie 3', 2.0, None),
 ('User 2', 'Movie 4', 5.0, None),
 ('User 3', 'Movie 4', 3.0, None),
 ('User 5', 'Movie 4', 3.0, None),
 ('User 1', 'Movie 5', 2.0, None),
 ('User 4', 'Movie 5', 3.0, None),
 ('User 5', 'Movie 5', 1.0, None),
 ('User 2', 'Movie 6', 4.0, None),
 ('User 4', 'Movie 6', 2.0, None),
 ('User 1', 'Movie 7', 1.0, None),
 ('User 3', 'Movie 7', 5.0, None),
 ('User 4', 'Movie 7', 3.0, None),
 ('User 5', 'Movie 7', 1.0, None),
 ('User 2', 'Movie 8', 4.0, None),
 ('User 4', 'Movie 8', 4.0, None),
 ('User 1', 'Movie 9', 2.0, None),
 ('User 3', 'Movie 9', 4.0, None),
 ('User 4', 'Movie 9', 1.0, None),
 ('User 2', 'Movie 10', 4.0, None),
 ('User 4', 'Movie 10', 3.0, None),
 ('User 2', 'Movie 11', 3.0, None),
 ('User 3', 'Movie 11', 2.0, None),
 ('User 4', 'Movie 11', 4.0, None),
 ('User 1', 'Movie 12', 5.0, None),
 ('User 4', 'Movie 12', 1.0, None),
 ('User 5', 'Movie 12', 5.0, None)]

Building the model

With train/test split

Next, we do a train/test split, and train the model. Note the model is contained in an object called algo.

from surprise import SVD, KNNBasic, SlopeOne
from surprise import Dataset
from surprise import accuracy
from surprise.model_selection import train_test_split

# We use the test dataset above
data = data

# sample random trainset and testset
# test set is made of 25% of the ratings.
trainset, testset = train_test_split(data, test_size=.25)

# You can try different algorithms, looking to reduced your RMSE
# algo = SVD()
algo = KNNBasic()
# algo = SlopeOne()

# Train the algorithm on the trainset, and predict ratings for the testset


algo.fit(trainset)
predictions = algo.test(testset)

# Then compute RMSE
accuracy.rmse(predictions)

Computing the msd similarity matrix...
Done computing similarity matrix.
RMSE: 1.2547





1.2546656662081634

# We can now look at the predictions
predictions

[Prediction(uid='User 4', iid='Movie 7', r_ui=3.0, est=1, details={'actual_k': 2, 'was_impossible': False}),
 Prediction(uid='User 3', iid='Movie 1', r_ui=3.0, est=3.6923076923076916, details={'actual_k': 2, 'was_impossible': False}),
 Prediction(uid='User 2', iid='Movie 8', r_ui=4.0, est=4.0, details={'actual_k': 1, 'was_impossible': False}),
 Prediction(uid='User 4', iid='Movie 9', r_ui=1.0, est=2.0, details={'actual_k': 1, 'was_impossible': False}),
 Prediction(uid='User 2', iid='Movie 4', r_ui=5.0, est=3.0, details={'actual_k': 1, 'was_impossible': False}),
 Prediction(uid='User 4', iid='Movie 11', r_ui=4.0, est=3.0000000000000004, details={'actual_k': 1, 'was_impossible': False}),
 Prediction(uid='User 2', iid='Movie 10', r_ui=4.0, est=3.0000000000000004, details={'actual_k': 1, 'was_impossible': False}),
 Prediction(uid='User 5', iid='Movie 5', r_ui=1.0, est=2.0555555555555554, details={'actual_k': 2, 'was_impossible': False})]

Using the entire dataset

Above, we did a train test split, but we can also use the entire dataset and train a model based on that. We do that next.

# You can also use the entire dataset without doing a train-test split
trainset = data.build_full_trainset()

# Build an algorithm, and train it.
algo = KNNBasic()
algo.fit(trainset)
algo.predict(uid='User 4', iid='Movie 6')

Computing the msd similarity matrix...
Done computing similarity matrix.





Prediction(uid='User 4', iid='Movie 6', r_ui=None, est=2.5714285714285716, details={'actual_k': 2, 'was_impossible': False})

---

Tying it all up

The above is interesting, but in fact what we need is a prediction of what to recommend to each user. The code below brings everything together.

Below is a full implementation that uses the ratings data to predict ratings for the missing ratings, and then provides what movies to recommend to each user.

We fit our algorithm on the entire dataset, then get predictions on the empty rating cells using a method build_anti_testset(). A function iterates through everything, sorts and brings out the movies to recommend.

# Source: https://surprise.readthedocs.io/en/stable/FAQ.html#how-to-get-the-top-n-recommendations-for-each-user

from collections import defaultdict

from surprise import SVD
from surprise import Dataset


def get_top_n(predictions, n=10):
    """Return the top-N recommendation for each user from a set of predictions.

    Args:
        predictions(list of Prediction objects): The list of predictions, as
            returned by the test method of an algorithm.
        n(int): The number of recommendation to output for each user. Default
            is 10.

    Returns:
    A dict where keys are user (raw) ids and values are lists of tuples:
        [(raw item id, rating estimation), ...] of size n.
    """

    # First map the predictions to each user.
    top_n = defaultdict(list)
    for uid, iid, true_r, est, _ in predictions:
        top_n[uid].append((iid, est))

    # Then sort the predictions for each user and retrieve the k highest ones.
    for uid, user_ratings in top_n.items():
        user_ratings.sort(key=lambda x: x[1], reverse=True)
        top_n[uid] = user_ratings[:n]

    return top_n


# First train an SVD algorithm on the movielens dataset.
# data = Dataset.load_builtin('ml-100k')
trainset = data.build_full_trainset()
algo = SVD()
algo.fit(trainset)

# Than predict ratings for all pairs (u, i) that are NOT in the training set.
testset = trainset.build_anti_testset()
predictions = algo.test(testset)

top_n = get_top_n(predictions, n=10)

# Print the recommended items for each user
for uid, user_ratings in top_n.items():
    print(uid, [iid for (iid, _) in user_ratings])

User 1 ['Movie 10', 'Movie 8', 'Movie 4', 'Movie 11', 'Movie 6']
User 2 ['Movie 12', 'Movie 2', 'Movie 3', 'Movie 7', 'Movie 9', 'Movie 5']
User 3 ['Movie 8', 'Movie 2', 'Movie 10', 'Movie 6', 'Movie 12', 'Movie 3', 'Movie 5']
User 5 ['Movie 10', 'Movie 6', 'Movie 8', 'Movie 11', 'Movie 9', 'Movie 3', 'Movie 1']
User 4 ['Movie 2', 'Movie 1', 'Movie 4', 'Movie 3']