Smaller Default Larger

Soutenance de thèse de Doctorat  LMD en Informatique :   BOULNEMOUR Imene

Soutenances

Mme. BOULNEMOUR Imene soutiendra une thèse de Doctorat en LMD en informatique intitulée :"Caractérisation des séries temporelles pour la recherche et la classification ".

Membres du jury:
                       Président:             Redjimi Mohamed                         Prof        Université 20 août 1955-Skikda
                       Rapporteur:           Boucheham Bachir                       Prof        Université 20 août 1955-Skikda

                       Examinateur:         Dr Brahimi Said                           Prof        Université 08 Mai 1945 de Guelma
                       Examinateur:        Dr Mazouzi Smaine                Prof         Université 20 août 1955-Skikda
                    

                                 


 

 

 Résumé Français

L‟objet de cette thèse concerne principalement : (a) La problématique de caractérisation des séries temporelles (ST) et (b) L‟investigation du domaine obligatoirement lié à cette problématique : Les mesures de distances et les mesures de similarité entre ST, ainsi que les techniques d‟appariement (ou alignement) des ST. Ces dernières techniques sont beaucoup plus robustes que les mesures de distance/similarité, mais, elles sont peu nombreuses et difficiles à inventer. La caractérisation des ST a pour but de décrire de façon compacte, mais pertinentes ce type de données (les ST). Compacte au sens de la réduction autant que possible de la redondance des données dans les ST, en n‟extrayant que les caractéristiques effectivement discriminantes. Cela nécessite le plus souvent de faire muter les ST du domaine temporel à un domaine beaucoup plus expressif en termes de pouvoir de discrimination. Dans ce contexte, nous allons établir un état de l‟art et une catégorisation des techniques de caractérisation des ST. Grossièrement parlant, nous pouvons déjà avancer que ces techniques peuvent être classées en quatre domaines: (1) Le domaine temporel tels que les histogrammes, les motifs et l‟approche PLA (Piecewise Linear Approximation), (2) Le domaine fréquentiel, tel que la Transformée de Fourier Discrète (DFT), (3) Le domaine temps-fréquences, tel que la Transformée des Ondelettes Discrètes (DWT : Discrete Wavelet Transform) et (4) La transformée par décomposition en valeurs singulières (SVD : Singular Value Decomposition), qui relève du domaine de l‟algèbre linéaire. Pour le point d‟intérêt (b), notre étude montre l‟existence de quatre familles de techniques de comparaison des ST. Il y a d‟abord (1) Les techniques de comparaison utilisant les données directes des ST combinées à des mesures de distance/similarité, telle que la distance Euclidienne, (2) Les techniques de comparaison basées caractéristiques combinées aussi à une mesure de distance / similarité, telle que la DFT et (3) Les technique d‟alignement, telle que la célèbre et très pertinente méthode : DTW (Dynamic Time Warping). Enfin, (4) une autre classe de techniques d‟alignement des ST basées signatures (caractéristiques globales) a été récemment proposée par Boucheham [Boucheham, 2008] : la méthode SEA (Shape Exchange Algorithm). Son auteur la présente comme la rivale de la DTW ; mais, plus précise et plus pertinente. Comme contributions personnelles dans le cadre de cette thèse, nous avons proposé quatre travaux dont deux ont été publiés au niveau international : (1) L‟élaboration d‟une technique d‟alignement pour l‟alignement des ST quasi-périodiques (STQP), telles que les tracés ECG (Electrocardiogramme) et les ST du Capnogram (Qualité de la respiration). Notre méthode, intitulée QPDTW (Quasi-Periodic Dynamic Time Warping) [Boulnemour, 2018], est une fusion entre la méthode DTW et la méthode SEA [Boucheham, 2008]. L‟intérêt de ce travail est que, selon les travaux de Boucheham [Boucheham, 2008 et 2013], l‟alignement des STQP serait le cas le plus complexe à résoudre. Brièvement, notre méthode QPDTW permet d‟aligner de manière effective les STQP même lorsqu'elles sont déphasées et bruitées de manières significatives. (2) Développement d'un classifieur binaire basé QPDTW pour la détection d'anomalies dans les tracés ECG [Boulnemour, 2016]. Ce travail en particulier a eu un écho remarquable sur Researchgate. (3) Développement d‟une méthode accélérée à base de la transformation en ondelettes de Haar et de la méthode QP-DTW pour la recherche de similarité dans l‟ECG. (4) Développement d‟un classifieur de type KNN basé QPDTW pour la classification des ST générales. La base utilisée dans ce cas étant l'UCR (University of California at Riverside) [Chen, 2015] utilisée mondialement comme benchmark pour évaluation des techniques de classification et de clustering des TS. Les résultats sont prometteurs, que se soit pour la détection d'anomalies, la recherche ou pour la classification des séries temporelles


 Résumé Anglais

