COMP9313: Big Data Management
Course web site: http://www.cse.unsw.edu.au/~cs9313/
Chapter 9:
Recommender Systems
Recommendations
Recommendations
Products, web sites, blogs, news items, …
Recommender Systems
Recommender Systems
❖ Application areas
➢ Movie recommendation (Netflix)
➢ Related product recommendation (Amazon) ➢ Web page ranking (Google)
➢ Social recommendation (Facebook)
Netflix Movie Recommendation
Why using Recommender Systems?
❖ Value for the customer
➢ Find things that are interesting
➢ Narrow down the set of choices
➢ Help me explore the space of options ➢ Discover new things
➢ Entertainment
❖ Value for the provider
➢ Additional and probably unique personalized service for the customer ➢ Increase trust and customer loyalty
➢ Increase sales, click trough rates, conversion etc.
➢ Opportunities for promotion, persuasion
➢ Obtain more knowledge about customers
The Impact of Recommender Systems
❖ 35% of the purchases on Amazon are the result of their recommender system, according to McKinsey.
❖ During the Chinese global shopping festival of November 11, 2016, Alibaba achieved growth of up to 20% of their conversion rate using personalized landing pages, according to Alizila.
❖ Recommendations are responsible for 70% of the time people spend watching videos on YouTube.
❖ 75% of what people are watching on Netflix comes from recommendations, according to McKinsey
❖ Employing a recommender system enables Netflix to save around $1 billion each year, according to the paper “The Netflix Recommender System: Algorithms, Business Value, and Innovation”
https://tryolabs.com/blog/introduction-to-recommender-systems/
Recommender systems
❖ RS seen as a function ❖ Given:
➢ User model (e.g. ratings, preferences, demographics, situational context)
➢ Items (with or without description of item characteristics) ❖ Find:
➢ Relevance score. Used for ranking. ❖ Finally:
➢ Recommend items that are assumed to be relevant ❖ But:
➢ Remember that relevance might be context-dependent
➢ Characteristics of the list itself might be important (diversity)
❖ X = set of Customers
❖ S = set of Items
❖ Utility function u: X × S→R
➢ R = set of ratings
➢ R is a totally ordered set
➢ e.g., 0-5 stars, real number in [0,1]
❖ Utility Matrix
Formal Model
Key Problems
❖ Gathering “known” ratings for matrix
➢ How to collect the data in the utility matrix
❖ Extrapolate unknown ratings from the known ones ➢ Mainly interested in high unknown ratings
We are not interested in knowing what you don’t like but what you like
❖ Evaluating extrapolation methods
➢ How to measure success/performance of recommendation methods
Gathering Ratings
❖ Explicit
➢ Ask people to rate items
➢ Doesn’t work well in practice – people can’t be bothered
❖ Implicit
➢ Learn ratings from user actions
E.g., purchase implies high rating
Paradigms of Recommender Systems
Recommender systems reduce information overload by estimating relevance
Paradigms of Recommender Systems
Personalized recommendations
Paradigms of Recommender Systems
Collaborative: “Tell me what’s popular among my peers”
Paradigms of Recommender Systems
Content-based: “Show me more of the same what I’ve liked”
Paradigms of Recommender Systems
Knowledge-based: “Tell me what fits based on my needs”
Paradigms of Recommender Systems
Hybrid: combinations of various inputs and/or composition of different mechanism
Paradigms of Recommender Systems
❖ Content-based – supervised machine learning used to induce a classifier to discriminate between interesting and uninteresting items for the user
❖ Collaborative – aggregation of consumers’ preferences and recommendations to other users based on similarity in behavioral patterns
❖ Knowledge-based – knowledge about users and products used to reason what meets the user’s requirements, using discrimination tree, decision support tools, case-based reasoning (CBR)
Part 2: Content
show me more of the same what I’ve liked
based Recommendation
❖ Main idea: Recommend items to customer x similar to previous items rated highly by x
❖ What do we need:
➢ Some information about the available items such as the genre
(“content”)
➢ Some sort of user profile describing what the user likes (the preferences)
❖ Example:
➢ Movie recommendations:
Recommend movies with same actor(s), director, genre, … ➢ Websites, blogs, news:
Recommend other sites with “similar” content 9.21
based Recommendations
Plan of Action
Item profiles
Circles Triangles
User profile
What is the “Content”?
❖ Most CB-recommendation techniques were applied to recommending text documents.
➢ Like web pages or newsgroup messages for example.
❖ Content of items can also be represented as text documents.
➢ With textual descriptions of their basic characteristics.
➢ Structured: Each item is described by the same set of attributes
The Night of the Gun
Press and journalism, drug addiction, personal memoirs,
The Lace Reader
Fiction, Mystery
American contemporary fiction, detective, historical
Into the Fire
Romance, Suspense
Suzanne Brockmann
American fiction, murder, neo-Nazism
➢ Unstructured: free-text description. 9.23
❖ For each item, create an item profile
❖ Profile is a set (vector) of features
➢ Movies: author, title, actor, director,…
➢ Text: Set of “important” words in document
❖ How to pick important features?
➢ Usual heuristic from text mining is TF-IDF
(Term frequency * Inverse Doc Frequency)
Term … Feature Document … Item
Item Profiles
Frequency (TF
❖ Compute the overall importance of keywords ➢ Given a keyword i and a document j
TF-IDF (i,j) = TF(i,j) * IDF(i)
❖ Term frequency (TF)
➢ Let freq(i,j) number of occurrences of keyword i in document j
➢ Let maxOthers(i,j) denote the highest number of occurrences of another keyword of j
➢𝑇𝐹𝑖,𝑗 = 𝑓𝑟𝑒𝑞(𝑖,𝑗) 𝑚𝑎𝑥𝑂𝑡h𝑒𝑟𝑠(𝑖,𝑗)
❖ Inverse Document Frequency (IDF)
➢ N: number of all recommendable documents
➢ n(i): number of documents in which keyword i appears
➢𝐼𝐷𝐹(𝑖)=𝑙𝑜𝑔 𝑁 𝑛(𝑖)
Inverse Document
User Profiles and Prediction
❖ User profile possibilities:
➢ Weighted average of rated item profiles
➢ Variation: weight by difference from average rating for item ➢…
❖ Prediction heuristic:
➢ Given user profile x and item profile i, estimate
𝑢(𝒙,𝒊) = cos(𝒙,𝒊) = 𝒙·𝒊 |𝒙|⋅|𝒊|
Pros: Content
❖ +: No need for data on other users
❖ +: Able to recommend to users with unique tastes
❖ +: Able to recommend new & unpopular items ➢ No first-rater problem
❖ +: Able to provide explanations
➢ Can provide explanations of recommended items by listing
content-features that caused an item to be recommended
based Approach
Cons: Content
❖ –: Finding the appropriate features is hard ➢ E.g., images, movies, music
❖ –: Recommendations for new users ➢ How to build a user profile?
❖ –: Overspecialization
➢ Never recommends items outside user’s content profile ➢ People might have multiple interests
➢ Unable to exploit quality judgments of other users
based Approach
Part 3: Collaborative Filtering
show me more items favored by others who have similar tastes with me
Collaborative Filtering (CF)
❖ The most prominent approach to generate recommendations ➢ used by large, commercial e-commerce sites
➢ well-understood, various algorithms and variations exist ➢ applicable in many domains (book, movies, DVDs, ..)
❖ Approach
➢ use the “wisdom of the crowd” to recommend items
❖ Basic assumption and idea
➢ Users give ratings to catalog items (implicitly or explicitly)
➢ Customers who had similar tastes in the past, will have similar tastes in the future
❖ Consider user x
❖ Find set N of other users whose ratings are “similar” to
x’s ratings
❖ Estimate x’s ratings based on ratings
of users in N
Collaborative Filtering
based ollaborative
– iltering
❖ The basic technique
➢ Given an “active user” (Alice) and an item 𝑖 not yet seen by Alice
find a set of users (peers/nearest neighbors) who liked the same items as Alice in the past and who have rated item 𝑖
use, e.g. the average of their ratings to predict, if Alice will like item 𝑖
do this for all items Alice has not seen and recommend the best-rated
❖ Basic assumption and idea
➢ If users had similar tastes in the past they will have similar tastes
in the future
➢ User preferences remain stable and consistent over time
based ollaborative
– iltering
➢ A database of ratings of the current user, Alice, and some other
users is given:
➢ Determine whether Alice will like or dislike Item5, which Alice has not yet rated or seen
based ollaborative
– iltering
❖ Some first questions
➢ How do we measure similarity?
➢ How many neighbors should we consider?
➢ How do we generate a prediction from the neighbors’ ratings?
Finding “Similar” Users
❖ Let rx be the vector of user x’s ratings ||𝑟 ∩𝑟 ||
❖ Jaccard similarity measure 𝑥 𝑦 ||𝑟 ∪𝑟 ||
rx = [*, _, _, *, ***]
ry = [*, _, **, **, _]
➢ Problem: Ignores the value of the rating ❖ Cosine similarity measure
➢ Problem: Treats missing ratings as “negative” ❖ Pearson correlation coefficient
➢ Sxy = items rated by both users x and y
➢ sim(x, y) = cos(rx, ry) = 𝑥 𝑦 ||𝑟 ||⋅||𝑟 ||
rx, ry as sets:
rx = {1, 4, 5}
ry = {1, 3, 4}
σ𝒔∈𝑺𝒙𝒚 𝒓𝒙𝒔 − 𝒓𝒙
σ 𝒓 −𝒓 𝟐 σ 𝒔∈𝑺𝒙𝒚 𝒙𝒔 𝒙
𝒓 −𝒓 𝟐 𝒔∈𝑺𝒙𝒚 𝒚𝒔 𝒚
rx,ry…avg. rating of x, y
rx, ry as points:
rx = {1, 0, 0, 1, 3}
ry = {1, 0, 2, 2, 0}
Similarity Metric
Cosine similarity:
𝒔𝒊𝒎(𝒙, 𝒚) =
σ𝒊 𝒓𝒙𝒊 ⋅ 𝒓𝒚𝒊
σ 𝒓𝟐 ⋅ σ 𝒓𝟐 𝒊𝒙𝒊 𝒊𝒚𝒊
❖ Intuitively we want: sim(A, B) > sim(A, C) ❖ Jaccard similarity: 1/5 < 2/4
❖ Cosine similarity: 0.380 > 0.322
➢ Considers missing ratings as “negative” ➢ Solution: subtract the (row) mean
sim A,B vs. A,C: 0.092 > -0.559
Notice cosine sim. is correlation when data is centered at 0
Similarity Metric (
❖ A popular similarity measure in user-based CF: Pearson correlation
σ𝒔∈𝑺𝒙𝒚 𝒓𝒙𝒔 − 𝒓𝒙 𝒓𝒚𝒔 − 𝒓𝒚 σ𝒔∈𝑺𝒙𝒚 𝒓𝒙𝒔 − 𝒓𝒙 𝟐 σ𝒔∈𝑺𝒙𝒚 𝒓𝒚𝒔 − 𝒓𝒚
➢ Possible similarity values between -1 and 1;
sim = 0,85
sim = 0,00 sim = 0,70 sim = -0,79
➢𝑟=1σ𝑟 𝑥𝑖 𝑘 𝑦∈𝑁𝑦𝑖
➢ 𝑟 = σ𝑦∈𝑁 𝑠𝑥𝑦⋅𝑟𝑦𝑖
➢ Other options?
❖ Many other tricks possible…
Rating Predictions
From similarity metric to recommendations:
❖ Let rx be the vector of user x’s ratings
❖ Let N be the set of k users most similar to x who have rated item i ❖ Prediction for item s of user x:
Shorthand:
𝒔𝒙𝒚 = 𝒔𝒊𝒎 𝒙, 𝒚
r=b+ xi xi
jN(i;x) s
CF: Common Practice
❖ Define similarity sij of users i and j ❖ Select k nearest neighbors N(i; x)
➢ Users most similar to i, that have ratings on x ❖ Estimate rating rxi as the weighted average:
s (r −b ) ij xj xj
baseline estimate for rxi 𝒃𝒙𝒊 = 𝝁 + 𝒃𝒙 + 𝒃𝒊
μ = overall mean movie rating bx = rating deviation of user x = (avg. rating of user x) – μ
bi = rating deviation of movie i 9.39
r =jN(i;x)sr
ij xi jN(i;x) s
❖ User-based CF is said to be “memory-based”
➢ the rating matrix is directly used to find neighbors / make
predictions
➢ does not scale for most real-world scenarios
➢ large e-commerce sites have tens of millions of customers and millions of items
❖ Model-based approaches
➢ based on an offline pre-processing or “model-learning” phase ➢ at run-time, only the learned model is used to make predictions ➢ models are updated / re-trained periodically
➢ large variety of techniques used
➢ model-building and updating can be computationally expensive
based and Model
based Approaches
❖ So far: User-user collaborative filtering ❖ Another view: Item-item
➢ Basic idea:
Use the similarity between items (and not users) to make
predictions
➢ For item i, find other similar items
➢ Estimate rating for item i based on ratings for similar items
➢ Can use same similarity metrics and prediction functions as in user-user model
sij… similarity of items i and j rxj…rating of user u on item j
N(i;x)… set items rated by x similar to i
Item Collaborative Filtering
ij jN(i;x) s
jN(i;x) xi
❖ Example:
➢ Look for items that are similar to Item5
➢ Take Alice’s ratings for these items to predict the rating for Item5
Item Collaborative Filtering
1 2 3 4 5 6 7 8 9 10 11 12 1
Item CF (|N|=2)
– unknown rating
– rating between 1 to 5
1 2 3 4 5 6 7 8 9 10 11 12 1
Item CF (|N|=2)
– estimate rating of movie 1 by user 5 9.44
1 2 3 4 5 6 7 8 9 10 11 12 1
Item CF (|N|=2)
sim(1,m) 1.00
-0.18 0.41 -0.10 -0.31 0.59
Here we use Pearson correlation as similarity: 1) Subtract mean rating mi from each movie i
m1 = (1+3+5+5+4)/5 = 3.6
row 1: [-2.6, 0, -0.6, 0, 0, 1.4, 0, 0, 1.4, 0, 0.4, 0] 2) Compute cosine similarities between rows
Neighbor selection:
Identify movies similar to movie 1, rated by user 5
1 2 3 4 5 6 7 8 9 10 11 12 1
Item CF (|N|=2)
sim(1,m) 1.00
-0.18 0.41 -0.10 -0.31 0.59
Compute similarity weights:
s1,3=0.41, s1,6=0.59
1 2 3 4 5 6 7 8 9 10 11 12 1
Item CF (|N|=2)
Predict by taking weighted average:
r1.5 = (0.41*2 + 0.59*3) / (0.41+0.59) = 2.6 9.47
𝒓𝒊𝒙 = σ𝒋∈𝑵(𝒊;𝒙) 𝒔𝒊𝒋 ⋅ 𝒓𝒋𝒙 σ𝒔𝒊𝒋
Item vs. User
In practice, it has been observed that item-item often works better than user-user
Why? Items are simpler, users have multiple tastes 9.48
Pros/Cons of Collaborative Filtering
❖ + Works for any kind of item
➢ No feature selection needed ❖ – Cold Start:
➢ Need enough users in the system to find a match ❖ – Sparsity:
➢ The user/ratings matrix is sparse
➢ Hard to find users that have rated the same items ❖ – First rater:
➢ Cannot recommend an item that has not been previously rated
➢ New items, Esoteric items ❖ – Popularity bias:
➢ Cannot recommend items to someone with unique taste ➢ Tends to recommend popular items
More on Ratings
❖ Probably the most precise ratings
❖ Most commonly used (1 to 5, 1 to 7 Likert response scales)
❖ Main problems
➢ Users not always willing to rate many items
number of available ratings could be too small → sparse rating matrices → poor recommendation quality
➢ How to stimulate users to rate more items?
Explicit Ratings
More on Ratings
❖ Typically collected by the web shop or application in which the recommender system is embedded
❖ When a customer buys an item, for instance, many recommender systems interpret this behavior as a positive rating
❖ Clicks, page views, time spent on some page, demo downloads …
❖ Implicit ratings can be collected constantly and do not require
additional efforts from the side of the user
❖ Main problem
➢ One cannot be sure whether the user behavior is correctly interpreted
➢ For example, a user might not like all the books he or she has bought; the user also might have bought a book for someone else
❖ Implicit ratings can be used in addition to explicit ones; question of correctness of interpretation
Implicit Ratings
Collaborative Filtering: Complexity
❖ Expensive step is finding k most similar customers: O(|X|)
❖ Too expensive to do at runtime
➢ Could pre-compute
❖ Naïve pre-computation takes time O(k ·|X|)
– X … set of customers
❖ Ways of doing this:
➢ Near-neighbor search in high dimensions (LSH) ➢ Clustering
➢ Dimensionality reduction
❖ Supported by Hadoop: Apache Mahout https://mahout.apache.org/users/basics/algorithms.html
What is a Good Recommendation in Practice?
❖ Total sales numbers
❖ Promotion of certain items
❖ Click-through-rates
❖ Interactivity on platform
❖ Customer return rates
❖ Customer satisfaction and loyalty
Evaluation
Evaluation
Test Data Set
Evaluating Predictions
❖ Compare predictions with known ratings ➢ Root-mean-square error (RMSE)
σ 𝑟 − 𝑟∗ 2 where 𝒓 is predicted, 𝒓∗ is the true rating of x on i 𝑥𝑖 𝑥𝑖 𝑥𝑖 𝒙𝒊 𝒙𝒊
➢ Precision at top 10:
% of those in top 10
➢ Rank Correlation:
Spearman’s correlation between system’s and user’s complete
❖ Another approach: 0/1 model ➢ Coverage:
Number of items/users for which system can make predictions ➢ Precision:
Accuracy of predictions
➢ Receiver operating characteristic (ROC)
Tradeoff curve between false positives and false negatives 9.56
The Netflix Prize
❖ Training data
➢ 100 million ratings, 480,000 users, 17,770 movies ➢ 6 years of data: 2000-2005
❖ Test data
➢ Last few ratings of each user (2.8 million)
➢ Evaluation criterion: Root Mean Square Error (RMSE) =
➢ Netflix’s system RMSE: 0.9514 ❖ Competition
➢ 2,700+ teams
➢ $1 million prize for 10% improvement on Netflix
The Netflix Utility Matrix
17,700 movies
480,000 users
17,700 movies
Training Data Set
Utility Matrix
480,000 users
: Evaluation
Test Data Set
RMSE=1σ 𝑟Ƹ−𝑟 R (𝑖,𝑥)∈𝑅 𝑥𝑖 𝑥𝑖
True rating of user x on item i
Bell System
❖ The winner of the Netflix Challenge!
❖ Multi-scale modeling of the data: Combine top level, “regional” modeling of the data, with
a refined, local view:
Overall deviations of users/movies
➢ Factorization:
Addressing “regional” effects
➢ Collaborative filtering: Extract local patterns
Global effects
Factorization
Collaborative filtering
Modeling Local & Global Effects
➢ Mean movie rating: 3.7 stars
➢ The Sixth Sense is 0.5 stars above avg.
➢ Joe rates 0.2 stars below avg.
Baseline estimation:
Joe will rate The Sixth Sense 4 stars
❖ Local neighborhood (CF/NN):
➢ Joe didn’t like related movie Signs
➢ Final estimate:
Joe will rate The Sixth Sense 3.8 stars