Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
Maatallaoui Ayoub
Master 2 Sciences du Langage
Université Stendhal – Grenoble 3
Projet de fin d'étude en Maitrise Informatique:
Mesure de Similarité des Séries Temporelles
Encadré par: M. Kerkeni Nizar
mail: ayoub.maat@gmail.com
________________________________________________________________________________
 Faculté des Sciences de Monastir 

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
Table des matières
Introduction générale............................................................................................................................1
Chapitre 1 : État de l'art.......................................................................................................................3
1.1.Introduction................................................................................................................................3
1.2. Signaux physiologiques............................................................................................................3
1.3. Étude du sommeil.....................................................................................................................3
1.4.Électroencéphalogramme (EEG)...............................................................................................6
1.4.1 Enregistrement de l’électroencéphalogramme .................................................................6
1.4.2 Composantes de l'électroencéphalogramme....................................................................7
1.5. Stades du sommeil ...................................................................................................................9
1.6. Complexes K...........................................................................................................................10
1.7. Analyse automatique du sommeil ..........................................................................................11
1.8. Conclusion .............................................................................................................................12
Chapitre 2 : Similarité des séries temporelles...................................................................................13
2.1. Introduction.............................................................................................................................13
2.2. Mesure de similarité entre séries temporelles.........................................................................13
2.2.1 Distance Euclidienne......................................................................................................14
2.2.2 Dynamic Time Warping (DTW)....................................................................................15
2.2.3 Longest Common Subsequence (LCSS)........................................................................16
2.3. Agrégation des séries temporelles...........................................................................................17
2.3.1 Agrégation euclidienne..................................................................................................18
2.3.2 Agrégation basée sur la distance DTW..........................................................................19
2.4. Algorithme des K moyennes...................................................................................................21
2.5. Conclusion..............................................................................................................................22
Chapitre 3 : Reconnaissance des complexes K.................................................................................23
3.1.Introduction..............................................................................................................................23
3.2.Matériel ...................................................................................................................................23
3.2.1 Sujets...............................................................................................................................23
3.2.2 Données .........................................................................................................................23
3.3.Méthodes .................................................................................................................................24
3.4.Mesure de similarité avec Longest Common Subsequence (LCSS).......................................24
3.4.1 Traitement des données...................................................................................................24
3.4.2 Aspect algorithmique......................................................................................................25
3.4.3 Contraintes......................................................................................................................26
3.4.4 Réalisation.......................................................................................................................26
3.5.Agrégation avec la distance LCSS ..........................................................................................30
3.5.1 Problématique.................................................................................................................30
3.5.2 Méthodologie..................................................................................................................30
3.6.Conclusion...............................................................................................................................32
Conclusion générale...........................................................................................................................33
Bibliographie......................................................................................................................................34
________________________________________________________________________________
 Faculté des Sciences de Monastir 

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
Liste des figure
Figure 1.1: Chaîne de mesure des signaux physiologiques [13]..........................................................5
Figure 1.2: Ondes cérébrales pour un sujet normal..............................................................................8
Figure 1.3: Principaux grapho-éléments de l’EEG...............................................................................9
Figure 1.4: Exemple d’un complexe K...............................................................................................10
Figure 2.1: Comparaison de deux séries temporelles à l’aide de la distance Euclidienne.................14
Figure 2.2: Comparaison de deux séries temporelles à l’aide de la distance Dynamic Time Warping.
............................................................................................................................................................15
Figure 2.3: Exemples d'application des distances: (a) Euclidienne, (b) DTW,(c) LCSS sur deux série
A s temporelles A et B........................................................................................................................17
Figure 2.4: Agrégation euclidienne des séries temporelles................................................................18
Figure 2.5: Matrice des distances locales LDM (à gauche) et globales GDM (à droite)...................19
Figure 2.6: Agrégation basée sur les arcs associatifs DTW................................................................20
Figure 3.1: Matrice des distances S....................................................................................................27
Figure 3.2: Matrice des sous-séquences R.........................................................................................29
Figure 3.3: Rétro-propagation de la matrice R...................................................................................29
________________________________________________________________________________
 Faculté des Sciences de Monastir 

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
Introduction générale
    L'étude clinique du sommeil humain consiste en l’acquisition et à l’enregistrement d’un ensemble 
