Key roles of closed sets and minimal generators in concise representations of frequent patterns

Abstract

The last years witnessed an explosive progress in networking, storage, and processing technologies resulting in an unprecedented amount of digitalization of data. Hence, there has been a considerable need for tools or techniques to delve and efficiently discover valuable, non-obvious information from large databases. In this situation, data mining is an important research field which offers efficient solutions for such an extraction. Much research in data mining from large databases have focused on the discovery of frequent patterns which are then used to identify relationships between sets of items in a database, through for example association rule derivation. In practice, however, the number of frequently occurring patterns is very large, hampering their effective exploitation by the end-users. In this situation, many works have been interested in defining manageably-sized sets of patterns, called concise representations, from which redundant patterns can be regenerated. In this paper, we concentrate on exact concise representations of frequent patterns. Thus, we describe their close relation with important concepts like the framework of ε-adequate representation and the minimum description length principle. Based on the mathematical settings of Formal Concept Analysis, we also show the complementarity between minimal generators and closed itemsets. Then, we focus on the key role played by these patterns for solving several problem associated to various pattern classes. In this respect, we classify concise representations of frequent itemsets according to their common characteristics. Then, we analyze a representative of each class and show its close link with minimal generators. Finally, we carry out a critical study of concise representations with respect to several aspects and comparative criteria which proves the importance of considering closed sets and minimal generators.