Average number of frequent (closed) patterns in Bernoulli and Markovian databases

In data mining, enumerate the frequent or the closed patterns is often the first difficult task leading to the association rules discovery. The number of these patterns represents a great interest. The lower bound is known to be constant whereas the upper bound is exponential, but both situations correspond to pathological cases. For the first time, we give an average analysis of the number of frequent or closed patterns. Average analysis is often closer to real situations and gives more information about the role of the parameters. In this paper, two probabilistic models are studied: a Bernoulli and a Markovian. In both models and for large databases, we prove that the number of frequent patterns, for a fixed frequency threshold, is exponential in the number of items and polynomial in the number of transactions. On the other hand, for a proportional frequency threshold, the number of frequent patterns is polynomial in the number of items and does not involve the number of transactions. Finally, we prove in the Bernoulli model that the number of closed patterns, for a proportional frequency threshold, is polynomial in the number of items.