Size of random Galois lattices and number of closed frequent itemsets
Emilion, Richard; Lévy, Gérard (2009), Size of random Galois lattices and number of closed frequent itemsets, Discrete Applied Mathematics, 157, 13, p. 2945–2957. http://dx.doi.org/10.1016/j.dam.2009.02.025
TypeArticle accepté pour publication ou publié
Journal nameDiscrete Applied Mathematics
MetadataShow full item record
Abstract (EN)Given a sample of binary random vectors with i.i.d. Bernoulli(pp) components, that is equal to 1 (resp. 0) with probability pp (resp. 1−p1−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.
Subjects / KeywordsAssociation rule; Bernoulli distribution; Classification; Complexity; Data mining; Frequent itemset; Galois lattice; Winning coalition
Showing items related by title and author.