?
Introducing the closure structure and the GDPM algorithm for mining and understanding a tabular dataset
Pattern mining is one of the most studied fields in data mining. Being mostly motivated by practitioners, pattern mining algorithms are often based on heuristics and are lacking suitable formalization. In this paper, we are revisiting pattern mining, and especially itemset mining, which allows one to analyze binary datasets in searching for interesting and meaningful itemsets and respective association rules. We introduce a concise representation –the closure structure– based on closed itemsets and their minimum generators (called “passkeys”) for capturing the intrinsic content of a dataset. The closure structure allows one to understand the content of the dataset in terms of closed sets and equivalence classes of itemsets. We discuss theoretical properties of passkeys which are concise representatives of closed itemsets. We propose a formalization of the closure structure and passkeys in terms of Formal Concept Analysis, which is well adapted to studying such elements. Besides theoretical results, we present the GDPM algorithm for enumerating passkeys and discovering the closure structure. GDPM is rather unique as it returns a characterization of a dataset content in terms of complexity levels, highlighting the diversity and the distribution of the itemsets. Finally, some experiments show how the GDPM algorithm and the closure structure can be practically used.
