Tài liệu Extraction de sous-trajectoires d’abeilles luận văn ths. công nghệ thông tin

mémoire de fin d’études Extraction de sous-trajectoires d’abeilles Rédigé par : NGUYEN Van Tho Promotion 17 - IFI Encadrant : Karell BERTET La Rochelle, Avril – Octobre, 2014 Ce stage a été réalisé au Laboratoire Informatique, Image et Interaction L3i et a été financé par la région Poitou-Charentes. Remerciements Je tiens tout d’abord à remercier Madame Karell Bertet, responsable de mon stage pour le temps qu’elle m’a consacré durant ce stage, ses conseils précieux pendant 6 mois de mon stage. 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. Je tiens à remercier Monsieur Bruno Lescalier pour le fournissement de données. Mes remerciements vont aussi aux ma femme, ma famille et mes amis pour leur encouragement. i Résumé L’objectif de ce stage est de rechercher les sous-trajectoires maximales fréquentes d’abeilles. 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. Les fondements mathématiques derrières l’AFC, le treillis de Galois et le système de fermeture permettent d’en étendre le cadre applicatif à des descriptions plus sophistiquées, telles que les séquences. Dans ce stage nous présentons une méthode d’analyse formelle de concepts séquentiels ; une extension de l’AFC et la recherche de concepts pertinents en utilisant les treillis de Galois. Elle consiste d’abord à discrétiser les trajectoires d’abeilles en séquences. Et puis, calculer le treillis de Galois du contexte séquentiel (une extension du contexte formel) qui consiste à rechercher les sous-séquences communes maximales à l’ensemble de séquences. 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é. Mots-clés. treillis de Galois, analyse formelle de concepts, trajectoire,données séquentielles, fouille de données. Abstract The aim of this thesis is to mine the frequent closed sub-trajectories of bees. The Formal Concept Analysis (FCA) is often used to analyze the data describing the relationship between a set of objects and a set of attributes. The mathematical foundation behind the FCA, the Galois lattice and closure system allow to extend the application of FCA to more sophisticated data descriptions, such as sequence. In this work, we present a formal analysis of sequential concepts; an extension of the FCA and its application for mining relevant concepts. Firstly, we discretize the trajectories of bees to sequences. Then, we construct the Galois lattice of sequential context (an extension of the formal context) which consists of searching the maximum common sub-sequences of a set of sequences. Experiments were conducted to validate the feasible of the proposed approach, as well as illustrate the possibility of applying the supervised or unsupervised learning methods. Keywords. Galois lattices, formal concept analysis, trajectory, sequential data, data mining ii Table des matières Page 1 2 3 Introduction 1.1 Contexte . . . . . . . . . 1.2 Problématique . . . . . . 1.3 Principales contributions 1.4 Organisation du mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . État de l’art 2.1 Analyse formelle de concepts . . . . . . . . . . . . . 2.1.1 Contexte formel . . . . . . . . . . . . . . . 2.1.2 Structure de treillis . . . . . . . . . . . . . . 2.1.3 Calcul du treillis . . . . . . . . . . . . . . . 2.2 Recherche des motifs séquentiels . . . . . . . . . . . 2.2.1 Préliminaires . . . . . . . . . . . . . . . . . 2.2.2 Recherche des motifs séquentiels maximaux 2.2.3 Recherche des motifs séquentiels fermés . . 2.3 Arbre des suffixes généralisés . . . . . . . . . . . . . 2.3.1 Définitions . . . . . . . . . . . . . . . . . . 2.3.2 Construction de arbre des suffixes généralisés 2.3.3 Arbre des suffixes généralisés (GST) . . . . . 2.4 Recherche des sous-séquences communes maximales 2.4.1 Définitions . . . . . . . . . . . . . . . . . . 2.4.2 Calcul de U(v) pour chaque noeud interne v . 2.4.3 Algorithme pour calculer lca(x,y) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Analyse formelle de concepts séquentiels 3.1 Treillis de Galois des contextes séquentiels . . . . . . . . 3.1.1 Définitions . . . . . . . . . . . . . . . . . . . . 3.1.2 Treillis de Galois des séquences . . . . . . . . . 3.1.3 Calcul de treillis de Galois de contexte séquentiel 3.1.4 Recherche des concepts pertinents . . . . . . . . iii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 2 3 . . . . . . . . . . . . . . . . 4 4 4 5 8 8 9 10 10 11 11 12 14 15 15 16 17 . . . . . 24 24 24 26 27 29 4 5 Application aux trajectoires d’abeilles 4.1 Discrétisation des trajectoires d’abeilles 4.1.1 Discrétisation selon la vitesse . 4.1.2 Discrétisation selon la direction 4.2 Expérimentations . . . . . . . . . . . . . . . . 31 31 31 33 34 Conclusion et perspectives 5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 38 38 iv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Figures 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Le treillis des concepts du contexte formel 2.1 . . . . . . . . . . . . . . Arbre des suffixes de la chaîne xabxac [Gus97] . . . . . . . . . . . . . Arbre des suffixes et arbre des suffixes implicites de la séquence xabxa . Arbre des suffixes généralisés de "xabxa" et "babxba"[Gus97], le premier nombre indique la séquence, le deuxième nombre indique la position du commencement du suffixe . . . . . . . . . . . . . . . . . . . . . . . . Les feuilles en rectangle ayant identifieur i, les nœuds en cercle sont lcas des feuilles de Γi [Gus97] . . . . . . . . . . . . . . . . . . . . . . . . Les nombres de chemin d’un arbre binaire entier de 15 noeuds . . . . . Les partitions des noeuds . . . . . . . . . . . . . . . . . . . . . . . . . 7 11 14 Contexte séquentiel et treillis de Galois . . . . . . . . . . . . . . . . . Treillis de concepts du contexte de table 3.1 . . . . . . . . . . . . . . . Intégration de méthode proposée à la bibliothèque java-lattices : Le diagramme de paquetages avec principales classes . . . . . . . . . . . . Les bordures et les concepts pertinents avec min_sup = 30% et min_long=3 26 26 Un vecteur vitesse avec ses trois composants . . . . . . . . . . . . . . . Un exemple de trajectoires en 3D et un exemple de contexte séquentiel des vitesses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Angle entre deux vecteurs créés par trois points d’une fenêtre . . . . . . Nombre des concepts pertinents et nombre total de concepts avec une taille de fenêtre de 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ratio entre le nombre de concepts pertinents et le nombre total de concepts (pour des séquences de vitesse) . . . . . . . . . . . . . . . . . . . Ratio entre le nombre de concepts pertinents et le nombre total de concepts (pour des séquences de direction) . . . . . . . . . . . . . . . . . . Treillis des concepts des séquences de direction . . . . . . . . . . . . . 32 v 14 17 21 22 29 30 33 33 35 36 36 37 List of Tables 2.1 2.2 2.3 2.4 La table binaire décrivant la relation I du contexte (O, S , I) Un exemple de concept formel . . . . . . . . . . . . . . . Base de données transactionnelles des clients . . . . . . . Version séquentielle de la base de données . . . . . . . . . . . . . 5 6 9 9 3.1 Un exemple de contexte séquentiel . . . . . . . . . . . . . . . . . . . . 25 4.1 4.2 4.3 Correspondant entre les vitesses et les codes . . . . . . . . . . . . . . . Correspondance entre les directions et les codes . . . . . . . . . . . . . Un exemple de contexte séquentiel des directions . . . . . . . . . . . . 32 34 34 vi . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1 Introduction 1.1 Contexte L’abeille est une espèce bio-indicatrice (ou dite "sentinelle de l’environnement"). Depuis plusieurs années nous sommes forcés de constater que le cheptel mondial des abeilles est en déclin. 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. Les travaux réalisés dans le cadre de la thèse de Guillaume Chiron permettent de suivre individuellement en 3D chaque abeille en vol devant la ruche, et ainsi extraire les trajectoires des abeilles à partir d’une carte de profondeur. L’idée de ce stage est d’étudier la faisabilité des méthodes d’extraction de motifs séquentiels aux trajectoires des abeilles. Ces méthodes ont pour objectif d’extraire les sous-séquences fréquentes dans un contexte supervisé ou non. 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. 1.2 Problématique 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. L’AFC, outil de représentation et d’extraction des connaissances sous 1 2 http://l3i.univ-larochelle.fr/APIALERTE Laboratoire Informatique, Image et Interaction (L3i), Université de La Rochelle 1 forme de règles d’association ou de concepts, ainsi la possibilité de classification dans le cas supervisé et de segmentation dans le cas non supervisé. 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. La plupart de ces algorithmes sont implémentés dans la bibliothèque java-lattices [Ber14] développée au laboratoire L3i où ce stage est réalisé. 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é. Dans le cas des séquences, il est nécessaire de définir un opérateur de fermeture qui correspond au calcul des sous-séquences communes maximales à un ensemble de séquences. Les objets sont alors décrits par des séquences, formant ainsi un contexte séquentiel à partir duquel il est possible de générer le treillis de Galois de séquences. 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. Des expérimentations seront menées sur des trajectoires d’abeilles qu’il s’agira de discrétiser en séquences. 1.3 Principales contributions Le travail de ce stage présente les contributions suivantes : (1) Deux méthodes de discrétisation de discrétiser les trajectoires d’abeilles en séquences : discrétisation selon la vitesse et discrétisation selon la direction. (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. (3) Expérimentations sur 20 trajectoires d’abeilles et accompagnées de quelques mesures d’évaluation. Bien que l’apprentissage est non-traité dans le carde de ce projet, nos résultats montrent que l’apprentissage supervisé/non-supervisé sur les trajectoires sont faisables. 2 1.4 Organisation du mémoire Le mémoire est organisé de la manière suivante : 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. Dans le chapitre 3, nous décrivons la méthode proposée, le treillis de Galois du contexte séquentiel et la recherche des concepts pertinents Le chapitre 4 présente les expérimentations et ses résultats 3 Chapter 2 État de l’art Nous présentons dans ce chapitre un tour d’horizon des travaux auxquels nous avons eu recours pour développer ce travail. 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. Nous rappelons ensuite en détail les algorithmes pour la recherche des sous-séquences communes maximales à l’ensemble des séquences. 2.1 Analyse formelle de concepts L’Analyse Formelle de Concepts (AFC) [Wil82; GWW99] a été présentée comme un domaine de mathématiques appliquées qui consiste à restructurer la théorie des treillis [Bir67]. L’AFC analyse les données décrivant la relation entre un ensemble d’objets et un ensemble d’attributs. 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. 2.1.1 Contexte formel Définition 2.1.1 (Contexte formel). Un contexte formel est un triplet K = (O, S , I) où O est un ensemble d’objets, S est un ensemble d’attributs et I est une relation binaire entre O et S i.e I ∈ OxS . (o, s) ∈ I signifie que l’objet o possède l’attribut s. Graphiquement, nous pouvons représenter un contexte formel par une table binaire (cross-table) mettant en relation objets et attributs. Les lignes de la table correspondent aux objets, les colonnes de la table correspondent aux attributs. (i, j) prend la valeur 1, vrai ou encore × si l’objet i possède l’attribut j. 4 I 1 2 3 4 5 a × b c d × × × × × × × × × × × × Table 2.1 – La table binaire décrivant la relation I du contexte (O, S , I) Exemple 2.1.1. Le contexte C décrit par la figure 2.1 consiste l’ensemble des objets O = {1, 2, 3, 4, 5} et l’ensemble des attributs S = {a, b, c, d}. 2.1.2 Structure de treillis La notion de concept formel est fondamentale pour AFC. 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 : Définition 2.1.2. Pour un contexte formel (O, S , I) pour tout A ⊆ O et B ⊆ S , on défini: (1) A0 = α(A) = {o ∈ O | oI s ∀s ∈ A} (2) B0 = β(B) = {s ∈ S | oI s ∀o ∈ B} Ces deux opérateurs de dérivation satisfont trois conditions ci-dessous : (1) Z1 ⊆ Z2 ⇒ Z10 ⊇ Z20 (2) Z ⊆ Z 00 (3) Z 000 ⊆ Z 0 Définition 2.1.3 (Concept formel). Un concept formel dans un contexte formel (O, S , I) est une paire (A, B) avec A ⊆ O, B ⊆ S , α(A) = B et β(B) = A. Les ensembles A et B sont appelés respectivement extent et intent du concept formel (A, B). La relation de sous-concept, de super-concept est définie comme ci-dessous: (A1 , B1 ) ≤ (A2 , B2 ) ⇔ A1 ⊆ A2 (B1 ⊇ B2 ) Exemple 2.1.2. Dans le tableau 2.2, le rectangle surligné représente le concept formel {A1, B1} = ({y2, y3, y4}, {x2, x3}) 5 I 1 2 3 4 5 a × × × b × × × × c × × × × d × × Table 2.2 – Un exemple de concept formel Définition 2.1.4 (Trellis). Un treillis est une paire L = (S , ≤) où : • ≤ est une relation d’ordre sur l’ensemble S, i.e. une relation binaire qui vérifie les propriétés suivantes : – réflexivité : pour tout x ∈ S , on a xI x – antisymétrie : pour tous x, y ∈ S , xIy et yI x impliquent x = y – transitivité : pour tous x, y, z ∈ S , xIy et yIz impliquent xIz • toute paire d’éléments x, y de S admet à la fois une borne inférieure et une borne supérieure – 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). – la borne supérieure de x et y, notée x ∨ y, est l’unique élément minimal (i.e. 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). Définition 2.1.5 (Treillis des concepts). Le treillis des concepts se défini pour une relation binaire I entre un ensemble O d’objets et un ensemble S d’attributs, encore appelé contexte. Le treillis des concepts d’un contexte (O, S , I) est une paire (C, ≤) où : • C est un ensemble de concepts défini sur P(O) × P(S ) par : (A, B) ∈ C ⇐⇒ A ⊆ O, B ⊆ S , B = α(A) et A = β(B) avec α(A) = {b ∈ S : aIb pour tout a ∈ A} β(B) = {a ∈ O : aIb pour tout b ∈ B} • ≤ est une relation binaire définie sur l’ensemble des concepts C, pour (A1, B1) et (A2, B2) ∈ C: (A1, B1) ≤ (A2, B2) ⇐⇒ B1 ⊆ B2 ⇐⇒ A1 ⊇ A2 6 La figure 2.1 montre le diagramme de Hasse du treillis de Galois du contexte 2.1. Une éclipse représente un concept et les arcs entre les éclipses matérialisent la relation d’ordre du plus général (en bas) vers le plus spécifique (en haut). []{a,b,c,d} {3}{b,c,d} {4}{a,b,c} {1}{a,b,d} {2,3,4}{b,c} {1,3}{b,d} {4,5}{a,c} {1,4}{a,b} {2,3,4,5}{c} {1,2,3,4}{b} {1,4,5}{a} {1,2,3,4,5}[] Figure 2.1 – Le treillis des concepts du contexte formel 2.1 Définition 2.1.6 (Treillis de Galois). Un treillis de Galois se définit à partir d’une correspondance de Galois (α, β) entre deux ensembles O et S . Soient A ⊆ O et B ⊆ S , on définit α et β comme suit: α : P(O) → P(S ) α(A) = {s ∈ S /(o, s) ∈ I, ∀o ∈ A} (2.1) β : P(S ) → P(O) α(B) = {o ∈ O/(o, s) ∈ I, ∀s ∈ B} (2.2) • α est une application isotone de P(O) vers P(S ) : X ⊆ Y implique α(X) ⊆ α(Y), • β est une application antitone de P(S ) vers P(O) : X ⊆ Y implique β(X) ⊇ β(Y), • (β ◦ α) est une application extensive sur P(S ) : X ⊆ O implique X ⊆ (β ◦ α)(X), • (α ◦ β) est une application extensive sur P(O) : X ⊆ S implique X ⊆ (α ◦ β)(X). où : P(X) est l’ensemble des parties de X 7 Les deux compositions (α ◦ β) et (β ◦ α) sont des opérateurs de fermetures définis respectivement sur O et S . Définition 2.1.7 (Opérateur de fermeture). Un opérateur de fermeture sur l’ensemble X est un mapping C : P(X) → P(X) satisfont pour A, A1 , A2 ⊆ X : A ⊆ C(A) A1 ⊆ A2 ⇒ C(A1 ) ⊆ C(A2 ) C(A) = C(C(A)) Définition 2.1.8 (Système de fermeture). Un ensemble de fermés X avec son opérateur de fermeture se compose un système de fermeture. Par exemple (O, α ◦ β) est un système de fermeture. 2.1.3 Calcul du treillis Plusieurs algorithmes ont été proposés pour calculer du treillis de Galois (ou générer les fermés). Un des premiers algorithmes proposés est l’algorithme de Chein [Che69], les concepts sont générés à partir de concept initial en utilisant un algorithme de calcul les sous-matrices. Des algorithmes plus récents ont amélioré la performance en testant les concepts existant pour éviter de les régénérer [Nor78; Gan84; Bor86]. L’algorithme Next Closure [Gan84] génère les concepts selon l’ordre lectical entre eux. Les concepts peuvent être générés de manière incrémentale [Nor78; GMA91; CR93]. L’algorithme de Bordat [Bor86] génère les concepts en calculant le diagramme de Hasse du treillis. Conclusion: Toute description d’objets par une connexion (α, β) qui vérifie les propriétés d’une connexion de Galois permet ainsi de maintenir le système de fermeture sur l’ensemble des objets, et donc de rendre possible la génération du treillis de Galois. 2.2 Recherche des motifs séquentiels La recherche des motifs séquentiels est un problème fondamental et essentiel dans de nombreuses applications (découverte des règles d’association, règles de classification ou regrouper les objets selon les motifs) d’exploration de données qui sont ordonnées telles que la base de données transactionnelles, la base de données des trajectoires... Plusieurs méthodes ont été proposées pour la recherche des motifs séquentiels. Les premières méthodes se basent sur l’algorithme Apriori [Agr+96] qui énumère tous les motifs séquentiels fréquents (i.e. partagés par un nombre suffisant d’objets). Puis d’autres solutions ont été proposées pour limiter le nombre de motifs fréquents générés qui est exponentiel. Cette énumération est un problème exponentielle. Il y a deux solutions à la recherche des motifs séquentiels. La première solution est de recherche seulement les motifs séquentiels maximaux [AS95]. La deuxième solution est de recherche seulement 8 les motifs séquentiels fermés en introduisant un système de fermeture sur l’ensemble des séquences [YHA03; WH04]. 2.2.1 Préliminaires Soit I = i1 , i2 , . . . , in est un ensemble de n items distinctifs. La base de données transactionnelles est noté D dont chaque transaction (tid, T ) a un unique identifiant tid et contient un ensemble d’items encore appelé motif T . Exemple 2.2.1. La table 2.3 est un exemple de base de données transactionnelles (sa version séquentielle est présentée dans la table 2.4). Customer Id 1 1 2 2 2 3 4 4 4 5 Transaction Time June 25 ’93 June 30 ’93 June 10 ’93 June 15 ’93 June 20 ’93 June 25 ’93 June 25 ’93 June 30 ’93 July 25 ’93 June 12 ’93 Items Bought 30 90 10, 20 30 40, 60, 70 30, 50, 70 30 40, 70 90 90 Table 2.3 – Base de données transactionnelles des clients Customer Id 1 2 3 4 5 Customer Sequence <(30)(90)> <(10 20) (30) (40 60 70)> <(30 50 70)> <(30) (40 70) (90)> <(90)> Table 2.4 – Version séquentielle de la base de données Définition 2.2.1 (motif). Un motif ou itemset est un ensemble non vide d’items. Définition 2.2.2 (séquence). Une séquence est une une liste ordonnée, non vide, de motifs notée (it1 ) . . . (itn ) où (it j ) est un motif. 9 Définition 2.2.3 (support). Le support d’un motif X noté supp(X) est le nombre de transactions dont X est sous-ensemble. |{(tid, T ) ∈ D/X ⊆ T }| supp(X) = |D| Le support prend sa valeur dans l’intervalle [0, 1]. Définition 2.2.4 (motif fréquent). Un motif est dit fréquent si son support est supérieur à un seuil min_support. Définition 2.2.5 (motif maximal). Un motif fréquent est dit maximal s’il n’est pas sous-ensemble d’aucun d’autre motif fréquent. Définition 2.2.6 (ensemble fermé). Un ensemble est dit fermé s’il n’a pas de superensemble avec la même fréquence. 2.2.2 Recherche des motifs séquentiels maximaux La recherche des motifs séquentiels maximaux a été introduite dans les travaux de R. Agrawal et R. Srikant [AS95]. Les auteurs présentait trois algorithmes dont deux permettaient l’extraction de motifs séquentiels maximaux à partir une base de données des transactions des clients. La base de données transactionnelles est transformée en des séquences (voir exemple dans les tables 2.3 et 2.4). La définition d’un motif séquentiel maximal est similaire à celle des itemsets fréquents maximaux. Ainsi, si une séquence s est fréquente et qu’il n’existe pas de séquences fréquentes s0 telles que s0 @ s, alors le motif séquentiel s est dit maximal. 2.2.3 Recherche des motifs séquentiels fermés Clospan [YHA03] est une méthode basée sur le principe depth-first et implémente l’algorithme PrefixSpan. En fait, il s’agit d’une optimisation de ce dernier, destinée à élaguer l’espace de recherche en évitant de parcourir certaines branches dans le processus de divisions récursives (en détectant par avance les motifs séquentiels non fermés). Le principe de CloSpan repose sur deux éléments essentiels : l’ordre lexicographique des séquences et la détection de liens systématiques entre deux items (i.e."β apparaît toujours avant γ dans la base de données"). BIDE (BI-Directional Extension) est proposée dans [WH04] étendre les séquences dans les deux directions, i.e. en avant (forward extension) et en arrière (backward extension). Cette méthode est plus efficace que Clospan dans le cas de bases contenant de trop nombreuses séquences fermées. 10 2.3 2.3.1 Arbre des suffixes généralisés Définitions Un arbre des suffixes [Gus97] est une structure de données qui permet de représenter tous les suffixes d’une chaîne de caractère. Définition 2.3.1 (Arbre des suffixes). Un arbre des suffixes T d’une chaîne de m caractères α est un arbre enraciné orienté avec exactement m feuilles de 1 à m. Chaque nœud interne, autre que la racine, a au moins deux enfants et chaque arête est étiquetée avec une chaîne non vide de α. 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. On l’appelle su f fi Si un suffixe coïncide avec un facteur du texte, aucune feuille ne correspondra au suffixe. Pour éviter ce problème, on ajoute un caractère artificiel, par exemple $ à la fin du texte. 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] 11 2.3.2 Construction de arbre des suffixes généralisés Un arbre des suffixes peut être construire en temps linéaire. Le premier algorithme linéaire algorithme est proposé par Weiner [Wei73] en 1973. McCreight [McC76] propose un autre algorithme linéaire mais plus efficace pour la gestion de mémoire. En 1995, Ukkonen [Ukk95] a présenté un algorithme qui est aussi efficace que celui de McCreight mais plus simple. Nous allons donc représenter en détaille l’algorithme d’Ukkonen. 2.3.2.1 Algorithme d’Ukkonen L’algorithme d’Ukkonen permet de construire un arbre des suffixes à temps linéaire. Il traite les symboles de la chaîne un par un et de de gauche à droite (incrémental). 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. Un arbre des suffixes implicites pour un préfixe α[0..i] de α est définie de façon similaire en prenant l’arbre des suffixes de α[0..i]$ et suppression les symboles $, des arêtes et des nœuds comme ci-dessus [Gus97]. L’arbre des suffixes implicites encode tous les suffixes de la séquence α, mais les suffixes ne terminent pas forcément aux feuilles. Nous n’utilisons arbre des suffixes implicites que pour les résultats intermédiaires pendant la construction de arbre des suffixes. La Figure 2.3 représente l’arbre des suffixes et l’arbre des suffixes implicites de la séquence xabxa. Nous constatons que les suffixes a et xa ne terminent par aux feuilles dans l’arbre des suffixes implicites. Définition 2.3.3. Nous désignons par Ii l’arbre des suffixes implicites de α[0..i] pour i de 0 à n - 1. L’algorithme de Ukkonen [Ukk95] construit un arbre des suffixes implicites Ii pour chaque préfixe α[0..i] de α. Ces arbres de suffixes sont construits de façon incrémentale de I0 jusqu’à In−1 . On associe à chaque nœud interne le mot corresponds à l’étiquette depuis la racine jusqu’à ce nœud. Ainsi la racine est associée à . On associe l’indice j à la feuille au bout du chemin étiqueté par y[j.. n ] depuis la racine. Nous présentons d’abord un premier algorithme en O(n3 ) et présenterons des optimisations pour avoir un algorithme en O(n). Algorithme en O(n3 ) L’algorithme d’Ukkonen est divisé en n phases: • À phase i + 1, l’arbre T i+1 est construit à partir de T i . 12 • Chaque phase i + 1 est ensuite divisée en i + 1 extensions • A l’extension j, insère y[j..i+1] dans l’arbre en – recherchant la fin du chemin étiqueté par y[j..i] depuis la racine de T i – rajoutant y[i+1] si nécessaire Algorithm 1 Algorithme d’Ukkonen en bref: Ukkonen(α) Entrée: α : chaîne entrée Sortie: T : arbre des suffixes 1: construire T 0 2: for i ← 0, n − 1 do //phase i+1 3: for j ← 0, i + 1 do //extension j 4: Trouver la fin du chemin étiqueté par y[j..i] depuis la racine 5: Ajouter y[i+1] si nécessaire 6: end for 7: end for Durant l’extension j de la phase i+1, l’algorithme trouve la fin du chemin étiqueté par y[j..i] depuis la racine pour, éventuellement, ajouter y[i+1]. Cet ajout se fait alors en accord avec 3 règles. • Règle 1 Si le chemin étiqueté par y[ j..i] depuis la racine se termine sur une feuille, alors y[i+1] est ajouté à la fin de étiquette de la branche menant à la cette feuille. • Règle 2 Si le chemin étiqueté par y[ j..i] depuis la racine ne se termine pas sur une feuille et qu’aucun chemin étiqueté par y[i+1] ne commence après ce chemin. Alors une nouvelle feuille est créée avec une branche y menant étiqueté e par y[ i+1]. Si le chemin étiqueté par y[ j..i] depuis la racine ne se termine pas sur un nœud alors un nouveau noeud doit être créé et la branche cassée. • Règle 3 Si le chemin étiqueté par y[ j..i] depuis la racine ne se termine pas sur une feuille. Alors un chemin étiqueté par y[i+1] commence après ce chemin. Donc y[j..i+1] est déjà dans l’arbre : on ne fait rien. Algorithme en O(n) En utilisant les corollaires du lemme 2.3.1 et quelques astuces nous pouvons construire un arbre des suffixes en O(n). Consultez-vous le livre de Gusfield pour plus de détails et la preuve de ce lemme. Lemme 2.3.1. Si un nouveau nœud interne av est ajouté à l’arbre pendant l’extension j de la phase i+1 alors soit il y a d déjà un nœud interne v dans arbre, soit un nœud interne v va être créé dans l’extension j+1 de la phase i+1. Cet algorithme est basé sur le principe d’accélération avec lien suffixe et la notion d’arbre de suffixes implicites Figure 2.3 13