Recommendation System

Lecture 02

• Fardina Fathmiul Alam

CMSC 320 - Introduction to Data Science

2026

​

COLLABORATIVE FILTERING

​

TYPE 2: Item-based collaborative filtering

COLLABORATIVE FILTERING: ANOTHER VERSION

Alternative view that often works better: Item-Item (NEXT)

COLLABORATIVE FILTERING: TYPES

​

Item-based collaborative filtering:

Item-Based CF recommends items based on similarity between items

CORE IDEA:

• Instead of finding similar users, we find similar items (movies/products)
• Then recommend items similar to what the user already liked

How?

• Look at items the user has already rated
• Find other items that are similar to those items
• Recommend items with high similarity scores

Item-based collaborative filtering

But how do we know about this ‘similarity’?

​

we compute similarity using user ratings.

Item-based collaborative filtering

If same users give similar ratings to two items, then those items are considered similar

​

Item-based CF

• does not care about genres, descriptions, or any content features at all.

Two completely unrelated movies could be "similar" just because the same audience watches and rates them the same way.

• The similarity is purely behavioural, not content-based.

​

STEPS OF Item-based collaborative filtering

1. Build item-user matrix
1. Rows = items, columns = users [we can also create vice versa], Values = interactions (ratings/purchases)
2. Compute item-item similarity (Cosine / Pearson)
3. For a target item: Find similar items
4. Use user’s ratings on those items to:
• Predict rating

​

​

​

​

​

​

1. Recommend Top-N items

​

Courtesy: Jure Leskovec & Mina Ghashami, Stanford

Algorithm: “Rate an unseen item i as the mean of my ratings for other items, weighted by their similarity to i.”

Note: The matrix is sparse, but the empty cells are not (necessarily) zero!

EXAMPLE (ITEM-ITEM CF)

Item-based collaborative filtering: Let’s say, |N| =2 (the size of the neighborhood, or the number of similar items)

Figure: User - Item Interaction Matrix where Movie Ratings is between [1-5].

EXAMPLE (ITEM-ITEM CF; |N|=2)

Let’s say, we want to know what USER 5 think about Movie 1?

You want to predict whether User 5 will like Movie 1, given that they already liked Movies 3, 4, 5, and 6.

​

• Find items similar to Movie 1 — i.e., how similar Movie 1 is to Movies 3, 4, 5, and 6 (based on how other users rated them) → similarity calculation to identify the most similar items.
• For |N| = 2 (i.e., the top 2 most similar movies): Check if User 5 liked those similar movies: Example: If Movie 1 is similar to Movies 3 and 5, and User 5 liked Movies 3 and 5 → high chance User 5 will like Movie 1.
• Predict a rating or score for Movie 1 using weighted similarity

​

Notes: Here,

• We are not comparing User 5 to other users.
• We doesn’t care what other users think about Movie 1 — only how Movie 1 relates to the items that User 5 liked.

EXAMPLE (ITEM-ITEM CF; |N|=2): NEIGHBOUR SELECTION

Let’s say, we want to know what USER 5 think about Movie 1?

Let’s say, we already know that, Movie 3 and Movie 6 are most similar to Movie 1.

We now need to calculate similarity between these rows!

Step 2: Similarity measure between Items (using cosine similarity)

When computing similarity between two movies, we must use only users who have rated both movies (overlapping co-rated users).

​

​

• sim(Movie 1, Movie 2) =0.75 (Common users: User 3, 11 )

​

• sim(Movie 1, Movie 3) = 0.97 (Common users: User 1, 9 , 11)
• sim(Movie 1, Movie 4) = 0.89 (Common users: User 3, 11)
• sim(Movie 1, Movie 5)= 0.86 (Common users: User 3,6, 11)
• sim(Movie 1, Movie 6)= 1.0 (Common users: User 1,3,11)

s(1,M)

1.0

0.75

0.97

0.89

0.86

1.0

** Common users = intersection of users who rated both items.

N=2. so movie 3 and 6 are most 2 similar movies to movie 5

Step 2: Similarity measure between Items (using cosine similarity)

