Lakhdar Sais

KR Conference 2024 Conference Paper

LAD-based Feature Selection for Optimal Decision Trees and Other Classifiers

• David Ing
• Said Jabbour
• Lakhdar Sais
• Fabien Delorme

The curse of dimensionality presents a significant challenge in data mining, pattern recognition, computer vision, and machine learning applications. Feature selection is a primary approach to address this challenge. It aims to eliminate irrelevant and redundant features while preserving the relevant ones to reduce computation time, improve prediction performance, and enhance the understanding of data. In this paper, we introduce a new feature selection (FS) technique based on the Logical Analysis of Data (LAD), a pattern learning framework that combines optimization, Boolean functions, and combinatorial theory. One of its main objectives is to generate minimal support sets of features (subsets of features) that discriminate between different groups of data. To generate such subsets, we first reduce the complexity of the LAD optimization task by transforming it into the problem of enumerating minimal hitting sets in a hypergraph, for which efficient implementations exist. Those feature subsets are then ranked based on a scoring method before selecting the highest quality one. Moreover, we explore the relationship between optimal Decision Trees (DTs) and LAD-based FS, introducing new optimality criteria, namely DTs involving a minimum number of features. Finally, we conduct comparative evaluations of LAD-based approach against several state-of-the-art (SOTA) FS methods on benchmark datasets, including two-class binary datasets and numerical datasets with two and multiple classes. Experiments reveal that our approach is competitive with SOTA methods, selecting high-quality feature subsets that maintain or enhance the performance of DTs and other classifiers like SVM, KNN, and Naive Bayes.

IJCAI Conference 2023 Conference Paper

A Symbolic Approach to Computing Disjunctive Association Rules from Data

• Said Jabbour
• Badran Raddaoui
• Lakhdar Sais

Association rule mining is one of the well-studied and most important knowledge discovery task in data mining. In this paper, we first introduce the k-disjunctive support based itemset, a generalization of the traditional model of itemset by allowing the absence of up to k items in each transaction matching the itemset. Then, to discover more expressive rules from data, we define the concept of (k, k′)-disjunctive support based association rules by considering the antecedent and the consequent of the rule as k-disjunctive and k′-disjunctive support based itemsets, respectively. Second, we provide a polynomial-time reduction of both the problems of mining k-disjunctive support based itemsets and (k, k′)-disjunctive support based association rules to the propositional satisfiability model enumeration task. Finally, we show through an extensive campaign of experiments on several popular real-life datasets the efficiency of our proposed approach

AAMAS Conference 2022 Conference Paper

A Declarative Framework for Maximal k -plex Enumeration Problems

• Said Jabbour
• Nizar Mhadhbi
• Badran Raddaoui
• Lakhdar Sais

It is widely accepted that an ideal community in networks is the one whose structure is closest to a (maximal) clique. However, in most real-world graphs the clique model is too restrictive, as it requires complete pairwise interactions. More relaxed cohesive subgraph models were then studied. A 𝑘-plex is one of the arguably most studied pseudo-clique model. A 𝑘-plex of size 𝑛 is a subgraph where any vertex is adjacent to at least (𝑛 − 𝑘) vertices. Unfortunately, some maximal 𝑘-plexes, by involving irrelevant subgraphs, are far from designing meaningful communities in real-world networks. In this paper, we first introduce a novel variant of 𝑘-plex model, called cohesive 𝑘-plex, which is more appropriate for modeling closelyinteracting communities. Then, we reduce the problem of enumerating maximal (cohesive) 𝑘-plexes in a graph to those of enumerating the models of a formula in propositional logic. Afterwards, to make our approach more efficient, we provide a decomposition technique that is particularly suitable for deriving smaller and independent sub-problems easy to resolve. Lastly, our extensive experiments on various real-world graphs demonstrate the efficiency of the proposed approach w. r. t state-of-the-art algorithms.

AIJ Journal 2017 Journal Article

Mining Top-k motifs with a SAT-based framework

• Said Jabbour
• Lakhdar Sais
• Yakoub Salhi

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.

KR Conference 2016 Conference Paper

A MIS Partition Based Framework for Measuring Inconsistency

• Said Jabbour
• Yue Ma
• Badran Raddaoui
• Lakhdar Sais
• Yakoub Salhi

In this paper, we propose a general framework, both parameterized and parameter-free, for defining a family of fine-grained inconsistency measures for propositional knowledge bases. The parameterized approach allows to encompass several existing inconsistency measures as specific cases, by properly setting its parameter. And the parameter-free approach is defined to avoid the difficulty in choosing a suitable parameter in practice but still keeps a desired ranking for knowledge bases by their inconsistency degrees. The fine granularity of our framework is based on the notion of MIS partition that considers the inner structure of all the minimal inconsistent subsets of a knowledge base. Moreover, MinCostSATbased encodings are provided, which enable the use of efficient SAT solvers for the computation of the proposed measures. We implement these algorithms and test them on some real-world datasets. The preliminary experimental results for a variety of inputs show that the proposed framework gives a wide range of possibilities for evaluating large knowledge bases.

IJCAI Conference 2016 Conference Paper

A SAT-Based Approach for Mining Association Rules

• Abdelhamid Boudane
• Said Jabbour
• Lakhdar Sais
• Yakoub Salhi

Discovering association rules from transaction databases is one of the most studied data mining task. Many effective techniques have been proposed over the years. All these algorithms share the same two steps methodology: frequent itemsets enumeration followed by effective association rules generation step. In this paper, we propose a new propositional satisfiability based approach to mine association rules in a single step. The task is modeled as a Boolean formula whose models correspond to the rules to be mined. To highlight the flexibility of our proposed framework, we also address two other variants, namely the closed and indirect association rules mining tasks. Experiments on many datasets show that on both closed and indirect association rules mining tasks, our declarative approach achieves better performance than the state-of-the-art specialized techniques.

IJCAI Conference 2009 Conference Paper

• Youssef Hamadi
• Said Jabbour
• Lakhdar Sais

Conflict driven clause learning, one of the most important component of modern SAT solvers, is also recognized as very important in parallel SAT solving. Indeed, it allows clause sharing between multiple processing units working on related (sub- )problems. However, without limitation, sharing clauses might lead to an exponential blow up in communication or to the sharing of irrelevant clauses. This paper, proposes two innovative policies to dynamically adjust the size of shared clauses between any pair of processing units. The first approach controls the overall number of exchanged clauses whereas the second additionally exploits the relevance quality of shared clauses. Experimental results show important improvements of the state-of the-art parallel SAT solver.

IJCAI Conference 2007 Conference Paper

• Christophe Lecoutre
• Lakhdar Sais
• S
• eacute; bastien Tabary
• Vincent Vidal

In this paper, nogood recording is investigated within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i. e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of our approach.

IJCAI Conference 1997 Conference Paper

Tractable Cover Compilations

• Yacine Boujkhad
• Eric Gregoire
• Pierre Marquis
• Bertrand Mazure
• Lakhdar Sais

Tractable covers are introduced as a new ap­ proach to equivalence-preserving compilation of propositional knowledge bases. First, a gen­ eral framework is presented. Then, two specific cases are considered. In the first one, partial interpretations are used to shape the knowl­ edge base into tractable formulas from several possible classes. In the second case, they are used to derive renamable Horn formulas. This last case is proved less space-consuming than prime implicants cover compilations for every knowledge base. Finally, experimental results show that the new approaches can prove effi­ cient w. r. t. direct query answering and offer significant time and space savings w. r. t. prime implicants covers.