Mining Top-k motifs with a SAT-based framework

作者：Jabbour Said^*; Sais Lakhdar^*; Salhi Yakoub^*

来源：Artificial Intelligence, 2017, 244: 30-47.

DOI：10.1016/j.artint.2015.11.003

• Boolean satisfiability
• Data mining
• Modeling
• Top-k motifs

In this paper, we introduce a new problem, called Top-k SAT, that consists in enumerating the Top-k models of a propositional formula. A Top-k model is defined as a model with less than k models preferred to it with respect to a preference relation. We show that Top-k SAT generalizes two well-known problems: the Partial MAX-SAT problem and the problem of computing minimal models. Moreover, we propose a general algorithm for Top-k SAT. Then, we give an application of our declarative framework in data mining, namely, the problem of mining Top-k motifs in the transaction databases and in the sequences. In the case of mining sequence data, we introduce a new mining task by considering the sequences of itemsets. Thanks to the flexibility and to the declarative aspects of our SAT-based approach, an encoding of this task is obtained by a very slight modification of mining motifs in the sequences of items.

• 出版日期2017-3