de   signaux   physiologiques   au   cours   d’une   nuit   de   sommeil,   ce   processus   étant   appelé 
polysomnographie.   Les   signaux   physiologiques   enregistrés   sont   les   principaux   paramètres   du 
sommeil, en particulier l’électroencéphalogramme (EEG). De plus, et en fonction de la pathologie à 
étudier, il est nécessaire d’enregistrer d’autres paramètres végétatifs tels que le rythme cardiaque, 
l’activité respiratoire, les mouvements des jambes, etc... 
    L’électroencéphalogramme (EEG) est composé par des ondes de sommeil, caractérisées par leur 
fréquence, et un ensemble de grapho­éléments particuliers caractérisés par leur morphologie. Lors 
de l’analyse du sommeil par le clinicien, la détection de ces grapho­éléments constitue une étape 
importante qui lui permet de conforter sa prise de décision. 
    Notre objectif est de développer un module de reconnaissance automatique des grapho­éléments 
présents dans le signal EEG. Cette reconnaissance automatique pourra aider le clinicien à éliminer 
d'éventuelles ambiguïtés dans la reconnaissance d'un stade particulier du sommeil. Le module que 
nous   développerons   sera   intégré   par   la   suite   dans   une   plate­forme   logicielle   nommée   jEDF 
(http://www.ltim.org/membres/kerkeni/jEDF.php).
        Les   signaux   physiologiques   sont   une   source   d'informations   importante   pour   étudier   les 
mécanismes internes du comportement des êtres humains. L'analyse et l'étude de ces signaux sont 
un domaine qui intéresse des chercheurs de différentes disciplines telles que l'informatique et la 
médecine. C'est dans  ce  cadre  que se déroule notre projet qui vise à atteindre trois objectifs :
•
Comprendre   les   caractéristiques   des   signaux   physiologiques   et   en   particulier 
l'électroencéphalogramme (EEG).
•
Effectuer une étude bibliographique des différents algorithmes de mesure de similarité des 
séries temporelles.
•
Développer un module permettant de mesurer la similitude entre deux portions du signal 
________________________________________________________________________________
 Faculté des Sciences de Monastir 

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
EEG (séries temporelles). Ce module doit permettre à l'utilisateur de conclure, selon le 
résultat obtenu, si les deux portions du signal sont semblables ou non. Ce module doit aussi 
faire la visualisation et la sauvegarde des résultats de l'analyse.
    Le rapport présente les différentes étapes par lesquelles nous avons passé pour réaliser ce travail. 
Dans le premier chapitre nous commencerons par une présentation de l'état de l'art dans lequel nous 
introduirons les notions médicales utilisées dans ce projet. Nous allons ensuite, dans le chapitre 
suivant, présenter les résultats de notre étude bibliographique sur les différents algorithmes de 
mesure de similarité existants. Dans le troisième chapitre nous poursuivrons par la présentation des 
étapes   et   des   études   faites   pour   réaliser   ce   travail   et   implémenter   notre   module   logiciel.   En 
conclusion,   nous   récapitulerons   l'ensemble   des   travaux   et   ferons   brièvement   référence   aux 
perspectives possibles de notre projet.
________________________________________________________________________________
 Faculté des Sciences de Monastir 

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
 Chapitre 1  : État de l'art
1.1. Introduction
     Les séries temporelles sont des données ordonnées dans le temps et cet ordonnancement a une 
signification. Ainsi, on ne peut pas leur appliquer des méthodes de fouille de données classiques 
mais bien des méthodes spécialement adaptées surtout pour la mesure de similarités. Dans notre 
travail, ces séries temporelles sont des portions extraites de l'électroencéphalogramme (EEG).
    L’étude clinique de ce signal physiologique se base essentiellement sur la reconnaissance visuelle 
d’un ensemble d’informations particulières de deux types : les ondes, caractérisées par leur spectre 
fréquentiel, et les grapho­éléments caractérisés par leur morphologie temporelle.
    Dans ce chapitre, nous suivrons les étapes énumérées ci­dessous :
➢
Description du principal signal physiologique analysé lors de l’étude du sommeil qui est 
l’EEG.
➢
Définition des six états de vigilance appelés aussi stades du sommeil.
➢
Définition du grapho­élément sujet de notre travail : le complexe K.
➢
Description de l’analyse visuelle.
➢
Présentation de l'analyse automatique du sommeil.
1.2.  Signaux physiologiques
    Les êtres vivants sont le siège de phénomènes biologiques intimement liés aux activités vitales. 
Ces   phénomènes   biologiques   se   mesurent   à   travers   des   grandeurs   physico­électriques   ou   non 
électriques appelées signaux physiologiques. Ces signaux sont selon les cas, stables, lentement 
variables, transitoires ou plus ou moins périodiques. Ainsi, le métabolisme, c’est­à­dire l’activité 
chimique incessante qui caractérise l’état vivant dans chaque cellule modifie, dans chaque tissu, des 
grandeurs physico­chimiques. L’évolution de ces grandeurs reflète l’activité d’une population de 
________________________________________________________________________________
 Faculté des Sciences de Monastir 
1

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
cellules   ou   d’un   organe.   L’électrogenèse   biologique   peut   être   étudiée   grâce   à   la   mesure   des 
différences de potentiels générés par cette activité. L’enregistrement de leur variation au cours du 
temps   permet   de   localiser   des   foyers   d’électrogenèse   au   niveau   d’un   organe   et   d’étudier   leur 
organisation topographique. 
    L’apparition du traitement numérique des signaux physiologiques en médecine a permis un essor 
important   dans   l’approche   clinique   et   thérapeutique.   La   particularité   de   ces   signaux   réside 
essentiellement dans leur variabilité dans l’espace et dans le temps et d’un patient à un autre. De 
plus, pour chaque fonction ou organe, nous avons la possibilité de mesurer les différents types de 
signaux physiologiques. Deux paramètres principaux caractérisent à priori ces signaux, à savoir 
l’amplitude et la  fréquence. Néanmoins, d’autres informations qui décrivent mieux la  fonction 
explorée peuvent être extraites [1].
    Parmi ces signaux, les plus connus sont : l’électrocardiogramme (ECG) qui caractérise l’activité 
électrique   du   cœur,   l’électroencéphalogramme   (EEG)   qui   reflète   celle   du   cerveau   et 
l’électromyogramme (EMG) qui nous renseigne sur l’activité électrique musculaire en un point 
donné.
•
Principes du traitement des signaux physiologiques
    Le signal électrique issu du capteur (un dispositif capable de recueillir et de traduire l’information 
émise au sein de l’organisme) fait l'objet d'un traitement analogique (amplification, filtrage...) puis 
subit une conversion Analogique/Numérique (figure 1.1). Cette conversion consiste à échantillonner 
à fréquence fixe le signal pour en donner une valeur comprise entre un minimum et un maximum 
avec   un   nombre   fini   de   valeurs   possibles   (256   valeurs   si   on   utilise   une   conversion 
Analogique/Numérique sur 8 bits).
1.3.  Etude du sommeil
    D'après les règles de Rechtschaffen et Kales [2], une bonne introspection du sommeil requiert au 
minimum l'analyse de trois signaux physiologiques :  
➢
L'électroencéphalogramme (EEG) qui mesure l'activité électrique du cerveau à la surface du 
________________________________________________________________________________
 Faculté des Sciences de Monastir 
2

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
scalp. Nous détaillerons les caractéristiques de ce signal dans le prochain paragraphe.
➢
L'électro­oculogramme (EOG) qui représente l’enregistrement de l’activité oculaire. Cette 
activité est due à l’existence d’une différence de potentiel entre la cornée (positive) et la 
rétine (négative) [15]. L’activité oculaire au cours du sommeil est utile pour obtenir des 
informations supplémentaires sur le sommeil.
➢
 L'électromyogramme (EMG) qui reflète l’activité électrique des muscles. Pour l’étude du 
sommeil, il est recommandé d’enregistrer l’activité des muscles mentonniers. La présence 
ou l’absence de l’activité musculaire peut être, dans le cas d’une ambiguïté, un indicateur 
supplémentaire pour l’identification de quelques stades du sommeil.
Figure 1.1: Chaîne de mesure des signaux physiologiques[13].
    Il s'avère aujourd'hui que ces seuls paramètres ne suffisent pas à détecter certaines pathologies 
telles que les apnées du sommeil ou les parasomnies. Ainsi, il est courant, en routine clinique, de 
recueillir également d'autres variables physiologiques telles que : 
•
L'électrocardiogramme   (ECG)   qui   enregistre   l’activité   électrique   du   cœur.   Les 
innombrables cellules musculaires qui le constituent sont dotées de propriétés spéciales 
________________________________________________________________________________
 Faculté des Sciences de Monastir 
3

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
dont les deux plus importantes sont le pouvoir mécanique de contraction et l’activité 
électrique rythmique.
•
La pléthysmographie inductive thoracique et abdominale représentant les mouvements 
respiratoires.
•
L'enregistrement sonore des éventuels ronflements.
•
Le débit d'air nasal.
•
La saturation en oxygène dans le sang.
•
Une séquence vidéo pour repérer les mouvements anormaux du sujet (somnambulisme, 
crises d'épilepsie, etc...).
       L’examen clinique pour l’étude du sommeil contient une analyse visuelle des enregistrements 
polysomnographiques qui est souvent précédée par un questionnaire relatif aux habitudes de vie du 
patient et son appréciation sur la qualité de son sommeil de tous les jours. Après l’enregistrement 
polygraphique le patient aura à renseigner un deuxième questionnaire, portant sur le déroulement de 
sa nuit de sommeil. Ensuite, un clinicien neurophysiologiste effectue une analyse visuelle. Grâce a 
l’hypnogramme qui est le tracé résultant de l’analyse visuelle le clinicien peut avoir une vue globale 
sur le déroulement de la nuit du sommeil.
1.4. Électroencéphalogramme (EEG)
 1.4.1  Enregistrement de l’électroencéphalogramme
       L'électroencéphalographie  est   l'enregistrement   de   l'activité   électrique   du   cerveau   par   des 
électrodes placées sur le cuir chevelu. Le résultat de cet enregistrement est souvent représenté sous 
la forme d'un tracé appelé électroencéphalogramme. 
       L'électroencéphalographie  est un examen indolore et non­invasif qui renseigne sur l'activité 
électrique du cerveau au cours du temps et en particulier du cortex cérébral soit dans un but de 
diagnostique en neurologie, soit dans la recherche en neurosciences cognitives. Elle présente un 
intérêt, dans le diagnostique de l’épilepsie, des tumeurs cérébrales, des traumatismes crâniens et de 
________________________________________________________________________________
 Faculté des Sciences de Monastir 
4

---

Rapport PFE : Mesure de similarité des séries temporelles
________________________________________________________________________________
nombreuses maladies du système nerveux.
    On enregistre un électroencéphalogramme standard chez un patient éveillé, en position allongée, 
détendu ou en position assise. Sur un tracé EEG, il est possible d'identifier des activités électriques 
cérébrales rythmiques. Ces rythmes cérébraux sont classés selon leurs fréquences et permettent, par 
exemple, d'identifier ou de caractériser des états psychologiques en neurosciences fondamentales, 
ou pathologiques, en neurologies clinique.
 1.4.2  Composantes de l'électroencéphalogramme
     Le signal EEG contient un ensemble d’éléments caractérisés par leur fréquence, les ondes, et 
d'autres caractérisés par leur morphologie, les grapho­éléments. Les ondes qui composent le signal 
EEG sont (figure 1.2) :
•
Le rythme delta (fréquence entre 0,5 et 4Hz) n'est normal que si l'individu est plongé dans 
un   sommeil   profond.   Les   ondes   correspondantes   présentent   alors   des   amplitudes 
généralement plus élevées que pour toutes les autres ondes et sont plus marquées sur un 
EEG frontal  que central.
•
L'activité thêta (fréquence entre 4 et 8Hz) peut aussi bien être normale que anormale en 
fonction de l'âge et de la pathologie de la personne. En effet, elle est tout à fait naturelle s'il 
s'agit d'un adulte et que celui­ci est endormi. Par contre, si ce dernier est parfaitement 
éveillé, la présence d'ondes thêta peut être le signe d'un dysfonctionnement du cerveau. 
•
Le rythme alpha (fréquence entre 8 et 12Hz) est une activité normale d'un adulte éveillé, 
mais il est surtout présent lorsque l'individu se relaxe et garde les yeux fermés. Il apparaît 
simultanément des deux cotés de la tête généralement plus vers l'arrière qu'à l'avant, et est 
donc mieux visualisé sur un EEG occipital que sur un EEG central ou frontal. Il disparaît dès 
que le sujet ouvre les yeux ou dans le cas d'une activité mentale.
•
Le rythme sigma (fréquence entre 12 et 16Hz) est particulier puisqu'il correspond à un micro 
événement spécial du sommeil appelé fuseau. 
________________________________________________________________________________
 Faculté des Sciences de Monastir 
5

---

Document Outline

• ÿ
  • ÿ
  • ÿ
    • ÿ
  • ÿ
  • ÿ
• • ÿ
  • • ÿ
    • ÿ
  • • ÿ
  • ÿ
• ÿ
  • ÿ
    • ÿ
  • ÿ
    • ÿ
    • ÿ
  • • ÿ
  • ÿ
• ÿ

---