Machine Learning II:

Association Rules and Recommendation

Patrick Hall

Visiting Faculty, Department of Decision Sciences

George Washington University

Lecture 11 Agenda

• Association Rules
• Rule Evaluation Metrics
• Market Basket Analysis
• Interlude: Supervised Rule-based Models
• Recommendations
• Netflix Case
• Readings

Where are we in the modeling lifecycle?

Association Rules

Overview

Rule Evaluation Metrics

Overview: Association Rules

• Association analysis is useful for discovering interesting relationship(s) hidden in large data sets:
• Undiscovered relationships can be represented in the form of sets of items known as frequent itemsets or association rules.
• Association rules suggest relationships in transactions that can be used in many business practices.
• Two key issues that must be addressed in association analysis:
• Discovering patterns from large transactional datasets can be computationally expensive.
• Some of the discovered patterns may be spurious (random).

Source: Introduction to Data Mining

Mining Association Rules

Two-step approach:

​

1. Frequent itemset generation: Generate all itemsets whose support ≥ minimum support hyperparameter.�
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 computationally expensive!

Source: Introduction to Data Mining

Association Rules Mining

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.

Source: Introduction to Data Mining

Market-Basket Transactions

Examples of Association Rules:

​

• {Diaper} → {Beer}
• {Milk, Bread} → {Eggs, Coke}
• {Beer, Bread} → {Milk}

Implication means co-occurrence, not causality!

Terms and Definitions

• Itemset:
• A collection of one or more items
• Example: {Milk, Bread, Diaper}
• k-itemset
• An itemset that contains k items
• Frequent itemset:
• An itemset whose support is greater than or equal to a minimum support hyperparameter
• Support count (σ):
• Frequency of occurrence of an itemset
• E.g. , σ({Milk, Bread, Diaper}) = 2
• Support (s):
• Fraction of transactions that contain an itemset
• E.g., s({Milk, Bread, Diaper}) = 2/5

Source: Introduction to Data Mining

Rule Evaluation Metrics

• Association Rules:
• An expression of the form X → Y, where X and Y are itemsets.
• Example: {Milk, Diaper} → {Beer}
• Rule Evaluation Metrics:
• Support (s): fraction of transactions that contain both X and Y.
• Confidence (c): measures how often items in Y appear in transactions that contain X.
• Expected confidence (E[c]): number itemsets that contain Y.
• Lift (l): measure of correlation between itemsets: confidence/expected confidence.

Source: Introduction to Data Mining

Association Rules

​

​

​

​

​

​

​

Example of Rules:

{Milk, Diaper} → {Beer} (s=0.4, c=0.67)�{Milk, Beer} → {Diaper} (s=0.4, c=1.0)

{Diaper, Beer} → {Milk} (s=0.4, c=0.67)

{Beer} → {Milk, Diaper} (s=0.4, c=0.67) �{Diaper} → {Milk, Beer} (s=0.4, c=0.5)

{Milk} → {Diaper, Beer} (s=0.4, c=0.5)

Observations:

• All the rules are binary partitions of the same itemset: {Milk, Diaper, Beer}.
• Rules originating from the same itemset have identical support but can have different confidence.
• Thus, we may decouple the support and confidence requirements.

Source: Introduction to Data Mining

Probability that the two itemsets in a rule occur together.

​

​

Itemset: {KLYT6, IA45Y}

Rule: {KLYT6} → {IA45Y}

​

KLYT6 and IA45Y both occur together in ⅘ transactions

​

(KLYT6 and IA45Y) / |T|

s = 0.8

​

Support is symmetric:

s({KLYT6} → {IA45Y}) = s({IA45Y} → {KLYT6})

​

Rule Evaluation Metrics: Support

Conditional probability of a transaction containing itemset Y given that it contains itemset X.

​

​

Rule: {KLYT6} → {IA45Y}

​

⅘ of the transactions that contains KLYT6 (X)

also contains IA45Y (Y)

​

(KLYT6 and IA45Y) / {KLYT6}

c = 0.8

​

​

Rule Evaluation Metrics: Confidence

Proportion of transactions that contains the itemset in Y given that X and Y are independent.

​

​

Rule: {KLYT6} → {IA45Y}

​

⅘ of the transactions that contains IA45Y

​

IA45Y / |T|

​

E[c] = 0.8

​

​

Rule Evaluation Metrics: Expected Confidence

Confidence of the rule divided by the

expected confidence.

​

​

Rule: {KLYT6} → {IA45Y}

​

Lift = 0.8/0.8 = 1

​

​

Lift can be interpreted as a measure of association between the two itemsets. Values greater than 1 indicates positive correlation, values equal to 1 indicates zero correlation, and values less than 1 indicate negative correlation.

​

​

Rule Evaluation Metrics: Lift

Market Basket Analysis

Overview

“Association” analysis typically refers to products that are used one-per-customer – like personal banking products. (I have one checking account and one savings account.)

