Formal Concept Analysis and Pattern Structures for mining Structured Data

Aleksey Buzmakov 1
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
Résumé : Aujourd’hui de plus en plus de données de différents types sont accessibles. Ces données variées contiennent des informations précieuses qui peuvent aider à résoudre des problèmes pratiques ou servir à la science fondamentale. Mais comment peut-on extraire cette information précieuse ? L’Analyse Formelle de Concepts (AFC) et les pattern structures sont des systèmes formels qui permettent de traiter les données ayant une structure complexe. Mais comment peut-on les appliquer en pratique ? De plus, le nombre de concepts, i.e., de pièces élémentaires d’information, trouvé par l’AFC est fréquemment très grand. Pour faire face à ce problème, on peut simplifier la représentation des données, soit par projection de pattern structures, soit par introduction de contraintes pour sélectionner les concepts les plus pertinents. Quelle est la meilleure simplification de données ? Comment peut-on efficacement trouver les concepts satisfaisant une contrainte donnée ? Ce sont les questions que nous abordons dans cette thèse. Le manuscrit commence avec l’application de l’AFC à l’exploration de structures moléculaires et la recherche de structures particulières. Ces structures moléculaires sont codées comme des ensembles d’attributs. Même pour ce codage simple et sans contraintes supplémentaires, l’AFC est capable d’extraire des informations importantes dans de petits ensembles de données. Avec l’augmentation de la taille des ensembles de données, de bonnes contraintes deviennent essentielles. Pour cela on explore la stabilité d’un concept. La stabilité est une contrainte formelle bien-fondée. On montre expérimentalement que c’est un bon choix et on l’applique à l’exploration d’un ensemble de données de substances chimiques mutagènes. La recherche de concepts stables dans cet ensemble de données nous a permis de trouver de nouveaux candidats mutagènes potentiels qui peuvent être interprétés par les chimistes. Cependant, pour les cas plus complexes, la représentation simple par des attributs binaires ne suffit pas. En conséquence, on se tourne vers des pattern structures qui peuvent traiter différents types de données complexes. Le point important sur les pattern structures est qu’elles permettent la simplification des données au moyen de projections. On étend le formalisme original des projections pour avoir plus de liberté dans la manipulation de données. On montre que cette extension est essentielle pour analyser les trajectoires de patients décrivant l’historique de l’hospitalisation des patients. En effet, les trajectoires de patients sont des séquences d’hospitalisations et chaque hospitalisation est décrite par une description hétérogène. Ces données sont très riches et donc produisent un grand nombre de concepts. Le nouveau type de projection permet une réduction efficace de la notion d’espace et en combinaison avec des contraintes de stabilité on peut trouver des trajectoires communes importantes. En outre, les projections sont utiles pour corriger et compléter les données liées (linked open data) où les erreurs sont inévitables. On peut efficacement trouver certaines erreurs avec une approche à base de pattern structures. Une autre application des pattern structures est la recherche des interactions médicamenteuses dans un corpus de textes. On est capable d’extraire et d’expliquer les structures syntaxiques codant ce genre des relations. Les approches présentées jusque là ne permettent pas la découverte directe de motifs sous la contrainte de stabilité. En conséquence, le manuscrit se termine par une approche originale et très efficace qui permet de trouver directement des motifs stables. Cette approche est appelée Σοφια et est capable de trouver les meilleurs modèles stables en temps polynomial. L’efficacité est essentielle pour l’analyse de grands ensembles de données et cela souligne l’importance de Σοφια. On évalue ce nouvel algorithme sur plusieurs ensembles de données et les expériences montrent l’amélioration significative de Σοφια par rapport à ses concurrents pour les données binaires et des n-uplets d’intervalles. En outre, il ouvre une nouvelle direction de recherche pour l’exploitation de différents types de motifs en temps polynomial ce qui est très important dans le monde des mégadonnées.
Type de document :
Thèse
Artificial Intelligence [cs.AI]. Universite de Lorraine, 2015. English. 〈NNT : 2015LORR0112〉
Liste complète des métadonnées

Littérature citée [251 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01751818
Contributeur : Aleksey Buzmakov <>
Soumis le : lundi 23 novembre 2015 - 15:02:29
Dernière modification le : jeudi 17 mai 2018 - 01:27:02
Document(s) archivé(s) le : vendredi 28 avril 2017 - 21:30:00

Identifiants

  • HAL Id : tel-01751818, version 2

Citation

Aleksey Buzmakov. Formal Concept Analysis and Pattern Structures for mining Structured Data. Artificial Intelligence [cs.AI]. Universite de Lorraine, 2015. English. 〈NNT : 2015LORR0112〉. 〈tel-01751818v2〉

Partager

Métriques

Consultations de la notice

896

Téléchargements de fichiers

1344