Extraction des motifs fréquents sous contraintes

Abstract

Frequent pattern mining is one of the fundamental tasks of data mining. It consists in discovering interesting patterns for the user from the databases. Different types of patterns can be found from various types of data, such as transactional data, sequences, graphs and trees. This thesis is concerned with the two well-known tasks of pattern mining, namely frequent itemsets mining and sequential pattern mining. The first contribution of this thesis concerns the use of declarative approaches of the SAT type for mining frequent closed itemsets. These approaches are known to be flexible by allowing constraints to be added to mine particular patterns. One of the major problems of these approaches is the scalability due to the size of the encoding of large transactional databases. To reduce the size of these encodings, we have proposed more compact represen tations. More precisely, we show that our approach can be seen as a Boolean matrix compression problem. Our results show a significant reduction in encoding size. Our second contribution consists in exploiting the symmetries within the framework of mining sequential patterns. The search of these symmetries is performed by encoding the sequence table in the form of a colored directed graph. The symmetries are then enumerated by calculating the automorphisms of the graph. Finally, we propose two approaches to exploit the detected symmetries. In the first, we show how wecanimprovethesequential pattern mining by integrating the symmetries discovered in an Apriori-like algorithm. In the second approach we demonstrate how these symmetries can be used in preprocessing. This is achieved by modifying the original sequences database