Ph.D Loic Cerf

Constraint-based Mining of Closed Patterns in Noisy N-ary Relations

Download Draft here

Date de soutenance : 09/07/2010

Lieu (établissement) : INSA de Lyon

Jury               

Dr. Francesco Bonchi (Examinateur, Yahoo! Research, ES)

Dr. Jérémy Besson (Examinateur, Inst. of Math. & Informatics, LT)

Pr. Jean-François Boulicaut (Co-directeur de thèse, INSA Lyon)

Dr. Toon Calders (Examinateur, Eindhoven Tech. University, NL)

Pr. Bruno Crémilleux (Rapporteur, Université de Caen)

Pr. Arno Siebes (Examinateur, University of Utrecht, NL)

Pr. Hannu Toivonen (Rapporteur, University of Helsinki, FI)

Pr. Christel Vrain (Présidente, Université d’Orléans, FR)

Résumé. Les processus de découverte de connaissances nouvelles peuvent être fondés sur des motifs locaux extraits de grands jeux de données. Concevoir des algorithmes de fouille de données efficaces pour calculer des collections de motifs pertinents est un domaine actif de recherche. Beaucoup de jeux de données enregistrent si des objets présentent ou non certaines propriétés ; par exemple si un produit est acheté par un client ou si un gène est sur-exprimé dans un échantillon biologique. Ces jeux de données sont des relations binaires et peuvent être représentés par des matrices 0/1. Dans de telles matrices, un ensemble fermé est un rectangle maximal de '1's modulo des permutations arbitraires des lignes (objets) et des colonnes (propriétés). Ainsi, chaque ensemble fermé sous-tend la découverte d'un sous-ensemble maximal d'objets partageant le même sous-ensemble maximal de propriétés. L'extraction efficace de tous les ensembles fermés, satisfaisant des contraintes de pertinences définies par l'utilisateur, a été étudiée en profondeur. Malgré son succès dans de nombreux domaines applicatifs, ce cadre de travail se révèle souvent trop étroit. Tout d'abord, beaucoup de jeux de données sont des relations $n$-aires, c'est à  dire des tenseurs 0/1. Réduire leur analyse à  deux dimensions revient à  ignorer des dimensions additionnelles potentiellement intéressantes ; par exemple où un client achète un produit (analyse spatiale) ou quand l'expression d'un gène est mesurée (analyse cinétique). La présence de bruit dans la plupart des jeux de données réelles est un second problème qui conduit à  la fragmentation des motifs à  découvrir. On généralise facilement la définition d'un ensemble fermé pour la rendre applicable à  des relations de plus grande arité et tolérante au bruit (hyper-rectangle maximal avec une borne supérieure de '0's tolérés par hyper-plan). Au contraire, généraliser leur extraction est très difficile. En effet, les algorithmes classiques exploitent une propriété mathématique (la connexion de Galois) des ensembles fermés qu'aucune des deux généralisations ne préserve. C'est pourquoi notre extracteur parcourt l'espace des motifs candidats d'une façon originale qui ne favorise aucune dimension. Cette recherche peut être guidée par une très grande classe de contraintes de pertinence que les motifs doivent satisfaire. En particulier, cette thèse étudie des contraintes spécifiquement conçues pour la fouille de quasi-cliques presque-persistantes dans des graphes dynamiques. Notre extracteur est plusieurs ordres de grandeurs plus efficace que les algorithmes existants se restreignant à  la fouille de motifs exacts dans des relations ternaires ou à  la fouille de motifs tolérants aux erreurs dans des relations binaires. Malgré ces résultats, une telle approche exhaustive ne peut souvent pas, en un temps raisonnable, tolérer tout le bruit contenu dans le jeu de données. Dans ce cas, compléter l'extraction avec une agglomération hiérarchique des motifs (qui ne tolèrent pas suffisamment de bruit) améliore la qualité des collections de motifs renvoyées.

