Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Pattern-Growth Approach: Mining Frequent Patterns Without Candidate Generation

  • Bottlenecks of the Apriori approach
    • Breadth-first (i.e., level-wise) search
    • Candidate generation and test
      • Often generates a huge number of candidates
  • The FPGrowth Approach (J. Han, J. Pei, and Y. Yin, SIGMOD’ 00)
    • Depth-first search
    • Avoid explicit candidate generation
  • Major philosophy: Grow long patterns from short ones using local frequent items only
    • “abc” is a frequent pattern
    • Get all transactions having “abc”, i.e., project DB on abc: DB|abc
    • “d” is a local frequent item in DB|abc  abcd is a frequent pattern

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.