​

“Market Basket” analysis typically refers to products that are used many-per-customer, like groceries or essential items. (I buy many groceries every week.)

Market Basket Analysis

Source: Introduction to Pattern Discovery & SAS Institute

Barbie Doll ⇒ Candy

• Put them closer together in the store
• Put them far apart in the store
• Package candy bars with the dolls
• Package Barbie + candy + poorly selling item
• Raise the price on one
• Offer Barbie accessories for proofs of purchase
• Do not advertise candy and Barbie together
• Offer candies in the shape of a Barbie doll
• Recommend candy to people who buy Barbie dolls

Introduction to the Pattern Discovery & SAS Institute

Association Recommendation

• Association recommender systems are simple but effective
• Relies only on transactional data
• Likely the most direct method for creating personalized recommendations:
• “If you like X, then you might like Y”
• “These items are often bought together”

​

Interlude

Supervised Rule-based Models

Supervised Rule-based Models

Many interesting options exist for supervised classification with rule-based models, that are often highly interpretable. Popular approaches include:

​

• RuleFit (Friedman & Popescu, 2005)�
• Skope Rules �
• Scalable Bayesian Rule List �(Yang, Rudin, & Seltzer, 2017)

A description of Skope rules.

Scalable Bayesian Rulelist

Source: Scalable Bayesian Rule Lists

Recommendations

Netflix Case

The Netflix Prize

• From 2006 – 2009 Netflix ran a contest asking the public to submit algorithms to predict user ratings for movies

​

• Training data set of ~100,000,000 ratings and test data set of ~3,000,000 ratings were provided

​

• Offered a grand prize of $1,000,000 USD to the team who could beat Netflix’s own algorithm, Cinematch, by more than 10%, measured in RMSE

​

The Analytics Edge, MIT

Predicting the Best User Rating

• Netflix was willing to pay over $1M for the best user rating algorithm, which shows how critical the recommendation system was to their business.

​

• What data could be used to predict user ratings?

​

• Every movie in Netflix’s database has the ranking from all users who have ranked that movie

​

• We also know facts about the movie itself: actors, director, genre classifications, year released, etc.

​

Source: The Analytics Edge, MIT

Using Other User’s Rankings

• Consider suggesting to Carl that he watch “Men in Black”, since Amy rated it highly and Carl and Amy seem to have similar preferences.

​

• This technique is called Collaborative Filtering.

​

Source: The Analytics Edge, MIT

Using Move Information

This technique is called Content Filtering

We saw that Amy liked “Men In Black”

• It was directed by Barry Sonnenfeld

​

• Classified in the genres of action, adventure, sci-fi and comedy

​

• It stars actor Will Smith

​

Consider recommending to Amy:

• Barry Sonnenfeld’s movie “Get Shorty”

​

• “Jurassic Park”, which is in the genres of action, adventure, and sci-fi

​

• Will Smith’s movie “Hitch”

​

Source: The Analytics Edge, MIT

Strengths and Weakness

Collaborative Filtering Systems:�

• Can accurately suggest complex items without understanding the nature of the items.
• Requires a lot of data about the user to make accurate recommendations.
• Millions of items – need lots of computing power.

​

Content Filtering:�

• Requires very little data to get started.
• Can be limited in scope.

Source: The Analytics Edge, MIT

Hybrid Recommendation Systems

• Netflix uses both collaborative and content filtering.

​

• For example, consider a collaborative filtering approach where we determine that Amy and Carl have similar preferences.

​

• We could then do content filtering, where we would find that “Terminator”, which both Amy and Carl liked, is classified in almost the same set of genres as “Starship Troopers.”

​

• Recommend “Starship Troopers” to both Amy and Carl, even though neither of them have seen it before.

​

Source: The Analytics Edge, MIT

Recommendation Method Used

Collaborative Filtering:

​

• zon.com
• Last.fm
• Spotify
• Facebook
• LinkedIn
• Google News
• MySpace
• Netflix

​

​

Content Filtering:

• Pandora
• IMDB
• Rotten Tomatoes
• Jinni
• Rovi Corporation
• See This Next
• MovieLens
• Netflix

Source: The Analytics Edge, MIT

Cornerstone of these Well-known Businesses

Source: The Analytics Edge, MIT

TM

TM

TM

TM

TM

TM

The Edge of Recommendation Systems

• In today’s digital age, businesses often have hundreds of thousands of items to offer their customers.

​

• Excellent recommendation systems can make or break these businesses.

​

• Clustering algorithms, which are tailored to find similar customers or similar items, also form the backbone of many of these recommendation systems.

​

The Analytics Edge, MIT

Reading

• Introduction to Data Mining, Chapter 5
• Sections 5.1 – 5.3, and 5.7

​

• Elements of Statistical Learning
• Section 14.2�
• Introduction to Recommender Systems Handbook