On Mining Max Frequent Generalized Itemsets (full version) ⋆

Abstract. A fundamental task of data mining is to mine frequent itemsets. Since the number of frequent itemsets may be large, a compact representation, namely the max frequent itemsets, has been introduced. On the other hand, the concept of generalized itemsets was proposed. Here, the items form a taxonomy. Although the transactional database only contains items in the leaf level of the taxonomy, a generalized itemset may contain some non-leaf generalized items. Naturally, an interesting question arises: can we combine the two concepts and develop algorithms to mine max frequent generalized itemsets? This is a compact representation of the set of all frequent generalized itemsets. To the best of our knowledge, this paper is the first work that efficiently solves this new problem. Our solution has the following components: a conceptual classification tree, the algorithm MFGI class that dynamically generates the needed part of the conceptual classification tree by applying three pruning techniques, an online method for checking false positives, and an optimization technique called PHDB that batch-compute frequencies. Besides market-basket analysis, our technique has a vast range of other applications. For instance, identifying associations among (categories of) diseases, identifying associations among (groups of) occupations, and so on. Experimental results demonstrate the efficiency of our approach.