Les motifs graduels visent à décrire des co-variations au sein des données et sont de la forme plus l'âge est important, plus le salaire est élevé. Ces motifs ont fait l'objet de nombreux travaux en fouille de données ces dernières années, du point de vue des définitions que peuvent avoir de tels motifs et d'un point de vue algorithmique pour les extraire efficacement. Ces définitions et algorithmes considèrent qu'il est possible d'ordonner de manière stricte les valeurs (par exemple l'âge, le salaire). Or, dans de nombreux champs applicatifs, il est difficile voire impossible d'ordonner de cette manière. Par exemple, quand l'on considère l'expression de gènes, dire que l'expression d'un gène est plus importante que l'expression d'un autre gène quand leurs expressions ne diffèrent qu'à la dixième décimale n'a pas de sens d'un point de vue biologique. Ainsi, nous proposons dans cette thèse une approche fondée sur les ordres flous. Les algorithmes étant très consommateurs tant en mémoire qu'en temps de calcul, nous proposons des optimisations d'une part du stockage des degrés flous et d'autre part de calcul parallélisé. Les expérimentations que nous avons menées sur des bases de données synthétiques et réelles montrent l'intérêt de notre approche. / Gradual patterns aim at describing co-variations of data such as the older, the higher the salary. They have been more and more studied from the data mining point of view in recent years, leading to several ways of defining their meaning and and several algorithms to automatically extract them.They consider that data can be ordered regarding the values taken on the attributes (e.g. the age and the salary).However, in many application domains, it is hardly possible to consider that data values are crisply ordered. For instance, when considering gene expression, it is not true, from the biological point of view, to say that Gene 1 is more expressed than Gene 2 if the levels of expression only differ from the tenth decimal. This thesis thus considers fuzzy orderings and propose both formal definitions and algorithms to extract gradual patterns considering fuzzy orderings. As these algorithms are both time and memory consuming, we propose some optimizations based on an efficient storage of the fuzzy ordering informationcoupled with parallel algorithms. Experimental results run on synthetic and real database show the interest or our proposal.

Dans cette thèse, nous nous intéressons à la recherche d'“items” et d'“itemsets” d'intérêt via la décomposition de matrice binaire (Binary Matrix Factorization, BMF) et à la recherche d'objets représentatifs. Pour cela, nous étudions l'état de l'art des techniques de décomposition matricielle. Nous établissons, dans le premier Chapitre, un lien entre BMF et le problème de programmation binaire quadratique sans contraintes (Unconstrained Binary Quadratic Programming, UBQP) afin d'utiliser les algorithmes et heuristiques existant dans la littérature pour UBQP et les appliquer à BMF.Nous proposons dans le Chapitre 2 une nouvelle heuristique adaptée au calcul de BMF. Cette technique efficace optimise les solutions de BMF ligne par ligne (ou colonne par colonne) en inversant 1 bit à chaque fois. En utilisant le lien établi dans le Chapitre 2 qui nous permet d'appliquer les algorithmes et heuristiques d'UBQP à BMF, nous comparons la méthode proposée (1-opt-BMF) avec les heuristiques spécialisées pour UBQP (1-opt-UBQP) ainsi que les heuristiques classiques (1-opt-Standard). Nous montrons ensuite, en théorie et en pratique, l'efficacité de 1-opt-BMF sur une large variété de données publiques. Dans le Chapitre 3, nous nous intéressons au problème de la recherche des itemsets représentatifs en utilisant BMF et 1-opt-BMF. Pour cela, nous considérons dans un premier temps le lien entre le problème de “frequent itemset mining” et BMF, et proposons une nouvelle méthode que nous appelons “Decomposition Itemset Miner” (DIM). Une série d'expérience montre la qualité des résultats obtenus et l'efficacité de notre méthode.Enfinf, nous nous intéressons, dans le Chapitre 4, à la recherche d'objets représentatifs (qui donnent une vue globale sur les données) dans des données de grandes dimensions. Nous examinons les méthodes disponibles dans la littérature en donnant les avantages et les inconvénients de chacune. Ensuite, nous défnissons mathématiquement le problème de sélection d'instance (Instance Selection Problem: ISP) et présentons trois variantes à ce problème ainsi que leur solutions. Dans les expériences, nous montrons que, bien qu'ISP puisse surpasser les autres méthodes dans certains cas, il vaut mieux le considérer en général comme une technique complémentaire dans le cadre de la recherche des objets représentatifs. / This thesis focuses on mining representative items and itemsets using Binary Matrix Factorization (BMF) and instance selection. To accomplish this task, we first, in Chapter 1, consider the BMF problem by studying the literature on matrix decomposition techniques and the state-of-the-art algorithms. Then, we establish a connection between BMF problem and Unconstrained Binary Quadratic Programming (UBQP) problem in order to use UBQP's algorithms and heuristics, available in the literature, in case of BMF solutions. Next, in Chapter 2, we propose a new, efficient heuristic which flips 1 bit at the time in order to improve the solutions of BMF. Using the established link discussed in Chapter 2, which enables us to use heuristics of UBQP, we compare the proposed technique, called 1-opt-BMF with that of UBQP, called 1opt-UBQP as well as the standard approach, called 1-opt-Standard. We then show, theoretically and experimentally, the efficiency of 1-opt-BMF on a wide range of publicly available datasets. Next, in Chapter 3, we explore addressing the problem of finding representative itemsets via BMF. To do that, we first consider the theoretical relation between the frequent itemset mining problem and BMF; while established, we propose a new technique called Decomposition Itemset Miner (DIM). We then design a set of experiments to show the efficiency of DIM and the quality of its results.Finally, in Chapter 4, we consider the problem of finding representative objects (instances) in big, high-dimensional datasets. These objects helps us to find objects providing a global, top-view of the data and are very important in data analysis process. We first study the available methods for finding representative objects and discuss the pros and cons of each. We then formally define the Instance Selection Problem (ISP), provide three variants of that and examine their complexities before providing their solutions. In the experimental section, we show that although the ISP solutions can outperform other methods in some cases, in general it should be considered as a complementary technique in the context of finding representative objects.