When computing similarity between two movies, we must use only users who have rated both movies (overlapping co-rated users).

​

​

• sim(Movie 1, Movie 2) =0.75 (Common users: User 3, 11 )

​

• sim(Movie 1, Movie 3) = 0.97 (Common users: User 1, 9 , 11)
• sim(Movie 1, Movie 4) = 0.89 (Common users: User 3, 11)
• sim(Movie 1, Movie 5)= 0.86 (Common users: User 3,6, 11)
• sim(Movie 1, Movie 6)= 1.0 (Common users: User 1,3,11)

s(1,M)

1.0

0.75

0.97

0.89

0.86

1.0

** Common users = intersection of users who rated both items.

N=2. so movie 3 and 6 are most 2 similar movies to movie 5

Step 2: Similarity measure between Items (using cosine similarity)

** Common users = intersection of users who rated both items.

Item- Item Similarity Calculation Summary

Step 3: PREDICT AND RECOMMEND using Cosine Similarity

what USER 5 think about Movie 1?

User 5 rated:

• Movie 3 = 2
• Movie 6 = 3

So both top-2 movies are usable.

​

​

​

​

​

APPROXIMATE RATING WITH WEIGHTED MEAN

​

Predicted rating for User 5 on Movie 1 = 2.51.

2.51

OPTION 2: Pearson Correlation

We will use same example but this time will use Pearson Correlation (Centered Cosine) instead of cosine similarity to calculate similarity between items.

What USER 5 think about Movie 1?

Here we use “mean centered item-overlap cosine as similarity:

1. Subtract mean rating mi from each movie i
2. Compute (item-overlapping) cosine similarities between rows

Let’s say, we already know that, Movie 3 and Movie 6 are most similar to Movie 1.

EXAMPLE (ITEM-ITEM CF; |N|=2): SIMILARITY CALCULATION

Let’s say, we want to know what USER 5 think about Movie 1?

Compute Cosine Similarity S(1,m):

2. Compute (item-overlapping) cosine similarities between rows

​

EXAMPLE (ITEM-ITEM CF; |N|=2): SIMILARITY CALCULATION

Let’s say, we want to know what USER 5 think about Movie 1?

Compute Similarity Weight:

​

S_1,3 = 0.658

​

S_1,6= 0.768

​

We computed S_1,2, S_1,4,S_1,6 too! Let’s assume those are smaller!

​

​

​

​

​

Sim(1,m)

​

1.000

…

0.658

…

…

​

0.768

EXAMPLE (ITEM-ITEM CF; |N|=2): APPROXIMATE RATING WITH WEIGHTED MEAN

​

Let’s say, we want to know what USER 5 think about Movie 1?

Predict By Taking Weighted Average:

​

R_{user1,movies5} = R_1,5 =

​

(0.658*2 +0.768*3) / (0.658+0.768)

​

=2.54

~ 2.6

​

​

​

​

Sim(1,m)

​

1.000

…

0.658

…

…

​

0.768

EXAMPLE (ITEM-ITEM CF; |N|=2): APPROXIMATE RATING WITH WEIGHTED MEAN

​

Let’s say, we want to know what USER 5 think about Movie 1?

Predict By Taking Weighted Average:

​

R_{user1,movies5} = R_1,5 =

​

(0.658*2 +0.768*3) / (0.658+0.768)

​

=2.54

~ 2.6

​

​

​

Pros and Cons of Item based CF

Next: EVALUATION OF RECOMMENDATION SYSTEM

​

​

EVALUATION OF RECOMMENDATION SYSTEM

​

As always, before we use this algorithm, we'd like to know how well it performs!

What unique challenges are present here?

A sample user:

Ant Man Endgame Thor 1 Return of Thor Iron Dude

Justin 1 0 1 0 1

The challenge: We don't know if no rating means the person doesn't know about the movie, or if they do know about it and knew not to watch it because they wouldn't like it.

EVALUATION OF RECOMMENDATION SYSTEM

EVALUATION OF RECOMMENDATION SYSTEM cont.

​

PER USER LEAVE-ONE-OUT-CROSS-VALIDATION

