International audience

Computing high utility motifs is a fundamental data mining method for discovering useful itemsets yielding high utility values. Minimal and maximal high utility itemsets are two examples of compact representations used to reduce the output size due to the large and incomprehensible number of patterns. In this paper, we present a novel method for mining minimal and maximal high utility itemsets using propositional satisfiability. First, we show that minimal and maximal high utility patterns are X-minimal models of a CNF formula. Then, to improve the scalability issue of our method, we harness a decomposition paradigm that splits the transaction database into smaller and independent transaction sub-bases, allowing an efficient enumeration of minimal and maximal high utility itemsets. Finally, through extensive evaluation studies on various real-world datasets, we demonstrate that our approach is very competitive w.r.t. to the state-of-the-art specialized solutions.

Discovering useful patterns plays an essential role in data management and data mining. Frequent itemset mining in uncertain transaction databases semantically and computationally differs from traditional techniques applied on (standard) precise transaction databases. Uncertain transaction databases consist of sets of existentially uncertain items. The uncertainty of items in transactions makes traditional techniques in applicable. Recent works propose interesting SAT-based encodings for the problem of discovering frequent itemsets in deterministic transaction databases. Our aim in this work is to extend the SAT-based encoding of frequent itemset mining to uncertain databases. Then, we propose a novel declarative mining frame-work for extracting uncertain frequent patterns from uncertain transaction databases. It makes an original use of constraints relaxation to obtain upper bounds to the expected support of frequent patterns, while guaranteeing the enumeration of all frequent itemsets with no false negatives. We experimentally evaluated our approach. The experimental results on real and synthetic data sets demonstrate the effectiveness of our proposal in mining frequent patterns.

Frequent itemset mining (FIM) is a useful task for discovering frequent co-occurring items. Since its inception, a number of significant FIM algorithms have been developed to speed up mining performances. Unfortunately, for huge dataset, scalability remains an important issue. In this work, we propose a new propositional satisfiability (SAT) parallel approach, called PSATCFIM, to deal with closed frequent itemsets mining problem. It is designed to run on multicore machines and uses a divide and conquer approach to partition the enumeration process. Such partitioning based on guiding paths eliminates computational overlap between cores. Through empirical study, we demonstrate that PSATCFIM can achieve significant performance improvements with respect to the sequential based version.

The web plays an important role in people's social lives since the emergence of Web 2.0. It facilitates the interaction between users, gives them the possibility to freely interact, share and collaborate through social networks, online community forums, blogs, wikis and other online collaborative media. However, an other side of the web is negatively taken such as posting inflammatory messages. Thus, when dealing with the online community forums, the managers seek to always enhance the performance of such platforms. In fact, to keep the serenity and prohibit the disturbance of the normal atmosphere, managers always try to novice users against these malicious persons by posting such message (DO NOT FEED TROLLS). But, this kind of warning is not enough to reduce this phenomenon. In this context we propose a new approach for detecting malicious people also called 'Trolls' in order to allow community managers to take their ability to post online. To be more realistic, our proposal is defined within an uncertain framework. Based on the assumption consisting on the trolls' integration in the successful discussion threads, we try to detect the presence of such malicious users. Indeed, this method is based on a conflict measure of the belief function theory applied between the different messages of the thread. In order to show the feasibility and the result of our approach, we test it in different simulated data.