Abstract. Useful knowledge discovery processes can be based on patterns extracted from large datasets. Designing efficient data mining algorithms to compute collections of relevant patterns is an active research domain. Many datasets record whether some properties hold for some objects, e.g., whether an item is bought by a customer or whether a gene is over-expressed in a biological sample. Such datasets are binary relations and can be represented as 0/1 matrices. In such matrices, a closed itemset is a maximal rectangle of '1's modulo arbitrary permutations of the lines (objects) and the columns (properties). Thus, every closed itemset supports the discovery of a maximal subset of objects sharing the same maximal subset of properties. Efficiently extracting every closed itemset satisfying user-defined relevancy constraints has been extensively studied. Despite its success across many application domains, this framework often turns out to be too narrow. First of all, many datasets are $n$-ary relations, i.e., 0/1 tensors. Reducing their analysis to two dimensions is ignoring potentially interesting additional dimensions, e.g., where a customer buys an item (localized analysis) or when a gene expression is measured (kinetic analysis). The presence of noise in most real-life datasets is a second issue, which leads to the fragmentation of the patterns to discover. Generalizing the definition of a closed itemset to make it suit relations of higher arity and tolerate some noise is straightforward (maximal hyper-rectangle with an upper bound of '0's tolerated per hyper-plan). On the contrary, generalizing their extraction is very hard. Indeed, classical algorithms exploit a mathematical property (the Galois connection) of the closed itemsets that none of the two generalizations preserve. That is why our extractor browses the candidate pattern space in an original way that does not favor any dimension. This search can be guided by a very broad class of relevancy constraints the patterns must satisfy. In particular, this thesis studies constraints specifically designed for mining almost-persistent cliques in dynamic graphs. Our extractor is orders of magnitude faster than known competitors focusing on exact patternsin ternary relations or on noise-tolerant patterns in binary relations. Despite these results, such an exhaustive approach often cannot, in a reasonable time, tolerate as much noise as the dataset contains. In this case, complementing the extraction with a hierarchical agglomeration of the (insufficiently noise-tolerant) patterns increases the quality of the returned collection of patterns.

Publications liées à la thèse

L. Cerf, J. Besson, C. Robardet, J-F. Boulicaut. Data_Peeler: Constraint-based Closed Pattern Mining in n-ary Relations.  Proceedings SIAM International Conference on Data Mining SDM'08, Atlanta, USA, April 24-26, 2008. pp. 37-48.

J. Besson,  L. Cerf, R. Thévenoux, J-F. Boulicaut.Tackling closed pattern relevancy in n-ary relations. Proceedings 1st Workshop Mining Multidimensional Data MMD'08 co-located with ECML PKDD 2008, Antwerp, Belgium, September 15-19, 2008. pp. 2-16.

L. Cerf, D. Gay, N. Selmaoui, J-F. Boulicaut. A parameter-free associative classification method.  Proceedings 10th International Conference on Data Warehousing and Knowledge Discovery DaWaK'08, Torino, Italy, September 1-5, 2008. Springer LNCS 5182, pp. 293-314.

L. Cerf, J. Besson, C. Robardet, J-F. Boulicaut. Closed Patterns Meet n-ary Relations. Closed Patterns Meet n-ary Relations. ACM Transactions on Knowledge Discovery in Data 3(1) pp. 3:1-3:37. ACM Press. March 2009.

L. Cerf, J. Besson, J-F. Boulicaut. Extraction de motifs fermés dans des relations n-aires bruitées. Actes des 9ème Journées Francophones Extraction et Gestion de Connaissances EGC'09, Strasbourg (F), 27-30 janvier 2009, Cepadues-Editions, RNTI-E-15,  pp. 163-168.

L. Cerf, T. Bao N. Nguyen, J-F. Boulicaut. Discovering relevant cross-graph cliques in dynamic networks. Proceedings 18th Int. Symp. on Methodologies for Intelligent Systems ISMIS'09, Prague, Czech Republic, Springer LNCS 5722, pp. 513-522.

L. Cerf, P-N. Mougel, J-F. Boulicaut. Agglomerating Local Patterns Hierarchically with Alpha. Proceedings 18th ACM Conf. on Information and Knowledge Management CIKM'09, Hong Kong, China, 2-6 November 2009, pp. 1753-1756.