For each user, leave out one thing they've rated, and then predict the rating.

​

This tells us about how well we do at the things the user has seen (already rated), but we have no idea how they're doing with the things they haven't (new, not rated yet).

Collaborative vs Content Based Differences

(SOME MORE)�RECOMMENDER SYSTEMS (ISH)

26

ASSOCIATION RULES

In today's data-driven world, businesses strive to understand the relationships between different products or items purchased together by customers.

​

This understanding allows them to optimize marketing strategies, enhance product recommendations, and improve overall customer experience

ASSOCIATION RULES

Collaborative Filtering predicts preferences based on similar users' ratings

Complementary idea: Find rules that associate/connect the presence of one set of items with that of another set of items

​

28

Association rules are about finding connections between different sets of items. For example, if people often buy chips when they buy salsa, that's an association rule. It helps us understand how items are related to each other in a shopping basket.

ASSOCIATION RULES and RECOMMENDATION SYSTEM

• Identifies patterns and relationships between items in a dataset.
• Enhances recommendation systems by revealing item associations and user preferences.
• Leads to more diverse and accurate recommendations tailored to individual users.

We will now learn

• What is Association Rules
• What is Frequent Itemset
• Mining Association Rules: Two Steps
• Frequent Itemset Generation
• Apriori principle
• Rule Generation

​

Association rules

Idea: Association rules discover relationships between items that frequently occur together in transactions.

• Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction.

(when customers buy diapers, they are likely to also buy beer.)

Buying one set of items doesn't cause the purchase of another set. Instead, they tend to occur together frequently in transactions.

DEFINITION: FREQUENT ITEMSET

= 0/4 0r 40%

(or Frequency)

Association Rule Evaluations Matrics

S: measure the frequency of items appearing together.

C: How much more likely two items are bought together than by chance.

How often B is bought after A.

measures how likely it is for an item (consequent) to be bought when another set of items (antecedents) is already in the cart.

ASSOCIATION RULE MINING TASK

From a set of transactions T, find all rules where:

• Support≥ minsup threshold
• confidence ≥ minconf threshold

(Thresholds are set using business needs, domain knowledge, or trial and error.)

​

Brute-force approach:-

• List all possible association rules
• Compute the support and confidence for each rule
• Prune rules that fail the minsup and minconf thresholds

Computationally prohibitive!

Example: MINING ASSOCIATION RULES

Observations:

• All the above rules are binary partitions of the same itemset: {Milk, Diaper, Beer}
• Rules from the same set have identical support (s=0.4) but varying confidence (c).
• Thus, we may can adjust confidence independently of support, allowing flexibility in rule generation.

MINING ASSOCIATION RULES: TWO STEPS

Two-step approach:

​

1. Frequent Itemset Generation

• Generate all itemsets whose support count greater than or equal to minsup.

​

2. Rule Generation

​

• Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset

FREQUENT ITEMSET GENERATION IS STILL COMPUTATIONALLY EXPENSIVE

ONE SOLUTION: REDUCING NUMBER OF CANDIDATES

Apriori principle:- If an itemset is frequent, then all of its subsets must also be frequent

Illustrating Apriori Principle

Next:

Illustrating Apriori Principle for “Frequent Itemset Generation”

​

Set minimum support threshold.�

Find all frequent 1-itemsets.�

• Generate candidate 2-itemsets from frequent 1-itemsets.
• Prune candidates whose subsets are not frequent.
• Calculate Support Count (Frequency) for remaining candidates by scanning transactions.�

Repeat (generate 3-itemsets, then 4, etc.) until no more frequent itemsets.

ILLUSTRATING APRIORI PRINCIPLE

1. Frequent Itemset Generation

Given:

Calculate Support Count or Frequency

STEP 01: “1-ITEMSET GENERATION

Minimum Support Count (min_sup) = 3

ILLUSTRATING APRIORI PRINCIPLE

Frequent Itemset Generation

Given:

STEP 02: “2-ITEMSET GENERATION” FROM “1-ITEMSETS

Calculate Support Count or Frequency

