- Je tiens à remercier également les professeurs et les personnels de l’Institut de la Francophonie pour l’Informatique, des professeurs invités de m’avoir donné des cours de haut qualité et pour leur soutien tout au long de mes études.. - L’Analyse Formelle de Concepts (AFC) est souvent utilisée pour analyser les données décrivant la relation entre un ensemble d’objets et d’un ensemble d’attributs. - une extension de l’AFC et la recherche de concepts pertinents en utilisant les treillis de Galois. - Des expérimentations et de nombreuses évaluations ont été effectués pour valider la faisabilité de l’approche et illustrent la possibilité d’une application des méthodes d’apprentissage supervisé ou non-supervisé.. - 2 État de l’art 4 2.1 Analyse formelle de concepts. - 2.3 Arbre des suffixes généralisés. - 2.3.2 Construction de arbre des suffixes généralisés. - 2.3.3 Arbre des suffixes généralisés (GST. - 2.2 Arbre des suffixes de la chaîne xabxac [Gus97. - 2.3 Arbre des suffixes et arbre des suffixes implicites de la séquence xabxa . - 14 2.4 Arbre des suffixes généralisés de "xabxa". - 2.6 Les nombres de chemin d’un arbre binaire entier de 15 noeuds. - 3.4 Les bordures et les concepts pertinents avec min_sup = 30% et min_long=3 30 4.1 Un vecteur vitesse avec ses trois composants. - 2.4 Version séquentielle de la base de données. - L’abeille est une espèce bio-indicatrice (ou dite "sentinelle de l’environnement". - L’équipe du projet APIALERTE 1 du laboratoire L3i 2 s’est rendu dans les ruchers du domaine du Magneraud à plusieurs reprises pour capturer des vidéos de l’activité des d’abeilles devant la ruche. - Ainsi, une telle extraction est envisageable à partir de l’ensemble des trajectoires des abeilles pour en extraire les sous-séquences fréquentes, ou bien à partir d’une base d’apprentissage de trajectoires préalablement catégorisées (abeilles normales ou anormales par exemple), permettant ainsi d’identifier ou de caractériser les sous-trajectoires fréquentes ou non fréquentes par catégorie.. - Alors que les premiers travaux d’extraction de motifs fréquents visaient à calculer tous les sous-ensembles de motifs pour en extraire les plus pertinents [AS+94], de récentes méthodes issues de l’analyse formelle des concepts (AFC) reposent sur l’extraction de motifs fermés. - Malgré des traitements souvent exponentiels, les fondements mathématiques de l’AFC, qui reposent sur la théorie des treillis [Bir67] et des fermetures, garantissent des algorithmes efficaces et souvent optimaux. - L’AFC analyse les données décrit par la relation entre un ensemble d’objets et d’un ensemble d’attributs. - Alors que les objets sont classiquement décrits par des ensembles d’attributs, les propriétés d’un opérateur de fermeture permettent d’en étendre le cadre applicatif à des descriptions plus sophistiquées, telles que les graphes [GK01], les intervalles [Pol98], les formules logiques [FR04], les séquences, et plus généralement aux patterns [Kuz01]. - Plus formellement, ces extensions sont rendues possibles par la mise en place d’un opérateur de fermeture dans l’espace de description considéré. - L’objectif de ce stage est donc d’implémenter le calcul des sous-séquences communes maximales qui possède les propriétés d’un opérateur de fermeture. - Puis de l’intégrer au sein de la bibliothèque java-lattices par la mise en place d’un opérateur de fermeture sur les séquences, et d’un contexte séquentiel. - (2) Implémentation du calcul des sous-séquences communes, puis mise en place d’un contexte séquentiel, extension d’un contexte classique, avec les sous-séquences communes comme opérateur de fermeture. - La construction du treillis de Galois du contexte séquentiel est ainsi rendue possible en utilisant l’algorithme de Bordat [Bor86] ou l’algorithme Next Closure [Gan84] déjà implémentés au sein de la bibliothèque java-lattices.. - Dans le chapitre 2, nous présentons un état de l’art sur l’analyse formelle de concepts (AFC) et la recherche de sous-séquences communes maximales.. - Chapter 2 État de l’art. - Nous introduisons dans un premier temps les notions de l’Analyse Formelle de Concepts et les algorithmes proposés, puis nous évoquons les travaux existant pour la recherche de motifs séquentiels. - Ces données apparaissent couramment dans de nombreux domaines de l’activité humaine tels que la psychologie, la sociologie, l’anthropologie, la médecine, la biologie, linguistique, sciences informatiques, mathématiques et génie industriel. - Nous présentons dans cette section les notions de base de l’AFC et quelques algorithmes pour l’extraction de motifs séquentiels.. - Table 2.1 – La table binaire décrivant la relation I du contexte (O, S , I). - Pour définir le concept formel d’un contexte formel ( O, S, I ) nous avons besoins des opérateurs de dérivation définis pour les sous-ensembles arbitraires A ⊆ O et B ⊆ S. - Table 2.2 – Un exemple de concept formel Définition 2.1.4 (Trellis). - – la borne inférieure de x et y , notée x ∧ y , est l’unique élément maximal (plus grand élément) de l’ensemble des prédécesseurs (ou minorants) de x et y (ensemble des éléments z ∈ S tels que z ≤ x et z ≤ y).. - plus petit élément) de l’ensemble des successeurs (ou majorants) de x et y (ensemble des éléments z ∈ S tels que z ≥ x et z ≥ y. - Le treillis des concepts d’un contexte (O, S , I) est une paire (C. - Table 2.4 – Version séquentielle de la base de données. - Le support d’un motif X noté supp ( X ) est le nombre de transactions dont X est sous-ensemble.. - La définition d’un motif séquentiel maximal est similaire à celle des itemsets fréquents maximaux. - Les arêtes d’un noeud ont des étiquettes différentes.. - La principale caractéristique de l’arbre des suffixes est que pour toute feuille i, la concaténation des arête-étiquettes sur le chemin de la racine jusqu’à la feuille i définit exactement le suffixe de α qui commence à la position i. - Un exemple de l’arbre des suffixes pour la chaîne xabxac est représenté dans la figure 2.2.. - Figure 2.2 – Arbre des suffixes de la chaîne xabxac [Gus97]. - Un arbre des suffixes peut être construire en temps linéaire. - L’algorithme d’Ukkonen permet de construire un arbre des suffixes à temps linéaire.. - L’algorithme se base sur le concept de l’arbre des suffixes implicites.. - Définition 2.3.2 (Arbre des suffixes implicites. - Un arbre des suffixes implicites de chaîne α est un arbre obtenu à partir de l’arbre des suffixes α$ en supprimant tous les copies du terminal symbole $ à partir des étiquettes des arêtes de l’arbre, puis en enlevant les arêtes qui n’ont pas d’étiquette, puis enlever tous les noeuds qui n’ont pas au moins deux enfants.. - L’arbre des suffixes implicites encode tous les suffixes de la séquence α , mais les suffixes ne terminent pas forcément aux feuilles. - La Figure 2.3 représente l’arbre des suffixes et l’arbre des suffixes implicites de la séquence xabxa. - Nous désignons par I i l’arbre des suffixes implicites de α[0..i] pour i de 0 à n - 1.. - Sortie: T : arbre des suffixes. - Figure 2.3 – Arbre des suffixes et arbre des suffixes implicites de la séquence xabxa. - C’est un arbre des des suffixes pour un ensemble de chaîne A. - Pour construire l’arbre des suffixes généralisés T de A , d’abord, on ajoute à la fin de chaque chaîne α i une sentinelle $ i tel que i , j. - Figure 2.4 – Arbre des suffixes généralisés de "xabxa". - Algorithm 2 Algorithme pour construire l’arbre des suffixes généralisés : GST(A) Entrée: A un ensemble des séquences. - Sortie: L’arbre des suffixes généralisés T. - La recherche des sous-séquences communes maximales à un ensemble de séquence, LCS (longest common subsequence en anglais) est un problème dont la résolution repose sur l’arbre des suffixes généralisés. - La séquence S est une sous-séquence de la séquence α si S fait partie de α : S v α.. - La recherche des sous-séquences communes maximales peut être résolue à l’aide d’un arbre des suffixes généralisés avec une complexité en O( P |α i. - (1) Construire l’arbre des suffixes généralisés de l’ensemble des séquences A. - Les sous-séquences communes sont les chemins de la racine à ces nœuds internes. - La complexité de l’algorithme est de O(n) avec n = Σ | s i. - Le problème de LCS peut être résolu à l’aide d’un arbre des suffixes généralisés.. - Les sous-séquences communes sont les chemins de la racine aux ces nœuds internes. - La complexité de l’algorithme est de O ( n ) avec n = Σ |s i. - Soit T l’arbre des suffixes généralisés de l’ensemble des séquences A = {α 1 , α 2. - Dans un arbre enraciné T , un nœud u est un ancêtre d’un nœud v si u est sur le chemin unique de la racine à v. - Les valeurs de Γ i sont le nombre de dfs (nombre assigné par l’ordre d’un parcours en profondeur). - n (nombre de séquence) et le sous- séquence χ ( v ) de la racine à v est un sous-séquence commune de T . - 21: S ← la sous-séquence de la racine à v. - 2.4.3.1 Recherche de lca dans un arbre binaire entier 2.4.3.1.1 Prétraitement de l’arbre. - Si T est un arbre binaire entier, le chemin unique de la racine à un nœud est codé dans le nœud lui-même. - Pour chaque noeud v , son nombre de chemin path(v) est codé de la façon suivante:. - (1) En comptant à partir du bit de gauche (le bit de poids fort), le i-ième bit de path(v) correspond à la i-ième arête sur le chemin de la racine à v. - (1) Un des deux noeuds est ancêtre de l’autre: u est ancêtre de u ou v est ancêtre de u . - Figure 2.6 – Les nombres de chemin d’un arbre binaire entier de 15 noeuds Définition 2.4.6. - Algorithm 4 Transformation d’un arbre T en un arbre binaire entier B : preProcess(T) Entrée: T : un arbre arbitraire. - Cependant, les fondements mathématiques de l’AFC permettent étendre ces approches à d’autres types de description d’objets plus sophistiqués, tels que les graphes [GK01], les intervalles [Pol98], les formules logiques [FR04], les séquences, et plus généralement les patterns [Kuz01]. - Table 3.1 – Un exemple de contexte séquentiel. - Dans le contexte séquentiel de l’exemple 3.1. - cet algorithme génère récursivement à partir du concept minimal les successeurs immédiats d’un concept (cf algorithme 7) dans le diagramme de Hasse. - L’algorithme de Bordat s’étend facilement à un système de fermeture quel- conque, les successeurs immédiats d’un fermé sont alors générés récursivement à partir du fermé minimal ϕ. - Tout sous-concept d’un concept fréquent est un concept fréquent.. - Dans ce chapitre, nous présentons une application de l’extraction de sous-séquences pertinentes aux trajectoires d’abeilles. - L’objectif ici est seulement de valider la faisabilité de l’approche, et non de mener une étude poussée d’analyse du comportements des abeilles.. - La figure 4.1 représente un exemple de la vitesse en 3D. - Figure 4.1 – Un vecteur vitesse avec ses trois composants. - Où : v p i est la vitesse de l’abeille au point p i. - Figure 4.2 – Un exemple de trajectoires en 3D et un exemple de contexte séquentiel des vitesses. - La table 4.2 représente les 8 comportements de l’abeille.. - Table 4.3 – Un exemple de contexte séquentiel des directions. - Dans le cas de la discrétisation selon la direction, nous avons fixé la taille de fenêtre à 3. - Nombre de concepts. - Nous constatons aussi que la méthode de discrétisation par direction que nous utilisons ne donne pas beaucoup d’informations puisque le ratio γ est trop petit (moins de 0.01 quand le nombre de séquences est supérieur à 15).. - La méthode proposée s’appuie sur les fondements mathématiques de l’Analyse Formelle de Concepts qui permet d’étendre la connexion de Galois à des données non ensemblistes, et en particulier des séquences. - extension consiste à définir un opérateur de fermeture sur les séquences à partir de la relation d’ordre "sous-séquences". - Ces concepts sont composés des sous-séquences communes et maximales à un ensemble d’objets, éventuellement caractéristiques d’un comportement.