Size of random Galois lattices and number of closed frequent itemsets Original Research Article

Given a sample of binary random vectors with i.i.d. Bernoulli(image) components, that is equal to 1 (resp. 0) with probability image (resp. image), we first establish a formula for the mean of the size of the random Galois lattice built from this sample, and a more complex one for its variance. Then, noticing that closed image-frequent itemsets are in bijection with closed image-winning coalitions, we establish similar formulas for the mean and the variance of the number of closed image-frequent itemsets. This can be interesting for the study of the complexity of some data mining problems such as association rule mining, sequential pattern mining and classification.