Minimum Support Count (min_sup) = 3

ILLUSTRATING APRIORI PRINCIPLE

Frequent Itemset Generation

Given:

STEP 03: “3-ITEMSET GENERATION” FROM “2-ITEMSETS

2

Minimum Support Count (min_sup)= 3

ILLUSTRATING APRIORI PRINCIPLE

Frequent Itemset Generation

Given:

2

Minimum Support Count (min_sup) = 3

ILLUSTRATING APRIORI PRINCIPLE

Frequent Itemset Generation

Given:

Support

(No need to

generate candidates involving {Bread, Bear} or {Milk Bear}

2

Minimum Support

Count (min_sup) = 3

APRIORI ALGORITHM/ PRINCIPLE

Rule Generation: How to efficiently generate rules from frequent itemsets?

Given, min confidence = 70%

Confidence (X →Y) :

​

Our frequent itemsets: {BREAD}, {MILK}, {BEER}, {DIAPER},{BREAD,MILK}, {BREAD,DIAPER}, {MILK,DIAPER}, {BEER, ,DIAPER}

​

Therefore, candidate rules are:

​

For {BREAD,MILK}, there are two possibilities:

• Bread > Milk: 3/4: 0.75
• Milk > Bread: 3/4: 0.75

​

For {BEER, ,DIAPER}, there are two possibilities:

• Beer > Diaper: 3/3: 1 (strong!)
• Diaper > Bear: 3/4: 0.75

​

Continue the proceed for other all frequent datasets.

ANOTHER EXAMPLE: Rule Generation: LETS SAY {BREAD,MILK, DIAPER} is FREQUENT

Given, min confidence = 70%

Confidence (X →Y) :

​

We have 5 frequent itemsets: {BREAD,MILK},

{BREAD,DIAPER}, {MILK,DIAPER}, {BEER, ,DIAPER}, {BREAD,MILK, DIAPER}

​

​

For {BREAD,MILK ,DIAPER}, some possibilities:

• BREAD,MILK > Diaper: 3/3: 1
• MILK, DIAPER > BREAD: 3/3: 1
• BREAD, MILK > Diaper: 3/3 : 1

​

​

​

Another Example: Apriori Principle

There is only one itemset with minimum support 2. So

Try �[Coke^Chips]=>[Hot Dogs] ,

[Hot Dogs]=>[Coke^Chips] Assoc Rules

(min_sup)

The End

Additional Reading

Try if you are interested in collaborative filtering:

https://gist.github.com/marianamaroto/633da2272fea4aaf101cdff9e0393aa6#file-netflix_recommendation_system-ipynb

​

(NOT FOR THE EXAM)

ITEM-ITEM vs USER-USER

In practice, it has been observed that often works better than user-user item-item!

• Why? Items are simpler, users have multiple tastes (people are dynamic, their taste change while on the other hand items are constant)
• Item-based filtering finds similar items to what a person likes, no matter what others like.

Example:

Alice likes action but not romance.

Bob likes comedy and romance but not action.

Item-based filtering suggests movies based on what Alice or Bob liked, fitting their unique tastes.

Example: User Based Neighboorhood Collaborative Filtering

Scenario: Suppose User A and User B have similar movie preferences. User A has watched and liked movies X, Y, and Z.

​

Process: The system identifies User B as a similar user based on their past movie preferences. If User B has also liked movies X, Y, and Z, the system recommends other movies that User B has liked but User A hasn't seen yet.

​

Example: User A likes action movies, and the system identifies User B as having similar tastes. User B has watched and enjoyed movies W, X, and Y. The system recommends movie W to User A because it's likely to align with their preferences.

Example: Item Based Filtering

Scenario: Consider a scenario where a user has watched and liked movie X.

​

Process: The system identifies other movies that are similar to movie X based on certain criteria such as genre, actors, or director. It then recommends these similar movies to the user.

​

Example: User A likes the movie X, which is a science fiction film featuring actor A and directed by Director B. The system identifies other science fiction movies with actor A or directed by Director B, such as movies Y and Z, and recommends them to User A because of their similarity to movie X.