Ph.D Ruggero G. Pensa

Un cadre générique pour la co-classification sous contraintes : application à l’analyse du transcriptome

Download Draft here

Date de soutenance : 20/11/2006

Lieu (établissement) : INSA de Lyon

Jury              

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

Pr. Luc De Raedt (Examinateur, Université de Freiburg, Allemagne)

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

Dr. Céline Robardet (Co-directeur de la thèse, INSA Lyon)

Pr. Céline Rouveirol (Rapporteur, Université Paris 13)

Pr. Marc Sebban (Examinateur, Université de Saint-Etienne)

Résumé. La recherche de groupements intéressants dans les données booléennes (ensembles d'objets décrits par un ensemble de propriétés) a motivé la conception de méthodes d'extractions de motifs globaux (partitions) et de motifs locaux (ensembles fréquents, règles d'association et concepts formels). Cette thèse concerne la co-classification c'est-à-dire le calcul de bi-partitions (couplage de partitions sur les deux dimensions). Les algorithmes de co-classification disponibles ne permettent aux analystes d'exploiter leur connaissance du domaine qu'à travers un nombre réduit de paramètres. D'autre part, les techniques d'extraction de motifs locaux produisent d'énormes collections qui sont difficilement exploitables et interprétables. Nous avons développé une nouvelle méthode de co-classification qui calcule des bi-partitions à partir de motifs capturant des associations localement fortes (e.g., des concepts formels, une forme de motif tolérant aux exceptions appelé δ-bi-ensemble). Le principe consiste à exploiter l'information contenue dans la collection des motifs locaux en la propageant au niveau global pour faciliter l'optimisation de la fonction objectif. Il devient alors possible de propager un certain nombre de contraintes depuis l'extraction des motifs locaux jusqu'à la construction de la bi-partition (e.g., pour imposer des formes particulières aux groupes calculés). Il s'agit donc d'une contribution au domaine très récent de la classification sous contraintes. Une approche duale consiste à utiliser des motifs locaux pour faciliter l'interprétation de bi-partitions déjà calculées. Pour ce faire, nous proposons une méthode de caractérisation des co-clusters au moyen de motifs locaux auxquels sont associés des mesures d'intérêt. L'application de nos méthodes à l'analyse de données d'expression de gènes a montré la pertinence de nos propositions pour expliciter des hypothèses biologiques plausibles.

Abstract. The search for interesting groups in boolean data (sets of objects described by sets of properties) has motivated the design of methods for computing global patterns (e.g.., partitions), and extracting local patterns s(e.g., frequent itemsets, association rules, formal concepts. This thesis concerns co-clustering, i.e., computing bi-partitions (coupled partitions on both dimensions). When using available co-clustering algorithms, the user can hardly exploit his/her domain knowledge since he/she has limited possibilities for setting just a few parameters. On the other hand, classical local pattern mining techniques usually provide huge collections of patterns that are hard to evaluate and interpret. We have designed a new co-clustering framework which computes a bi-partition by starting from collections of patterns that capture locally strong associations (e.g., formal concepts, δ-bi-set that are a form of fault-tolerant patterns). The idea is that the available information about the local patterns can be exploited to build a relevant global pattern. It becomes possible to consider the declarative specification of constraints on the bi-partitions (e.g., user-defined requirements about the shape of clusters) and to use such constraints at the local pattern mining step and then during the co-clustering phase. As such, our proposal is a contribution to the recent domain of constraint-based clustering. A dual approach consists in using local patterns to interpret bi-partitions. We propose a method for co-cluster characterization by means of local patterns and their associated interestingness measures. The application of our methods to a gene expression data analysis scenario has illustrated the added-value of our proposal to give rise to plausible biological hypothesis.

Publications liées à la thèse

C. Robardet, R. G. Pensa, J. Besson, J-F. Boulicaut. Using classification and visualization on pattern databases for gene expression data analysis. Proceedings of the International Workshop on Pattern Representation and Management PaRMa'04 co-located with EDBT 2004, Heraclion - Crete, Greece, March 2004. CEUR Workshop Proceedings Vol. 96, pp. 107-118.

R. G. Pensa, J-F. Boulicaut. From local pattern mining to relevant bi-cluster characterization. Proceedings of the 6th International Symposium on Intelligent Data Analysis IDA'05, Madrid, Spain, September 2005. Springer LNCS 3646, pp. 293-304.

R. G. Pensa, C. Robardet, J-F. Boulicaut. A bi-clustering framework for categorical data. Proceedings of the 9^th European Conference on Principles and Practice of Knowledge Discovery in Databases PKDD'05, Porto (P), October 2005, Springer LNAI 3721, pp. 643-650.

R. G. Pensa, C. Robardet, J-F. Boulicaut. Towards constrained co-clustering in ordered 0/1 data sets. Foundations of Intelligent Systems - Proceedings of the 16th International Symposium on Methodologies for Intelligent Systems ISMIS'06, Bari (I), September 2006. Springer LNAI 4203, pp. 425-434.

R. G. Pensa, C. Robardet, J-F. Boulicaut. Supporting bi-cluster interpretation in 0/1 data by means of local patterns. Intelligent Data Analysis IDA 10(5):457-472, 2006.

R. G. Pensa, C. Robardet, J-F. Boulicaut. Co-classification sous contraintes. Actes de la conférence francophone d'apprentissage automatique CAp 2006, Trégastel (F), mai 2006, Presses Universitaires de Grenoble, pp. 155-170.