An algebraic semigroup method for discovering maximal frequent itemsets

Abstract Discovering maximal frequent itemsets is an important issue and key technique in many data mining problems such as association rule mining. In the literature, generating maximal frequent itemsets proves either to be NP-hard or to have O ( l 3 4 l ( m + n ) ) O\left({l}^{3}{4}^{l}\left(m+n)) complexity in the worst case from the perspective of generating maximal complete bipartite graphs of a bipartite graph, where m m , n n are the item number and the transaction number, respectively, and l l denotes the maximum of ∣ C ∣ ∣ Ψ ( C ) ∣ / ( ∣ C ∣ + ∣ Ψ ( C ) ∣ − 1 ) | C| | \Psi \left(C)| \hspace{0.1em}\text{/}\hspace{0.1em}\left(| C| +| \Psi \left(C)| -1) , with the maximum taken over all maximal frequent itemsets C C . In this article, we put forward a method for discovering maximal frequent itemsets, whose complexity is O ( 3 m n 2 β + 4 β n ) O\left(3mn{2}^{\beta }+{4}^{\beta }n) , lower than the known complexity both in the worst case, from the perspective of semigroup algebra, where β \beta is the number of items whose support is more than the minimum support threshold. Experiments also show that an algorithm based on the algebraic method performs better than the other three well-known algorithms. Meanwhile, we explore some algebraic properties with respect to items and transactions, prove that the maximal frequent itemsets are exactly the simplified generators of frequent itemsets, give a necessary and sufficient condition for a maximal i + 1 i+1 -frequent itemset being a subset of a closed i i -frequent itemset, and provide a recurrence formula of maximal frequent itemsets.