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.

Computational Complexity of Frequent Itemset Mining

  • How many itemsets are potentially to be generated in the worst case?
    • The number of frequent itemsets to be generated is senstive to the minsup threshold
    • When minsup is low, there exist potentially an exponential number of frequent itemsets
    • The worst case: MN where M: # distinct items, and N: max length of transactions
  • The worst case complexty vs. the expected probability
    • Ex. Suppose Walmart has 10^4 kinds of products
      • The chance to pick up one product 10^(-4)
      • The chance to pick up a particular set of 10 products: ~10^(-40)
      • What is the chance this particular set of 10 products to be frequent 10^3 times in 10^9 transactions?

Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.