What is Frequent Pattern Mining?
Tasks: Frequent itemset mining, Association Rule Mining, Sequential Pattern Mining
Task 1: Frequent Itemset Mining
Find all subsets of items that occur together in many transactions.
Task 2: Association Rule Mining
Find all rules that correlate the presence of one set of items with that of another set of items in the transaction database.
example: 98% of people buying tires and auto accessories also get automotive service done
Mining Frequent Itemsets: Basic Notions
support = number of occurences/number of transactions
Mining Frequent Patterns: Apriori Principle
Apriori Algorithm
FP tree Construction
Without Candidate Generation
Mining Frequent Patterns Using FP-Tree
conditional fp tree
Simple Association Rules: Basic Notions
Association Rules - Support
Association Rules - Confidence
Association Rules - Rule form
Association Rules - Generating Rules from Frequent Itemsets
Association Rules - Measurements
Objective measures
support
confidence
Subjective measures
- A rule (pattern) is interesting if it is
unexpected (surprising to the user) and/or
actionable (the user can do something with it)
Interestingness Measures: Correlation
Hierarchical Association Rules
Exploit item taxonomies (generalizations, is-a hierarchies) which exist in many applications
Mining: Top-Down Progressive Deepening
Multilevel support thresholds, redundancy, R-interestingness
R -Interestingness
Sequential Pattern Mining
the order of the items is the crucial information.
In an ordered sequence, items are allowed to occur more than one time.
Sequential Pattern Mining: Basic Notions
Sequential Pattern Mining Algorithms
Breadth-first search: Generate frequent sequences ascending by length
Projection-Based Sequence Mining: PrefixSpan: Representation
Allen’s Relationships of Intervals
Interval Patterns Mining: Discussion
Last changeda year ago
