Data Warehousing and Data Mining · Unit 5 · 6 hrs
Mining Frequent Patterns
Exam-focused notes for Mining Frequent Patterns (Data Warehousing and Data Mining, CSC420): what the TU syllabus asks and how it has actually been tested, with 6 solved past questions from this unit.
What this unit covers
- Frequent patterns
- Market basket analysis
- Frequent itemsets, closed itemsets, association rules
- Types of association rule (Single dimensional, multidimensional, multilevel, quantitative)
- Finding frequent itemset (Apriori algorithm, FP growth)
- Generating association rules from frequent itemset
- Limitation and improving Apriori
- From Association Mining to Correlation Analysis
- Lift
Finding frequent itemset
How do you generate strong association rules? From the following dataset find the frequent item set using FP growth algorithm using 3 as minimum support.
| Transaction ID | Items |
|---|---|
| T1 | {K, E, M, O, Y} |
| T2 | {K, E, O, Y} |
| T3 | {K, E, M} |
| T4 | {K, M, Y} |
| T5 | {K, E, O} |
[10]
Transactions: - T1: {K, E, M, O, Y} - T2: {K, E, O, Y} - T3: {K, E, M} - T4: {K, M, Y} - T5: {K, E, O} Minimum support = 3 A strong association rule $X \Rightarrow Y$ satisfies both thresholds: - $\text{support}(X \cup Y) \geq \text{min\support}$ - $\text{c...
Full solved answer →Apriori Algorithm - Frequent Itemsets and Association Rules
TID Items ------ 1 Bread, Cheese, Egg, Juice 2 Bread, Cheese, Juice 3 Bread, Milk, Yogurt 4 Bread, Juice, Milk 5 Cheese, Juice, Milk - Total transactions $N = 5$ - Minimum support $= 50\%$ - Minimum confidence $= 75\%$ Minimum support count $= 0.50 \times 5...
Full solved answer →Drawbacks of Apriori Algorithm and FP-Growth Analysis
Drawback 1: Generation of a huge number of candidate itemsets. Apriori generates a large number of candidate itemsets at every level. If there are $10^4$ frequent 1-itemsets, it must generate more than $10^7$ candidate 2-itemsets. To discover a long frequen...
Full solved answer →How Concept Hierarchy is Used in Extracting Information
Concept hierarchy is used in extracting information by:
- Organizing data at different levels of abstraction
- Enabling generalization and specialization of patterns
- Allowing drill-down and roll-up operations for multi-level analysis
- Facilitating hierarchical association rule mining
- Supporting semantic understanding of discovered patterns
--- A concept hierarchy is a sequence of mappings from low-level (specific) concepts to higher-level (general) concepts. It organizes data values into levels of abstraction. How it is used in extracting information: 1. Multilevel mining: Patterns/rules can ...
Full solved answer →Association Rules and Apriori Algorithm Analysis
- Support threshold (min support count) = 2 - Confidence threshold = 60% - Total transactions = 6 TID Items ------------ T1 HotDogs, Buns, Ketchup T2 HotDogs, Buns T3 HotDogs, Coke, Chips T4 Chips, Coke T5 Chips, Ketchup T6 HotDogs, Coke, Chips --- 1. Singl...
Full solved answer →Limitation and improving Apriori
List the problems of Apriori algorithm with its possible solutions. Consider the following transaction dataset. What association rules can be found in this set, if the minimum support is 3 and the minimum confidence is 80%?
| Transaction_ID | Item_List |
|---|---|
| T1 | {K, A, D, B} |
| T2 | {D, A, C, E, B} |
| T3 | {C, A, B, E} |
| T4 | {B, A, D} |
[10]
1. Huge number of candidate itemsets. At each level Apriori generates many candidates. For example, $10^4$ frequent 1-itemsets produce roughly $\binom{10^4}{2}\approx 5\times10^7$ candidate 2-itemsets. 2. Multiple database scans. The full database must be s...
Full solved answer →Make Unit 5 stick
Practice CSC420 with flashcards & quizzes