Summary
Summary Analysis of Customer Data
- Course
- Institution
Summary/lecture notes of the course Analysis of Customer Data.
[Show more]
Seller
Follow
sophiedekkers54
Reviews received
Content preview
Summary analysis of customer dataAssociation rule mining tries to find correlations between different items or itemset/sets
of items in a database.
- A rule-based machine learning method for discovering interesting relations between
variables in large databases.
- Initially used for market basket analysis to find how items purchased by customers
are related.
- Assumes all data are categorical. There is no good algorithm for numerical data.
Terminology
Set of items I = {i1, i2 …, im}
Supermarket example: a list of all articles sold in a supermarket.
Transaction t (smaller set of items)
t I, t is a subset of the entire set of items I.
the articles that someone buys in a supermarket.
Transaction database T = {t1, t2, …, tn}
Collection of transactions.
Example transaction database:
Another example: you could analyze a set of documents to see what kind of words, concepts,
or tags co-occur often. At that point, each document could be correlated to a list of
keywords.
- The keywords are items.
- Each document is a transaction.
- All the documents put together make up a transaction dataset.
- All the words that appear in the entire transaction database is I, the set of all possible
items.
Association rules
Association rules are "if-then" statements, that help to show the probability of relationships
between data items, within large data sets in various types of databases.
An association rule is an implication of the form:
- X Y, where X, Y I, and X Y =
A single item is an itemset of size 1.
A k-itemset is an itemset with k items.
, - E.g., {milk, bread, cereal} is a 3-itemset.
How do you determine which patterns are good/interesting or not interesting?
Support measure tells us how often a particular item occurs in our database or
how often a particular association rule holds in our dataset.
Sup = Pr(X Y)
It measures the probability of encountering an association rule or an itemset in
the dataset.
Confidence measure looks at the conditional probability. X implies Y but that
doesn’t mean that Y also implies X. it’s a one-directional association rule.
Conf = Pr(Y | X)
The confidence tells us what proportion of transactions that contain X also
contain Y.
When you’ve computed the support and confidence of a particular association rule, you can
tell how frequently it occurs and you can tell how confident you are in that rule. So, an
association rule tells us that when X occurs, Y occurs with a certain probability.
Support count = number of transactions in T that contain X.
- T = transaction dataset and X = itemset
n = the number of transactions in T.
Support and support count are often used as synonyms.
Absolute support = support count (number of transactions that contain the itemset)
Whole number
Relative support = support (proportion of transactions that contain the itemset)
Real number between 0 and 1
Goal = to find all rules that satisfy the user-specified minimum support (minsup) and
minimum confidence (minconf).
- Confidence measures how strong the rule is, support measures how reliable it is.
Example:
Transaction data:
Minsup = 30%
Minconf = 80%
An example frequent itemset:
- {Chicken, Clothes, Milk} [sup = 3/7]
Association rules form the itemset:
, - {Clothes} {Milk, Chicken} [sup = 3/7, conf = 3/3] confident
- {Milk, Chicken} {Clothes} [sup = 3/7, conf = 3/4] not confident
Mining algorithms
There are many. They all use different strategies and data structures.
- Any algorithm should find the same set of rules although their computational
efficiencies and memory requirements may be different.
We’ll study only one:
The apriori algorithm
Has two steps:
1. Find all item sets that satisfy the minimum support threshold (frequent item sets).
2. Use frequent item sets to generate rules.
Step 1: mining all frequent itemsets
Frequent itemset = itemset whose support minsup.
The apriori property (the key idea of the apriori algorithm): all subsets of a frequent itemset
are also frequent itemsets.
Iterative algo (also called level-wise search):
- Find all 1-item frequent itemsets, then all 2-item itemsets, etc.
- In each iteration k, only consider itemsets that contain some k-1 frequent itemset.
Example:
- Minsup = 0.5
You can see that when looking at the itemsets from a specific length, you only keep the ones
that comply to the minsup value. That is why in the F1 step itemset {4} is dropped.
The items are sorted in lexicographical order.
- Also called dictionary order.
For example, the permutations of {1,2,3} in lexicographic order are 123, 132, 213,
231, 312, and 321.
Apriori candidate generation
, Join step: generate all possible candidate itemsets Ck of length k.
Prune step: remove those candidates in Ck that cannot be frequent.
Simpler explanation:
1. Generate a list of all candidate itemsets of length-1 each item in the dataset is a
candidate itemset.
2. Prune infrequent 1-itemsets any candidate 1-itemset that does not meet the
minsup threshold is discarded.
3. Generate a list of candidate 2-itemsets the algorithm generates itemsets of length-
2 by combining frequent 1-itemsets.
4. Prune infrequent 2-itemsets any candidate 2-itemset that does not meet the
minsup threshold is discarded.
Step 2: generating rules from frequent itemsets
One more step is needed to generate association rules.
The algorithm generates association rules form the frequent itemsets, where each rule
consists of an antecedent (a set of items) and a consequent (a set of items). The confidence
of each rule is calculated as the support of the combined antecedent and consequent divided
by the support of the antecedent alone.
- A B is an association rule if: confidence (A B) > minconf
(support(A B) = support (AB) = support(X),
Confidence(A B) = support (AB) / support(A))
Generating rules example:
Suppose {2, 3, 4} is frequent, with sup=50%
- Proper nonempty subsets: {2,3}, {2,4}, {3,4}, {2}, {3}, {4}, with sup = 50%, 50%, 75%
75%, 75%, 75%, 75% respectively
These generate the following association rules:
The apriori algorithm is a very computational expensive algorithm.
Clearly the space of all association rules is exponential, O(3 m), where m is the number of
items in I. The mining exploits sparseness of data, and high minimum support and high
minimum confidence values. Still, it typically produces a huge number of rules, thousands,
tens of thousands, millions, …
Itemsets are unordered collections of items, events, etc.
Sequential patterns items, elements, events, etc. are ordered.
Transactional database vs. sequential database
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller sophiedekkers54. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $6.75. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52510 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now