Méthodes d'extraction de connaissances à partir de données modélisables par des graphes : Application à des problèmes de synthèse organique, Methods of knowledge extraction from data modelled by graphs. Application to organic synthesis problems

Frédéric Pennerath

Description

Sous la direction de Amedeo Napoli
Thèse soutenue le 02 juillet 2009: Nancy 1
Des millions de réactions chimiques sont décrites dans des bases de données sous la forme de transformations de graphes moléculaires. Cette thèse propose différentes méthodes de fouille de donnés pour extraire des motifs pertinents contenus dans ces graphes et ainsi aider les chimistes à améliorer leurs connaissances des réactions chimiques et des molécules. Ainsi on commence par montrer comment le problème central de la recherche des schémas de réactions fréquents peut se résoudre à l'aide de méthodes existantes de recherche de sous-graphes fréquents. L'introduction du modèle général des motifs les plus informatifs permet ensuite de restreindre l'analyse de ces motifs fréquents à un nombre réduit de motifs peu redondants et représentatifs des données. Si l'application du modèle aux bases de réactions permet d'identifier de grandes familles de réactions, le modèle est inadapté pour extraire les schémas caractéristiques de méthodes de synthèse (schémas CMS) dont la fréquence est trop faible. Afin de surmonter cet obstacle, est ensuite introduite une méthode de recherche heuristique fondée sur une contrainte d’intervalle entre graphes et adaptée à l’extraction de motifs de très faible fréquence. Cette méthode permet ainsi de déterminer à partir d'exemples de réactions et sous certaines conditions le schéma CMS sous-jacent à une réaction donnée. La même approche est ensuite utilisée pour traiter le problème de la classification supervisée de sommets ou d'arêtes fondée sur leurs environnements puis exploitée pour évaluer la formabilité des liaisons d'une molécule. Les résultats produits ont pu être analysés par des experts de la synthèse organique et sont très encourageants.
-Fouille de données
-Fouille de graphes
-Extraction sélective de motifs dans des données
-Recherche des motifs fréquents
Millions of chemical reactions are described in databases as transformations of molecular graphs. This thesis proposes different data-mining methods to extract relevant patterns included in those graphs and therefore to help chemists in improving knowledge about chemical reactions and molecules. One first shows how the central problem of searching frequent reaction patterns can be solved using existing graph-mining methods. Introducing the general model of most informative patterns then allows experts to reduce the analysis of these frequent patterns to a very small set of non-redundant patterns characteristic of data. If the application of this model to reaction database identifies large and characteristic families of reactions, the model doesn't allow in practice the extraction of reaction patterns characteristic of synthesis methods (abbr. CSM patterns) as their frequencies are far too low. In order to overcome this problem, is introduced a heuristic search algorithm based on a graph interval constraint and able to extract patterns with very low frequency. Thus this method determines from examples of chemical reactions and under some conditions the CSM pattern underlying a given input reaction. The same approach is then used to address the problem of supervised classification of vertices or edges based on their environment and then applied to evaluate formability of bonds in molecules. Experimental results have been analyzed by experts and are very encouraging.
Source: http://www.theses.fr/2009NAN10061/document

Sujets

• Exploration de données

Informations

• Publié par: Thesee
• Nombre de lectures: 65
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le
jury de soutenance et mis à disposition de l'ensemble de la
communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci
implique une obligation de citation et de référencement lors
de l’utilisation de ce document.

D’autre part, toute contrefaçon, plagiat, reproduction
illicite encourt une poursuite pénale.


➢ Contact SCD Nancy 1 : [e-mail]




LIENS


