Download presentation
Presentation is loading. Please wait.
1
Association Rule 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 Market-Basket transactions Example of Association Rules {Diaper} {Beer}, {Milk, Bread} {Eggs,Coke}, {Beer, Bread} {Milk}, Implication means co-occurrence, not causality!
2
Definition: Frequent Itemset
A collection of one or more items Example: {Milk, Bread, Diaper} k-itemset An itemset that contains k items Support count () Frequency of occurrence of an itemset E.g. ({Milk, Bread,Diaper}) = 2 Support Fraction of transactions that contain an itemset E.g. s({Milk, Bread, Diaper}) = 2/5 Frequent Itemset An itemset whose support is greater than or equal to a minsup threshold
3
Definition: Association Rule
An implication 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 Example:
4
Association Rule Mining Task
Given a set of transactions T, the goal of association rule mining is to find all rules having support ≥ minsup threshold confidence ≥ minconf threshold 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!
5
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 above 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
6
Mining Association Rules
Two-step approach: Frequent Itemset Generation Generate all itemsets whose support minsup 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
7
Frequent Itemset Generation
Given d items, there are 2d possible candidate itemsets
8
Frequent Itemset Generation
Brute-force approach: Each itemset in the lattice is a candidate frequent itemset Count the support of each candidate by scanning the database Match each transaction against every candidate Complexity ~ O(NMw) => Expensive since M = 2d !!!
9
Frequent Itemset Generation Strategies
Reduce the number of candidates (M) Complete search: M=2d Use pruning techniques to reduce M Reduce the number of transactions (N) Reduce size of N as the size of itemset increases Used by DHP and vertical-based mining algorithms Reduce the number of comparisons (NM) Use efficient data structures to store the candidates or transactions No need to match every candidate against every transaction
10
Reducing Number of Candidates
Apriori principle: If an itemset is frequent, then all of its subsets must also be frequent Apriori principle holds due to the following property of the support measure: Support of an itemset never exceeds the support of its subsets This is known as the anti-monotone property of support
11
Illustrating Apriori Principle
Found to be Infrequent Pruned supersets
12
Illustrating Apriori Principle
Items (1-itemsets) Pairs (2-itemsets) (No need to generate candidates involving Coke or Eggs) Minimum Support = 3 Triplets (3-itemsets) If every subset is considered, 6C1 + 6C2 + 6C3 = 41 With support-based pruning, = 13
13
Frequent Itemset Mining
2 strategies: Breadth-first: Apriori Exploit monotonicity to the maximum Depth-first strategy: Eclat Prune the database Do not fully exploit monotonicity
14
Apriori B, C A, C, D A, B, C, D B, D minsup=2 Candidates A B C D {}
15
Apriori A B C D {} minsup=2 Candidates 1 1 B, C A, C, D A, B, C, D
B, D minsup=2 Candidates A B 1 C 1 D {}
16
Apriori A B C D {} minsup=2 Candidates 2 2 B, C A, C, D A, B, C, D
B, D minsup=2 Candidates A B 2 C 2 D {}
17
Apriori A B C D {} minsup=2 Candidates 1 2 3 1 B, C A, C, D A, B, C, D
B, D minsup=2 Candidates A 1 B 2 C 3 D 1 {}
18
Apriori A B C D {} minsup=2 Candidates 2 3 4 2 B, C A, C, D A, B, C, D
B, D minsup=2 Candidates A 2 B 3 C 4 D 2 {}
19
Apriori A B C D {} minsup=2 Candidates 2 4 4 3 B, C A, C, D A, B, C, D
B, D minsup=2 Candidates A 2 B 4 C 4 D 3 {}
20
Apriori AB AC AD BC BD CD A B C D {} minsup=2 Candidates 2 4 4 3 B, C
A, C, D A, B, C, D B, D minsup=2 Candidates AB AC AD BC BD CD A 2 B 4 C 4 D 3 {}
21
Apriori AB AC AD BC BD CD A B C D {} minsup=2 1 2 2 3 2 2 2 4 4 3 B, C
A, C, D A, B, C, D B, D minsup=2 AB 1 AC 2 AD 2 BC 3 BD 2 CD 2 A 2 B 4 C 4 D 3 {}
22
Apriori ACD BCD AB AC AD BC BD CD A B C D {} Candidates minsup=2 1 2 2
3 BD 2 CD 2 A 2 B 4 C 4 D 3 {}
23
Apriori ACD BCD AB AC AD BC BD CD A B C D {} minsup=2 2 1 1 2 2 3 2 2
4 C 4 D 3 {}
24
Apriori Algorithm Method: Let k=1
Generate frequent itemsets of length 1 Repeat until no new frequent itemsets are identified Generate length (k+1) candidate itemsets from length k frequent itemsets Prune candidate itemsets containing subsets of length k that are infrequent Count the support of each candidate by scanning the DB Eliminate candidates that are infrequent, leaving only those that are frequent
25
Frequent Itemset Mining
2 strategies: Breadth-first: Apriori Exploit monotonicity to the maximum Depth-first strategy: Eclat Prune the database Do not fully exploit monotonicity
26
Depth-First Algorithms
Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D minsup=2
27
Depth-First Algorithms
Find all frequent itemsets Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D without D minsup=2 minsup=2 with D Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D minsup=2
28
Depth-First Algorithms
Find all frequent itemsets Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D without D minsup=2 minsup=2 A, B, C, AC, BC with D Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D minsup=2 A, B, C, AC
29
Depth-First Algorithms
Find all frequent itemsets Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D without D minsup=2 minsup=2 A, B, C, AC, BC with D Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D add D again minsup=2 AD, BD, CD, ACD A, B, C, AC, BC A, B, C, AC
30
Depth-First Algorithms
Find all frequent itemsets Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D without D minsup=2 minsup=2 A, B, C, AC, BC A, B, C, AC, BC, AD, BD, CD, ACD with D Find all frequent itemsets 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D minsup=2 AD, BD, CD, ACD + A, B, C, AC, BC A, B, C, AC
31
Depth-First Algorithm
DB 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D A: 2 B: 4 C: 4 D: 3
32
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 3 A, C 4 A, B, C 5 B, A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2
33
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D DB[CD] 3 A, C 4 A, B, C 5 B, A, A, B A: 2 A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3
34
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D DB[CD] 3 A, C 4 A, B, C 5 B, A, A, B A: 2 A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2
35
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 3 A, C 4 A, B, C 5 B, A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2
36
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 3 A, C 4 A, B, C 5 B, DB[BD] 4 A A:1 A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2
37
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 3 A, C 4 A, B, C 5 B, A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2
38
Depth-First Algorithm
DB DB[D] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 3 A, C 4 A, B, C 5 B, A: 2 B: 4 C: 2 A: 2 B: 4 C: 4 D: 3 AC: 2 AD: 2 BD: 4 CD: 2 ACD: 2
39
Depth-First Algorithm
DB 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2
40
Depth-First Algorithm
DB DB[C] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D B 2 B 3 A 4 A, B A: 2 B: 3 A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2
41
Depth-First Algorithm
DB DB[C] DB[BC] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D B 2 B 3 A 4 A, B 2 4 A A: 1 A: 2 B: 3 A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2
42
Depth-First Algorithm
DB DB[C] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D B 2 B 3 A 4 A, B A: 2 B: 3 A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2
43
Depth-First Algorithm
DB DB[C] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D B 2 B 3 A 4 A, B A: 2 B: 3 A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2 AC: 2 BC: 3
44
Depth-First Algorithm
DB 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2 AC: 2 BC: 3
45
Depth-First Algorithm
DB DB[B] 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D 1 2 4 A 5 A:1 A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2 AC: 2 BC: 3
46
Depth-First Algorithm
DB 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 ACD: 2 AC: 2 BC: 3
47
Depth-First Algorithm
DB 1 B, C 2 B, C 3 A, C, D 4 A, B, C, D 5 B, D A: 2 B: 4 C: 4 D: 3 AD: 2 BD: 4 CD: 2 Final set of frequent itemsets ACD: 2 AC: 2 BC: 3
48
ECLAT For each item, store a list of transaction ids (tids) TID-list
+TID-list.jpg "ECLAT For each item, store a list of transaction ids (tids) TID-list")
49
ECLAT Determine support of any k-itemset by intersecting tid-lists of two of its (k-1) subsets. Depth-first traversal of the search lattice Advantage: very fast support counting Disadvantage: intermediate tid-lists may become too large for memory
+subsets.+Depth-first+traversal+of+the+search+lattice..jpg "Advantage: very fast support counting. Disadvantage: intermediate tid-lists may become too large for memory. ")
50
Rule Generation Given a frequent itemset L, find all non-empty subsets f L such that f L – f satisfies the minimum confidence requirement If {A,B,C,D} is a frequent itemset, candidate rules: ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC BD, AD BC, BC AD, BD AC, CD AB, If |L| = k, then there are 2k – 2 candidate association rules (ignoring L and L)
51
Rule Generation How to efficiently generate rules from frequent itemsets? In general, confidence does not have an anti- monotone property c(ABC D) can be larger or smaller than c(AB D) But confidence of rules generated from the same itemset has an anti-monotone property e.g., L = {A,B,C,D}: c(ABC D) c(AB CD) c(A BCD) Confidence is anti-monotone w.r.t. number of items on the RHS of the rule
52
Rule Generation for Apriori Algorithm
Lattice of rules Pruned Rules Low Confidence Rule
Similar presentations
