Data Mining Association Analysis: Basic Concepts and Algorithms

Presentation on theme: "Data Mining Association Analysis: Basic Concepts and Algorithms"— Presentation transcript:

1 Data Mining Association Analysis: Basic Concepts and Algorithms
From Introduction to Data Mining By Tan, Steinbach, Kumar

2 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!

3 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

4 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:

5 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!

6 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

7 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

8 Frequent Itemset Generation
Given d items, there are 2d possible candidate itemsets

9 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 !!!

10 Computational Complexity
Given d unique items: Total number of itemsets = 2d Total number of possible association rules: If d=6, R = 602 rules

11 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

12 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

13 Apriori Principle If an itemset is frequent, then all of its subsets must also be frequent If an itemset is infrequent, then all of its supersets must be infrequent too (X  Y) (¬Y  ¬X) frequent frequent infrequent infrequent

14 Illustrating Apriori Principle
Found to be Infrequent Pruned supersets

15 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

16 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

17 {A} {B} {C} {E} {A C} {B C} {B E} {C E} {B C E}
Example  A database has five transactions. Let the min sup = 50% and min con f = 80%. Solution  Step 1: Find all Frequent Itemsets Frequent Itemset: {A} {B} {C} {E} {A C} {B C} {B E} {C E} {B C E}

18 Step 2: Generate strong association rules from the frequent itemsets
Example  A database has five transactions. Let the min sup = 50% and min con f = 80%.

19 Closed Itemset: support of all parents are not equal to the support of the itemset. Maximal Itemset: all parents of that itemset must be infrequent.

20 Itemset {c} is closed as support of parents (supersets) {A C}:2, {B C}:2, {C D}:1, {C E}:2 not equal support of {c}:3. And the same for {A C}, {B E} & {B C E}. Itemset {A C} is maximal as all parents (supersets) {A B C}, {A C D}, {A C E} are infrequent. And the same for {B C E}.

21 Algorithms to find frequent pattern
Apriori: uses a generate-and-test approach – generates candidate itemsets and tests if they are frequent Generation of candidate itemsets is expensive (in both space and time) Support counting is expensive Subset checking (computationally expensive) Multiple Database scans (I/O) FP-Growth: allows frequent itemset discovery without candidate generation. Two step: 1.Build a compact data structure called the FP-tree 2 passes over the database 2.extracts frequent itemsets directly from the FP-tree Traverse through FP-tree

22 Core Data Structure: FP-Tree
Nodes correspond to items and have a counter FP-Growth reads 1 transaction at a time and maps it to a path Fixed order is used, so paths can overlap when transactions share items (when they have the same prex ). In this case, counters are incremented Pointers are maintained between nodes containing the same item, creating singly linked lists (dotted lines) The more paths that overlap, the higher the compression. FP-tree may t in memory. Frequent itemsets extracted from the FP-Tree.

23 Step 1: FP-Tree Construction (Example)
FP-Tree is constructed using 2 passes over the data-set: Pass 1: Scan data and nd support for each item. Discard infrequent items. Sort frequent items in decreasing order based on their support. For our example: a; b; c; d; e Use this order when building the FP-Tree, so common prexes can be shared.

24 Step 1: FP-Tree Construction (Example)
Pass 2: construct the FP-Tree (see diagram on next slide) Read transaction 1: {a, b} Create 2 nodes a and b and the path null a b. Set counts of a and b to 1. Read transaction 2: {b, c, d} Create 3 nodes for b, c and d and the path null b  c  d. Set counts to 1. Note that although transaction 1 and 2 share b, the paths are disjoint as they don't share a common prex. Add the link between the b's. Read transaction 3: {a, c, d, e} It shares common prex item a with transaction 1 so the path for transaction 1 and 3 will overlap and the frequency count for node a will be incremented by 1. Add links between the c's and d's. Continue until all transactions are mapped to a path in the FP-tree.

25 FP-tree construction null After reading TID=1: a:1 b:1
Step 1: FP-Tree Construction (Example) null After reading TID=1: a:1 b:1 After reading TID=2: null b:1 a:1 b:1 c:1 d:1

26 FP-Tree Construction null b:2 a:8 b:5 c:2 c:1 d:1 d:1 c:3 e:1 d:1 e:1
Transaction Database null b:2 a:8 b:5 c:2 c:1 d:1 Header table d:1 c:3 e:1 d:1 e:1 d:1 e:1 d:1 Pointers are used to assist frequent itemset generation

27 FP-tree Size The size of an FP­tree is typically smaller than the size of the uncompressed data because many transactions often share a few items in common Best­case scenario: All transactions have the same set of items, and the FP­tree contains only a single branch of nodes. Worst­case scenario: Every transaction has a unique set of items. As none of the transactions have any items in common, the size of the FP­tree is effectively the same as the size of the original data. The size of an FP­tree also depends on how the items are ordered

28 Step 2: Frequent Itemset Generation
FP-Growth extracts frequent itemsets from the FP-tree. Bottom-up algorithm from the leaves towards the root Divide and conquer: rst look for frequent itemsets ending in e, then de, etc. . . then d, then cd, etc. . . First, extract prex path sub-trees ending in an item(set). Complete FP-tree prex path sub-trees

29 Step 2: Frequent Itemset Generation
Each prex path sub-tree is processed recursively to extract the frequent itemsets. Solutions are then merged. E.g. the prex path sub-tree for e will be used to extract frequent itemsets ending in e, then in de, ce, be and ae, then in cde, bde, cde, etc. Divide and conquer approach Prex path sub-tree ending in e.

30 Example Let minSup = 2 and extract all frequent itemsets containing e.
1. Obtain the prex path sub-tree for e: 2. Check if e is a frequent item by adding the counts along the linked list (dotted line). If so, extract it. Yes, count =3 so {e} is extracted as a frequent itemset. 3. As e is frequent, nd frequent itemsets ending in e. i.e. de, ce, be and ae. i.e. decompose the problem recursively. To do this, we must rst to obtain the conditional FP-tree for e.

31 Conditional FP-Tree The FP-Tree that would be built if we only consider transactions containing a particular itemset (and then removing that itemset from all transactions). Example: FP-Tree conditional on e.

32 Conditional FP-Tree To obtain the conditional FP-tree for e from the prex sub-tree ending in e: Update the support counts along the prex paths (from e) to reflect the number of transactions containing e. b and c should be set to 1 and a to 2.

33 Conditional FP-Tree To obtain the conditional FP-tree for e from the prex sub-tree ending in e: Remove the nodes containing e information about node e is no longer needed because of the previous step

34 Conditional FP-Tree To obtain the conditional FP-tree for e from the prex sub-tree ending in e: Remove infrequent items (nodes) from the prex paths E.g. b has a support of 1 (note this really means be has a support of 1). i.e. there is only 1 transaction containing b and e so be is infrequent can remove b.

35 Example (continued) 4. Use the the conditional FP-tree for e to nd frequent itemsets ending in de, ce and ae Note that be is not considered as b is not in the conditional FP-tree for e. For each of them (e.g. de), find the prex paths from the conditional tree for e, extract frequent itemsets, generate conditional FP-tree, etc... (recursive) Example: e de  ade ({d, e},{a, d, e}) are found to be frequent)

36 Example (continued) 4. Use the the conditional FP-tree for e to nd frequent itemsets ending in de, ce and ae Example: e ce ({c,e} is found to be frequent) etc... (ae, then do the whole thing for b,... etc)

37 Result Frequent itemsets found (ordered by sux and order in which they are found):