Scribd Logo
Upload

Welcome to Scribd!

  • 42 views

    What Is Frequent Pattern Analysis?

    Uploaded by

    Âįmân Śhêikh
    Frequent pattern mining analyzes data to find patterns that frequently occur together. It has many applications like market basket analysis. There are two main approaches: Apriori, which generates candidate patterns and tests them against the data; and FP-growth, which compresses the database into a tree structure and mines patterns from this without candidate generation. FP-growth scales better to large datasets as it avoids multiple database scans and generating a huge number of candidate patterns.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    What Is Frequent Pattern Analysis?

    Uploaded by

    Âįmân Śhêikh
    42 views5 pages
    Frequent pattern mining analyzes data to find patterns that frequently occur together. It has many applications like market basket analysis. There are two main approaches: Apriori, which generates candidate patterns and tests them against the data; and FP-growth, which compresses the database into a tree structure and mines patterns from this without candidate generation. FP-growth scales better to large datasets as it avoids multiple database scans and generating a huge number of candidate patterns.

    Original Description:

    SIA

    Original Title

    week3& 4

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Frequent pattern mining analyzes data to find patterns that frequently occur together. It has many applications like market basket analysis. There are two main approaches: Apriori, which generates candidate patterns and tests them against the data; and FP-growth, which compresses the database into a tree structure and mines patterns from this without candidate generation. FP-growth scales better to large datasets as it avoids multiple database scans and generating a huge number of candidate patterns.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    42 views5 pages

    What Is Frequent Pattern Analysis?

    Uploaded by

    Âįmân Śhêikh
    Frequent pattern mining analyzes data to find patterns that frequently occur together. It has many applications like market basket analysis. There are two main approaches: Apriori, which generates candidate patterns and tests them against the data; and FP-growth, which compresses the database into a tree structure and mines patterns from this without candidate generation. FP-growth scales better to large datasets as it avoids multiple database scans and generating a huge number of candidate patterns.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    What Is Frequent Pattern Analysis?

    •Frequent pattern: a pattern (a set of items, subsequences, substructures, etc.) that occurs frequently in a data set
    •Motivation: Finding inherent regularities in data
    •What products were often purchased together?— Powder and diapers?!
    •What are the subsequent purchases after buying a PC?
    •What kinds of DNA are sensitive to this new drug?
    •Can we automatically classify web documents?
    •Applications
    •Basket data analysis, cross-marketing, catalog design, sale campaign analysis, Web log (click stream) analysis,
    and DNA sequence analysis.

    Why Is Freq. Pattern Mining Important?


    •Discloses an intrinsic and important property of data sets
    •Forms the foundation for many essential data mining tasks
    •Association, correlation, and causality analysis
    •Sequential, structural (e.g., sub-graph) patterns
    •Pattern analysis in spatiotemporal, multimedia, time-series, and stream data
    •Classification: associative classification
    •Cluster analysis: frequent pattern-based clustering
    •Broad applications

    Basic Concepts: Frequent Patterns and Association Rules


    Itemset X = {x1, …, xk}
    Find all the rules X  Y with minimum support and confidence
    support, s, probability that a transaction contains X  Y
    confidence, c, conditional probability that a transaction having X also contains Y

    Mining Association Rules


    •Mining association rules can be reduced to mining frequent items
    •Association rule mining is a two-step process:
    •Find all frequent items as determined by minimum support
    •Generate strong association rules that satisfy minimum support and minimum confidence
    •If minimum support is low a large number of item-sets will be found

    Closed Patterns and Max-Patterns


    •A frequently occurring long pattern contains a combinatorial number of sub-patterns, e.g., {a1, …, a100}
    contains
    •Solution: Mine closed patterns and max-patterns instead
    •An itemset X is closed if X is frequent and there exists no super-pattern Y ‫ כ‬X, with the same support as X
    •An itemset X is a max-pattern if X is frequent and there exists no frequent super-pattern Y ‫ כ‬X
    •Closed pattern is a lossless compression of freq. patterns
    •Reducing the # of patterns and rules

    Closed Patterns and Max-Patterns


    Exercise.  DB = {<a1, …, a100>, < a1, …, a50>}
    Min_sup = 1.
    What is the set of closed itemset?
    <a1, …, a100>: 1
    < a1, …, a50>: 2
    What is the set of max-pattern?
    <a1, …, a100>: 1
    Scalable Methods for Mining Frequent Patterns
    •The downward closure property of frequent patterns
    •Any subset of a frequent itemset must be frequent
    •If {powder, diaper, nuts} is frequent, so is {powder, diaper}
    •i.e., every transaction having {powder, diaper, nuts} also contains {powder, diaper}
    •Scalable mining methods: Three major approaches
    •Apriori
    •Freq. pattern growth
    •Vertical data format approach

    Apriori: A Candidate Generation-and-Test Approach


    •Apriori pruning principle: If there is any itemset which is infrequent, its superset should not be
    generated/tested!
    •Method:
    •Initially, scan DB once to get frequent 1-itemset
    •Generate length (k+1) candidate itemsets from length k frequent itemsets
    •Test the candidates against DB
    •Terminate when no frequent or candidate set can be generated

    Important Details of Apriori


    How to generate candidates?
    Step 1: self-joining Lk
    Step 2: pruning
    How to count supports of candidates?
    Example of Candidate-generation
    L3={abc, abd, acd, ace, bcd}
    Self-joining: L3*L3
    abcd from abc and abd
    acde from acd and ace
    Pruning:
    acde is removed because ade is not in L3
    C4={abcd}

    Frequent Item Sets to Association Rules


    •Strong association rules are the ones that satisfy minimum support and minimum confidence
    •Find the combination that satisfy minimum confidence
    •They will form the association rules

    How to Count Supports of Candidates?


    •Why counting supports of candidates a problem?
    •The total number of candidates can be very huge
    • One transaction may contain many candidates
    •Method:
    •Candidate itemsets are stored in a hash-tree
    •Leaf node of hash-tree contains a list of itemsets and counts
    •Interior node contains a hash table
    •Subset function: finds all the candidates contained in a transaction

    Improving Efficiency of Apriori


    Challenges of Frequent Pattern Mining
    •Challenges
    •Multiple scans of transaction database
    •Huge number of candidates
    •Tedious workload of support counting for candidates
    •Improving Apriori: general ideas
    •Reduce passes of transaction database scans
    •Shrink number of candidates
    •Facilitate support counting of candidates

    Partition: Scan Database Only Twice


    •Any itemset that is potentially frequent in DB must be frequent in at least one of the partitions of DB
    •Scan 1: partition database and find local frequent patterns
    •Scan 2: consolidate global frequent patterns
    •An efficient algorithm for mining association in large databases.

    Reduce the Number of Candidates


    •A k-itemset whose corresponding hashing bucket count is below the threshold cannot be frequent
    •Candidates: a, b, c, d, e
    •Hash entries: {ab, ad, ae} {bd, be, de} …
    •Frequent 1-itemset: a, b, d, e
    •ab is not a candidate 2-itemset if the sum of count of {ab, ad, ae} is below support threshold
    •An effective hash-based algorithm for mining association rules.

    Sampling for Frequent Patterns


    •Select a sample of original database, mine frequent patterns within sample using Apriori
    •Scan database once to verify frequent itemsets found in sample, only borders of closure of frequent patterns are
    checked
    •Example: check abcd instead of ab, ac, …, etc.
    •Scan database again to find missed frequent patterns
    •Sampling large databases for association rules.

    Reduce Number of Scans


    Once both A and D are determined frequent, the counting of AD begins
    Once all length-2 subsets of BCD are determined frequent, the counting of BCD begins
    temset lattice

    Bottleneck of Frequent-pattern Mining


    •Multiple database scans are costly
    •Mining long patterns needs many passes of scanning and generates lots of candidates
    •To find frequent itemset i1i2…i100
    •# of scans: 100
    •# of Candidates: (1001) + (1002) + … + (110000) = 2100-1 = 1.27*1030 !
    •Bottleneck: candidate-generation-and-test
    •Can we avoid candidate generation?

    Mining Frequent Patterns Without Candidate Generation


    •Grow long patterns from short ones using local frequent items
    •“abc” is a frequent pattern
    •Get all transactions having “abc”: DB|abc
    •“d” is a local frequent item in DB|abc  abcd is a frequent pattern

    Frequent-Pattern Growth or FP-growth


    •Divide and conquer strategy
    •Compresses the database into a frequent-pattern tree or FP-tree
    •Compressed database is then divided into a set of conditional databases

    Construct FP-tree from a Transaction Database


    min_support = 3
    TID        Items bought      (ordered) frequent items
    100        {f, a, c, d, g, i, m, p}    {f, c, a, m, p}
    200        {a, b, c, f, l, m, o}        {f, c, a, b, m}
    300        {b, f, h, j, o, w}        {f, b}
    400        {b, c, k, s, p}        {c, b, p}
    500        {a, f, c, e, l, p, m, n}    {f, c, a, m, p}
    1.Scan DB once, find frequent 1-itemset (single item pattern)
    2.Sort frequent items in frequency descending order, f-list
    3.Scan DB again, construct FP-tree
    F-list=f-c-a-b-m-p
    Header Table

    Item  frequency  head


    f    4
    c    4
    a    3
    b    3
    m    3
    p    3

    Benefits of the FP-tree Structure


    •Completeness
    •Preserve complete information for frequent pattern mining
    •Never break a long pattern of any transaction
    •Compactness
    •Reduce irrelevant info—infrequent items are gone
    •Items in frequency descending order: the more frequently occurring, the more likely to be shared
    •Never be larger than the original database (not count node-links and the count field)

    FP-Growth Tree Construction Process


    •First create the root tree labeled with “null” after first scan
    •Scan the database next with each transaction processed in order of its support count

    FP Tree Construction
    •Start from length-1 pattern to construct the conditional pattern base
    •Construct the conditional FP-tree for the pattern base
    •Pattern growth is achieved by concatenating the suffix pattern with the frequent pattern

    Mining Frequent Patterns With FP-trees


    •Idea: Frequent pattern growth
    •Recursively grow frequent patterns by pattern and database partition
    •Method
    •For each frequent item, construct its conditional pattern-base, and then its conditional FP-tree
    •Repeat the process on each newly created conditional FP-tree
    •Until the resulting FP-tree is empty, or it contains only one path—single path will generate all the
    combinations of its sub-paths, each of which is a frequent patter
    Scaling FP-growth by DB Projection
    •FP-tree cannot fit in memory?—DB projection
    •First partition a database into a set of projected DBs
    •Then construct and mine FP-tree for each projected DB
    FP-Growth vs. Apriori: Scalability With the Support Threshold

    Why Is FP-Growth the Winner?


    •Divide-and-conquer:
    •decompose both the mining task and DB according to the frequent patterns obtained so far
    •leads to focused search of smaller databases
    •Other factors
    •no candidate generation, no candidate test
    •compressed database: FP-tree structure
    •no repeated scan of entire database
    •basic ops—counting local freq items and building sub FP-tree, no pattern search and matching

    You might also like