m´emoire de fin d’´etudes

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



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

.
.
.
.

.
.
.
.

.

.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

4
4
4
5
8
8
9
10
10
11
11
12
14
15
15
16
17


31
31
33
34

Conclusion et perspectives
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38
38
38

iv

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


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 . . . . . . . . . . . . .



.
.
.
.

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

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

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
×
×
× ×
× × ×
× × ×

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
×
×
×
×




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}[]


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

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


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 s telles que s
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

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

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


bxa$

xa

1

$a
xb

1

2

Figure 2.3 – Arbre des suffixes et arbre des suffixes implicites de la séquence xabxa

2.3.3

Arbre des suffixes généralisés (GST)

C’est un arbre des des suffixes pour un ensemble de chaîne A = {α1 , α2 , ..., αn }. 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 ⇐⇒ $i $ j . Puis, l’arbre des suffixes généralisé
peut être construit sur la concaténation de ces chaînes.

Figure 2.4 – 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

14


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
1: S ← une séquence vide
2: for all α ∈ A do
3:
S ← S + α + une sentinelle unique $
4: end for

(2) Rechercher les sous-séquences communes maximales en identifiant les nœuds
internes qui contient au moins une feuille de chaque chaîne. 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 = Σ|si |.
15


Le problème de LCS peut être résolu à l’aide d’un arbre des suffixes généralisés.
Lorsque l’arbre des suffixes généralisés est construit, on peut trouver les sous-séquences
communes en identifiant les nœuds internes qui contient au moins une feuille de chaque
chaîne. 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 = Σ|si |.
Soit T l’arbre des suffixes généralisés de l’ensemble des séquences A = {α1 , α2 , ..., αn }
(n ≥ 2). Pour chaque feuille de T , assigner un identifieur L( f ) = i pour indiquer que la
séquence associé à feuille est suffixe de la séquence αi . Par exemple, L( f ) = 1, le suffixe
terminé par f est commencé par la séquence 1. Pour un noeud arbitraire v de T , nous
définissons:
(1) C(v) est le nombre des identifieurs distinctifs des feuilles du sous-arbre issu de v.
(2) S (v) est le nombre des feuilles du sous-arbre issu de v.
(3) U(v) est le nombre des suffixes commencés par la même séquence.
(4) ni (v) est le nombre des feuilles ayant identifieur i dans le sous-arbre issu de v.
Les sous-séquence communede A correspondent aux noeuds v tel que C(v) = n.
Le lemme 2.4.1 permet d’exprimer C(v) en fonction de S (v) et U(v). S (v) se calcule
simplement en parcourant les feuilles du sous-arbre issu de v. La difficulté consiste donc
à calculer U(v).
Lemme 2.4.1. U(v) =

2.4.2

(ni (v) − 1) et C(v) = S(v) - U(v) [Gus97]


h(w) : w est dans le sous − arbre issu de v.

(2.3)

i:ni (v)>0

L’algorithme 3 décrit le calcul du LCS(A) en utilisant U(v). Pendant le parcours
ascendant, calculer C(v) = S (v) − U(v). Si C(v) = n (nombre de séquence) et le sousséquence χ(v) de la racine à v est un sous-séquence commune de T . Pour garantir que X
est l’ensemble des sous-séquences communes maximales, nous devons tester si χ(v) et
supprimer tous les χi ∈ X: χi χ(v).
Cet algorithme utilise le calcul du lca décrit dans la section suivante.

2.4.3

Algorithme pour calculer lca(x,y)

Baruch Schieber et Uzi Vishkin [SV88] ont proposé un algorithme pour trouver le plus
proche ancêtre communde deux noeuds u et v (lca(u,v)) en temps constant, après une
étape de prétraitement en temps linéaire. L’algorithme se base sur deux observations
[HT84]:
17


Algorithm 3 Algorithme pour trouver les sous-séquences communes maximales:
getLCA(A)
Entrée: A : un ensemble des séquences
Sortie: lcs : une liste des sous-séquences communes maximales
1: lcs ← ∅
2: GTS(A) 2

24:
25:
26:

i:ni (v)>0

C(v) ← S (v) − U(v)
if C(v) = |A|) then
S ← la sous-séquence de la racine à v
if S d’aucune séquence dans lcs then
lcs ← lcs S
end if
end if
end for

(1) Si l’arbre a des chemins simples (il n’y a pas de noeud qui apparait plus d’une
fois dans un chemin), il est possible de le prétraiter et puis de répondre à chaque
requête lca(u,v) en temps constant.
(2) Si l’arbre est un arbre binaire entier, il est possible de le prétraiter et puis de
répondre à chaque requête lca(u,v) en temps constant.

18