Code de la Propriété Intellectuelle. articles L 122. 4
Code de la Propriété Intellectuelle. articles L 335.2- L 335.10
http://www.cfcopies.com/V2/leg/leg_droi.php
http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm Departement de formation doctorale en informatique Ecole doctorale IAEM Lorraine
UFR STMIA
Methodes d’extraction de
connaissances a partir de donnees
modelisables par des graphes.
Application a des problemes de
synthese organique.
THESE
presentee et soutenue publiquement le 2 juillet 2009
pour l’obtention du
Doctorat de l’universite Henri Poincare – Nancy 1
(specialite informatique)
par
Frederic Pennerath
Composition du jury
President : Marie-Christine Haton Professeur emerite a l’universite Henri Poincare de Nancy
Rapporteurs : Bruno Cremilleux Professeur a l’universite de Caen Basse-Normandie
Pascal Poncelet Professeur a l’universite Montpellier II
Examinateurs : Amedeo Napoli Directeur de recherches CNRS au Loria (codirecteur de these)
Gilles Niel Charge de recherches CNRS a
l’Institut Charles Gerhardt de Montpellier
Lhouari Nourine Professeur a l’universite Blaise Pascal de Clermont-Ferrand
Geraldine Polaillon Enseignant-chercheur a Supelec (codirectrice de these)
Laboratoire Lorrain de Recherche en Informatique et ses Applications — UMR 7503Mis en page avec la classe thloria.Remerciements
Les personnes qui ont, a des degres divers, contribue a l’aboutissement de ce travail sont
nombreuses.Jelesenremercietoutes.Enpremierlieu,jeremercieAmedeoNapolipouravoir
accepte de diriger ma these, pour avoir propose un sujet tres interessant, pour m’avoir forme
auxpratiquesdumetierdechercheuretpourm’avoirfaitconancepardeladesincomprehen-
sions passageres. Je remercie particulierement Bruno Cremilleux et Pascal Poncelet d’avoir
accepted’ˆetrelesrapporteursdecememoire.Jelesenremercied’autantplusqu’illeurafallu
lireenrelativementpeudetempsundocumentassezlongetdontl’intrigue,jedoismerendre
a l’evidence, n’en fera pas le meilleur recit a suspens de cet ete 2009. Je remercie egalement
GeraldinePolaillonpouravoirparticipealadirectiondemathese,ainsiqueLhouariNourine,
Marie-Christine Haton et Gilles Niel pour avoir accepte de faire partie du jury et s’ˆetre ainsi
penches sur mes travaux. Merci aux chercheurs montpellierains chimistes ou informaticiens
Philippe Jau ret, Claude Laurenco, Gilles Niel et Philippe Vismara avec qui j’ai apprecie
de collaborer dans le cadre d’un projet PEPS nance par le CNRS. Vos remarques toujours
justes et constructives m’ont convaincu de l’importance qu’un scientique digne de ce nom
doit accorder a la precision de ses propos et a la rigueur de son travail. Merci notamment
aux chimistes Claude Laurenco et Gilles Niel d’avoir partage avec enthousiasme un peu de
leurscience.Grˆaceavous,lesmauvaissouvenirsdescoursdechimiesontoublies.Jeremercie
tout particulierement Gilles Niel pour son hospitalite et pour avoir toujours repondu avec la
plus grande amabilite a mes demandes repetees de service. Je tiens egalement a remercier la
direction de Supelec, qui m’a temoigne sa conance en me donnant la chance et les moyens
de preparer cette these. Merci en particulier a Patrick Turelle et Joel Jacquet de m’avoir
menage du temps a n que ma these puisse se derouler dans de bonnes conditions et d’avoir
renouvele leur conance a monegard a des moments di ciles. Merci aux nombreux collegues
quim’onttemoigneleursoutien,notammentOlivierPietquin,HerveFrezza-BuetetStephane
Vialle dont les plaisanteries parfois narquoises a mon egard n’avaient pour seul objectif, je
n’endoutepas,depiquermonamourpropreetainsidemeremotiver.Etpuissurtoutjetiens
a dire inniment merci a Aurelie pour avoir supporte mes monologues de chercheur contrarie
aveclaplusgrandepatience,poursonindefectiblesoutienetsesencouragementssanslesquels
je n’aurais jamais ose remettre en question mes choix professionnels. J’espere que tu ne le
regrettespas!Merciaussiamesparentsquiontencourageetsoutenuleursenfantsafairedes
etudes et plus particulierement a ma mere pour toute l’attention qu’elle a portee depuis tou-
jours a ses enfants. Je mesure combien cette these est aussi le fruit de ton travail. Merci aussi
atoutelafamilled’Alsaceoud’AuvergneetatouslesamisdeFranceetd’outre-Rhinpourles
moments de reconfort et de convivialite fort apprecies qu’ils ont apportes. Merci par avance
a toutes celles et ceux qui m’excuseront de ne pas les avoir cites ici. Merci en