Size of random Galois lattices and number of closed frequent itemsets |
| |
Authors: | Richard Emilion,Gé rard Lé vy |
| |
Affiliation: | a MAPMO, Université d’Orléans, 45100 Orléans, France b Université Paris Dauphine, 75016 Paris, France |
| |
Abstract: | Given a sample of binary random vectors with i.i.d. Bernoulli(p) components, that is equal to 1 (resp. 0) with probability p (resp. 1−p), 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 α-frequent itemsets are in bijection with closed α-winning coalitions, we establish similar formulas for the mean and the variance of the number of closed α-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. |
| |
Keywords: | Association rule Bernoulli distribution Classification Complexity Data mining Frequent itemset Galois lattice Winning coalition |
本文献已被 ScienceDirect 等数据库收录! |
|