Module 4:Frequent Pattern Analysis

• Frequent pattern analysis involves discovering patterns that occur frequently in a dataset, covering sets of items, subsequences, or substructures.
• Agrawal, Imielinski, and Swami first introduced frequent pattern analysis
• The motivation is to find inherent regularities in data, like co-occurring products, purchase sequences, sensitive DNA, and web document classification
• Frequent pattern analysis is applicable in basket data analysis, cross-marketing, catalog design, sale campaign analysis, weblog analysis, and DNA sequence analysis
• Frequent patterns are intrinsic properties of datasets that serve as the foundation for data mining tasks.
• Data mining tasks include association, correlation, causality analysis, sequential and structural pattern mining, spatiotemporal/multimedia/time-series/stream data analysis, classification, clustering, data warehousing as well as semantic data compression
• Association rule mining aims to find rules X → Y with minimum support and confidence.
• Support is the probability of a transaction containing both X and Y.
• Confidence is the conditional probability of a transaction containing Y, given it contains X.
• Closed patterns and max-patterns are mined instead of long patterns
• An itemset X is closed if it is frequent and has no super-pattern Y containing X with the same support.
• An itemset X is a max-pattern if frequent and no frequent super-pattern Y exists that contains X
• Closed patterns offer lossless compression of frequent patterns, effectively reducing the number of patterns and rules.
• Mining frequent itemsets in the worst case involves potentially generating many itemsets which are sensitive to the minimum support threshold
• The worst-case complexity is M^N, where M is the number of distinct items and N is the maximum transaction length.

Scalable Frequent Itemset Mining Methods

• Apriori utilizes a candidate generation-and-test approach.
• FPGrowth employs a frequent pattern growth approach
• ECLAT uses a vertical data format for frequent pattern mining.
• The downward closure property states that any subset of a frequent itemset must be frequent
• Scalable mining methods include Apriori, frequent pattern growth (FPgrowth), and the vertical data format approach.

Apriori Algorithm

• Apriori pruning principle states that if any itemset is infrequent, its superset should not be generated or tested.
• The Apriori algorithm initially scans the database to find frequent 1-itemsets
• It generates length (k+1) candidate itemsets from length k frequent itemsets, tests candidates against the DB, and terminates when no frequent or candidate set can be generated.
• Candidate itemsets can be stored in a hash-tree to obtain support
• A hash-tree's leaf nodes contain lists of itemsets and counts
• Interior nodes containing a hash table
• A frequent pattern, FPGrowth, recursively grows patterns by partitioning the database and only looking at frequent patterns
• It constructs conditional pattern-bases and FP-trees for each frequent item
• The process repeats on each newly created conditional FP-tree until the FP-tree is empty or contains a single path
• A single path generates the combination of sub-paths, each of which is a frequent pattern

Scaling FP-growth

• DB projection occurs if the FP-tree cannot fit in memory by partitioning into a set of projected DB’s
• Then construct and mine an FP-tree for each projected DB
• Partition projection occurs when the DB is partitioned based on the ordered frequent items and passes the unprocessed parts to the subsequent partitions
• The frequent pattern approach is divide-and-conquer.
• The frequent pattern mining task and DB are decomposed according to the frequent patterns obtained.
• This approach has no candidate generation or tests
• This approach uses a compressed FP-tree allowing for no repeated scans and employs basic operations such as counting local frequent items.
• ECLAT mines vertical data formats
• This approach uses a tid-list, which is a list of trans.-ids containing an itemset
• Deriving frequent patters based on vertical intersections
• This approach accelerates mining by only keeping track of differences of tids

Mining Frequent Closed Patterns: CLOSET

• In CLOSET a Flist is a list of all frequent items in support ascending order
• The CLOSET method divides search spaced into patterns that have d or do not have a
• This searches to find frequent closed patterns recursively

MaxMiner: Mining Max-Patterns

• 1st scan: find frequent items
• 2nd scan: find support for
• A, B, C, D, E are potential max-patterns
• BCDE is a max-pattern, so there's no need to check BCD, BDE, or CDE in a later scan

Pattern Evaluation

• Strong association rules can be uninteresting or misleading
• Support-confidence framework is not always enough
• Other correlation analysis metrics exist, such as lift and the X^2 measures, often disclosing more intrinsic pattern relationships
• Lift measures dependent/correlated events
• The use of only support and confidence measures can generate a large number of rules, many of which can be uninteresting.
• Augmenting with an interestingness measure, which focuses the mining toward rules, can improve strong patterned relationships and focus rules of high importance