Soutenance mémoire
Contexte applicatif
Le langage est un moyen de communication complexe dont l’origine remonte à plus de deux millions d’années. Au cours du temps, il n’a cessé d’évoluer et de s’affiner, entraînant ainsi la création des milliers de dialectes existant de nos jours. Dans le cadre de dialogues face à face, divers éléments communicatifs – tels que les expressions faciales, les gestes ou le ton – viennent enrichir le discours afin d’en faciliter la compréhension. En effet, différentes études [91, 40] ont montré que plus de la moitié des informations transmises dans une interaction interpersonnelle sont exprimées au travers de comportements non verbaux.
Ces différents aspects entraînent une grande difficulté à modéliser et comprendre les schémas dialogiques naturellement mis en œuvre par des interlocuteurs dans des situations données (e.g. : débat politique, dialogue entre un vendeur et un client, etc). Il existe, néanmoins, divers domaines applicatifs dans lesquels l’identification de tels schémas permettrait des progrès significatifs. Par exemple, l’étude de dialogues en contexte d’apprentissage serait susceptible de fournir des schémas récurrents efficaces permettant de guider la structuration des interactions entre un enseignant et ses élèves. Dans un cadre similaire, D’mello et al. [32] ont étudié des sessions de tutorat individuel qui leur ont, notamment, permis de constater que l’augmentation du nombre d’actions de nature collaborative entre le tuteur et l’étudiant permettait d’influencer positivement l’apprentissage. Un second exemple d’application qui pourrait bénéficier de l’identification de schémas dialogiques est la conception d’ACA (Agents Conversationnels Animés). Nous sommes de plus en plus amenés à communiquer avec des agents (e.g. : sites internet, jeux vidéos). Cependant, il est rare que ces interactions soient riches et naturelles pour l’humain [121]. Bien souvent, les réactions de l’agent – tant du point de vue verbal que non verbal – sont très limitées. La découverte de schémas dialogiques usuels pour les utilisateurs et efficaces pour un agent conversationnel donné est une piste sérieuse pour l’amélioration de ses capacités interactives.
Formalisation du problème d’extraction de régularités
Dans le cadre de nos travaux, nous choisissons de représenter un dialogue annoté par un tableau d’annotations dont chaque colonne correspond à une dimension du schéma de codage considéré. Plus précisément, étant donné un dialogue d comportant l énoncés et encodé selon un schéma de codage comportant c dimensions, nous considérons un tableau d’annotations t de taille l × c (représenté t[1..l][1..c]) tel que pour tout i, j ∈ {1, . . . , l} × {1, . . . , c}, t[i][j] corresponde à la jème annotation du ième énoncé de d. A chaque colonne d’un tableau d’annotations est associé un alphabet Ω (i.e. : un ensemble de caractères) contenant l’ensemble des annotations susceptibles d’apparaître dans la dimension correspondante du schéma de codage. Par exemple, l’alphabet associé à la première colonne du schéma de codage utilisé en table 1 est {E, A, D}.
En vue d’obtenir les régularités contenues dans un corpus de tableaux d’annotations, nous cherchons à identifier des sous-parties de tableaux d’annotations apparaissant plusieurs fois, de manière exacte ou approchée. Pour ce faire, nous souhaitons identifier des motifs fréquents. Un motif est défini comme un tableau d’annotations pouvant contenir une ou plusieurs fois le caractère ‘*’, appelé joker ou caractère don’t care. Un joker peut être remplacé par n’importe quel autre caractère et permet simplement l’obtention de motifs dont la forme n’est pas nécessairement rectangulaire. Par exemple, le motif m1 en figure 1a ne comporte que trois caractères, mais il est représenté par un tableau d’annotations de taille 3 × 2 grâce à l’ajout de trois jokers.
Un motif m apparaît exactement dans un tableau d’annotations t s’il est possible de remplaçer les caractères joker de m de telle sorte que m soit une sous-partie de t. Par exemple, le motif m1 en figure 1a apparaît exactement dans le tableau en figure 1c (il suffit de remplacer les trois jokers de m1 par B2, C2 et B4). Un motif apparaît de manière approchée dans un tableau t s’il est similaire à un motif apparaissant exactement dans t (la notion de similarité entre deux motifs est précisée par la suite). Le motif m2 est similaire au motif en figure 1d (la différence se résume à l’insertion d’une ligne) qui apparaît de manière exacte dans t, m2 apparaît donc de manière approchée dans t.
Extraction de motifs dans des tableaux d’annotations
Fouille de motifs fréquents
L’objectif de l’exploration de motifs est de détecter les structures les plus fréquentes apparaissant dans une base de données. Dans cette section nous n’avons pas pour objectif d’effectuer une présentation exhaustive des travaux de ce domaine, mais nous nous concentrons sur les techniques susceptibles d’être utilisées pour extraire des motifs récurrents dans des tableaux d’annotations et permettant la prise en compte des variabilités (Vcar) et (Vag) mentionnées en début de ce chapitre. Ainsi, certains aspects comportant peu de liens avec notre problématique – tels que les règles d’association [3], les motifs fermés [57], maximaux [126], multi-niveaux [57] ou multi-dimensionnels [105] – ne seront pas ici abordés.
Fouille d’itemsets fréquents
La première évocation de cette problématique a été présentée par Agrawal et al. en 1993 [3]. Leur l’objectif était d’analyser les habitudes d’achat de clients via leurs paniers de consommation (market basket). Ceci explique que plusieurs des termes relatifs à cette problématique soient employés dans la fouille de motifs fréquents (e.g. : item, transaction, client).
Soit I = {i1, . . . , in} un ensemble d’items. Une transaction est définie comme une collection non vide d’items de I à laquelle est associée un identifiant unique. Une transaction contenant deux items a et b est notée (ab) et une transaction ne contenant qu’un unique item c est simplement notée c afin d’alléger les notations. Considérons le cas du panier de consommation afin d’illustrer ces notations. Dans ce contexte les items sont des articles de magasins (e.g. : du lait, de la confiture), une transaction t correspond à un ensemble d’articles achetés en une fois par un client et l’identifiant associé à la transaction t permet, entre autres, de retrouver le client ainsi que la date à laquelle a eu lieu la transaction. Un itemset est un sous-ensemble d’items de I. L’itemset I1 est dit inclus dans une transaction T si I1 ⊆ T (i.e. : si tous les items de I1 figurent dans la transaction T). Étant donnée une base de données de transactions D = {T1, . . . , T|D|}, le support de l’itemset I1 est défini comme la proportion de transactions de D incluant I1. Par exemple, le support des itemsets {a} et {b, d} dans la base de données D = {(abc)(ad)(bd)c} sont respectivement 50% et 25%. Un itemset est dit fréquent si son support est supérieur ou égal à un support minimum fixé et noté min_support. Enfin, un itemset contenant k items est appelé un k-itemset.
Algorithme Apriori
Les algorithmes de type Apriori sont basés sur la propriété de la fermeture par le bas (downward closure) qui indique que tout itemset inclus dans un itemset fréquent est nécessairement fréquent. Par exemple, si le 4-itemset {a, b, c, d} est fréquent, les 3- itemsets qu’il contient (i.e. : {a, b, c}, {a, b, d}, {a, c, d} et {b, c, d}) le sont nécessairement eux aussi. Le premier algorithme de ce type a été proposé par Agrawal et al. [3] en 1993.
Dans ces algorithmes, les items fréquents – qui correspondent aux 1-itemsets fréquents – sont tout d’abord identifiés. Ensuite, pour tout entier k à partir de un et tant qu’il existe des k-itemsets fréquents, les deux étapes suivantes sont réalisées:
1. génération de (k + 1)-itemsets candidats (i.e. : les (k + 1)-itemsets susceptibles d’être fréquents) ;
2. élagage (i.e. : suppression) des candidats qui ne sont pas fréquents par calcul de leur support.
Les diverses méthodes Apriori diffèrent par la façon dont ces deux étapes sont réalisées. Leur principal défaut est qu’elles nécessitent de nombreuses lectures de la base de données (lors de la génération et de l’élagage des candidats) qui peuvent s’avérer très coûteuses en temps d’exécution.
|
Table des matières
Introduction
I Extraction de motifs dans des tableaux d’annotations
1 État de l’art des méthodes d’extraction de régularités
1.1 Fouille de motifs fréquents
1.1.1 Fouille d’itemsets fréquents
1.1.2 Fouille de séquences d’itemsets fréquentes
1.1.3 Extraction de sous-structures fréquentes
1.2 Fouille de séquences de caractères
1.2.1 Algorithme de Needleman-Wunsch
1.2.2 Alignement local de séquences de caractères
1.2.3 Alignement local de tableaux de caractères
1.3 Discussion
2 Modélisation et résolution du problème d’extraction de motifs
2.1 Algorithme LP CA − DC
2.1.1 Description de l’algorithme
2.1.2 Discussion
2.2 Approche par extraction d’arborescences
2.2.1 Définitions et notations
2.2.2 Calcul du score d’un alignement
2.2.3 Modélisation du problème d’extraction d’alignements
2.2.4 Algorithme SABRE
2.3 Conclusion
II Classification non supervisée de motifs
3 État de l’art des méthodes de classification non supervisée
3.1 Heuristiques
3.1.1 Méthodes hiérarchiques
3.1.2 Méthodes de type partition
3.2 Approches exactes
3.2.1 Partitionnement non contraint
3.2.2 Poids des parties contraint
3.2.3 Nombre de sommets par partie fixé
3.2.4 Nombre de parties contraint
3.3 Discussion
4 Approche polyèdrale pour le problème de K-partitionnement
4.1 Définitions et notations
4.2 Formulations
4.2.1 Formulation (F1)
4.2.2 Formulation (F2)
4.2.3 Comparaison des formulations
4.3 Dimension et facettes
4.3.1 Dimension de Pn,K
4.3.2 Facettes
4.4 Conclusion
5 Étude numérique
5.1 Évaluation de la qualité des inégalités définissant des facettes non triviales de Pn,K
5.1.1 Algorithmes de séparations
5.1.2 Amélioration de la relaxation par famille d’inégalités
5.2 Résolution numérique par un algorithme de plans coupants
5.2.1 Description générale de l’algorithme
5.2.2 Obtention d’une solution entière à partir d’une solution fractionnaire
5.2.3 Algorithmes de séparation
5.2.4 Gestion des algorithmes de séparation et des coupes ajoutées
5.2.5 Résultats numériques
5.3 Conclusion
III Mise en œuvre et conclusions
6 Expérimentations
6.1 Présentation des données
6.2 Logiciel VIESA
6.3 Évaluation de LPCA-DC et des heuristiques de partitionnement
6.3.1 Calcul de la dissimilarité inter-motifs avec LPCA-DC
6.3.2 Protocole d’expérimentation
6.3.3 Résultats et discussion
6.4 Evaluation de SABRE et l’algorithme de plans coupants
6.4.1 Calcul de la dissimilarité inter-motifs avec SABRE
6.4.2 Protocole d’expérimentation
6.4.3 Résultats
6.5 Discussion
Conclusion
