Closed Itemset Mining: A graph theory perspective

Data Mining is the field which targets the extraction and the analysis of usable data from a large database. In this paper, we focus on the most studied problems in the field. That is finding closed frequent itemsets. Up to now, various graph theory techniques have been proposed to solve the frequent itemsets problem. Unfortunately, these techniques have the drawback of neglecting the existing relationship between each pair of items that appear in the same transaction. In this paper, first of all, we present a scalable new modeling approach which allows the representation of a transaction dataset by an undirected and labeled graph. The labels are astutely computed and properly assigned to the bonds. Secondly, based on the clique notion in graph theory, we propose polynomial and exact algorithm that computes all the closed frequent itemsets. In terms of CPU-time and the memory usage, our first testing results show the efficiency of our algorithm compared to recent methods selected in the literature. Thus, the benefit of using our graph model is its ability to be simply extended when the corresponding dataset is updated.In other words, the proposed labeled graph incorporates all the information contained in the transaction database. This is the strong aspect of the model, which can be used to investigate more challenging issues related to the problem dealt within this paper.