Frequent Pattern Analysis

2013. 2. 6. 15:34

Frequent pattern is a pattern that occurs frequently in a data set.

(absolute) support, or, support count: frequency of an itemset
(relative) support: fraction of transactions that contains an itemset (i.e., the probability that a transaction contains an itenset
An itemset X is frequent if X's support is no less than a Minsup threshold.

Find all the rules X → Y with minimum support and confidence

support(s): probability that a transaction contains both (or more) of two itemsets (X ∪ Y)
confidence(c): conditional probability that a transaction having an itemset X also contains another itemset Y

A long pattern contains a combinatorial number of sub-patterns, e.g., {a₁, a₂, …, a₁₀₀} contains 2¹⁰⁰ - 1 sub-patterns!

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.
Example:
　- DB = {<a₁, a₂, …, a₁₀₀>, <a₁, a₂, …, a₅₀>}, Minsup = 1
　- set of closed itemset: <a₁, a₂, …, a₁₀₀> = 1, <a₁, a₂, …, a₅₀> = 2
　- set of max-pattern: <a₁, a₂, …, a₁₀₀> = 1

The worst case complexity vs. the expected probability

For example, suppose Walmart store has 10⁴ kinds of products.

The chance to pick up one product: 10^-4
The chance to pick up a particular set of 10 products: about (10^-4)¹⁰ = 10^-40
What is the chance this particular set of 10 products to be frequent 10³ times in 10⁹ transactions?
Solution:

Any subset of a frequent itemset must be frequent.

If {beer, diaper, nuts} is frequent, so is {beer, diaper}.

Scalable mining methods: Three major approaches

SENS