This study is mainly concerned with : (a) Time Series (TS) Characterization problematic and (b) Investigation the, necessarily linked domain: Distance and similarity measures within the context of TS. This last point includes also the more complicated problem of TS alignment. These are also TS matching techniques, but known as being at the same time more effective but more hard to derive. TS characterization aims to express in a compact, yet pertinent fashion TS. Compact means that data redundancy is reduced as much as it can, yet, the extracted features are as discriminatory as possible. To this end, TS are usually moved from the temporal domain to other more expressive domains in terms of power of discrimination. In this context, a state of the art and a categorization of existing such techniques will be established in this thesis. Generally speaking, we already can announce the existence of four classes of such methods. (1) Temporal domain techniques, such as Histogram, Motifs and PLA (Piece-Wise Linear Approximation) approaches, (2) Frequency domain techniques, such as DFT (Discrete Fourier Transform) and DCT (Discrete Cosine Tranform), (3) Time-Frequency techniques, such as DWT (Discrete wavelet Transform) under its various variants and (4) SVD: Singular Value Decomposition techniques that belongs to the algebraic domain. For aim (b), the study shows existence of four families of such techniques: (1) Techniques that use directly data combined with some kind of distance/similarity, such as the Euclidian distance, (2) Feature-based techniques that use some kind of extracted features, like Fourier coefficients, combined to some kind of distance/similarity measure, (3) Alignment techniques, such as the famous and very appreciated DTW (Dynamic Time Warping) technique. Recently, a new TS alignment technique has been proposed by Boucheham (Boucheham, 2008) known as SEA (Shape Exchage Algorithm) as a rival to DTW and the sole capable of aligning QPTS (Quasi-Periodic Time Series) (Boucheham, 2008). SEA is rather based on the novel paradigm of Signature Exchange between the two TS to align. As personal contributions within the context of this thesis, we have proposed four works, two of which published internationally : (1) Elaboration of a novel TS alignment techniques that is capable also to align QPTS, such as ECG (Electrocardiogram) and Capnogram (Quality of respiration signal) traces. Our method is denominated QPDTW for it is a fusion of the two TS rivals methods: DTW and SEA of Boucheham (Boucheham, 2008). According to Boucheham (2008 and 2013), aligning QPTS represents the most complex situation in the context of TS alignment techniques. Briefly, QPDTW can effectively align even significantly noisy and also phase-shifted TS for instance. (2) Development of a binary QPDTW-based classifier for anomaly detection in ECG traces (Boulnemor, 2016). Perhaps it is worth to mention that this work attracted great attention on Researchgate. (3) Development of a HaarTransform based accelerated version of QPDTW for similarity search in ECG TS. (4) Development of QPDTW-based, KNN-type of general TS classifier. This classifier was tested on the UCR (University of California at Riverside) (Chen, 2015), universally admitted as the reference Benchmark for Ts classification and Clustering. Briefly, obtained results for QPDTW, Anomaly detection in ECG traces, Ts Search by similarity and Classification are promising