SIFT-Words. DDTW Derivative Dynamic Time Warping. DM Data Mining. DoG Difference of Gaussians. DTW Dynamic Time Warping. DTW-NN 1-Nearest Neighbor associated with Dynamic Time Warping. ED Euclidean Distance. EDR Edit Distance on Real Sequences. ERP Edit Distance on Real Penalty. EVI Enhanced Vegetation Index. IDF Inverse Document Frequency. LANDSAT Land Satellite

Keywords: . BoW Bag-of-Words. CNN Convolutional Neural Networks. COTE Collective Of Transformation-based Ensembles LCSS Longest Common Subsequences PROP Proportional Elastic Ensemble. RS Remote Sensing. SAX Symbolic Aggregate approXimation. SAX-VSM Symbolic Aggregate approXimation -Vector Space Model. SFA Symbolic-Fourier Approximation. SIFT Scale-Invariant Feature Transform TWED Time Warp Edit Distance. VSM Vector Space Model. WDDTW Weighted Derivative Dynamic Time Warping Time Series Classification, Remote Sensing Time Series, Bag-of-Words, SIFT features, Time Series Shapelets, Convolutional Neural Networks, Adversarial Examples

1D One Dimensional. 2D Two Dimensional.

ABS Adversarially

ii

Résumé en Français

La classification de séries temporelles a suscité beaucoup d'intérêt ces dernières années en raison de nombreuses applications telles que la surveillance des électrocardiogrammes, la reconnaissance vocale ou la modélisation environnementale. Dans cette thèse, notre but est de proposer de nouveaux algorithmes pour la classification de séries temporelles qui sont adaptés aux applications de télédétection mais également qui obtiennent de très bonne performance par rapport aux algorithmes de classification de séries temporelles standards. La classification des séries temporelles présente en effet un intérêt particulier pour la télédétection : celle-ci utilise des séries temporelles d'images satellitaires afin de générer automatiquement des cartes d'occupation des sols et de couverture terrestre [START_REF] Clark | A scalable approach to mapping annual land cover at 250 m using modis time series data: A case study in the dry chaco ecoregion of south america[END_REF][START_REF] Hüttich | On the suitability of modis time series metrics to map vegetation types in dry savanna ecosystems: A case study in the kalahari of ne namibia[END_REF][START_REF] Wardlow | Large-area crop mapping using time-series modis 250 m ndvi data: An assessment for the us central great plains[END_REF].

Ce résumé introduit les différentes problématiques abordées dans cette thèse. Dans un premier temps, nous développerons un court argumentaire afin de montrer l'intérêt de la classification de séries temporelles ainsi que des données issues de la télédétection. Puis nous développerons les travaux réalisés dans le cadre du doctorat. Ces travaux sont divisés en trois parties, chaque partie correspondant à un futur chapitre.

La classification de séries temporelles

L'étiquetage manuel de données est un processus long et coûteux, or le volume de données ne cesse de grandir. Afin de pouvoir utiliser ces données il est souvent nécessaire de les classer, cependant le volume est tel qu'il est impossible de le faire manuellement. L'utilisation d'algorithmes d'apprentissage est un moyen de résoudre ce problème : des données peuvent servir d'entrées à un algorithme afin d'être classées. Ces données peuvent être : des documents (du texte), des images, des nuages de points ou encore des séries temporelles.

Nous nous intéressons ici à la classification de données, pour laquelle on définit l'apprentissage comme l'étape de construction du modèle, et la prédiction comme l'étape de classification de nouvelles données. Dans le cadre de l'apprentissage supervisé, l'apprentissage sur des données d'entraînement (dont on connaît la classe d'appartenance) permet d'apprendre un modèle qui sera ensuite utilisé pour classer de nouvelles données. Le but des algorithmes de classification est d'apprendre un modèle qui minimisera le nombre d'erreur sur ces nouvelles données, ce modèle doit donc être capable de généraliser sur les données d'apprentissage. De plus, pour être exploitables, les classifieurs doivent être rapides dans l'étape de construction du modèle et/ou dans la prédiction d'une classe par le modèle. Il peut être intéressant de tenir compte du temps requis pour classer une nouvelle donnée. En effet certains algorithmes ont besoin de plus de ressources pour s'en-

Résumé en Français

iii traîner mais effectueront une classification rapide voire instantanée, c'est le cas pour les réseaux de neurones. Dans le cadre d'application où l'on s'entraîne une seule fois et où l'on classifie toujours avec le même modèle, choisir un algorithme qui classifie très rapidement peut être un bon choix, même si son temps d'apprentissage est plus long que d'autres algorithmes. Finalement, comme les données proviennent de nombreux domaines, il est peu probable qu'un algorithme soit le meilleur sur l'ensemble des jeux de données existants et à venir [START_REF] Wolpert | No free lunch theorems for optimization[END_REF]. D'où la nécessité de choisir un algorithme adapté aux données utilisées.

La classification de séries temporelles On se place maintenant dans le cadre où nos données sont des séries temporelles pouvant être vues comme une suite de valeurs réelles et ordonnées. Deux séries temporelles enregistrées par un même capteur peuvent être différentes soit à cause d'un décalage temporel (en cas d'actions asynchrones) soit à cause d'une dilatation si les deux actions n'ont pas été réalisées à la même vitesse. Parmi les caractéristiques que doivent avoir les classifieurs de séries temporelles, on peut noter : la robutesse aux distorsions temporelles (telles que les décalages dans le temps et la dilatation) mais également des caractéristiques liées à la classification de données en général telles que la robutesse au bruit et aux valeurs aberrantes.

La classification de données issues de la télédétection La classification automatique de la couverture terrestre à partir de données satellitaires est un sujet important qui permet de produire des cartes représentant les différents types de sols (tels que eau, forêts ou villes). Cependant les changements rapides dans l'aménagement du paysage et l'utilisation des terres rendent nécessaire une mise-à-jour régulière des cartes, qu'il est impossible de faire de manière manuelle à l'échelle de la planète. On a donc besoin d'algorithmes de classification afin de pouvoir générer de manière régulière et automatique des cartes de couverture terrestre.

Le but de cette thèse est d'apporter de nouvelles approches pour la classification de séries temporelles, nous allons donc nous intéresser à un cas d'application précis : les séries temporelles d'images satellitaires. Chaque série temporelle représente l'évolution des valeurs d'un indice (par exemple mesurant le taux de végétation) au cours du temps pour une zone précise. La longueur de la série dépend de la durée d'acquisition et du temps de revisite du satellite, par exemple si l'on considère un satellite dont la résolution temporelle est de huit jours et une période d'acquisition d'un an, on aura une série temporelle environ de longueur 46. Grâce aux séries temporelles d'images satellitaires, on peut observer les profils des différents types de sols et notamment les profils de végétaux, qui diffèrent selon le type de plantation. iv

Résumé en Français

Il est donc nécessaire pour les communautées scientifiques de télédétection et d'apprentissage automatique de travailler ensemble à l'élaboration de méthodes adaptées aux données satellitaires. Dans cette thèse, nous avons choisi de nous concentrer sur des méthodes d'apprentissage permettant de prendre en compte les particularités des séries temporelles, avec des méthodes robustes aux décalages temporels, prenant en compte l'évolution des valeurs au cours du temps et qui permettent une interprétation des résultats obtenus.

Travaux sur les algorithmes de classification de séries temporelles

Dans le but d'améliorer les performances des algorithmes de classification de séries temporelles, il a été montré qu'un moyen simple était de transformer les séries en se basant sur des éléments discriminatoires tels que des caractéristiques locales [START_REF] Lines | A shapelet transform for time series classification[END_REF]. C'est pourquoi, nous proposons deux algorithmes de classification de séries temporelles basées sur l'utilisation de caractéristiques locales. Ces caractéristiques correspondent aux différentes variations d'une série temporelle telles que les pics ou les vallées.

La méthode Dense Bag-of-Temporal-SIFT-Words : D-BoTSW

Dans notre première approche, correspondant au chapitre 2, nous représentons des séries temporelles sous la forme d'un ensemble de caractéristiques locales. Pour cela, on transforme les séries en histogramme comptant la fréquence d'apparition de ces caractéristiques locales, puis on donne cette nouvelle représentation à un classifieur afin de prédire sa classe d'appartenance.

De manière plus détaillée, notre algorithme se déroule de la façon suivante. Nous utilisons des descripteurs locaux basés sur la méthode SIFT, adaptés pour les données en une dimension et extraits à intervalles réguliers (on parlera d'extraction dense). Ces descripteurs sont basés sur le voisinage du point considéré et prennent en compte les différentes tendances de la série autour de ce point. Ils permettent donc d'identifier : les pics, les vallées, les tendances à la hausse, c'est-à-dire les différentes variations de chaque série. Afin de mieux représenter les séries temporelles, nous utilisons ensuite la représentation par sac de mots. L'idée est de générer un dictionnaire de mots, où chaque mot rassemble un ensemble de descripteurs qui sont proches : on aura donc des mots différents pour les pics et pour les vallées. Chaque série temporelle est donc transformée en un histogramme comptant la fréquence d'apparition de chaque mot. La taille de Résumé en Français v l'histogramme et la taille du dictionnaire seront donc identiques. Les histogrammes servent d'entrées à un SVM linéaire pour l'étape de prédiction. Un fois le modèle appris (c'est-à-dire le dictionnaire et les poids du SVM), on peut prédire les classes de nouvelles séries temporelles en utilisant le dictionnaire afin de générer l'histogramme correspondant puis le classifieur appris.

L'algorithme D-BoTSW n'est pas adapté pour tous les problèmes de classification de séries temporelles. En effet, la représentation par sac de mots ignore l'ordre d'apparition des caractéristiques, D-BoTSW n'est donc probablement pas l'algorithme le plus approprié pour la classification de séries temporelles où cela importe. Au contraire, les décalages temporels dans les séries temporelles sont facilement gérés par D-BoTSW, de plus l'algorithme est robuste au bruit.

Le temps d'apprentissage dépend principalement de l'étape de génération du dictionnaire et d'apprentissage des paramètres du SVM. En effet, les descripteurs SIFT reposent sur des opérations simples et peu coûteuses ; et l'étape de transformation d'une série en histogramme est très rapide une fois le modèle généré. L'algorithme D-BoTSW peut donc être une bonne option pour les applications où l'on souhaite classer de nouvelles données en utilisant toujours le même modèle.

Des expériences approfondies, menées sur 85 jeux de données, montrent que notre méthode Dense Bag-of-Temporal-SIFT-Words (D-BoTSW) surpasse de façon significative quasiment tous les classificateurs de référence comparés. En effet, sur dix algorithmes de classification considérés comme références dans le domaine, des tests statistiques ont montré que D-BoTSW est significativement meilleur que six d'entre eux, équivalent à trois autres et uniquement battu par une seule méthode.

L'algorithme Adversarially-Built Shapelets : ABS

La deuxième approche, correspondant au chapitre 3, est basée sur l'apprentissage de sous-séries caractéristiques (shapelets) permettant de différencier les différentes classes de séries temporelles. [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF] ont proposé un premier algorithme basé sur les shapelets. L'un des freins majeurs à l'utilisation de cet algorithme est le temps d'apprentissage, en effet la recherche de shapelets est basée sur un algorithme force brute très gourmand en temps. Plusieurs algorithmes ont été proposés afin de réduire le temps de recherche des shapelets [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF][START_REF] Ye | Time series shapelets: A novel technique that allows accurate, interpretable and fast classification[END_REF]. Contrairement aux autres algorithmes basés sur ce principe, l'algorithme Learning Time Series Shapelets (LTS) apprend ces sous-séries au lieu de les rechercher. La méthode LTS est une des deux méthodes basées sur les shapelets obtenant les meilleurs performances, il est donc intéressant de proposer un moyen d'améliorer cette méthode. vi

Résumé en Français

Afin de comprendre la construction de notre méthode, il est nécessaire de connaître les étapes clés de l'algorithme LTS [START_REF] Grabocka | Learning time-series shapelets[END_REF]. L'algorithme LTS est une méthode basée sur des caractéristiques locales qui cherche à apprendre des sous-séries discriminantes (c'est-à-dire les shapelets) à partir d'un ensemble de séries temporelles. La distance d'une série avec chaque shapelet est calculée, puis un classifieur linéaire est utilisé afin de prédire la classe d'appartenance de cette série. Il est donc nécessaire d'apprendre à la fois les shapelets mais également les paramètres du classifieur. Les auteurs de la méthode LTS proposent de le faire de manière itérative en actualisant en même temps les shapelets et les paramètres du classifieur.

Pour contruire l'algorithme ABS, nous montrons dans un premier temps qu'il est possible d'écrire l'algorithme LTS en tant que cas particulier d'un réseau neuronal convolutif (CNN). Pour cela, nous présentons les différentes couches d'un réseau de neurones convolutifs (convolution, pooling et fully connected) afin de faire le lien entre les deux approches. Il a été prouvé [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] que les CNNs sont vulnérables aux exemples adversaires. Les exemples adversaires sont des données générées dans le but de tromper un CNN : pour cela, on modifie de manière imperceptible mais déterministe une image bien classée par un CNN. Nous démontrons que comme les CNNs, l'algorithme LTS est suceptible d'être vulnérable aux exemples adversaires (des séries temporelles adversaires dans notre cas). Il a été établi que l'introduction d'exemples adversaires dans le processus d'apprentissage permettait de générer des réseaux plus robustes tout en améliorant légèrement les performances [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]. Nous proposons donc une méthode dont l'apprentissage est basé à la fois sur des séries temporelles non-modifiées et sur des séries adversaires. À chaque itération, nous générons de nouvelles séries temporelles adversaires. Celles-ci permettent de générer des shapelets plus robustes et d'améliorer les performances globales de l'algorithme.

L'algorithme ABS est particulièrement intéressant pour les problèmes de séries temporelles où une ou plusieurs sous-séries permettent de bien différencier les différentes classes. Les algorithmes LTS et ABS étant des cas particuliers de réseaux de neurones convolutifs, il est donc possible d'implémenter des algorithmes ayant un temps d'apprentissage faible. Concernant le temps de prédiction, il est comme pour tous les réseaux de neurones très faible.

Des expériences montrent une amélioration significative de la performance entre l'algorithme LTS et notre proposition Adversarially-Built Shapelets (ABS). Comparés aux autres méthodes de classification de séries temporelles, ABS obtient de bonnes performances puisque sur onze algorithmes de classification (les dix précédentes ainsi que D-BoTSW), des tests statistiques ont montré que ABS est significativement meilleur que six d'entre eux, équivalent à deux autres et battu par trois (dont D-BoTSW).

Résumé en Français vii

Applications sur des jeux de données de séries temporelles issues de la télédétection

Le dernier chapitre se concentre sur les applications en télédétection. En effet, nous avons précédemment décrit l'intérêt de la classification automatique de séries temporelles pour les applications en télédétection. Nous avons donc choisi d'expérimenter sur deux jeux de données disponibles en ligne : TiSeLac et Brazilian Amazon.

TiSeLac Ce jeu de données a été proposé dans le cadre d'un challenge ayant pour but de rapprocher les communautés d'apprentissage automatique et de télédétection. Pour cela, des données, enregistrées par le satellite Landsat au niveau de l'île de la Réunion, ont été préparées afin de former des séries temporelles multi-variées (10 indices différents) associées à leur coordonnées. Nous avons réduit ce jeu de données à un seul indice (NDVI) afin de pouvoir l'exploiter avec des algorithmes travaillant sur des séries temporelles univariées en entrée. Le NDVI est un indice de végétation dont la valeur varie en fonction du type de sol, par exemple une végétation dense aura une valeur élevée de NDVI alors qu'un sol enneigé aura une valeur très basse.

Le jeu de données TiSeLaC contient à la fois des classes de végétation (telles que des forêts) ainsi que des classes non végétales (telles que des zones urbaines). De plus, les séries temporelles ont une grande variabilité intra-classe aussi bien temporellement parlant qu'en amplitude. La variabilité en amplitude est due à la topologie particulière de l'île de la Réunion aux reliefs très escarpés ainsi qu'aux différents climats présents sur l'île. La variabilité temporelle des séries issues de la télédétection est un phénomène répandu principalement dû à des dates de semis différentes et aux conditions climatiques.

Brazilian Amazon Ce jeu de données contient des séries temporelles provenant du satellite MODIS et extraites dans l'état du Mato Grosso au Brésil. C'est un exemple applicatif particulièrement intéressant puisque les données représentent différentes parcelles agriculturales issues des régions tropicales. Le jeu de donnés Brazilian Amazon est composé uniquement de classes végétales. L'indice végétal utilisé pour la représentation des séries temporelles est l'EVI, qui comparé au NDVI a l'avantage de ne pas saturer en présence de végétation dense.

Le jeu de données regroupe 5 classes différentes : (a) soja, (b) coton, (c) soja + millet, (d) soja + maïs, et (e) soja + coton. On peut différencier les cultures dites uniques (c'est-à-dire une culture par an), des cultures dites intensives ou doubles cultures (c'est-à-dire deux cultures / récoltes par an). viii

Résumé en Français

Chacun des jeux de données a été évalué sur plusieurs algorithmes de classification de séries temporelles. Bien que les méthodes basées sur des caractéristiques, telles que BOSS et D-BoTSW, ont montré des résultats prometteurs, ce sont les méthodes basées sur les shapelets (c'est-à-dire ABS et LTS) qui ont montré les meilleurs performances sur les deux jeux de données. Avec l'arrivée de nouveaux satellites ayant des résolutions spatiales et temporelles plus précises, il est très probable que la performance de ces algorithmes s'améliore dans le futur. En effet, une résolution temporelle plus fine permettra une représentation plus précise des differents cycles phénologiques, donc probablement de générer des caractéristiques plus discriminantes. Une résolution spatiale plus fine va permettre quant-à-elle de travailler avec des séries temporelles plus pures (c'est-à-dire qu'il y aura moins de mélange de classes dans chaque pixel).

Des modèles simplifiés des deux méthodes proposées dans ce manuscript (D-BoTSW et ABS) ont servi à illustrer les résultats obtenus sur Brazilian Amazon. Pour D-BoTSW, nous avons généré un dictionnaire réduit afin de représenter les différentes caractéristiques ainsi que les histogrammes associés. Pour ABS, nous avons généré un ensemble de shapelets ainsi que les poids du modèle linéaire. A partir des modèles, nous avons pu vérifier xii

INTRODUCTION

Motivation

This thesis aims at bringing new methodologies to classify time series data. We consider that a time series corresponds to an ordered sequence of real-valued datapoints representing the evolution of a quantity over time. They arise in many domains and have a wide range of applications. Classification aims at identifying amongst a list of categories to which category a new data belongs. Time series classification is of particular interest for the remote sensing community that uses satellite images time series in order to generate land use and land cover maps. Satellite images time series data have been widely used in order to classify vegetation [START_REF] Clark | A scalable approach to mapping annual land cover at 250 m using modis time series data: A case study in the dry chaco ecoregion of south america[END_REF][START_REF] Hüttich | On the suitability of modis time series metrics to map vegetation types in dry savanna ecosystems: A case study in the kalahari of ne namibia[END_REF][START_REF] Wardlow | Large-area crop mapping using time-series modis 250 m ndvi data: An assessment for the us central great plains[END_REF]. Indeed, time series data are able to represent the phenological cycle that differs according to the land cover type.

In the following, we present time series classification algorithms based on local features, such as peask or valleys, since results interpretation and analysis is of paramount interest for remote sensing applications. Moreover, feature-based approaches often lead to high performance. Our motivation is thus to bring machine learning and remote sensing communities closer by providing algorithms that are adapted for remote sensing applications and that also achieve high accuracy w.r.t. time series classification baselines.

A Need for Automatic Classification.

In the last decades, the amount of data generated by sensors, such as satellites or ECGs, is constantly and exponentially growing. In order to exploit this data, it needs to be categorized and labeled, which quickly became impossible to do manually. Hence, scalable automatic processes classifying data had to be developed.

The creation of classification algorithms is a way to solve this problem of new and numerous data to categorize. The first step is the training phase, during which the algorithm builds a model from already labeled data. During the prediction step, this model is applied to new, unlabeled data. Note that many data types can be used as inputs of such algorithms: documents (e.g. text), images, videos, point clouds or time series. The data may come from many different fields, such as biology, economy, or geology, and varies greatly in size and forms.

Introduction

Classification algorithms aim at minimizing the prediction error on new data, to do so it is necessary to build models that generalize the data. Moreover, in order to be exploitable, classifiers need to be fast (learning and / or prediction steps) as well as to be robust to noise and outliers. Concerning the prediction step, the time required to classify a new data has to be taken into acocount. Indeed, some algorithms need more resources to train the model but will perform a fast or instantaneous classification, as it is the case for neural networks. If we plan to learn the model once and perform multiple classification using the same model, it can be interesting to choose an algorithm that predicts fastly, even if its learning time requires more resources. In order to take into account the intra-class variability (i.e. the differences between the time series of the same class), the classifiers must also be able to generalize well the information.

Also, the classification is more or less complex depending on the nature of the data. It is thus impossible to create an algorithm that obtains the best performance on all available data, as stated by the no free lunch theorem [START_REF] Wolpert | No free lunch theorems for optimization[END_REF]. However, the theorem also states that the only way to find an algorithm more efficient than another is to adapt the algorithm to the problem.

Time Series Classification

Amongst all classification problems, we are interested in time series classification, for which dedicated algorithms range from the simple k-nearestneighbor algorithm associated with Euclidean distance to ensemble methods dedicated to time series.

The temporal ordering inside time series makes them particularly interesting to study. The correlation between close points will be stronger than the one between distant points. Finally, temporal distortions such as time shifts and dilations can be present in time series, it is thus necessary to propose time series classification algorithms robust to these distortions.

Remote Sensing Applications.

For the last decades, Earth observation has been used to better understand our planet and to follow its evolution. The characterization of continental surface transformations such as deforestation, evolution of agricultural practices or urbanization, is essential to evaluate the impact of global warming, public policies, or conflicts. Remote sensing satellites acquire images over the entire surface of Earth, offering the possibility to produce an up-to-date land use / land cover map. Land use mapping is a crucial tool for remote sensing applications, such as global changes tracking or large-scale Introduction 3 crop monitoring.

Remote sensing data has been widely used in different forms such as images and time series. It has also been used to solve a large variety of problems such as monitoring agricultural parcels, mapping or environmental modeling. Automatic classification of remote sensing data is of high interest as the labeling step is limited (a) by the high cost, both in human resources and in time through field campaigns or labeling by experts, and (b) by the huge amount of data to label. Moreover, fast changes in landscape make necessary the frequent update of maps, which can not be done manually at a global scale.

The purpose of this thesis is to provide new approaches for the classification of time series, and we focus our applications on satellite images time series. Each remote sensing time series represents the evolution of an index value over time for a specific area. The length of the series depends on the acquisition period and the revisit time of the satellite: if we consider a satellite whose temporal resolution is of eight days and a one year acquisition period, we will have a time series of approximately 46 datapoints, which corresponds to the 46 images acquired by the satellite. Thanks to satellite images time series, it is possible to observe the profiles of different soil types and in particular vegetation profiles, which differ according to the flora.

It is therefore necessary for the scientific communities of remote sensing and machine learning to work together to develop methods adapted to satellite data. This thesis focuses on interpretable learning methods for time series, robust to time shifts and taking into account the different features (e.g. trends, peaks) of this type of data.

Contributions

In order to improve the performance of time series classification algorithms, transforming time series into a new representation based on discriminative features has shown to be effective [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF][START_REF] Lines | A shapelet transform for time series classification[END_REF]. Since characteristics such as peaks and valleys are interesting properties of time series, we aim to transform time series into a new representation, based on these characteristics, that can be used with general learning algorithms. Our approaches thus build on feature-based representations of time series.

Introduction

SIFT features and Bag-of-Words representation. Basically, the algorithm combines the extraction of descriptive features at regular time steps in the time series with a histogram representation. The raw time series are transformed into a new representation that gathers the different descriptive characteristics into similarity groups, the new representation is then fed into a classifier.

The D-BoTSW algorithm can be divided into the following steps. First, we extract dense keypoints inside time series, i.e. we extracted a list of points at regular time step that serve as bases for our future descriptors. Then, we describe these keypoints using 1D-SIFT features, these feature use neighboring points in order to describe the neighborhood of each keypoints and to detect characteristics such as peaks or valleys inside time series. Once we have our descriptors, we generate a codebook, i.e. we gather similar features together in order to simplify the representation. To do so, we transform each time series into a new representation corresponding to a normalized histogram of words occurences, which allow us to easily compare two time series. Finally, we perform the classification on the new representation.

Since the Bag-of-Words representation ignores temporal order, temporal shifts in time series are easily handled by D-BoTSW. However, when ordering matters, D-BoTSW is probably not the most suitable algorithm. The proposed algorithm is robust to both noise and temporal shifts. Moreover, it exhibits high performance compared to state-of-the-art time series classification algorithms.

A detailed explanation of this algorithm as well as experimentations on it can be found in Chapter 2.

Adversarially-Built Shapelets

Our second contribution is an improved version of the Learning Time series Shapelets (LTS) algorithm. Shapelets are discriminative sub-series that are used to predict the class label. Many algorithms were proposed for shapelets discovery. However the LTS algorithm was the first to propose to learn them instead of searching them.

In order to understand the construction of our method, it is necessary to know a few key steps of the LTS algorithm [START_REF] Grabocka | Learning time-series shapelets[END_REF]. The LTS algorithm seeks to learn a set of discriminative sub-series. To do so, the first step is to transform the time series into a set of features, where a feature corresponds to the distance between a series and a shapelet. The next step is to use these features (i.e. distances) in a linear classifier to predict the class label of this series. The authors of the LTS method propose to do it iteratively by updating at the same time the shapelets and the weights of the classifier using training series.

To build the ABS algorithm, the first part of our work was to demon-

Remote Sensing Applications

Many remote sensing applications use time series data such as land cover mapping or agricultural monitoring. Moreover the amount of remotely sensed data is constantly growing because of the new and upcoming satellite platforms available. It is thus important to bring machine learning and remote sensing communities closer. We present two remote sensing time series datasets we experiment on using time series baselines.

The first dataset, named TiSeLaC, was proposed as part of a challenge aiming to bring together the communities of machine learning and remote sensing. The time series were recorded by the Landsat satellite above Reunion Island and represent an interesting challenge to differentiate a large number and variety of classes.

The second dataset, called Brazilian-Amazon, contains EVI time series from the MODIS satellite extracted in the state of Mato Grosso in Brazil. This is a particularly interesting application example since the data represent different agricultural parcels and come from tropical regions. On the one hand, one can differentiate the so-called unique cultures (i.e. one crop per year) and double cultures (i.e. two crops / crops per year). On the other hand, the dataset groups 5 different classes: 2 unique culture classes and 3 double culture classes.

Simplified models of our two proposed algorithms (D-BoTSW and ABS) were used in order to illustrate the results obtained on the Brazilian Amazon dataset. For D-BoTSW, we have generated a reduced dictionary that represents the different characteristics as well as per-class histograms. For ABS, we generated a set of shapelets as well as the weights of the linear model. Using the information extracted from the models, we were able to verify different hypotheses on the data.

The characteristics of this data are developed both in term of machine learning (noise, high intra class variability) and remote sensing (vegetation index, climate) points of view. Results interpretation and analysis is provided for both of our algorithms.

Introduction Organisation

The purpose of this thesis is to bring new solutions for the classification of time series data, with some applications in remote sensing. In order to fulfill these goals, this manuscript will be organized in four chapters.

The first chapter gives an overview of time series classification algorithms in the literature, from basic concepts to advanced algorithms. These algorithms are gathered according to their specificities then compared to other baselines.

The second chapter introduces a first time series classifier based on feature extraction. This algorithm named Dense Bag-of-Temporal-SIFT-Words relies on two well-known and powerful methods: SIFT features (adapted to our data) and the Bag-of-Words representation.

The third chapter presents a second time series algorithm, which is based on an already existing classifier: Learning Time series Shapelets (LTS), which is also a feature-based algorithm. Our proposed method is called Adversarially-Built Shapelets and rely on the introduction of adversarial time series.

Finally, the fourth and last chapter focus on remote sensing applications with different datasets. The first one gathers agricultural time series from Brazil and the second one a variety of time series extracted from Reunion island. This chapter gives an overview of the state of the art Time Series Classification (TSC) algorithms, from basic concepts to advanced algorithms. First, we introduce notations and definitions related to TSC. Many algorithms use raw time series whereas others change the time series representation before the classification step. We thus categorize the different time series classification models that exist and review some of them with their most relevant characteristics. We start with the distance-based time series classification models, then we review the feature-based, finally we introduce the ensemble time series classifiers. In this chapter, we only aim at categorizing the different types of time series classification algorithms as well as detailing the most famous and most competitive ones ; and refer the curious reader to the numerous existing papers on this problem [START_REF] Bagnall | The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances[END_REF][START_REF] Fu | A review on time series data mining[END_REF]. We then present metrics for model evaluation. We conclude this chapter by briefly reviewing other challenging time series problems.

Introduction

1

TIME SERIES CLASSIFICATION STATE-OF-THE-ART

Basic Definitions and Notations

In the following, we provide definitions as well as useful notations in order to define the time series classification problem.

Definition 1.1 (Time Series). A time series x i of length n is an ordered sequence of valued data points, measured at regular time intervals, noted

x i = x i,1 , x i,2 , . . . , x i,n (1.1)
where x i,j denotes the j-th element of the time series x i .

Time series can be univariate or multivariate. A time series containing records of a single (respectively of multiple) observation(s) is referred to as univariate (respectively multivariate). Since we focus on univariate time series in this document, the term time series should thus be considered as univariate time series. A note will be added for algorithms that can be used with multivariate time series.

Let X be a set of time series {x 1 , x 2 , . . . , x N }. X can be referred to as dataset. For simplicity, we assume that all time series in the same dataset have the same length n. If a method can be applied on time series with different lengths, it will be specified.

The association of a time series with a label (x i , y i ) corresponds to a labeled time series, whereas a time series without a label (x i ) is called an unlabeled time series.

Definition 1.2 (Labeled Dataset).

A labeled dataset D corresponds to a set of time series associated with a set of labels (one label for each time series). Label y i represents the class of the i-th time series x i .

D = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x N , y N )} (1.2)

Basic Definitions and Notations

11

In the following, we denote labeled dataset as a dataset, and a set of datasets is referred to as database. A time series in a dataset D can also be called an instance of D.

A classification process aims at putting together individual objects or data into classes, categories or groups based on their charasteristics. Classification can be categorized into supervised, unsupervised and semi-supervised classifications. In this thesis, we focus on supervised classification, whose purpose is to correctly assign a class to a new, unseen, unlabeled data. Supervised classification first step corresponds to the training step. During training, the classification algorithm learns a model based on labeled data. For parametric methods, the best set of parameters θ is also learned at this step. This second step is called classification or prediction. In order to correctly classify new, unseen data, the classifiers must generalize well from the training data to new cases and situations.

Definition 1.3 (Classifier).

A classifier is a function f that maps the time series from their original space to the space of possible class labels, noted

f : X -→ {1, . . . , m} N or f : x i -→ {1, . . . , m} (1.3)
f (x i ) is called the prediction of the class label for the time series x i . If f (x i ) = y i then the classifier makes the right prediction.

To evaluate the performance of a classifier, a common method is to split a dataset D into two datasets D train and D test . The classifier will learn on D train , whereas D test will stay unseen during training and will be used to evaluate the classifier.

Classification Challenges

The purpose of any classifier is to find the function f that maximizes the accuracy given D train . Considering that D test is not known during f 's training, as well as it differs from D train due to many reasons depending on the data, this task is far from trivial. We assume in the following that D train and D test share both the same data distribution and the same class label sets. Being able to generalize well on unseen and unlabeled data is a challenging problem that many researchers are working on in order to bring new -more accurate -solutions. If we also consider time series data which arise in a wide range of domains and applications, such as medicine (ElectroCardioGram (ECG)), environmental applications (Land Cover Maps), object recognition or economics with different characteristics (e.g. length), we can notice that there is no best single method. This intuition is confirmed by the no free lunch theorem [START_REF] Wolpert | No free lunch theorems for optimization[END_REF]. This theorem states that there is no method, applicable to all problems, that can always optimizes a cost function ; and that the only way to find an algorithm more efficient than another is to adapt the algorithm to the problem.

Moreover, in order to be exploitable, classifiers need to be 12

Chapter 1. Time Series Classification State-of-the-Art

• fast,

• robust to noise and outliers, Indeed, there are more and more data collected that require fast classifiers to process them. On one hand, parametric methods, while more adaptative since they can better fit the characteristics of the data, might be a bit slower during training considering that they need to select the best parameter(s). On the other hand, one should also consider the time required to classify a new data, indeed some algorithms which need more time to train will perform fast classification, e.g. Time Series Shapelets [START_REF] Ye | Time series shapelets: A novel technique that allows accurate, interpretable and fast classification[END_REF]. Classifiers also need to be robust to noise in order to take into account the intra-class variability. Outliers can appear in the data (e.g. due to acquisition problems) making some classifiers failing at classifying them into the right category. It is thus important to build classifiers that are robust to noise and outliers. In the following, we consider a set of (non-exhaustive) characteristics in order to compare the different similarity measures and classifiers, such as

• the ability to deal with temporal distortions (such as time shifts and dilation),

• the robustness to noise and outliers,

• the computational cost,

• the number of parameters.

TSC versus Vector Classification

Vector classification problems can sometimes be seen as similar to TSC problems, however it is important to notice important differences between these two classification tasks. In both cases, we aim at classifying an object, where this object can be considered as a vector of values. An important feature to consider is the relation of temporal order between points of the time series. A time series corresponds to values measured at regular time step where the ordering matters, it is thus not possible to change the order of elements in time series. On the other side, elements of a vector correspond to values of different features such as dimension, it is thus possible to change their order without any impact on the classification. Finally, while time series length may vary, the vector length must stay the same into a dataset.

In TSC problems, we will see that the temporal structure of the data often plays an important role in order to discover / extract features that enable one to discriminate the classes.

Distance-based Time Series Classifiers

The distance-based methods compute point-to-point distances between time series. In this section, we review the most relevant (dis)similarity mea-

Distance-based Time Series Classifiers

13 sures as well as distance based classifiers for time series classification. In order to perform the classification step, these distances then need to be associated with a classifier such as k-Nearest Neighbors (kNN) or Support Vector Machines (SVM).

Dissimilarity Measures

The notion of similarity is a fundamental concept in scientific communities. Its purpose is to compare two instances by computing a single value quantifying their similarity. We consider in the following that instances are either vectors or time series. A similarity (respectively dissimilarity) measure is a real-valued function that measures how close (respectively dissimilar) two instances are to each other. The closer the instances are, the larger the similarity is. There exists many (dis)similarity measures and definitions of it, amongst them we denote a particular case: distance metrics.

Definition 1.4 (Distance Metric). A distance metric d between two instances

x i and x must follow the following rules:

1. Non-negativity:

d(x i , x ) ≥ 0 2. Identity: d(x i , x ) = 0 if and only if x i = x 3. Symmetry: d(x i , x ) = d(x , x i ) 4. Triangle inequality: ∀x z : d(x i , x z ) + d(x z , x ) ≥ d(x i , x ) The distance metric d is a function d : X × X -→ [0, +∞) (1.4)
Many techniques, that can be used for classification such as metric trees (e.g. M-Tree, GNAT [START_REF] Ratanamahatana | Mining time series data[END_REF]), can only be used with distance metrics. Using distance metrics can thus be an advantage compared to using non-distance metrics.

Based on L p Distances

L p distances correspond to a set of functions where p is a strictly positive real number (p ∈ R * + ). The L p distance, or Minkowski distance, can be considered as a generalization of Manhattan (p = 1), Euclidean (p = 2) and Chebyshev (p = ∞) distances. The L p norm is defined as

z p = n i=1 |z i | p 1 /p (1.5)
The L p distance (or Minkowski distance) between two sequences z and v is defined as

d p (z, v) = z -v p = n i=1 |z i -v i | p 1 /p (1.
d ED (z, v) = z -v 2 = n i=1 (z i -v i ) 2
(1.7)

The Figure 1.1 represents the ED between the red and the blue time series. DTW is a sequence alignment method that can handle temporal shift and compare time series with different lengths. However, it does not respect the triangle inequality thus is not a distance metric, is sensitive to outliers, noise, and has a quadratic computational time. DTW can be speeded up, e.g. using global constraints on warping path. DTW algorithm Given two time series x i and x (of length n), we form a n-by-n grid where each grid-point (j, k) corresponds to the alignment between x i,j and x ,k . In order to compute the overall cost, we first have to compute the point-to-point cost. The warping path w corresponds to a sequence w = w 1 , w 2 , . . . , w L , where w m correspond to a pair (j m , k m ) (indicating a match between x i,jm and x ,km ). The space of possible warping paths W should satisfy the following three conditions:

1. Monotonicity, i.e. the points must be ordered in time:

j m-1 ≤ j m and k m-1 ≤ k m ,
2. Continuity, i.e. the steps in the grid should be consecutive: The overall cost c of a warping path w between x i and x is defined as

j m -j m-1 ≤ 1 and k m -k m-1 ≤ 1,
c w (x i , x ) = L m=1 d(x i,jm , x ,km ) (1.8)
The optimal warping path between x i and x is the warping path having the minimal cost amongst all possible warping paths W. The DTW distance corresponds to the cost of the optimal warping path. DTW(x i , x ) = min w∈W c w (x i , x )

(1.9)

Global constraints on time warping Finding the optimal DTW path can be time consuming, to solve this problem many speed-up techniques have been proposed. Some of them are based on restricting the space of possible warping paths. Amongst them, the Sakoe-Chiba band [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] and the Itakura parallelogram [START_REF] Itakura | Minimum prediction residual principle applied to speech recognition[END_REF] Derivative Dynamic Time Warping An extension of DTW called Derivative DTW (DDTW) was proposed by [START_REF] Keogh | Derivative dynamic time warping[END_REF]. This extension is based on the observation that two time series may also have differences in the y-axis. DTW can sometimes produce singularities in order to explain these differences. To solve this issue, [START_REF] Keogh | Derivative dynamic time warping[END_REF] thus proposed DDTW which considers the higher level of feature shape by estimating derivatives of time series data. DDTW can be seen as DTW where each time series x i is replaced by its derivative in a preprocessing step. DDTW uses the distance between the derivatives instead of distance between time series, which reduces the number of singularities. One can easily apply global constraints on DDTW as well as proposed speed-up techniques for DTW due to their similar process.

Weighted Dynamic Time Warping [START_REF] Jeong | Weighted dynamic time warping for time series classification[END_REF] proposed another extension of DTW called Weighted Dynamic Time Warping (WDTW). WDTW can be viewed as a penalty-based DTW, which takes the time difference between two points into account when computing their distances. The closer the points are, the smaller weight is imposed (i.e. the less penalty is imposed). Large shifts, which are associated with larger weights, are more penalized than smaller shifts. WDTW algorithm is identical to DTW algorithm, the only difference is the distance measure used to compare two data points. One advantage of WDTW is than it can easily be extended to variants of DTW: e.g. the association of DDTW with WDTW (Weighted Derivative Dynamic Time Warping: WDDTW) has been proposed in [START_REF] Jeong | Weighted dynamic time warping for time series classification[END_REF].

One can also easily apply global constraints as well as proposed speed-up techniques for DTW on WDTW.

Summary on Dynamic Time Warping DTW can be used to measure the similarity between time series with temporal shifts and distortions. Many speed-up techniques have been proposed to reduce the quadratic complexity of DTW. Amongst them global constraints enables one to reduce the complexity of DTW (e.g. for Sakoe-Chiba band from O(n 2 ) to O(n • r)), however it does not make DTW less sensitive to noise, outliers, nor make it a metric.

To reduce the sensitivity to noise and outliers, some enhancement of DTW were proposed such as DDTW and WDTW (that can also both handle time series with different lengths).

Edit Distance

Edit distance is a method that quantifies how dissimilar two strings are. Strings can be considered as a sequence of discrete values, where each value is a letter or symbol of the alphabet. The distance between two strings can be seen as the smallest number of added, deleted, substituted (or transposed) symbols as stated in [Jurafsky and Martin, 2000, Part I, Chapter 5].

Chapter 1. Time Series Classification State-of-the-Art

x i - 3 7 4 - 6 2 1 5 x 5 3 2 4 7 6 - 1 - Figure 1.5 -Example of LCSS distance between two sequences
Deleting a symbol is equivalent to adding a symbol in the other time series.

In the following, an added symbol will be referred to as a gap element.

Edit distance can be used in order to compare time series. For instance, a time series can be transformed into a sequence of discrete values, where each discrete value correspond to a range of continuous values, i.e. into a string. Another possibility is that, instead of checking whether two symbols from strings are identical, point-to-point in time series distance can also be compared to a predefined threshold.

The following edit distances are able to compare time series with different lengths as well as can be used for multivariate time series. Moreover, Edit-based distances can take into account outliers, contrary to DTW.

Distance Based on Longest Common SubSequences

The basic idea of the Longest Common SubSequences (LCSS) problem is to find the longest common subsequence between two sequences, where we allow some elements to be unmatched or left out. LCSS distance allows only insertion and deletion of elements, not substitution. In order to be used for time series (which are continuous variables), we need to relax the constraint on the equality in the LCSS algorithm. Indeed, two continuous values are unlikely to be exactly equal, however they can be closed to each other (|x i,jx ,k | < δ).

Definition 1.5 (LCSS Distance). Given two time series x i and x , the LCSS distance is defined as

d δ (x i , x ) =      0 if x i or x is empty 1 + d δ h(x i ), h(x )) if |x i,-1 -x ,-1 | < δ max d δ (h(x i ), x ), d δ (x i , h(x ))
otherwise (1.10) Where δ is the tolerance threshold and h(x i ) corresponds to the head function, i.e. to the time series x i without its last point x i,-1 .

Given two sequences x i = {3, 7, 4, 6, 2, 1, 5} and x = {5, 3, 2, 4, 7, 6, 1}, their LCSS is {3, 4, 6, 1}, as shown in Figure 1.5. In the time series literature, LCSS distance has been applied on univariate time series [START_REF] Das | Finding similar time series[END_REF], as well as on multivariate time series [START_REF] Vlachos | Discovering similar multidimensional trajectories[END_REF]. LCSS is an alignment method that can handle outliers and temporal shifts, however it is not a metric and has a quadratic complexity. [START_REF] Chen | Robust and fast similarity search for moving object trajectories[END_REF] proposed the Edit Distance on Real Sequences (EDR). In order to take into account the continuous nature of the variables, the constraint on the equality is also relaxed. Definition 1.6 (Edit Distance on Real Sequences). Given two time series x i and x , the EDR between two data points is defined as

Edit Distance on Real Sequences

d EDR * (x i,j , x ,k ) =      0 if |x i,j -x ,k | ≤ δ 1 if x i,j or x ,k is a gap 1 otherwise (1.11)
where δ is the tolerance threshold.

In order to compute the distance d EDR (x i , x ) between two time series respectively of length n and m, we can use a dynamic programming style:

d EDR (x i , x ) =                n if m = 0 m if n = 0 min      d EDR (r(x i ), r(x )) + d EDR * (x i,1 , x ,1 ), d EDR (x i , r(x )) + 1, d EDR (r(x i ), x ) + 1      otherwise
(1.12) Where r(x i ) corresponds to the time series x i without its first point x i,1 .

Chen et al. [2005] showed that EDR supports local time shifts, is is more robust to noise than DTW and LCSS, however its complexity is quadratic and it is not a distance metric.

Edit Distance on Real Penalty

The Edit Distance on Real Penalty (ERP) has been proposed by [START_REF] Chen | On the marriage of lp-norms and edit distance[END_REF]. ERP is a distance metric, which is associated with a penalization. This penalization is a constant value g that is applied when gaps are created (to create an optimal alignment).

Definition 1.7 (Edit Distance on Real Penalty). Given two time series x i and x , the ERP between two data points is defined as

d ERP * (x i,j , x ,k ) =      |x i,j -x ,k | if neither x i,j nor x ,k are gaps |x i,j -g| if x ,k is a gap |x ,k -g| if x i,j is a gap (1.13)
where g a constant value.

In order to compute the distance d ERP (x i , x ) between two time series, 20

Chapter 1. Time Series Classification State-of-the-Art we can again use a dynamic programming style:

d ERP (x i , x ) =                n k=1 |x ,k -g| if n = 0 n j=1 |x i,j -g| if n = 0 min      d ERP (r(x i ), r(x )) + d ERP * (x i,1 , x ,1 ), d ERP (x i , r(x )) + d ERP * (x ,1 , g), d ERP (r(x i ), x ) + d ERP * (x i,1 , g)      otherwise
(1.14) Where g the penalization term (i.e. the gap -set to 0 by authors).

ERP is based on EDR but uses actual distance between points instead of fixed values. ERP is able to handle outliers and temporal shift. Plus ERP can be indexed since it is a distance metric, thus it can be easily fasten despite a quadratic complexity. [START_REF] Marteau | Time warp edit distance with stiffness adjustment for time series matching[END_REF] proposed the Time Warp Edit Distance (TWED) another elastic similarity metric (i.e. can handle shifts in time series). TWED elasticity is controlled by a parameter called stiffness γ using time stamp differences as part of the local matching cost. An infinite stiffness makes the distance equivalent to the ED, whereas a null stiffness is similar to DTW without warping window. A second parameter is involved in TWED, it corresponds to penalty λ for insertion or deletion operations, similarly to the previously seen edit distance. TWED has three operations: delete_x i , delete_x and match. Definition 1.8 (Time Warp Edit Distance). Given two time series x i and x , the TWED is defined as

Time Warp Edit Distance

d λ,γ (x i , x ) = min            d λ,γ (h(x i ), x ) + d(x i,-1 , x i,-2 ) + λ + γ • d(t i,-1 , t i,-2 )) d λ,γ (x i , h(x )) + d(x k,-1 , x ,-2 ) + λ + γ • d(t ,-1 , t ,-2 )) d λ,γ (h(x i ), h(x )) + d(x i,-1 , x ,-1 ) + d(x i,-2 , x ,-2 ) + γ • (d(t i,-1 , t ,-1 ) + d(t i,-2 , t ,-2 )) (1.15)
where λ is the constant penalty added in case of a deletion (λ ≥ 0), γ the stiffness parameter (γ ≥ 0), h(x i ) corresponds to the time series x i without its last point x i,-1 (which time instant is denoted t i,-1 ) and d a L p metric.

The TWED metric can handle temporal distortions and is robust to noise, yet it is not a parameter free distance. Nonetheless, thanks to the stiffness parameter, TWED can control the admissible shift in time series, which is very useful on data where the temporal location matters. Note that TWED can both handle multivariate time series as well as different lengths ones.

Distance-based Time Series Classifiers

21 1.2.1.5 Move-Split-Merge [START_REF] Stefan | The move-split-merge metric for time series[END_REF] introduced the Move-Split-Merge (MSM), which is based on a set of operations: move, split and merge. move is equivalent to a substitution (i.e. changes the value of an element), split will double an element (i.e. add the same element right after itself) and merge merges two consecutive elements into one. Each operations has an associated cost c, except the move operation which cost corresponds to the absolue value of the difference between the original element and the new one. The distance between two time series corresponds to the cost of the cheapest sequence of operations that transforms the first time series into the second one. MSM is a distance metric which is robust to temporal shifts and which is able to deal with time series of different lengths and multivariate time series. [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF] proposed a kernel to handle the time series alignment problem. This DTW-inspired kernel aligns time series using the softminimum of all alignment costs in order to define a positive definite kernel. It has a quadratic complexity of O(n 2 ), which is similar to the DTW measure. Definition 1.9 (Global Alignment Kernel). The Global Alignment Kernel (GAK) k GAK between two time series x i and x is defined as

Global Alignment Kernel

k GAK (x i , x ) = w∈W e -Dx i ,x (w) (1.16)
where we consider W as the set of all possible alignments, w as an alignment (of length L), and

D x i ,x (w) = L j=1 φ(x i,π 1 (j) , x ,π 2 (j) ) (1.17)
where φ is a positive-definite kernel.

As DTW, it is possible to use dynamic programming to compute the kernel value. GAK can handle both different lengths and multivariate time series. [START_REF] Cuturi | Fast global alignment kernels[END_REF] later proposed a fast version of this kernel, that considers a smaller subset of admissible alignments. This fast version can be seen as adding global constraints, similar to Sakoe-Chiba band for DTW. Then [START_REF] Cuturi | Soft-DTW: a Differentiable Loss Function for Time-Series[END_REF] build on GAK to propose soft-DTW for time series clustering and prediction, where they compute the soft-minimum of all alignment costs.

Chapter 1. Time Series Classification State-of-the-Art

Summary on (Dis)Similarity Measures

Numerous similarity measures for time series exist, we detailed in this manuscript a small selection of them. Each one of them can be associated with a classifier. A comparison of their characteristics can be found in Table 1.1.

To evaluate the performance (last column of Table 1.1), we compute the one-sided Wilcoxon Signed Rank Test on the University of East Anglia & University of California Riverside (UEA / UCR) database (85 datasets). We use accuracies provided by [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF], on available similarity measures associated with the 1-NN classifier, as shown on Table 1.2. The one-sided Wilcoxon Signed Rank Test is a non-parametric statistical test that can be used to determine if a method is statistically better than another (i.e. p-value < 5%). The number of stars for the performance is assigned based on the number of times the similarity measure is better than the other ones (associated with 1-NN). The number of stars ranges from 0 (the minimum), for measures that are never significantly better than the others (i.e. ED, DDTW), to 3 (the maximum), which corresponds to the best similarity measure (i.e. MSM).

Feature-based Time Series Classifiers

Feature-based methods extract features from time series before the classification step where a classifier can be used on the extracted features. Many different works have been proposed with different kind of features. In this section, we first start by introducing time series representations that are used in the literature. Then, we review the most relevant feature-based time series classifiers. Finally, we present some shapelet-based algorithms.

Time Series Representations

Time series classification can be performed on both raw and transformed time series. The most natural representation of time series is the raw representation, i.e. the ordered list of valued data points. However, there are many tasks for which a representation that highlights some specificities of time series is the most suitable one, e.g. frequency for speech recognition. Due to the wide range of possible applications for time series data, numerous representations have been proposed by the time series community from Fourier and Wavelet Transformations to SIFT-based Representation, through Piecewise Approximations. In the following, we focus on the most wellknown time series representations.

Feature-based Time Series Classifiers

O(n) - - ED O(n) - 999 DTW O(n 2 ) - 899 DDTW O(n 2 ) - 999 EDR O(n 2 ) 1 - ERP O(n 2 ) 1 889 GAK O(n 2 ) 1 - LCSS O(n 2 ) 1 889 MSM O(n 2 ) 1 888 TWED O(n 2 ) 2 889 WDDTW O(n 2 ) 2 899 WDTW O(n 2 ) 2 889

Fourier and Wavelet Transformations

Fourier transformation represents a time series as a sum of sinusoidal functions, whereas wavelet transformation approximates a time series by a set of orthonormal representations. Both Discrete Fourier Transform (DFT) and Discrete Wavelet Transform (DWT) reduce the dimensionality of time series.

Discrete Fourier Transform

The basic idea of DFT is to represent the time series x i as a linear combination of cosines and sines (with amplitudes a, b and phase w), where only the first few coefficients are kept.

x ij = n k=1 (a k cos(2πw k j) + b k cos(2πw k j)) (1.18) DF T (x i ) = < (a 0 , b 0 ), (a 1 , b 1 ), . . . , (a n , b n ) > (1.19)
In order to find the best match of a time series, [START_REF] Agrawal | Efficient similarity search in sequence databases[END_REF] proposed the following process:

1. Obtain the DFT coefficients for every time series of D, 2. Build the multidimensional index using the first few Fourier coefficients of every time series of D,

3.

Perform the similarity search.

The DFT most popular implementation is the Fast Fourier Transform (FFT) proposed by [START_REF] Cooley | An algorithm for the machine calculation of complex fourier series[END_REF], and illustrated in Figure 1.6.

Discrete Wavelet Transform

Wavelet bases are able to represent both frequency and location informations inside a time series [Hastie et al., 2009, Chapter 5]. This is a key advantage compared to Fourier Transform which can only capture frequency information. Wavelets are generated by translations and dilations of a single scaling function ψ(x) (mother wavelet), where translations can be defined by ψ(z) → ψ(z + 1) and dilations by

ψ(z) → ψ(2 • z).
The first proposed DWT is the Haar wavelet, which mother wavelet is

ψ(z) = ⎧ ⎪ ⎨ ⎪ ⎩ 1 for 0 ≤ z < 1 /2 -1 for 1 /2 ≤ z < 1 0 otherwise (1.20)
Let j be the dilation index, k the translation one, the general form is written as

ψ j k (z) = 2 j /2 ψ(2 j z -k) (1.21)
Haar wavelet corresponds to a sequence of continuous square-shaped functions that approximates the time series. Wavelet Transform has been widely used by the time series community. [START_REF] Chan | Efficient time series matching by wavelets[END_REF] proposed an efficient time series indexing method. [START_REF] Wu | A comparison of dft and dwt based similarity search in time-series databases[END_REF] go further and explore DFT and DWT-based similarity seach in time series datasets, where they show that both methods yield comparable results, even if DWT-based methods have lower complexity than DFT ones. [START_REF] Kahveci | Variable length queries for time series data[END_REF] Chapter 1. Time Series Classification State-of-the-Art use wavelets in order to find similar patterns in time series, thanks to the wavelet-based compression of the time series they were able to significantly reduce the computation time without performance loss.

Piecewise Aproximations

Numerous Piecewise Aproximations methods have been proposed in order to reduce the dimensionality of time series, we detail here the most relevant ones. [START_REF] Keogh | Scaling up dynamic time warping for datamining applications[END_REF]; [START_REF] Yi | Fast time sequence indexing for arbitrary lp norms[END_REF] independantly introduced Piecewise Aggregate Aproximation (PAA), a dimensionality reduction technique. The idea is to divide a time series of length n into n segments, then to compute the average of these segments. The main advantages of PAA are the interpretability and the simplicity of the method, PAA is a compression-based technique. [START_REF] Chakrabarti | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF] introduced an extension of PAA called Adaptive Piecewise Constant Aproximation (APCA). It is possible to observe that in some datasets, the time series information is concentrated on specific locations whereas the rest of the time series provides few information (e.g. regarding the separability of classes). In order to take this observation into account, APCA transforms the time series into a set of variable length segments instead of same length segments as PAA does. APCA has two parameters for each segment: its value (the mean of the segment) and its length. APCA is thus more flexible than PAA leading to a better approximation of time series.

Piecewise Aggregate Aproximation

Adaptive Piecewise Constant Aproximation

Piecewise Linear Aproximation

The basic idea of Piecewise Linear Aproximation (PLA, [START_REF] Cameron | Piece-wise linear approximations[END_REF]; [START_REF] Keogh | An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback[END_REF]) is to represent the time series as a sequence of linear segments. Given a time series x i , we seek for an approximate function: PLA( [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF] introduced the Symbolic Aggregate approXimation (SAX) method that converts a time series into a symbolic form representation. The first step of the SAX algorithm is to normalize the data to have zero mean and standard deviation of one. Then to reduce the dimensionality of the time series, the PAA dimensionality reduction technique is applied. The next step is the discretization step: the symbols (corresponding to mean values 1.3. Feature-based Time Series Classifiers 27 included into a specific interval) are selected such that they are equiprobable. The number of symbols is to be determined by the user.

x i ) = a • z + b, with z = [x i,z 1 , x i,z 2 , . . . x i,z k-1 , x i,z k ] and followings the properties: (a) z 1 = 1 (b) z k = n and (c) z i < z i+1 .

Symbolic Aggregate approXimation

Symbolic-Fourier Approximation

The Symbolic-Fourier Approximation (SFA) is a symbolic representation proposed by [START_REF] Schäfer | Sfa: a symbolic fourier approximation and index for similarity search in high dimensional datasets[END_REF]. Its first step consists in approximating all the time series using DFT, then to determine multiple discretisations from all these DFT approximations using the Multiple Coefficient Binning (MCB) discretization technique. The MCB is a data adaptative quantization technique that computes intervals from training samples. In the second step, each DFT approximation is discretized (one by one) using the MCB discretization resulting in a SFA representation of the time series.

SIFT-based Representation

The Scale-Invariant Feature Transform was first introduced in the computer vision community on problems such as recognition tasks, trajectory tracking [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The SIFT algorithm detects and describes local features in images. Local features should correspond to regions of interest and be scale and location invariant. Key location / key points are defined as extrema (minima and maxima) of the Difference of Gaussians (DoG) function, this step can be referred to as Scale-Invariant feature detection. More details on the full algorithm are available in [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. In the following, we present time series representation based on SIFT which are adapted for one-dimensional (1D) data. [START_REF] Xie | A Scale-Invariant Local Descriptor for Event Recognition in 1D Sensor Signals[END_REF] proposed an algorithm that detects keypoints based on DoG detector [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], where each keypoints is represented by a scale-invariant feature descriptor. The general overwiew of the framework can be described by the following steps:

Scale-Invariant Classifier with "R" metric (SIC-R)

1. Keypoints detection [START_REF] Candan | sDTW: Computing DTW Distances Using Locally Relevant Constraints Based on Salient Feature Alignments[END_REF] introduced a new constraint to speed up DTW based on salient features: sDTW. These salient features are identified by a SIFT-like algorithm and then used to restrict the search space of possible warping Chapter 1. Time Series Classification State-of-the-Art paths in DTW. The proposed approach can identify not only the center positions but also the sizes of the features, which is a key advantage in order to find a more precise alignment of time series. Experiments have shown that sDTW helps improving DTW accuracy.

DTW Pruning Constraints based on Salient Feature Alignments

Codebook-based Representations

We previously detailed some of the most relevant time series features representation. In the following we provide some keys on how to simply use these features in order to compare time series.

Codebook-based representations are highly related with the Bag-of-Words (BoW) model. We first start by introducing the BoW model then we detailed some time series classification algorithms using the BoW model (or very similar technique such as Vector Space Model (VSM)). Some previously introduced methods can be associated with a codebook-based representation, e.g. BoP and SAX-VSM that use SAX representation, later another example will be provided in Chapter 2 where we combine 1D SIFT descriptors with a codebook representation.

Bag-of-Words

The BoW model consists in representing an instance using a histogram of word occurrences. Despite the fact that the temporal order of words is ignored, the BoW representation is able to capture high-level structural information using both local and global characteristics. Indeed, the overall representation is built by extracting the sub-sequences from the time series, local (i.e. peaks, valleys) and global (i.e. general shape) characteristics are thus taken into consideration. The BoW ability to quantize the words might lead to information loss, nonetheless it provides some robustness to noise. Many codebook-based representations use the k-means method in order to select k codewords. The selected codewords correspond to cluster centers, and each local feature is assigned to the nearest cluster center. The Bag-of-Words model has been widely used since it can lead to powerful and accurate methods. [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF] proposed the Bag-of-Patterns (BoP) approach which combines the Symbolic Aggregate approXimation (SAX) representation of the time series with the Bag-of-Words technique. In order to extract words from the transformed series, [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF] use a sliding window. Then, they build the 1-NN classifier using frequencies of words within the time series as features. [START_REF] Senin | SAX-VSM: Interpretable Time Series Classification Using SAX and Vector Space Model[END_REF] proposed the SAX-VSM algorithm, which is based on two well-known techniques: SAX and VSM. SAX transforms raw time series into a symbolic representation, then VSM constructs a BoW representation from the symbols. SAX-VSM and BoP have many common characteristics, except that the Term Frequency -Inverse Document Frequency (TF-IDF) is used as a weighting scheme on the SAX-VSM representation (BoP uses no weighting scheme).

Bag-of-Patterns

Feature-based Time Series

Classifiers 29 1.3.2.2 SAX-VSM
More precisely, the first step is to apply the SAX algorithm in order to transform raw time series to a list of SAX words. Time series are then treated as bag-of-SAX-words on which a TF-IDF normalization method is applied. The final step is to create class-characteristic weight vectors that are used for classification of new time series. To do so [START_REF] Senin | SAX-VSM: Interpretable Time Series Classification Using SAX and Vector Space Model[END_REF] look for characteristic subsequences that are representatives of a class (similarly as time series shapelets -introduced later in this chapter) that they use to build a single representation for each class (instead of one per training time series). [START_REF] Baydogan | A Bag-of-Features Framework to Classify Time Series[END_REF] introduced the Time Series Bag-of-Features (TSBF) algorithm. TSBF extracts time series segments of various lengths and positions and generates a codebook of those patterns that will be used to feed the classifier. TSBF can be outlined as follow:

Time Series Bag-of-Features

1. Extract local features from each segment of the time-series, 2. Create a supervised codebook of the features using random forest,

Transform the codebook features collection into a global bag-of-features

representation for each time series (using frequencies), 4. Classify the global bag-of-features representation using a random forest classifier.

TSBF leads to high performance compared to competitive baseline methods.

Bag-of-Words based on Discrete Wavelet Coefficients

Wang et al. [2013a] proposed an algorithm that segments time series into local patterns and measures their frequencies as classification features. Segments of pre-determined length are extracted along the time series using sliding window. The set of segments is then transformed to feature vectors using DWT. Finally the BoW representation of words frequencies is used to feed a Nearest-Neighbors classifier.

Chapter 1. Time Series Classification State-of-the-Art

Bag-of-SFA-Symbols

The Symbolic-Fourier Approximation (SFA) is a symbolic representation used in Bag-of-SFA-Symbols (BOSS) which was introduced by [START_REF] Schäfer | The boss is concerned with time series classification in the presence of noise[END_REF]. BOSS uses the sliding window technique to create SFA words representing the time series then generates a codebook representation from them. Sliding windows split the time series (of length n) in consecutive fixed-length windows (i.e. nw + 1 windows of length w). For consistency, each window s is z-normalized ( s-mean(s) std(s) ) BOSS uses the 1-NN classification on SFA representation. This transformation aims at reducing the noise and at representing the time series as strings. BOSS is fast, robust to noise and obtains high accuracies score on several datasets.

Building on BOSS, Schäfer [2015a] proposed Bag-of-SFA-Symbols in Vector Space (BOSS VS) that can be seen as an enhancement of the BOSS method: BOSS-VS has significantly lower computation complexity. However, BOSS obtains higher performance than BOSS-VS, even if the difference is not significant.

Shapelet-based Algorithms

Time series shapelets were first introduced by Ye and [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF]. A shapelet is a subsequence extracted in a time series that enables one to differentiate the different classes. [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF] proposed a brute force algorithm to build a decision tree classifier where shapelets are chosen amongst all the possible candidates (i.e. the set of all continuous subsequence of the considered length). The chosen shapelets correspond to the candidates that are the most discriminative for the classes.

Definition 1.10 (Dissimilarity measure between a time series and a shapelet). The dissimilarity measure between a time series x i (of length n) and a shapelet s k (of length L (with L < n)) is defined as

d(x i , s k ) = min j=1,...,J 1 L L =1 (x i,j+ -1 -s k, ) 2 (1.22) with J = n -L + 1.
Advantages of shapelets include their interpretability as well as fast classification time. However the shapelet discovery step has a high complexity (i.e. is a time consuming process). The first improvement of the brute force algorithm was proposed by the same authors in [START_REF] Ye | Time series shapelets: A novel technique that allows accurate, interpretable and fast classification[END_REF], where they introduced an early abandon pruning method. Since then, many works have been published on time series shapelets, we review the most relevant ones.

Feature-based Time Series Classifiers

31

Shapelets-based methods are particularly useful when only a subpart of the time series is discriminative, as well as when some subparts of the time series are missing (e.g. objects outline where the object is partially broken). Shapelets-based methods also provide interpretability of the results since it is possible to extract the most discriminative shapelet(s). Methods that extract several shapelets use various discriminative subparts of time series thus generally lead to better performance.

Fast Shapelets

Rakthanmanon and [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF] proposed a fast version of the algorithm in order to reduce the complexity of the original algorithm from [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF]. The main idea for a fast shapelets discovery is to transform high-dimensional time series to a low-dimensional discrete representation. Indeed, it is more efficient to extract information from a smaller representation.

Time series are transformed into a SAX representation. For a given time series, multiple SAX words are generated using the sliding window technique, where each word corresponds to a symbolic representation of a subsequence. In order to compare two time series, [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF] exploit the random projection idea by applying a random mask on the SAX representation. If two time series are similar, then there is a high probability of collisions between their SAX representations (a collision happens when two SAX representations are identical). After r random projections, it is possible to look for the best random projections candidates that maximize the separability of the different categories.

The shapelets candidates are then limited to the raw subsequences of time series corresponding to the best random projections in the SAX representation domain. Then, we apply the same process than the original algorithm on a reduced set of shapelet candidates. Fast shapelets algorithm is faster than the original shapelet algorithm, however its overall accuracy does not differ from the original algorithm. Transform the data by computing the K dissimilarity measures between the time series and the set of selected shapelets. Each time series will be transformed to a set of K features (corresponding to the previously computed distance values)

Shapelet Transform

Transform: N × n -→ N × K (1.23)

Apply decision tree on shapelet transformed time series

The parameters of the model, which are the minimal and the maximal shapelet length as well as the number K of shapelets to be selected, are selected by a simple algorithm provided by [START_REF] Lines | A shapelet transform for time series classification[END_REF].

1.3.3.3 Learning Shapelets [START_REF] Grabocka | Learning time-series shapelets[END_REF] propose to learn the shapelets instead of searching the best one(s) in a set of shapelet candidates, indeed one of the main drawback of the shapelet method from [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF] was the extensive search to find a discriminative shapelet. Grabocka's method offers a significant performance improvement compared to extensive search, moreover it is able to learn the best set of K shapelets. Learning Time series Shapelets (LTS) algorithm is based on a gradient descent method. In order to initialize the shapelets, subseries of length L are extracted from the training time series, then a K-means is performed on them. The shapelets are initialized to fit the K-means cluster centers, then the shapelets are learned iteratively during the learning step. The shapelets are updated by minimizing a classification loss function through the iterations of a gradient descent optimization process. The idea is to jointly learn both the logistic regression weights w and the shapelets S that minimize the classification objective function F:

arg min S,w F(S, w) = arg min S,w N i=1 L(y i , wM i + w 0 ) (1.24)
where L is the classification loss function and M is the matrix representing the distances between a dataset X = {x i } N i=1 and a set of K shapelets S = {s k } K k=1 . The dissimilarity measure between the i-th time series x i and the k-th shapelet s k is written as Ensemble classifiers lead to more accurate and more precise results than single classifier(s) alone. The combination of predictions using various classifiers will be able to get the advantages of the subset of classifiers that are the most well-suited for the considered dataset. This is really useful when no prior information are known about the dataset.

M i,k = d(x i , s k ) = min j=1,...,J 1 L L =1 (x i,j+ -1 -s k, ) 2 (1.25)
Amongst drawbacks, ensemble classifiers have higher computational time and space complexities as well as low interpretability. The time and space complexities grow with the number of classifiers. The total amount of space required by the ensemble corresponds to the sum of space required by each classifier of the ensemble (plus some extra space for the Decision Making Process (DMP)). However, time complexity can be reduced using parallel computing system to the time needed to process the longest time method (plus some extra time for the DMP). Finally, the more classifiers involve in the DMP, the less comprehensible the decision is. Thus, the interpretability decreases with the number of classifiers of the ensemble.

In the time series classification domain, only the stacking approach has been investigated, we thus detail two stacking ensemble classifiers for time series data that combine several classifiers.

Proportional Elastic Ensemble

Proportional Elastic Ensemble (PROP), which was introduced by Lines and [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF], is a combination of nearest neighbour classifiers that use elastic baselines distance measures. PROP merges eleven elastic similarity measures: ED, DTW, DDTW, DTW-CV, DDTW-CV, WDTW, WDDTW, LCSS, ERP, TWED, MSM, where DTW-CV means DTW with Sakoe-Chiba band set through Cross-Validation.

Each classifier (a function associated with the 1-NN classifier) runs independently, then a weighted voting scheme is used for the prediction. [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF] studied four voting schemes, we develop only the one corresponding to the PROP algorithm since it leads to the best performance.

Chapter 1. Time Series Classification State-of-the-Art

The PROPortional voting scheme assigns the weight proportionally to the Cross-Validation accuracy on the training data. PROP significantly outperforms all standalone classifiers compared to in the paper. COTE is an ensemble classifier that contains transformations in time, frequency, change and shapelet domains from 35 standalone classifiers. Each classifier is associated to a weight during the classification step. The higher the accuracy on the training set, the larger the weight.

Collective Of Transformation-based Ensembles

COTE combines:

• Four transformations, in frequency domain with a transformation of data using Power Spectrum and in change domain: three autocorrelation-based approaches. These transformations are associated with eight classifiers

• k-NN

• SVM with linear kernel

• SVM with quadratic kernel

• Naive Bayes

• Bayesian network

• C4.5 decision tree

• Random Forest

• Rotation Forest

• PROP Elastic Ensemble for the time domain (11 classifiers) In COTE, weights are assigned proportionally to the cross-validation accuracy on the training data, as in PROP. COTE is significantly more accurate than competing baselines algorithms and is on average the most accurate algorithm (on UEA / UCR database).

Summary on Time Series Classification Algorithms

Many algorithms have been described, Table 1.3 summarizes the main characteristics of these time series classification algorithms. Performance was evaluated by computing the one-sided Wilcoxon Signed Rank Test on the UEA / UCR database (on 85 datasets) for each classifier, from classification rates provided by [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF]. The computational cost was COTE and PROP are considered to be the more powerful and accurate time series classification algorithms to this day. However since they correspond to sets of classifiers, they have a high computational cost. When no prior information is known, it might be a good choice to use COTE and PROP since they are able to adapt well on different characteristics (e.g. presence or absence of temporal distortions).

Standalone classifiers often offer good performance and might be considered as providing sufficient accuracy for some applications. An algorithm should be choosen carefully depending on: There is no time series classifiers that outperforms all others, however a classifier choosen w.r.t. the dataset characteristics will often lead to higher accuracy than a randomly selected classifier.

Model Selection and Evaluation

Metrics for Evaluating Time Series Classifiers Performance

A wide range of metrics have been proposed, we only provide formulas of the evaluation metrics used in this dissertation. dataset and is also called classification rate. For

D test = {(x i , y i )} N i=1
, where instances from the test set are only used to compute the accuracy and not the prediction:

Accuracy(f ) = | {i|(f (x i ) = y i )} N i=1 | N (1.26)
Definition 1.12 (Error Rate). The error rate, which corresponds to the percentage of misclassified instances, can be expressed as a function of the accuracy:

ER(f ) = 1 -Accuracy(f ) (1.27) 1.6.2 UEA / UCR Database
The University of East Anglia & University of California Riverside (UEA / UCR) time series database [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF][START_REF] Chen | The ucr time series classification archive[END_REF] was built in order to improve the quality of papers using time series data. There are currently 85 datasets available in the UEA / UCR database, compared to 20 at the very beginning. Using all or a subset of them enables one to easily evaluate the performance of an algorithm compared to other methods. The UEA / UCR database does not aim at representing all real-life problems. It provides however a large panel of problems, from very small datasets to larger ones, see In the time series classification literature, the performance of algorithms is often measured on a fixed set of problems that uses separate train and test datasets, such as UEA / UCR database architecture. This database has been used in a large amount of research papers on time series analysis, many time series classification algorithms thus provide classification rates on UEA / UCR datasets. One may consider that a fixed database may not represents all real-life tasks one may encountered thus does not enable one to check if a classifier that works well on a specific database will generalize well on new tasks. That is one the reason why an open call for new time series datasets to fulfill the UCR / UEA database is still open.

The UEA / UCR database provides a large set of datasets with different characteristics. Some of these characteristics are detailed in the paper where the datasets were first introduced, however there is no paper that details characteristics for all the datasets. Datasets may be subject to temporal shifts, temporal distortions, noise, outliers, or sensitive to the order of different events, to abrupt changes, the amplitude taken by the time series values can be important, only a subpart of the time series can be relevant for the classification, etc. There is no classifier than can outperform all others on a large variety of problems with such different characteristics. Each classifier has advantages and drawbacks thus works better on dataset with specific characteristics, a detailed listing of time series dataset characteristics would enables one to better choose a classifier depending on the characteristics of the considered dataset.

Another drawback of the UEA / UCR database is the lack of very large datasets (in terms of number of time series or length). In real-life problems, it is often possible to acquired a large number of time series leading to large dataset (e.g. more than 10000 training time series). It has been shown than the performance depends on the train set size thanks to experiments on synthetic datasets: the larger the training set, the smaller the error rate (e.g. in [START_REF] Wang | Experimental comparison of representation methods and distance measures for time series data[END_REF]). Providing very large real-life datasets might 1.7. Other challenging problems related to Time Series Classification 39 be difficult due to the lack of labels, however it is necessary as it can affect the performance of some methods. Moreover some methods might require more data for an optimal training and thus might be under-estimated on the UEA / UCR datasets.

In Chapter 4, we use two remote sensing time series datasets that contain many time series (500 time series per class) with few datapoints: the length of the time series is 24. These time series have a high intra-class variability. Moreover, time shifts and dilations occur in both datasets. These two remote sensing datasets can be used to enlarge the variety of problems contained in the UEA / UCR database.

Other challenging problems related to Time Series Classification

Time series classification brings up a lots of challenges due to the specificities of time series data, however there are related tasks using time series that are as much as challenging as TSC. In this section, we will briefly review time series challenges that will not be studied in this thesis.

Anomaly Detection

In order to detect anomaly in time series, we have to find outlier points or abnormal subsequences relative to standard data, i.e. to find patterns that do not match with the normal behavior of time series. Anomaly detection in time series has many applications such as realtime monitoring of sensors (e.g. to check patients' health in hospital using ECG) or resource usage (e.g. to track unplanned electricity consumption in winter). Anomaly detection is thus an important topic that can prevent critical situations. Anomaly detection methods can either be supervised, semi-supervised or unsupervised. Supervised techniques can be seen as a special case of binary classification where the labeled data are either normal (0) or abnormal (1). In order to detect anomaly, a typical approach consists to generate a model normal behavior of time series then to look for the subseries / points that do not correspond to the model expectation. An overview of different anomaly detection methods can be found in [START_REF] Chandola | Anomaly detection: A survey[END_REF]; [START_REF] Cheboli | Anomaly detection of time series[END_REF].

Clustering Data clustering [START_REF] Aghabozorgi | Timeseries clustering -a decade review[END_REF][START_REF] Everitt | Cluster Analysis[END_REF], which can be referred to as data partitioning, corresponds to unsupervised classification, it aims at dividing an unlabeled dataset into different homogeneous groups that share common charasteristics. Elements in the same cluster are more similar (e.g. according to a distance measure) to each other than those that belongs to other clusters. The definition of similarity and the number of clusters have a high influence on clustering results, that is 40 Chapter 1. Time Series Classification State-of-the-Art the reason why it should be chosen carefully. Cluster analysis can not be considered as an automatic task, since results of clustering are required to be interpreted, but more as a process extracting knowledge from data. This process can be based on a multi-objective optimization problem in order to obtain relevant and well-separated clusters, in that case the clustering function should both minimize the intra-class variability and maximize the inter-class variability. There are multiple ways and algorithms to separate data into clusters, the most famous one is a centroid-based method called k-means. Time series clustering can be easily applied using k-means on codebook representation for example. Domain Adaptation Domain adaptation problems arise when datasets have different probability distributions. Instead of train and test sets, a source and a target domains are used (D source and D target ). The main purpose here is to transfer the knowledge learned from D source to D target the unknown domain. In classic supervised learning problems, it is assumed that instances of D train and instances of D test follow the same probability distribution P. The goal is thus to learn a classification function f such that it maximizes the accuracy on new unseen data following P. However for domain adaptation problems, instances of D source (respectively instances of D target ) follow the probability distribution P S (respectively P T ), where P S and P T are not equal. The purpose is thus to learn f such that it maximizes the accuracy on new unseen data following P T . f can be trained with instances following P S only ; or from P S and P T (using labeled or unlabeled instances). Domain Adaptation methods can either be supervised, semisupervised or unsupervised depending on the information available on the instances of each domain. Time series domain adaptation problems have been studied in [START_REF] Petitjean | Temporal domain adaptation under time warping[END_REF] where domain adaptation problem stems from the fact that the time series are acquired at two different years.

Summary Time series data comes from many domains and have many applications. Many tasks can be solved using time series data such as anomaly detection, clustering tasks, domain adaptation problems, early classification, forecasting as well as classification. Time series data thus provide challenging problems to solve.

As seen in Chapter 1, numerous approaches for time series classification are based on feature extraction associated with a Bag-of-Words (BoW) representation of these features. This can be easily explained by the fact that there exists many possibilities for feature extraction in time series, where some are based on symbolic representation (e.g. SAX) while others rely on the neighborhood of keypoints (e.g. Scale-Invariant Feature Transform (SIFT)). SIFT feature extraction framework has led to widely used descriptors thanks to its efficiency and effectiveness in image classification. Moreover, SIFT features are easily adaptable from 2D (for image) to 1D features (for time series), making SIFT a reasonable choice for feature representation of time series. Finally, the BoW representation has proved its robustness to noise, its easiness of use as well as its capability to help building highly accurate methods thanks to its ability to capture both local and global information.

In this chapter, we propose a new time series classification algorithm, that builds on two well-known and powerful methods in computer vision: local features which are extracted from time series using a SIFT-based approach, and a global representation of time series using these features which is produced using the BoW technique.

Related Work

This section first introduces the SIFT feature extraction framework proposed by [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], then introduces key notions related to the BoW technique.

Scale-Invariant Feature Transform

SIFT was first introduced by [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF][START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] in the computer vision community for image matching task. In order to be effective, the feature transform should follow some useful characteristics such as: (a) Scale Invariance, (b) Rotation Invariance, (c) Illumination Invariance, (d) Viewpoint Invariance. SIFT identify a large number of interest points in both locations and scales e.g. Figure 2.1. These keypoints are both distinctive and invariant and can be found even if the point of view of the object changes. The adaptation of SIFT framework from 2D to 1D requires some simplification in particular there is no need for illumination and rotation invariances for time series data. 1D SIFT only has to be scale and location invariant.

The overall 2D SIFT feature extraction framework can be divided into several steps:

1. Scale space computation 2. Location of keypoints

Scale Space Computation

The first step is to compute the scale space. To efficiently find the key locations in images, [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] proposes to use the Difference-of-Gaussians (DoG) function to detect scale-space extrema in the scale space. This can be easily done by computing a pyramid of smoothed, convoluted images. Let L(x, y, σ) be the convolution ( * ) of an image I(x, y) with a Gaussian function G(x, y, σ) of width σ L(x, y, σ) = G(x, y, σ) * I(x, y)

(2.1)

where G(x, y, σ) is equal to

G(x, y, σ) = 1 2π σ 2 e -(x 2 +y 2 )/2σ 2 .
(2.

2)

The DoG function is defined as

D(x, y, σ) = (G(x, y, k sc σ) -G(x, y, σ)) * I(x, y) (2.3) = L(x, y, k sc σ) -L(x, y, σ), (2.4)
where k sc is a parameter of the method that controls the scale ratio between two consecutive scales. The DoG function is particularly efficient to compute: an image substraction is applied on convoluted images. Moreover, the detected extrema have stable location accross images.

Location of Keypoints Keypoints correspond to DoG extrema, selection of keypoints based on the extrema of a scale-space representation is a reliable method to detect events that persist over large changes in scale [START_REF] Mikolajczyk | Detection of local features invariant to affines transformations[END_REF]. In order to locate them on the scale space, each pixel is compared with its neighbors. For images, each pixel has 8 neighbors on the same level and 9 on the above and below levels. If a pixel is a maximum or a minimum amongst all its neighbors then it is selected as a key location. Since most of the pixels are eliminated within a few comparisons, the detection of keypoints has a small cost. Keypoints detection is illustrated in Figure 2.1, where each arrow represents a keypoint and its main orientation.

Construction of the Keypoint Descriptors

Keypoint descriptors correspond to local gradients. They are measured at the selected scale around each keypoint. Their construction ensures stable location, scale and orientation for each keypoints, as well as robustness against small local shifts. 3 -SIFT -Keypoint Description [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] each arrow corresponds to the sum of the gradient magnitudes in the region around. For efficiency, [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] proposes to use precomputed gradients from the pyramid that were used for key locations detection. Neighbors are separated into different regions then each region are represented by a histogram of n b bins of size a. Keypoint descriptors are then used to generate codewords that will form a codebook. The codewords can be seen as approximations of the keypoint descriptors.

Dense Extraction Dense SIFT has been proposed as an extension to the SIFT framework. The idea is to create a codebook which is not based on key location but based on dense sampling. Dense sampling extracts keypoints at regular positions and scales in both location and scale instead of scale space extrema. Thus dense sampling can be seen as applying a regular grid on an image and in our case repeating this process over multiple scale. [START_REF] Jurie | Creating efficient codebooks for visual recognition[END_REF]; [START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF] showed that dense representation consistently outperforms equivalent keypoint representation. [START_REF] Liu | Sift flow: Dense correspondence across different scenes[END_REF] were the first to propose a Dense SIFT version for image alignment and registration, later [START_REF] Vedaldi | Vlfeat: An open and portable library of computer vision algorithms[END_REF] proposed a fast algorithm for the computation of a dense set of SIFT descriptors. Dense sampling outperforms equivalent keypoint representation, however it also produces a very large number of features, which slows down the overall computation since features need to be computed and compared.

Bag-of-Words

The Bag-of-Words model consists in representing documents using a histogram of word occurrences. It is a very common technique in text mining, information retrieval and content-based image retrieval because of its simplicity and performance. The latter can be explained by the fact that the BoW representation is able to capture both local and global structure sim-48 Chapter 2. TSC based on Local Features Representation ilarity information, despite the fact that the location of words is ignored. Another advantage of the BoW representation is its robustness to noise. However since it quantizes words, it might lead to information loss. For large images, it is often more appropriate to consider the similarity between data based on higher-level structures such as histogram or featurebased representations instead of raw data. For images, classifiers using BoW representation are based on the following operations: first converting images into words, then computing a histogram of words occurrences and finally building a classifier upon this histogram representation. Standard techniques such as Random Forests, Support Vector Machines (SVM) or k-Nearest-Neighbors (k-NN) can be used for the classification step.

BoW normalization Dense sampling on multiple Gaussian-filtered data provides considerable information to process. It also tends to generate words with little informative power, as stop words do in text mining applications. In order to reduce the impact of those words, there exists several normalization schemes for BoW, such as Signed Square Root normalization (SSR) and Term Frequency -Inverse Document Frequency normalization (TF-IDF). In order to obtain the SSR-normalized representation, the sign square root function is applied to each element z of an unnormalized BoW representation (sign(z)• |z| ). TF-IDF is a weighting method that measures how important is a term comparatively to the full term collection. TF-IDF normalization can be divided into two steps: first increase the weight term proportionally to the frequency of the term in the document, then weight down the frequent terms and scale up the rare ones from the full term collection. Both SSR and TF-IDF normalizations are commonly used in image retrieval and classification based on histograms such as in [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of pca and whitening[END_REF][START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF][START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF][START_REF] Sivic | Video google: A text retrieval approach to object matching in videos[END_REF]. [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF] showed that reducing the influence of frequent codewords before L 2 normalization could be profitable. They apply a power α ∈ [0, 1] on their global representation. SSR normalization corresponds to the case where α = 0.5. TF-IDF normalization also tends to lower the influence of frequent codewords. To do so, document frequency of words is computed as the number of training time series in which the word occurs. BoW are then updated by diving each component by its associated document frequency. In the following, SSR and TF-IDF are both applied before L 2 normalization.

(Dense) Bag-of-Temporal-SIFT-Words Algorithm

2.2 (Dense) Bag-of-Temporal-SIFT-Words Algorithm

In the following, Dense Bag-of-Temporal-SIFT-Words (D-BoTSW) corresponds to the dense keypoints extraction, whereas BoTSW corresponds to the scale space extrema detection. D-BoTSW can be seen as the extended and improved version of BoTSW.

Both methods are based on three main steps: (a) extraction of keypoints in time series, (b) description of these keypoints through gradient magnitude at a specific scale, (c) BoW representation of time series, where words correspond to quantized version of the description of keypoints. These steps are depicted in Figure 2.6 (dense version) and detailed below.

The Bag-of-Patterns [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF] and the BOSS [START_REF] Schäfer | The boss is concerned with time series classification in the presence of noise[END_REF] algorithms are two works close to D-BoTSW. Indeed, they both extract features that are used in a histogram representation. The main difference with D-BoTSW is that the feature are discrete for both BoP and BOSS, whereas descriptive features in D-BoTSW are real-valued.

Keypoints extraction in time series

The first step of our method consists in extracting keypoints in time series. Two approaches are described here: the first one is based on scalespace extrema detection [START_REF] Bailly | Bag-of-Temporal-SIFT-Words for Time Series Classification[END_REF]) and the second one proposes a dense extraction scheme (Bailly et al. [2016a,b]).

Scale-space extrema detection

The 2D SIFT framework is transformed to fit 1D time series data. Keypoints in time series can be detected as local extrema in terms of both scale and (temporal) location. These keypoints are important sub-part of time series, since they correspond to extrema at a specific scale. They are often detected near time series extrema, as shown on Figure 2.4.

The scale-space extrema are identified using a DoG function, and form a list of scale-invariant keypoints. Let L(t, σ) be the convolution ( * ) of a time series S(t) with a Gaussian function G(t, σ) of width σ:

L(t, σ) = S(t) * G(t, σ) (2.5)
where G(t, σ) is defined as Figure 2.5 -Detection of extrema using Difference-of-Gaussians function.

G(t, σ) = 1 √ 2π σ e -t 2 /2σ 2 . ( 2
On the left, the considered point (in red) is not an extrema compared to its neighbors (in green). On the right, the considered point is the minima amongst its neighborhood, it is thus a selected keypoint. The different scales are represented by the grey gradient.

(Dense) Bag-of-Temporal-SIFT-Words Algorithm

51 [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] proposes the Difference-of-Gaussians (DoG) function to detect scale-space extrema in images. Adapted to time series, a DoG function is obtained by subtracting two time series filtered at consecutive scales:

D(t, σ) = L(t, k sc σ) -L(t, σ), (2.7)
where k sc is a parameter of the method that controls the scale ratio between two consecutive scales. Keypoints are then detected at time index t in scale j if they correspond to extrema of D(t, k sc j σ 0 ) in both time and scale, where σ 0 is the bandwidth of the Gaussian corresponding to the reference scale. At a given scale, each point has two neighbors: one at the previous and one at the following time instant. Points also have six more neighbors: three one scale up and three others one scale down (at the previous, same and next time instants), leading to a total of eight neighbors, as shown in Figure 2.5. If a point is higher (or lower) than all of its neighbors, it is considered as an extremum in the scale-space domain and hence a keypoint. Figure 2.4 shows an example of the scale-space extrema detection, where keypoints are detected near local extrema.

Dense extraction

Previous works have shown that better classification could be achieved by using densely extracted local features [START_REF] Jurie | Creating efficient codebooks for visual recognition[END_REF][START_REF] Wang | Evaluation of local spatio-temporal features for action recognition[END_REF]] at regular step. In this section, we present the adaptation of this setup to our BoTSW scheme. Keypoints selected with dense extraction no longer correspond to extrema but are rather systematically extracted at all scales every τ step time steps on Gaussian-filtered time series L(•, k sc j σ 0 ). Unlike scale-space extrema detection, regular sampling guarantees a minimal amount of keypoints per time series. This is especially crucial for smooth time series from which very few keypoints are detected when using scale-space extrema detection. In all cases, description of these keypoints covers the description of scale-space extrema if τ step is small enough, which leads to a more robust representation. A dense extraction scheme is represented in Figure 2.6.

Description of the extracted keypoints

Next step in our process is the description of keypoints. A keypoint at time index t and scale j is described by gradient magnitudes of L(•, k sc j σ 0 ) around t. To do so, n b blocks of size a are selected around the keypoint. Gradients are computed at each point of each block and weighted using a Gaussian window of standard deviation a×n b 2 so that points that are farther in time from the detected keypoint have lower influence. Then, each block

(Dense) Bag-of-Temporal-SIFT-Words Algorithm

53 is described by two values: the sum of positive gradients and the sum of negative gradients. Resulting feature vector is hence of dimension 2 × n b .

(Dense) Bag-of-Temporal-SIFT-Words for Time Series Classification

Training features are used to learn a codebook of k words, where we apply a k-means clustering on all the features extracted from the whole set of training time series. Words represent different local behaviors in time series. Then, for a given time series, each feature vector is assigned the closest word in the codebook. The number of occurrences of each word in a time series is computed. (D-)BoTSW representation of a time series is the normalized histogram of word occurrences.

Bag-of-Words normalization

It has been shown that Bag-of-Words normalizations on dense sampling lead to higher accuracy of the model. Indeed the normalizations reduce the impact of words with little informative power, leading to more stable representation. We show in the experimental part that using BoW normalizations helps improving the accuracy of D-BoTSW. The normalized histograms finally feed a classifier (Linear SVM) that learns how to discriminate classes from this BoW representation.

Complexity study

The process of computing (D-)BoTSW representation for a time series has linear time complexity in the number of features extracted. When using scale space extrema detection (BoTSW), this number mainly depends on the data. For some datasets we might detect very few features, whereas for other datasets we extract much more features. It is thus complicated to evaluate the complexity of BoTSW. When using dense extraction (D-BoTSW), this number depends on the length of the time series. For a time series of length n, features will be computed at n/τ step different time instants. At each time instant, features will be computed at all scales and the number of scales is log(n/8σ 0 ) log ksc . Finally, time complexity of computing D-BoTSW for a time series of length n is in O (n log n). SIFT framework is effective, efficient and provides features that are robust and invariant. Yet for smoothed data with the scale space extrema detection, few key locations will be detected leading to poorly represented data. Dense sampling solves this problem by extracting keypoints at regular locations, which guarantees a minimal amount of keypoints. However since the number of keypoints grows with the time series length and the time step, dense sampling can lead to a very large number of features for large datasets, which requires larger storage space, and which slows down the time computation for the codewords generation step.

Pros and cons of (D-)BoTSW

The Bag-of-Words representation has many advantages such as its robustness to noise and its ability to handle temporal shifts. Nevertheless, the BoW representation causes information loss during the quantization step. In most cases, this information loss will have no impact, however in datasets that contain very similar classes the information loss might lead to similar BoW representation for distinct classes (thus lead to poor performance). Another facet to take into account is that BoW representation ignores the temporal order of words. For datasets where ordering of events matter, it is adviced not to use a time series classification algorithm using a BoW representation such as (D-)BoTSW. In other to tackle this ordering issue, we [START_REF] Tavenard | Efficient Temporal Kernels between Feature Sets for Time Series Classification[END_REF] use temporal kernels between feature sets ; this paper can be seen as an extension of D-BoTSW but will not be detailed in this manuscript.

D-BoTSW longest step corresponds to the k-means learning process and the fitting of the linear SVM classifier, since dense extraction, features description and transformation to BoW representation can be done efficiently ; D-BoTSW is thus able to fastly classify new data.

Finally, it is possible to visualized the model generated by D-BoTSW. This model consists of the descriptive features and the histogram representation. They can be used together in order to see the most important features for each class and thus offer some interpretability of the results. An illustration of this interpretability is provided in Chapter 4.

Experiments on UCR/UEA datasets

In this section, we investigate the impact of both dense extraction of keypoints and normalizations of the Bag-of-Words on classification performance. We then compare our results to the ones obtained by 9 relevant baselines.

Experiments are conducted on the 85 currently available datasets from the UEA / UCR repository [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF].

Experiments on UCR/UEA datasets 55

For the sake of reproducibility, C++ source code used for (D-)BoTSW in these experiments is made available for download 1 , and all raw numbers are available in Appendix A. To provide illustrative timings for our method (D-BoTSW), we ran it on a personal computer (laptop with 2.70GHz CPU and 16 GB RAM), for a given set of parameters, using dataset Cricket_X [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF] that is made of 390 training time series and 390 test ones. Each time series in the dataset is of length 300. Extraction and description of dense keypoints take around 2 seconds for all time series in the dataset. Then, 75 seconds are necessary to learn a k-means and fit a linear SVM classifier using training data only. Finally, classification of all D-BoTSW corresponding to test time series takes less than 1 second. Note that the time computation could be reduced by sub-sampling the amount of features to learn the codewords in the k-means.

Experimental setup

Parameters a, n b , k and C SVM of (D-)BoTSW are learned by Cross-Validation (CV), whereas we set σ 0 = 1.6 and k sc = 2 1/3 , as these values have shown to produce stable results [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Parameters a, n b , k and C SVM vary inside the following sets: {4, 8}, {4, 8, 12, 16, 20}, 2 i , ∀i ∈ {5..10} and {1, 10, 100} respectively. A linear SVM is used to classify time series represented as (D-)BoTSW. For our approach, the best sets (in terms of accuracy) of (a, n b , k, C SVM ) parameters are selected by performing cross-validation on the training set. Due to the heterogeneity of the datasets, leave-one-out cross-validation is performed on datasets where the training set contains less than 300 time series, and 10-fold cross-validation is used otherwise. These best sets of parameters are then used to build the classifier on the training set and evaluate it on the test set. For datasets with little training data, it is likely that several sets of parameters yield best performance during the cross-validation process. For example, when using DiatomSiz-eReduction dataset, BoTSW has 150 out of 180 parameter sets yielding best performance, while there are 42 such sets for D-BoTSW with SSR normalization. In both cases, the number of best parameter sets is too high to allow a fair parameter selection. When this happens, we keep all parameter sets with best performance at training and perform a majority voting between their outputs at test time.

Parameters a and n b both influence the descriptions of the keypoints; different datasets will required different settings of these parameters thus their optimal values should be chosen carefully for each dataset in order the description of keypoints to fit the shape of the data. If the data contains sharp peaks, the size of the neighborhood on which features are computed (equal to a × n b ) should be small. On the contrary, if it contains smooth

Chapter 2. TSC based on Local Features Representation

peaks, descriptions should take more points into account. The number k of codewords needs to be large enough to represent precisely the different features. However, it needs to be small enough in order to avoid overfitting (especially for datasets with only few training time series). We consequently allow a large range of values for k to better take into account the heterogeneity of the UEA / UCR database.

For all experiments with dense extraction, we set τ step = 1, and we extract keypoints at all scales. Using such a value for τ step enables one to have a sufficient number of keypoints even for small time series, and guarantees that keypoint neighborhoods overlap so that all subparts of the time series are described.

Comparison of Dense Extraction and Scale-Space Extrema Detection

Figure 2.7 shows a pairwise comparison of error rates between BoTSW and its dense counterpart D-BoTSW for all datasets in the UEA / UCR repository. A point on the diagonal means that methods obtain equal error rates (•). A point above the diagonal illustrates a dataset for which D-BoTSW outperforms BoTSW ( ), whereas a point below the diagonal illustrates a dataset for which D-BoTSW is outperformed by BoTSW ( ). The further a point is from the diagonal, the larger the difference is. Win/Tie/Lose scores is given in the bottom-right corner of the figure. D-BoTSW reaches better performance than BoTSW on 66 datasets, equivalent performance on 6 datasets and worse on 13 datasets. One-sided Wilcoxon signed rank test is also used to compare the methods, if the p-value is less than the 5% significance level, one of the method is considered as significantly better than the other one, e.g. Figure 2.7 shows that D-BOTSW (L 2 ) is significantly better than BoTSW (L 2 ) (p < 5%). The dense sampling version, D-BoTSW, improves classification rate on a large majority of datasets compared to the scale space extrema detection version. In the following, we show how to further improve these results thanks to BoW normalization.

Experiments have shown that scale space extrema detection did not always provide keypoints on time series. It happens in Adiac dataset where BoTSW has an error rate of 51.9% and it drops down to a 25.1% error rate using the dense version D-BoTSW thanks to additional keypoints.

Impact on Bag-of-Words normalization

The BoW representation was L 2 -normalized for BoTSW, we keep this normalization for D-BoTSW. Since [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF] showed that reducing the influence of frequent codewords before L 2 normalization could be profitable, we study the impact of both the Signed Square Root (SSR) and the Inverse Document Frequency (IDF) normalizations prior the L 2 normalization for our codebook.

As can be seen in Figure 2.8, the SSR normalization improves classification performance, the IDF however does not improve it. Lowering the influence of largely-represented codewords using SSR normalization hence leads to more accurate classification with D-BoTSW. SSR normalization significantly improves classification accuracy. This is backed by Figure 2.9, which shows that SSR normalization tends to spread energy across BoW dimensions, leading to a more balanced representation than other two normalization schemes.

Empirical comparison with State-of-the-Art techniques

In the following, we will consider a SSR-normalized D-BoTSW, since this setup is the one providing the best classification performance. We now compare our D-BoTSW to the most popular state-of-the-art methods for time series classification. All time series classification algorithms used here are detailed in Chapter 1. The UEA / UCR repository provides error rates for the 85 datasets with Euclidean distance 1-NN (ED-NN) and Dynamic Time Warping 1-NN (DTW-NN) [START_REF] Ratanamahatana | Everything you know about dynamic time warping is wrong[END_REF]. Numerical performance values on UEA / UCR database are available in Appendix A. In order to check if a method is significantly better than another, we provide Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

Experiments on UCR/UEA datasets

D-BoTSW is significantly better than

BoP (p = 0.000) D-BoTSW is significantly better than DTW-NN (p = 0.000) D-BoTSW is significantly better than ED-NN (p = 0.000) D-BoTSW is significantly better than LTS (p = 0.000) D-BoTSW is significantly better than SAXVSM (p = 0.000) D-BoTSW is significantly better than TSBF (p = 0.005) D-BoTSW is not significantly better than PROP (p = 0.218) D-BoTSW is not significantly better than SMTS (p = 0.173) BOSS is not significantly better than D-BoTSW (p = 0.139)

COTE is significantly better than D-BoTSW (p = 0.000) Table 2.1 -D-BoTSW -One sided Wilcoxon Test p-values. If the p-value is less than the 5% significance level, the method is considered significantly better than the one it is compared to.

the p-values of the one-sided Wilcoxon signed rank test in Table 2.1.

We use published error rates on 85 datasets from [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF] for the following time series classification algorithms: BoP [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF], BOSS [START_REF] Schäfer | The boss is concerned with time series classification in the presence of noise[END_REF], COTE [START_REF] Bagnall | Time-series classification with COTE: the collective of transformation-based ensembles[END_REF], LTS [START_REF] Grabocka | Learning time-series shapelets[END_REF], PROP [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF], SAX-VSM [START_REF] Senin | SAX-VSM: Interpretable Time Series Classification Using SAX and Vector Space Model[END_REF] and TSBF [START_REF] Baydogan | A Bag-of-Features Framework to Classify Time Series[END_REF] ; as well as published error rates for the SMTS method (45 datasets) [START_REF] Baydogan | Learning a symbolic representation for multivariate time series classification[END_REF]]. 2.10 & 2.11 show that D-BoTSW performs better than 1NN combined with ED (ED-NN) or DTW (DTW-NN), BoP, LTS SAX-VSM and TSBF ; and that this difference is statistically significant. Indeed the one-sided Wilcoxon signed rank test has a p-value of p < 5% for all the methods mentioned above. D-BoTSW also performs better than SMTS, however the difference is not statistically significance (p = 0.173). We can also notice from Figure 2.11 that BOSS and D-BoTSW have comparable Win/Tie/Lose performance. Note that, if D-BoTSW is not significantly better than BOSS (p = 0.862), the reverse is also true (p = 0.139).

On Standalone Classifiers

It is striking to realize that D-BoTSW not only improves classification accuracy, but might improve it considerably. Error rate on Shapelet Sim dataset drops from 0.495 (ED-NN) and 0.348 (DTW-NN) to 0 (D-BoTSW), for example. Pairwise comparisons of methods show that D-BoTSW is significantly better than almost all state-of-the-art standalone classifiers (i.e. better than 7 out of 8 tested baselines).

With Ensemble Classifiers

In Figure 2.12, we compare our standalone classifier D-BoTSW to two ensemble classifiers: PROP and COTE. PROP and COTE are considered to be the best time series classifiers (in terms of performance). Wilcoxon tests show that COTE outperforms D-BoTSW (p = 0.0 < 5%). However neither D-BoTSW nor PROP is significantly better than the other. It is more than satisfactory to obtain a higher classification rates on more datasets than PROP, with a Win/Tie/Lose of 48/2/36 in favor of D-BoTSW.

Further work based on a more precise representation than the BoW one could lead to a more competitive algorithm, and might even be significantly better than PROP. Moreover, ensemble classifiers can benefit from the design of new standalone classifiers such as D-BoTSW.

Experiments on UCR/UEA datasets

Discussion

We noticed that D-BoTSW performs especially well in the presence of sufficiently long time series. On the contrary, when faced with short training time series e.g. ItalyPowerDemand (of length 24), it is more likely (though still a minority) that non-parametric methods such as DTW-NN or ED-NN are competitive against D-BoTSW. This can be easily explained by the fact that D-BoTSW rely on the notion of neighborhood and on the number of keypoints per time series, which are related with a time series length.

On one hand, D-BoTSW has proven its robustness to noise e.g. on simulated UEA / UCR datasets such as CBF, synthetic_control and Two_Patterns. On the other hand, D-BoTSW limitations can be seen on datasets where it is difficult to distinguish the different classes such as Wine (2 classes) and OliveOil (4 classes) as shown on Figure 2.13. Concerning the dense sampling of D-BoTSW, some experiments with very large train set were not able to run on a personal computer due to the amount of space required by the generated features, using a computing cluster with more memory fixed this problem.

D-BoTSW exhibits high accuracy and high performance on a large set of datasets. These experiments, conducted on a wide variety of time series datasets, show that D-BoTSW significantly outperforms most considered standalone classifiers. [2009], are a family of time series classification algorithms relying on local shape-based similarity. Amongst them, the Shapelets Transform [START_REF] Lines | A shapelet transform for time series classification[END_REF] and the Learning Time Series Shapelets [START_REF] Grabocka | Learning time-series shapelets[END_REF] methods are the most competitive w.r.t. the state-of-the-art time series classification baselines.

IMPROVING TIME SERIES SHAPELETS BASED ON ADVERSARIAL EXAMPLES Contents

Convolutional Neural Networks (CNNs) are a family of neural networks that exploits the local spatial correlation present in natural images. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] showed that neural networks can be fooled by adversarial examples which correspond to close-to-original synthetic data for which the network fails to predict the right class label. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] and [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] both proposed a methodology that uses adversarial examples in order to generate more robust classifiers. Indeed, one property of adversarial examples is that they can provide an additional regularization benefit.

In this chapter, we propose an enhancement of the Learning Time Series Shapelets algorithm [START_REF] Grabocka | Learning time-series shapelets[END_REF] based on the insertion of adversarial time series in the training procedure. We first introduce the different key concepts we built on, then show how they can be related to each other. Finally, we present our proposed method first theoretically then experimentally.

Related Work

Our approach for time series classification , which is named Adversarially-Built Shapelets (ABS), builds on three techniques from machine learning and deep learning communities. The classifier Learning Time series Shapelets (LTS) proposed by [START_REF] Grabocka | Learning time-series shapelets[END_REF] learns time series shapelets that will be used to predict the class labels of new data. In order to improve this method, we (a) make the link between the LTS algorithm and CNNs [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF][START_REF] Lecun | Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks[END_REF], (b) use a regularization method specific to CNNs (i.e. adversarial training [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF][START_REF] Szegedy | Intriguing properties of neural networks[END_REF]), (c) show that this regularization also works for the LTS model.

On Learning Time Series Shapelets

Details about time series shapelets baselines are available in Chapter 1. We focus here on the LTS algorithm [START_REF] Grabocka | Learning time-series shapelets[END_REF], which learns the shapelets instead of looking for them.

LTS is based on logistic regression where both the weights of the logistic regression and the shapelet coefficients are learned and updated through the iterations of a gradient descent process. The process can be seen as the

Related Work

69 following: at each iteration, the time series is represented by a feature vector corresponding to the similarity between the time series and the different shapelets. Then, a logistic regression is applied in order to get the prediction for the time series. The LTS method learns the K best shapelets.

More precisely, it starts by initializing the shapelets to K-means cluster centers of all the sub-series of length L extracted from the training time series. Then, the shapelets are updated (learned) by minimizing a classification loss function through the iterations of a gradient descent optimization process. The idea is to jointly learn both the weights of the logistic regression w and the shapelets S that minimize the following classification objective function F:

arg min S,w F(S, w) = arg min S,w N i=1 L(y i , wM i + b) (3.1)
where

• L is the classification loss function, defined as

L(y i , wM i +b) = -y i •ln σ(wM i +b) +(1-y i )•ln 1-σ(wM i +b) (3.2)
• M is the N × K matrix representing the distances between a dataset X = {x i } N i=1 and a set of K shapelets S = {s k } K k=1 . The dissimilarity measure between the i-th time series x i and the k-th shapelet s k is computed as

M i,k = d(x i , s k ) = min j=1,...,J 1 L L =1 (x i,j+ -1 -s k, ) 2 (3.3)
where d(x i , s k ) corresponds to the minimal distance between a time series x i (of length n) and a shapelet s k (of length L) and J = n-L+1.

For a specific time series x i , the objective function is defined as

F i = L(θ|x i , y i ) + λ W N K k=1 w 2 k (3.4) with θ = (w, b).
This approach offers a significant improvement in term of accuracy compared to approaches searching shapelets. It is also the first shapelet-based method which actually learns the shapelets instead of searching them.

On Convolutional Neural Networks

Neural Networks Classifiers

Also called artificial neural networks, they are systems based on highly connected nodes (neurons) often organized in layers and are inspired by There exists several types of architecture of neural networks, we only detail the one used in this manuscript: the CNN model. A neuron is the elementary unit of a artificial neural network, it is connected to input sources (such as other neurons) and returns a new information as output. Each neuron of a layer performs a transformation on its inputs (α 1 , . . . , α K ). Each input is associated with a weight coefficient and the neuron considers the weighted sum of its inputs: b + K k=1 w k α k (with b the bias coefficient) as the input of an activation function g. The output of a neuron will thus be (see Figure 3.2)

α 1 α 2 . . . α K 1 a w 1 w 2 w K w 0 with a = g(w 0 + k w k • α k )
a = g(b + K k=1 w k α k ) (3.5)
The activation function g is usually a non-linear function, such as the following sigmoid function The activation functions have different characteristics and properties, e.g. the sigmoid function is differentiable which can be useful. Both ReLu and sigmoid function gives intermediate values, it is not always the case (e.g. the binary step activation function that returns 0 for z < 0 and 1 otherwise).

g(z) = σ(z) = 1 1 -e -z , ( 3
Once the model is learned, the network is able to perform fast classification. Neural networks perform well on a wide variety of problems (e.g. images, speech, and time series classification [START_REF] Lecun | Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks[END_REF]) and can thus be found in many domains. However, due to their complexity (e.g. number of parameters, layers) they are often seen and used as black boxes; e.g. AlexNet [START_REF] Krizhevsky | Imagenet classification with deep convolutional neural networks[END_REF] has 60 millions of parameters, it is thus nearly impossible to determine the most discriminative features by studying the weights of multiple layers.

Neural networks exist in many form such as Convolutional Neural Networks (CNNs), which have been successfully applied for image recognition and classification. These networks are invariant to small transformations, distortions as well as translations. Each CNN is built on a set of three types of layers: (a) Convolution, (b) Pooling, (c) Fully Connected.

Convolution Layer

The primary purpose of convolution is to extract features from the input image using different filters. The number of filters as well as their size are defined by the user.

Let us consider a grayscale image represented by a 2D matrix of pixels. In order to obtain the features of an image, we apply a convolution between the image and a smaller matrix: the filter. The result obtained by the convolution of the image with the filter is called feature map. Since the image and the filter have different sizes, we extract sub-regions of the image using the sliding window technique, as shown on neighboring pixels of an image. Each convolution provides one feature that corresponds to the dot product between the filter and the sub-region (on which we apply an activation function g). The convolution thus preserves the spatial relationship between neighboring pixels by learning features using sub-regions of the image.

Different filters will have different effects since they detect different characteristics from an image. Some filters can blur the visual aspect of an image (e.g. gaussian filter), whereas different filters will sharpen it or detect its edges. Different filters will thus result in different feature maps. The filters will be learned by the CNN during the training process.

Pooling Layer

Pooling is also referred to as subsampling since it reduces the dimensionality of each feature map in order to retain the most important information. There exists different types of pooling: max, average, min, etc, that respectively takes the larger, the average, the smaller feature value amongst the considered sub-region of the feature map. The pooling operation has several benefits, such as reducing the number of parameters of the network and making the model more robust (e.g. invariant to small deformations).

Fully Connected Layer

Fully connected layers are used to predict the class label of an input image, which convolution and pooling layers can not do. There is thus at least one fully connected layer at the end of a CNN to perform the classification. Fully connected layers join each neurons from its layer to every neurons from the previous layer, in order to use features generated by convolution and pooling layers to classify the input data. The predictions correspond to probabilities of belonging to a specific class, thus the sum of all proba-Figure 3.5 -Examples of Adversarial Image. From left to right: an original image I, a perturbation η and its adversarial image Ĩ = I + η. On the first line, the image originally classified as a panda (with 60% level confidence) is slightly perturbed then labeled by the same network as some monkey (with 99% level confidence) [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]. The second line shows an image originally classified as a kitten and with an adversarial peer labeled as a goldfish by the same network1 . bilities in the output layer will be one. Finally, the network assigns to the input image the class that has the highest probability among all possible categories.

On Figure 3.4, we can see an input image processed by a CNN which has one convolutional layer with three filters, followed by a pooling layer, and where the network has to choose between five classes. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] showed that applying a visually imperceptible perturbation on an image could cause a neural network (and several other machine learning models) to misclassify an image, which is correctly classified without the perturbation, as illustrated on Figure 3.5. This perturbed image is referred to as an adversarial example.

On Adversarial Examples

Deep neural networks have retained a lot of attention due to their efficiency and high performance on classification tasks. It could be expected from such networks to be robust to small changes of their input. However, a perturbation can be applied on an image in order to fool the network. This perturbation can be generated using a deterministic process that maximizes

Chapter 3. Improving TS Shapelets based on Adversarial Examples

the prediction error of the network.

Let f N be a neural network such that it takes a n × image I as input and outputs a class label amongst m possible categories, f N : R n× -→ {1, . . . , m}.

To find an adversarial image for the image I using a n × perturbation η, the idea is to minimize η 2 such that the adversarial image is misclassified:

f N (I + η) = f N (I).
As long as η ∞ < , with sufficiently small for the perturbation to be imperceptible, we expect the classifier to predict the same class label for both I and Ĩ.

The existence of adversarial examples is due to the fact that deep neural networks are not smooth classifiers i.e. classifiers with smooth decision boundaries. As adversarial examples are often shared by different networks, [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] show that they correspond to low-probability pockets in the decision space and are caused by linear behavior in high dimensional spaces. Informally, adversarial examples are improbable data. However, they expose some important flaws in the model and more particularly in how the model makes its predictions. These low-probability pockets are of particular interest for our purpose as they can help regularize the model, i.e. build more robust model, thanks to the generation of adversarial time series.

Adversarial training consists in adding continuously generated adversarial examples into the original training set at each iteration during the training step. At the beginning of each iteration, adversarial examples are generated using the current model, then the weights of the model are updated using both original training data and the corresponding adversarial data. At each iteration, new adversarial examples are thus computed. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] and [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] proved that adversarial training provides an additional regularization benefit to the classifier, resulting in a reduction of the vulnerability of the model to adversarial examples and in a regularization of the model. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] proposed a fast way to generate adversarial examples, making adversarial training feasible: the fast gradient sign method.

Let us consider an image I, its label y I and its adversarial peer Ĩ = I + η. Let θ be the set of parameters of the model and J(θ, I, y I ) the adversarial objective function, i.e. the cost used to train the neural network. The model will compute the dot product between this adversarial image Ĩ and a weight vector w:

w Ĩ = w I + w η (3.8)
The adversarial perturbation will cause a growing of w η of the activation. In order to maximize the impact of this increase under some constraints [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] propose to set η to η = • sign(∇ I J(θ, I, y I )) (3.9)

Link between CNNs and LTS 75

Indeed, it will enable one to obtain an optimal max-norm constraint perturbation. This way of generating adversarial examples is called the fast gradient sign descent. [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] observe that adversarial examples occur in contiguous regions and not in fine pockets. We can thus consider a direction of perturbation rather than specific points in decision space, since it is the direction that matters the most.

Link between Convolutional Neural Networks and Learning Time Series Shapelets

In this section, we first start by explaining that the LTS algorithm is a special case of convolutional neural network (for 1D data). Then, we will explain how this fact can be used to build a more robust algorithm that learns time series shapelets.

LTS representation as a CNN

In LTS, the primary idea is to jointly learn both the weights of the logistic regression w and the shapelets S that minimize the classification objective function F (eq.

M i,k = min j=1,...,J 1 L L =1 (x i,j+ -1 -s k, ) 2
In the following, we denote τ j i as the subsequence of the i-th time series x i starting at the j-th index and of length L: τ j i = [x i,j , x i,j+1 , . . . , x i,j+L-1 ]. In order to compute M i , we need to compute the minimal distances between the time series x i and the set of shapelets S (of length L). It can be divided in the following steps:

1. First, we compute the distances between each shapelet and all the possible subseries of x i . The sub-series of x i can be extracted using a sliding window technique. Shapelets from LTS are thus equivalent to filters from the convolution step of a CNN, computing the distance between shapelets and each subsequence of a time series thus corresponds to a convolution layer for time series. For LTS, the convolution exploits the temporal relationship between neighboring points, which is equivalent to a convolution applied on an image which exploits the spatial relationship between neighboring pixels. Indeed, the different subseries correspond to sub-parts of the time series extracted at regular step.

2. Then, we select the minimal distances between x i and s k for i ∈ {1, 2, . . . , N } and k ∈ {1, 2, . . . , K}. This step corresponds to a minpooling layer.

3. Finally, we use the weights of the logistic regression w in order to predict the class label of the time series, which is equivalent to the fully connected layer of a CNN.

All these steps are pictured in Figure 3.6, where:

• The red and blue bullets respectively correspond to the distance between the first shapelet s 1 and two subsequences of the time series:

τ 1 i & τ 2 i .
• The grey bullet corresponds to the minimal distance between the first shapelet s 1 and the time series x i ,

• In order to get the predictions, we use the logistic regression weights In the literature, this relationship between LTS and CNN has been mentionned -to our knowledge -only in [START_REF] Cui | Multi-scale convolutional neural networks for time series classification[END_REF] and [START_REF] Lods | Learning dtw-preserving shapelets[END_REF].

What does it means that LTS is a specific case of a CNN? Which impact does it have?

We showed that it is possible to write the learning time series shapelets algorithm as a instance of a convolutional neural network. [START_REF] Szegedy | Intriguing properties of neural networks[END_REF] and [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF] both show that CNNs are vulnerable to adversarial examples and that adversarial training can be used to build more robust models for image classification. A natural way to improve the LTS In the following, we provide an improvement of the LTS method, which is based on adversarial examples in order to generate more robust time series shapelets. At each epoch during the learning process, we learn new adversarial time series that we use -in association with original time series -to update the weights and the shapelets. Adversarial time series provide an additional regularization benefit for the shapelets and experiments show an improvement of the performance between the LTS baseline and our framework.

The proposed method

We first start by studying the general case formulation as introduced in [START_REF] Goodfellow | Explaining and harnessing adversarial examples[END_REF]. Then, we consider the shapelet formulation for our specific case. In each case, the impact of adversarial training is investigated.

General problem formulation

We first start by considering a linear model. We remind that the logistic sigmoid function is defined as

σ(z) = 1 1 + e -z (3.10)
Given a set of examples of N input time series: X = {x 1 , x 2 , . . . , x N } and their associated class labels y = {y 1 , y 2 , . . . , y N }, we have for the binary classification case (y ∈ {-1, 1}) and for linear models

P (y i = 1|θ, x i ) = σ(w x i + b) (3.11)
Where y i corresponds to the target (i.e. class label) associated with the i-th time series x i and where the parameters of the model are represented by θ = (w, b). Thus,

P (y i = -1|θ, x i ) = 1 -σ(w x i + b) (3.12) = σ(-(w x i + b)) (3.13)
Consequently, for y i ∈ {-1, 1}, we can write

P (y i |θ, x i ) = σ(y i (w x i + b)) (3.14)
In order to define the cost function, we first have to consider the definition of the likelihood function where the joint probability is the product of

L(θ|X , y)

= P (y|θ, x) = N i=1 P (y = y i |θ, x i ) (3.15)
For convenience, we choose to use the log-likelihood function, defined as

log L(θ|X , y) = N i=1 log P (y = y i |θ, x i ) (3.16)
The training cost corresponds to the negative log-likelihood of probabilities, so

J(θ, X , y) = -log L(θ|X , y) (3.17) = N i=1 log 1 + e -y i (w x i +b) (3.18) = N i=1 ζ(-y i (w x i + b)) (3.19) with ζ(z) = log(1 + exp(z))
, a representation of this function is provided in Figure 3.7. Finally for the general problem formulation, the training cost can be written as

J(θ, X , y) = ζ(-y(w X + b)) (3.20)

The proposed method 79

Impact of Adversarial Training If we consider a particular time series x i and its adversarial equivalent xi , then we have

J(θ, x i , y i ) = ζ(-y i (w x i + b)) (3.21)
and

J(θ, xi , y i ) = ζ(-y i (w xi + b)) (3.22) = ζ(-y i (w x i + w η i + b)) (3.23)
We know that

η i = • sign(∇ x i J(θ, x i , y i )) = -y i • sign(w), thus J(θ, xi , y i ) = ζ(-y i (w x i + b) + w 1 ) (3.24)
If we compare the training cost of normal and adversarial time series, we see that the perturbation results in the addition of a regularization term w 1 into the ζ function. The term w 1 would suggest a L 1 regularization however the fact that this term is inside the ζ function implies some important differences.

• First case: The model makes an accurate prediction.

We know that for -y i (w x i + b) << 0, i.e. is sufficiently lower than 0, we have J i (θ, x i , y i ) 0 ; and y i and (w x i + b) have the same sign consequently the model prediction is both confident and accurate for the label prediction of x i .

If we add w 1 before feeding to the ζ function, we will also have Ji (θ, x i , y i ) 0 if the prediction is confident enough. Under this condition, Ji (θ, x i , y i ) and J i (θ, x i , y i ) will be equivalent and the model will act as if no regularization has be done. Consequently, the penalty which is added during training disappears once the model has learned to make confident enough predictions.

• Second case: The model makes an inaccurate prediction. We also know that for -y i (w x i + b) > 0, we have (w x i + b) and y i of opposite signs i.e. it corresponds to the case where the model prediction is inaccurate.

Here, J i (θ, x i , y i ) > 0 and adding the perturbation will result in an increasing cost: Ji (θ,

x i , y i ) > J i (θ, x i , y i ) (since ζ(z + c) > ζ(z) for c > 0).
A closer look at the perturbation term enables one to see that the L 1 norm is applied on w, which will tend to shrink the coefficients, but only when the model is inaccurate. Whereas L 1 regularization continues to shrink the coefficients though the iterations process even when the model makes confident predictions. With adversarial training, the regularization is taken into account when the model does not fit the data, whereas when the model fits the data the regularization does not have any effect. This is a very interesting property since the model will be able to converge to the true (w, b), unlike L 1 which 80 Chapter 3. Improving TS Shapelets based on Adversarial Examples fails to deactivate in case of good margin. The perturbation on inputs will thus only shrink the coefficients w to prevent overfitting when needed (i.e. during training when the model does not make confident predictions).

Shapelet formulation

If we consider the classification process proposed by [START_REF] Grabocka | Learning time-series shapelets[END_REF] for the Learning Time series Shapelets algorithm, the problem formulation becomes

P (y|θ, X ) = σ(w M + b) (3.25)
and the objective function is

F i = L(θ|x i , y i ) + λ W N K k=1 w 2 k (3.26)
where λ W is a regularization parameter and L(θ|x i , y i ) corresponds to

L(θ|x i , y i ) = -log P (y i |θ, x i ) = log(1 + e -y i (w M i +b) ) (3.27)
We remind that the perturbation will not be applied directly on M but on the time series X . The perturbation is thus limited by [X -η; X +η], we don't need to add a regularization term for this perturbation (since by definition, we have η ∞ < ). On Figure 3.8, we can observe, for a particular time series, the impact of the limitation η ∞ < on its admissible adversarial equivalents.

The purpose here is to define the training cost of the adversarial formulation. To do so, we first compute the gradient of the objective function, then we compute the training cost of the adversarial formulation.

Gradient of the objective function

In the following, we denote the gradient of the objective function for the i-th time series with respect to the j-th point of the i-th time series as

∇ x i,j F i = ∂F i ∂x i,j (3.28)
= ∂L(θ|x i , y i ) ∂(w M i + b) K k=1 ∂(w M i + b) ∂M i,k ∂M i,k ∂x i,j (3.29)
where,

• M i corresponds to the minimal distances between the i-th time series x i and the set of shapelets S. 3.9 -Match between a time series x i and a shapelet s k (of length L = 18). Here j * k = 28, i.e. the minimal distance between x i and s k is obtained for τ 28,45], i.e. if j is one of the indices where x i matches with s k .

M i = [M i,1 , M i,2 , . . . , M i,K ], • ∂L(θ|x i , y i ) ∂(w M i + b) = ∂ log(1 + e -y i (w M i +b) ) ∂(w M i + b) = -y i 1 + e y i (w M i +b) ,
j * k i = τ 28 i . Thus ∂M i,k ∂x i,j = 0 if j ∈ [j * k , j * k + L -1] = [

Chapter 3. Improving TS Shapelets based on Adversarial Examples

• ∂(w M i + b) ∂M i,k = w k , • ∂M i,k ∂x i,j = ∂ min j 1 L L l=1 (x i,j+l-1 -s k,l ) 2 ∂x i,j
If we consider that the minimum for

L l=1 (x i,j+l-1 -s k,l ) 2 is obtained
when j * k is the index of x i where x i starts to match with s k , then the derivative

∂M i,k ∂x i,j will be non zero if j ∈ [j * k , j * k + L -1] (Figure 3.9). • If j ∈ [j * k , j * k + L -1], then ∂M i,k ∂x i,j = 2 L (x i,j * k +l j * k -1 -s k,l j * k )
with l j * k the position of the match between x i and s k . Here, we could rewrite j as j

= j * k + l j * k -1 (1 ≤ l j * k ≤ L). • Else if j / ∈ [j * k , j * k + L -1], then ∂M i,k ∂x i,j = 0.
Since j * k and l * k depend on k, we have to consider the shapelets s k only for a limited number of cases, j must be part of the matching indices of x i with

s k i.e. j ∈ [j * k , j * k + L -1].
If we define the set of indices {k } (such as {k } ⊆ {1, 2, . . . , K}) as the indices of shapelets where x i,j matches with s k ,l , we now have

∇ x i,j F i = ∂L(θ|x i , y i ) ∂(w M i + b) k ∂(w M i + b) ∂M i,k ∂M i,k ∂x i,j (3.30)
Training cost of the adversarial formulation If we perturb the time series x i to obtain xi = x i + η i and if we set η i to • sign(∇ x i J(θ, x i , y i )) (as in eq. 3.9) ; then M i,k will become

Mi,k = min j 1 L L l=1 x i,j+l-1 + sign(∇ x i,j+l-1 F i ) xi,j+l-1 -s k,l 2 (3.31)
If we compute the cost function for the i-th time series, we will have

J i,S (θ, x i , y i ) = ζ -y i (w M i + b) (3.32)
and the adversarial version

Ji,S (θ, x i , y i ) = ζ -y i (w Mi + b) (3.33) = ζ - y i L k w k min j l x i,j+l-1 + sign(∇ x i,j+l-1 F i ) -s k,l 2 -y i b (3.34)

The proposed method 83

Considering that min j is obtained for j * k , i.e. that the minimal distance between xi and S k starts at the j * k -th index of xi .We deduce that Ji,S (θ,

x i , y i ) = ζ - y i L k w k l x i,j * k +l-1 -s k,l 2 -y i 2 k w k - 2y i L k w k l sign ∇ x i,j * k +l-1 F i x i,j * k +l-1 -s k,l -y i b (3.35) = ζ -y i (w M i + b) No perturbation -y i 2 k w k - 2y i L k w k l sign ∇ x i,j * k +l-1 F i x i,j * k +l-1 -s k,l A (3.36)
where A corresponds to the effect of the adversarial training (i.e. the perturbation part). A depends on sign ∇ x i,j * k +l-1 F i , we might use it to obtain a better expression of A.

We know thanks to equation 3.30, that

sign ∇ x i,j F i = sign   ∂L(θ|x i , y i ) ∂(w M i + b) k ∂(w M i + b) ∂M i,k ∂M i,k ∂x i,j   (3.37) = -y i • sign   k w k x i,j * k +l j * k -1 -s k ,l j * k   (3.38)
In equation 3.38, j * k corresponds to the first index where x i and s k match ; whereas in equation 3.36, j * k corresponds to the first index where xi and s k match. So in order both j * k to be equivalent, we make the assumption that the match with the shapelets does not change between perturbed and the original time series.

By doing so, we are able to keep equations as simple as possible (since we can make some simplifications). Moreover, it is a realistic assumption since as long as we use a sufficiently small the probability that the matches between x i and xi with s k start at the same index j * k is high. According to the notation we have j = j * k + l -1 and we previously stated that j should look like j

* k + l j * k -1 in order ∂M i,k
∂x i,j not to be zero, thus by identification we have l = l j * k . Consequently,

sign ∇ x i,j * k +l-1 F i = -y i sign   k w k (x i,j * k +l-1 -s k ,l )   (3.39)

Chapter 3. Improving TS Shapelets based on Adversarial Examples

Then A becomes,

A = -y i 2 k w k - 2y i L k w k l sign ∇ x i,j * k +l-1 F i x i,j * k +l-1 -s k,l (3.40)
= -y i 2 k w k A 1 + 2 L k w k l sign k w k (x i,j * k +l-1 -s k ,l ) x i,j * k +l-1 -s k,l A 2 (3.41)
Now, let us consider the specific case where k takes a single value (i.e. x i,j matches with a single shapelet) and that this value is k. Depending on the number of shapelets this assumption might not be realistic, however in order to better understand what is happening this simplification is necessary. Considering it, we can simplify A 2 the following way:

A 2 = 2 L k w k l sign w k (x i,j * k +l-1 -s k,l ) x i,j * k +l-1 -s k,l (3.42)
= 2 L k |w k | l x i,j * k +l-1 -s k,l (3.43)
= 2 L k |w k | x S i -s k 1 ν k (3.44) = 2 L wν 1 (3.45)
where

x S i = [x i,j * k , . . . , x i,j * k +L-1
]. Thus, under the previous hypothese, A 2 will always be positive. However sign(A 1 ) depends on the sign(y i ), which can be positive or negative. We have two cases:

• When A 1 < A 2 , the adversarial training will add a positive element into the ζ function. Regularization will only be performed when the model doesn't fit the data; whereas when the model makes confident and accurate predictions, it will act as if no regularization was done.

• However when A 1 > A 2 , a negative element will be including in the ζ function resulting into a smaller cost ( Ji,S (θ, x i , y i ) < J i,S (θ, x i , y i )).

When the model fits the data, it will have no impact (since the cost value will still be 0). However if the model predictions are inaccurate, the cost will be underestimated and consequences will be: we won't be abe to measure precisely how close our prediction matches the true one. Consequently, it might perturb the convergence of the model.

The proposed method

85

If we take a closer look at the expression of A 1 and A 2 , we can say that A 1 is most likely to be smaller than A 2 . Indeed, in A 1 we add the w k s without paying attention to their signs, so the sum (of elements that can be either positive or negative) is likely to be smaller than the sum of absolute values of w k (such as in A 2 ) even weighted by a positive element (ν k ). Another fact tends to show that A 1 is likely to be smaller than A 2 : the sum in A 1 is multiply by a 2 factor, whereas the sum of absolute values in A 2 is only mutiply by a factor. Consequently, for small enough epsilon values, the probability to be in the case where A 1 < A 2 is high, i.e. most of the time, we will apply a regularization when the model does not fit the data and the penalty will disappear when the model makes confident and accurate prediction.

We obtain similar observations that in the general formulation, it thus confirms our intuition that adversarial examples can provide a regularization benefit to LTS.

ABS algorithm

There is no differences neither for the initialization of the shapelets nor for the prediction step between LTS and ABS algorithms. We thus only provide a description of the learning step for both LTS and ABS (respectively in Algorithms 1 & 2) to easily compare them. The differences are written in green in order to be better visualized. Moreover, we slightly simplify the algorithm (e.g. we consider a binary class problem and only one scale for the length of the shapelets) for readibility. Note that the function generate_adversarial_time_series(x, ) returns the adversarial time series:

x adv = x + sign(∇ x J(θ, x, y)).
Interpretability of ABS ABS is built on LTS, the main difference between the two algorithms append during the learning step. Indeed, ABS has to learn adversarial time series at the beginning of each iterations. The model generated by ABS is the same than the one generated by LTS (i.e. the shapelets associated with the parameters of the classifier). ABS thus benefits from the same interpretabitily than LTS. The shapelets of the model offer interpretable features; and associated with their corresponding weights, it is even possible to detect the most influential shapelets for each class. An illustration of the interpretability of the model generated by ABS is available in Chapter 4.

Chapter 3. Improving TS Shapelets based on Adversarial Examples

Require: Training dataset x ∈ R N ×n , K shapelets S (of length L), η the learning rate, the number of iterations maxIter. Ensure: The shapelets S ∈ R K×L , and the parameters θ = (w, b) (i.e. the classification weights w ∈ R K and the bias b ∈ R).

for iter from 1 to maxIter do for i from 1 to N do for k from 1 to K do

w k ← w k -η ∂F i ∂w k for l from 1 to L do s k,l ← s k,l -η ∂F i ∂s k,l end for end for b ← b -η ∂F i ∂b end for end for return S, θ
Algorithm 1: Learning Shapelets Algorithm [START_REF] Grabocka | Learning time-series shapelets[END_REF] Require: Training dataset x ∈ R N ×n , K shapelets S (of length L), η the learning rate, the number of iterations maxIter, the adversarial perturbation . Ensure: The shapelets S ∈ R K×L , and the parameters θ = (w, b) (i.e. the classification weights w ∈ R K and the bias b ∈ R).

x temp ← x for iter from 1 to maxIter do x adv ← generate_adversarial_time_series(x temp , )

x ← x temp + x adv for i from 1 to 2×N do for k from 1 to K do

w k ← w k -η ∂F i ∂w k for l from 1 to L do s k,l ← s k,l -η ∂F i ∂s k,

Experiments on UEA / UCR datasets

In this section, we compare Learning Time series Shapelets (LTS) algorithm with our method, called Adversarially-Built Shapelets (ABS) algorithm. We then compare our results to the ones obtained by 10 other relevant baselines (i.e. the 9 previous and D-BoTSW).

Experiments are conducted on 74 of the 85 currently available datasets from the UEA / UCR repository [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF], due to memory and time limitations of our computation system. Raw numbers are available in Appendix A.

Source code

We choose to base our ABS code on the time series classification code provided by [START_REF] Bagnall | The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances[END_REF] 2 that includes many classification algorithms. Amongst them, a Java version of the LTS algorithm is implemented.

Considering the number of datasets as well as some computation resource limitation, we decided to set the defaults parameters (as recommended by the author):

• the regularization parameter λ w = 0.01,

• the number of scales R = 3,

• the percentage of series length to 0.2,

• the number of iterations to 600, and to slightly modify the initializeShapeletsKMeans function. In order to initialize the shapelets we take a random number of 10 000 sub-series (if the number of sub-series is greater than 10 000), or all the sub-series (i.e. the algorithm is unchanged).

For the sake of reproducibility, the source code used for LTS and ABS in these experiments are made available for download3 .

Impact of adding adversarial time series

Figure 3.10 shows a pairwise comparison of error rates between LTS and its adversarial counterpart ABS for tested datasets of the UEA / UCR database. ABS (with set by cross-validation in {0.001, 0.01, 0.1}) reaches better performance than LTS on 36 datasets, equivalent performance on 20 datasets and worse on 18 datasets. The error rate differences between LTS and ABS might seem small, however this can be explained by the fact that ABS is based on LTS. We used the previously introduced one-sided Wilcoxon signed rank test in order to check if the difference is significant. We obtained a p-value of 0.002 which is below the 5% significance level, our experiments thus show that ABS is significantly better than LTS.

Empirical Comparison of ABS with State-of-the-Art Techniques

We use published error rates on 85 datasets from [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF] for the following time series classification algorithms: BoP [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF], BOSS [START_REF] Schäfer | The boss is concerned with time series classification in the presence of noise[END_REF], COTE [START_REF] Bagnall | Time-series classification with COTE: the collective of transformation-based ensembles[END_REF], ED-NN, DTW-NN, PROP [START_REF] Lines | Time series classification with ensembles of elastic distance measures[END_REF], SAX-VSM [START_REF] Senin | SAX-VSM: Interpretable Time Series Classification Using SAX and Vector Space Model[END_REF] and TSBF [START_REF] Baydogan | A Bag-of-Features Framework to Classify Time Series[END_REF]. As well as published error rates for the SMTS method (45 datasets) [START_REF] Baydogan | Learning a symbolic representation for multivariate time series classification[END_REF]. 3.4.3.1 On Standalone Classifiers From Table 3.1 and Figures 3.11 & 3.12,we Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

Discussion

91

ABS is significantly better than BoP (p = 0.000) ABS is significantly better than DTW-NN (p = 0.000) ABS is significantly better than ED-NN (p = 0.000) ABS is significantly better than LTS (p = 0.002) ABS is significantly better than SAXVSM (p = 0.000) ABS is better than SMTS (p = 0.053), however it is not significant ABS is better than TSBF (p = 0.270), however it is not significant PROP is better than ABS (p = 0.243), however it is not significant BOSS is significantly better than ABS (p = 0.002) COTE is significantly better than ABS (p = 0.000) D-BoTSW is significantly better than ABS (p = 0.013) Table 3.1 -ABS -One sided Wilcoxon Test p-values. If the p-value is less than the 5% significance level, the method is considered significantly better than the one it is compared to. 5% significance level). If we consider a 10% significance level then ABS is also significantly better than SMTS.

• The Win/Tie/Lose score indicates that ABS obtains a better classification accuracy on a few more datasets than TSBF, however Wilcoxon p-values shows that the difference is not significant.

• Finally both BOSS and D-BoTSW are significantly better than ABS, on the UEA / UCR database. Note that the UEA / UCR contains a large variety of problems for which all algorithms are not adapted. Thus, in order to choose an algorithm, one should consider the characteristics of its data and not only the performance obtained on the UEA / UCR database.

With Ensemble Classifiers

In Figure 3.13, we compare our standalone classifier ABS to ensemble classifiers. Wilcoxon tests show that ABS is not statistically better than neither PROP nor COTE (respectively p = 0.758 and p = 1.0). Testing the reverse hypothesis that ABS is outperformed by these methods gives significance for COTE (p < 5%) but not for PROP (p = 0.243).

Discussion

Since the first paper on shapelets from [START_REF] Ye | Time series shapelets: a new primitive for data mining[END_REF], many approaches using time series shapelets were proposed. Our contributions for Considering the growing interest for deep learning model (and in particular for convolutional neural networks), this work could serve as a basis for future work on time series shapelets.

Future work

A fast implementation of ABS using a convolutional neural networks framework could be beneficial in term of computation performance (e.g. with CNNs libraries of Python such as keras).

Moreover, since we show that LTS is an instance of a CNN, it might be interesting to evaluate the impact of the CNN setup, such as the choice of the activation function or the impact of the number of layers. The shape and size of the filters often play an important role in the learning process of a CNN, further investigation on the shapelet sizes might also be necessary. A more adapted CNN setup can lead to further improvment of the method.

Several methods have been proposed to avoid overfitting for CNNs (such as dropout and early stopping), an evaluation of their impact on the LTS algorithm is relevant and might help building a better algorithm.

Chapter 4. Time Series Classification: Remote Sensing Applications

In this chapter, we investigate Remote Sensing Time Series Classification (RS-TSC) problems. Automatic land cover classification from satellite image time series is of paramount relevance to assess vegetation and crop status, with important implications in agriculture, biofuels and food. Moreover it is also very useful in order to monitor urban development as well as to follow land cover changes.

We first present specificities of remote sensing data. Then we introduce two remote sensing time series datasets: TiSeLac (proposed by [START_REF] Ienco | TiSeLaC : Time Series Land Cover Classification Challenge[END_REF]) and Brazilian Amazon (introduced in Bailly et al. [2016a]). Finally we experiment on these datasets on both time series classification baselines and previously introduced algorithms: Dense Bag-of-Temporal-SIFT-Words (D-BoTSW, Chapter 2) & Adversarially-Built Shapelets (ABS, Chapter 3).

Remote Sensing (Time Series) Data

Remote Sensing Data

Remote sensing data have been widely used in many forms such as images [START_REF] Tuia | Active learning methods for remote sensing image classification[END_REF][START_REF] Xie | Remote sensing imagery in vegetation mapping: a review[END_REF], hyperspectral images [START_REF] Melgani | Classification of hyperspectral remote sensing images with support vector machines[END_REF] or time series [START_REF] Arvor | Classification of modis evi time series for crop mapping in the state of mato grosso[END_REF]Bailly et al., 2016a;[START_REF] Gómez | Optical remotely sensed time series data for land cover classification: A review[END_REF]Gond et al., 2013a]. Remote sensing data have also been used in a wide variety of problems such as agriculture monitoring [START_REF] Duveiller | A conceptual framework to define the spatial resolution requirements for agricultural monitoring using remote sensing[END_REF], vegetation mapping [START_REF] Xie | Remote sensing imagery in vegetation mapping: a review[END_REF] and environmental modeling [START_REF] Dusseux | Temporal kernels for the identification of grassland management using time series of high spatial resolution satellite images[END_REF].

Satellite Characteristics and Evolution

Each satellite is characterized by:

• Its spatial resolution i.e. the pixel size of taken images that represents the area at the surface of the earth,

• Its temporal resolution or revisit time i.e. the time elapsed between two observations of a given location,

• Its spectral resolution which is the ability of the sensor to discriminate signals of different wavelengths. It depends on the number of spectral bands but also the width of these bands.

While the first sensors were mainly dedicated to meteorology, such as the Advanced Very High Resolution Radiometer (AVHRR) in the 70's, which has a kilometric resolution associated with a wide field of view; sensors evolve to high spatial resolution leading to a larger number of applications. In the 2000's, the sensors spatial resolution with a high temporal resolution reaches 250 to 300 meters, e.g. Moderate Resolution Imaging Spectrora-4.1. Remote Sensing (Time Series) Data 97 diometer (MODIS) sensors abroad Terra and Aqua satellites. Projects dedicated to earth observation through satellites with high spatial resolution have thus been developed such as the Landsat program launched by the National Aeronautics and Space Administration (NASA) in 1972. Eight satellites were launched by this program, two of them are still in orbit: Landsat-7 and Landsat-8; they acquire data all over continental surfaces. Landsat-8 has two sensors that have spatial resolutions of 30 meters (visible, Near Infra-Red (NIR), Short-Wave Infra-Red (SWIR)), 100 meters (thermal) and 15 meters (panchromatic) as well as 16 days temporal resolution 1 .

Data Limitation

Producing an accurate and up-to-date land cover map is an important topic for remote sensing applications. Moreover the amount of remotely sensed data is constantly growing because of the new and upcoming satellite platforms available. However, due to the high cost in terms of money and human resources for labelling data through field campaigns or through expert knowledge, only a very limited number of labeled data are available. Additionally, fast changes in landscape and land use would require a neverending labeling.

Remote Sensing Time Series Data

A remote sensing time series is obtained when images of the same given location are acquired at different dates. It is characterized by its temporal resolution, i.e. the number of images and the gap between the different acquisitions. Note that vegetation indices (e.g. EVI, NDVI) are often prefered to raw values.

Remote sensing time series are often challenging to classify since they combine several characteristics that can perturb the classification. The vegetation and agricultural landscapes significantly vary across Earth resulting in temporal distortions and shifts in time series. Agricultural practices can also cause shifts in amplitude. Due to atmosphere conditions (e.g. clouds), remote sensing time series often contain outliers and are often noisy.

Remote Sensing Time Series Classification

Many methods have been proposed for the classification of satellite data, for applications such as land cover mapping. However, few focus on the classification of satellite images time series. This can be explained by the lack of reference data (i.e. labeled), as well as by the recent availability of 1. https://landsat.usgs.gov/landsat-8 Chapter 4. Time Series Classification: Remote Sensing Applications time series with high spatial resolutions.

Since the early 2000s, the high temporal resolution of the Moderate Resolution Imaging Spectroradiometer (MODIS) sensor aboard the TERRA and AQUA satellites allows the monitoring of phenological cycles in order to classify vegetation types. MODIS time series have been used for many applications such as

• Crop mapping in [Arvor et al., 2011a;[START_REF] Chang | Corn and soybean mapping in the united states using modis time-series data sets[END_REF]. Arvor et al. [2011a] use crop mapping in order to evaluate the agricultural intensification in the state of Mato Grosso, in Brazil and to understand its impact. They focus on the different agricultural practices involving three commercial crops (soybean, maize and cotton) planted in single or double cropping systems. [START_REF] Chang | Corn and soybean mapping in the united states using modis time-series data sets[END_REF] investigate the use of MODIS time series in order to map and monitor United States corn and soybean fields.

• Forest mapping in [START_REF] Gond | Vegetation structure and greenness in central africa from modis multi-temporal data[END_REF], where authors aim at generating a more precise map of forests in the Congo Basin in the context of global changes.

• Land cover mapping in [START_REF] Clark | A scalable approach to mapping annual land cover at 250 m using modis time series data: A case study in the dry chaco ecoregion of south america[END_REF][START_REF] Hüttich | On the suitability of modis time series metrics to map vegetation types in dry savanna ecosystems: A case study in the kalahari of ne namibia[END_REF].

The characterization of land cover mapping in all type of ecosystem is indeed of interest for a suitable and sustainable land management purpose.

• Multi-year agricultural mapping in [START_REF] Brown | Classifying multiyear agricultural land use data from Mato Grosso using time-series MODIS vegetation index data[END_REF], where authors aim at showing the agricultural landscape of Mato Grosso (Brazil) including the type of practices (single or double cropping). The first Landsat satellite was launched in 1972, since then the Landsat spatial and spectral resolutions have been improved leading to high resolution satellite images time series. The Landsat time series have been used in many applications such as detecting forest cover changes [START_REF] Hansen | High-resolution global maps of 21st-century forest cover change[END_REF], as well as mapping the surface water [START_REF] Pekel | Highresolution mapping of global surface water and its long-term changes[END_REF] in the context of global changes. [START_REF] Gómez | Optical remotely sensed time series data for land cover classification: A review[END_REF] provide a general overview for land cover classification using satellite images time series. [START_REF] Bégué | Remote sensing and cropping practices: A review[END_REF] focus on methodologies that map cropping practices using remote sensing time series, in order to improve the monitoring of cropping practices in the context of food security.

Numerous papers have been published using remote sensing time series data, however data are often unavailable or have been preprocessed by authors, making it impossible to both reproduce the experiments and use the data for further comparison. In the following, we use two datasets of remote sensing time series, available online. These datasets includes time series collected from the Reunion island as well as the Brazilian amazon.

TiSeLac Dataset

TiSeLac Dataset

In order to bring machine learning and remote sensing communities closer, a classification challenge was proposed by [START_REF] Ienco | TiSeLaC : Time Series Land Cover Classification Challenge[END_REF]. The data used for this challenge corresponds to satellite image time series.

The challenge

The purpose of this challenge was to classify a set of satellite image time series collected above the Reunion Island (with a 30m resolution) acquired by LANDSAT-8 sensor in 2014. There are a fixed train and test sets coming from the same satellite images. Therefore, they cover the same time period, and training and testing data have the same distribution.

The dataset uses a set of 23 images acquired in 2014 and provides a total of ten features: seven surface reflectances as well as three complementary spectral indices. The 7 surface reflectances are Ultra Blue, Blue, Green, Red, Near-InfraRed, Short-Wavelength InfraRed (SWIR) 1 & 2. And the 3 computed indices corresponds to Normalized Difference Vegetation Index (NDVI), Normalized Difference Water Index (NDWI) and Brightness Index (BI).

Satellite image time series were labeled using two publicly available datasets: the Corine Land Cover (CLC) map from 2012, and the Registre Parcellaire Graphique (RPG) from 2014.

• The Registre Parcellaire Graphique is a geographical information system allowing the identification of agricultural parcels. It was set up by France in 2002 and it is the only geographic database of this size to be annually updated. Indeed as part of european union common agricultural policy, farmers have to declare which crops they cultivate for each one of their fields as well as the type of cultures (e.g. if it is irrigated or not). Agricultural classes information thus comes from the RPG database.

• The Corine Land Cover2 consists of computer aided photo-interpretation of satellite images. The programm was launch in 1985 by the european union. CLC classes that have been considered are the nonagricultural ones (e.g. forests or urban areas). The challenge training set consists of a set of 81 714 multi-dimensional satellite image time series with their associated labels and coordinates. The challenge testing set is composed of 17 973 satellite image time series with labels and coordinates as well.

Dataset

In order to run all our baseline classification algorithms, we reduce this multivariate dataset to a univariate dataset. Amongst all surface reflectances and radiometric indices, we choose only one index: the Normalized Difference Vegetation Index (NDVI). Indeed the NDVI is a widely used vegetation index e.g. for vegetation mapping.

The second step is to define the set of land cover classes to consider. We choose to keep the 9 classes present in the original dataset in order to ensure land cover diversity. The dataset thus gathers the following classes: We reduce the amount of training and test time series in order to be able to run experiments on more time series classification algorithms. Thus we keep 500 time series per class in the training set (i.e. 4 500 training time series), as done in the Brazilian Amazon dataset. For testing, we select 5 000 time series from the test set.

The last step consists in removing the coordinates information from the dataset. The dataset can be reconstructed using available data from Ienco [2017] using the first 500 NDVI time series for each class for the training set and the first 5 000 NDVI time series for the testing set. This can be seen as a random selection since the data were already shuffled, as indicated by the coordinates. Moreover, classification rates obtained for the challenge are not expected to be reached since we reduce the original dataset to one index (on 10) and remove the coordinates. The Reunion island, which is located in the southern hemiphere, has a tropical climate with two distinct seasons. The wet season starts in December and ends in February, whereas the dry season runs from May to September. It is a volcanic island with several volcanos such as Piton des Neiges and Piton de la Fournaise. The island relief is thus very uneven with numerous height variations causing the island to have a large number of microclimates. The Reunion island climate is thus distinguished by a great variability especially due to its particular relief resulting in large disparities. On one hand, disparities come from precipitation differences between the windward coast (east) and the leeward coast (west). On the other hand, disparities are explained by temperature differences between the warmer areas (coastal zones) and colder areas (mountainous zones).

Information on Normalized Difference Vegetation Index

NDVI values belong to range -1.0 to +1.0. Low NDVI values 3 (e.g. 0.1 or less) can correspond to rocks, sand or snow. Medium NDVI values represent sparse vegetation such as shrubs, grasslands or crops (low season). Finally, High NDVI values (e.g. > 0.6) correspond to dense vegetation such as forests and crops before harvest.

TiSeLaC classes

The TiSeLaC dataset contains both vegetation classes (e.g. forests) as well as non-vegetation classes (e.g. urban areas). On Figure 4.4, we observe that there is an high intra-class variability both temporally (e.g. sugarcane crops) and in amplitude (e.g. urban areas). Temporal variability can be explained by different sowing dates, whereas amplitude shifts might be due to altitude or climate differences.

Visually the most distinguishable class is the sugarcane crops. Indeed sugarcane time series can be easily identify thanks to their distinctive NDVI profiles. On the contrary forests, other crops and grasslands have very similar profiles (same observation for urban areas, sparse vegetation and other builtup surfaces).

The specificities of the different classes are listed below:

1. Urban Areas. Reunion island cities are not as dense as european cities [START_REF] Rivière | Sustainable cities in tropical climates: Presentation of the "beauséjour" case study in reunion island[END_REF]. Moreover there exists many green spaces in 7. Sugarcane crops time series have the most distinguishable profiles since NDVI values drop after harvests. Sugarcane crops represent ∼60% of the cultivated area on Reunion island, the harvesting period of sugarcane crops spreads over around a month. [START_REF] Denize | Développement d'un modèle de classification d'images SAR pour la cartographie des cultures tropicales : Exemple de l'île de la Réunion[END_REF] 8. The Other crops class is formed by many crops (e.g. pineapple and bananas crops) as well as orchards (e.g. lychees and mangos). This diversity of crops results in a high intra-class variability for this class.

9. The Water has a high intra-class variability that can be explained by the turbidity of the water. The turbidity of the water is a measure of the water clarity which can perturb NDVI values.

In order to distinguish the different TiSeLaC classes, we can not rely on distinctive features. Indeed different classes have similar profiles but can be discriminated thanks to their mean NDVI values, e.g. forests and grasslands.

Brazilian Amazon Dataset

Mapping croplands is of primary interest to estimate cultivated areas and agricultural production or to qualify the agricultural practices and their potential impacts on the environment. This assessment is especially true for tropical areas. Indeed, these regions which concentrate major global natural resources are expected to supply a large proportion of increasing production demand at global scale.

Brazilian Amazon Dataset

105 Since the early 2000s, the temporal resolution of the MODIS sensor onboard the Terra and Aqua satellites allows the monitoring of phenological cycles in order to classify vegetation types. Such approach appears to be especially relevant in tropical areas where vegetation index time series enable one to limit the constraints related to high cloud cover rates. In the Brazilian amazon, many studies based on MODIS vegetation index time series were carried out to map croplands and crop types [START_REF] Chang | Corn and soybean mapping in the united states using modis time-series data sets[END_REF][START_REF] Clark | A scalable approach to mapping annual land cover at 250 m using modis time series data: A case study in the dry chaco ecoregion of south america[END_REF][START_REF] Hüttich | On the suitability of modis time series metrics to map vegetation types in dry savanna ecosystems: A case study in the kalahari of ne namibia[END_REF][START_REF] Wardlow | Large-area crop mapping using time-series modis 250 m ndvi data: An assessment for the us central great plains[END_REF]. However, in a context of climate change and crop expansion to other Brazilian states, agricultural calendars are expected to evolve so that it is necessary to implement new methodologies to process remote sensing time series.

In the following, we propose a dataset which time series were extracted in the Brazilian amazon and represent MODIS vegetation index time series corresponding to diverse cropping practices.

Study Area

The study area is located in the state of Mato Grosso, in the southern Brazilian amazon, as shown on Figure 4.5. This state has suffered dramatic land use changes since the 1970s due to the rapid progress of an agricultural frontier. This frontier was the result of efficient public policies to encourage people to settle the large and plane areas of native savannas and forests. It led to the establishment of a powerful agricultural sector dedicated to the production of commodities such as soybean, maize or cotton in large-scale farms. Indeed, Mato Grosso is nowadays one of the world's biggest producer of these crops. As a consequence until the mid-2000s the agricultural sector was especially criticized for its severe impacts on forests since Mato Grosso has long been known for its high deforestation rates.

Nonetheless, deforestation decreased for ten years and the historical extensive agriculture model is being replaced by intensive agriculture practices [START_REF] Macedo | Decoupling of deforestation and soy production in the southern Amazon during the late 2000s[END_REF]. For example, double cropping agriculture systems have been generalized in Mato Grosso (from 35 to 62% of the net cropped area [START_REF] Arvor | Analyzing the agricultural transition in Mato Grosso, Brazil, using satellite-derived indices[END_REF]) and especially concern the cultivation of soybean followed by maize, millet or cotton. In this case, soybean is sown first between late September and late November and cultivated until early January and late March. When soybean is harvested, maize and cotton are sown to be harvested between late May (for maize) and mid-July (for cotton).

Although the average agricultural calendar is well known in this region, slight differences may occur at regional scale due to rainfall variability [START_REF] Arvor | Spatial patterns of rainfall regimes related to levels of double cropping agriculture systems in Mato Grosso (Brazil): Spatial patterns of rainfall regimes in Mato Grosso[END_REF] or logistics issues. Indeed, for largest farms (up to 35,000 ha), the sowing or harvesting period can last up to three months. This issue is important to emphasize since it implies a large temporal variability in vegetation index time series for pixels of a same crop class thus affecting [START_REF] Huete | Overview of the radiometric and biophysical performance of the MODIS vegetation indices[END_REF]. When missing data occurs (e.g. due to meteorological conditions), we performed linear extrapolation using closest available data points before and after the missing data.

The field data used for validation is the same as in [Arvor et al., 2011a]. It is based on an extensive field campaign carried out in 2007 to collect validation data about crop type, crop yield and sowing and harvesting dates for two harvests (2006 and 2007). Seventy-six farms were visited and mapped in thirteen municipalities from the two main agricultural regions in Mato Grosso, i.e. along the BR163 road and the Chapada dos Parecis. Five crop classes were identified:

1. Soybean,

Specificities

Due to the climatic conditions in the state of Mato Grosso in Brazil different agricultural practices can be observed: single cropping and double cropping. These practices -as well as with large farms and logistics issuesgenerate a specific agricultural calendar.

Indeed, to ensure two harvests (Soybean and {Cotton, Maize or Millet}) in the same year, it is necessary for farmers to be organized. Cotton, maize and millet do not have the same phenological cycle: cotton has the longest one followed by maize ; i.e. cotton crops require more time from sowing to harvesting than both maize and millet crops. It is thus necessary to start sowing the soybean that will be followed by cotton earlier than the one to be 5. https://github.com/a-bailly/time_series_data/tree/master/ brazilian-amazon 4.4. TiSeLaC Dataset versus Brazilian Amazon Dataset 109 followed by maize, since the soybean followed by cotton need to be harvest first. The same reasonning apply to soybean with maize and soybean plus millet. Moreover since millet is usually not planted for commercial use but rather for soil cover, it is logical to be sown last (for double cropping) as it will not be harveted.

Concerning cropping practices, single soybean can be sown later than double cropping soybean since there will be only one harvest. After single cropping soybean is harvested, it is possible to observe that the vegetation grows again on Figure 4.6. This can be explained by the fact that the rainy period is not over. Cotton cultivated in single cropping is sown later than soybean for a practical reason: cotton need to be harvested during the dry season i.e. after the end of the rainy period.

Knowledge on remote sensing data can help building more specific approaches. For the Brazilian Amazon, we show that there exists a specific agricultural calendar that can bring more information to help properly classify properly the time series.

TiSeLaC Dataset versus Brazilian Amazon Dataset

The TiSeLaC dataset is more challenging than the Brazilian Amazon one for the following reasons:

1. It contains more classes.

2. The profiles proximity of several classes makes the classification more challenging for TiSeLaC than for Brazilian Amazon.

3. The lack of distinctive features in the data makes it more difficult to extract knowledge from TiSeLaC, making it harder to properly classify the time series, especially for feature-based algorithms.

We can thus expect better classification performance on Brazilian Amazon than on TiSeLaC.

Experiments on Remote Sensing Time Series datasets

In order to follow the UEA / UCR dataset format, we split each dataset into a training and a testing sets, as detailed in We run the experiments on the following algorithms:

• The available implementations of Bag-of-Patterns, BOSS, DTW-NN, LTS, SAX-VSM, SMTS from [START_REF] Bagnall | The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances[END_REF] 6 . Note that we slightly modifiy the LTS algorithm since we take a maximum of 10 000 random sub-series to initialize shapelets instead of all the sub-series of the training set. This modification has low impact on performance, however it requires less computational space and less time for large datasets.

• Our implementation of ABS which is available on GitHub 7 . As describe in Chapter 3, we initialize the shapelets using either the entire set of sub-series (if < 10 000) or a maximum random set of 10 000 sub-series. We also use recommended LTS parameters:

• The regularization parameter λ w = 0.01,

• The number of scales R = 3,

• The percentage of series length to 0.2,

• The number of iterations to 600. Finally, we use cross-validation to learn the parameter for the adversarial perturbation inside the set {0.001, 0.01, 0.1}.

• Our implementation of D-BoTSW which is available on GitHub 8 . Note that in order to reduce the computation time, we set the parameters k (k-means) and C (SVM) respectively to 1024 and 1.

Results Interpretation

From Table 4.2, we see that for both datasets, shapelet-based methods (LTS & ABS) perform nicely. We can also notice that in the top 4 methods there is also a feature-based method (BOSS for TiSeLaC and D-BoTSW for Brazilian-Amazon) as well as the simple ED-NN.

Learning Time series Shapelets and Adversarially-Built Shapelets are both able to identify a set a sub-series (shapelets) that characterize well the different classes thus that lead to a small amount of errors for these two remote sensing time series datasets.

ED-NN performs well on these two datasets, it might come from the fact that the time series length is relatively small (only 23 datapoints per time series). On the contrary, we observe that DTW-NN obtained a larger number of errors than ED-NN on both datasets. We show that the Brazilian Amazon data respect an agricultural calendar, where time series of the same class can have a small temporal shift due to practical reason. Aligning time series might seem like a good idea since it can enable one to take in account this temporal variability. However, it is necessary to consider the maximum temporal shift of the time series of the same class, which DTW-NN does not.

Finally, the feature-based methods BOSS and D-BoTSW often achieve good performance. However, the length of the time series of these two remote sensing datasets is relatively small and can affect their performances. Nonetheless, we have to keep in mind that new satellites such as Sentinel 1 & 2 with a smaller revisit time provide longer remote sensing time series, which enable these method to build their model on more characteristics, i.e. to have a more precise representation. All four BOSS, D-BoTSW, LTS and ABS can thus expect to achieve better performance on other remote sensing time series datasets with longer time series.

Study of Robutness Methods for Remote Sensing Data

Specificities: Growing Amount of Data

We propose to further experiment in order to evalutate the impact of the number of time series per class on the performance of the different algorithms. We use a subset of the training set in order to create increasingly large training sets (respectively 20, 50, 100, 200 & 500 training time series per class) that we run on ABS, BoP, BOSS, D-BoTSW, ED-NN, LTS and SAX-VSM algorithms. Figures 4.9 and 4.8 summarize the results respectively for datasets TiSeLaC and Brazilian-Amazon. For each size, we learn on 6 different training sets and compute the error rates on the same testing set (i.e. the previous testing set with 5 000 time series). The average error rates are given in Table 4 We observed in Table 4.2 that BoP and SAX-VSM have the highest error rates in both cases. A possible explanation comes from the fact that both BoP and SAX-VSM reduce the data dimensionality. However, for our applications, it might be a problem considering that the time series have a relatively small length (only 24 datapoints). These two approaches are thus unlikely to perform well on remote sensing datasets with time series having few datapoints.

We experiment on two other feature-based methods: BOSS and D-BoTSW. Their features are more robust and lead to better performance than BoP and SAX-VSM. However they also suffer from the low dimensionality of the data, i.e. from the small time series length. We expect to obtain better performance on remote sensing time series with higher temporal resolution for both BOSS and D-BoTSW, since they rely on the notion of neighborhood. Note that the difference between minimal and maximal error rate is larger for BOSS, which suggest that D-BoTSW is more robust to variations.

Descriptive Features

In order to illustrate both our proposed algorithms: ABS & D-BoTSW, we have generated some shapelets and codewords for the Brazilian Amazon dataset which has more distinguishable features than the TiSeLaC one.

Experiments on Remote Sensing Time Series datasets

Adversarially-Built Shapelets

In order to illustrate ABS algorithm, we have generated a set of shapelets for the Brazilian Amazon dataset, as shown on Figure 4.10, we also provide associated weights and bias in Table 4.3. For readibility, 1. We fixed the number of shapelets to 6 instead of computing it using Grabocka's formula.

2. We run this experiment on default parameters (# of scales: R = 3 and percentage of time series length = 0.2), however we only plot the sufficiently long shapelets (corresponding the third scale, with 12 datapoints) for readibility.

The number of classification errors is slightly higher than the one obtained with more shapelets since we obtained an error rate of 0.306 instead of 0.285 previously.

It is possible to associate a shapelet with a specific class, such as • The shapelet with the Soybean+Cotton class. Indeed, there are two consecutive large peaks which corresponds to the Soybean+Cotton profile.

• The , and shapelets represent a large peak followed by three smaller ones.

• The shapelet has the largest second peak between the three considered shapelets ; thus we assume that this shapelet is related to the Soybean+Maize class.

• The second peak of the shapelet is a bit smaller than the one ; we can make the following hypothesis: the shapelet is associated with the Soybean+Millet class.

• Finally, the has the smallest second peaks, our assumption is that it is related with the Soybean class.

• Both and shapelets correspond to the end of a small / medium peak followed by a large one, which can correspond to Cotton class. In Figure 4.7, we observe that the different classes have a high intraclass variability, these two different shapelets representing the same classes can be seen as a good illustration of this variability.

Thanks to the weights associated with each class and each shapelet (see Table 4.3), we are able to check our hypotheses. For each class we hightlight the most influential shapelet(s) which confirmed our previous assumptions e.g. the class Soybean is associated with the shapelet.

Dense Bag-of-Temporal-SIFT-Words

In order to illustrate D-BoTSW algorithm, we have generated a set of codewords for the Brazilian Amazon dataset (see Figure 4.11) as well as corresponding histogram per class (see Figure 4.12). For a better visualization we set the parameters to:

• The number of points per block a to 2, • The number of blockss n b to 6, • The number of codewords k to 16, • And the SVM parameter C SVM to 1. The error rate obtained with this setup (0.316) is approximatly the same than the one obtained with the cross validation (0.295). In the following, we will refer to a specific codeword by its coordinates, i.e. one letter to specify the line and a number for the column, as indicated on Figure 4.11. For example, the D1 codewords has two long arrows pointing up for blocks four and five otherwise small arrows. Each codeword represents a total amount of 12 datapoints, i.e. around half of the total time series. Note that examples of time series and their corresponding codewords can be found in Figure 2.6(c).

Several codewords show the presence of one peak such as A2, B2 or D2, others suggest even two peaks e.g. E1 and G2 . It is possible to observe that the second peak of E1 has much smaller values that the second peak of G2. The histogram value associated with E1 should thus be larger for class Soybean+Maize than for the other classes ; and those with G2 larger for class Soybean+Cotton. In order to check this hypothesis, we generated the average histogram per class for the Brazilian Amazon training set, on Figure 4.12. The larger the values, the more important the codeword is detected in the class. We can observe that

• Class Soybean+Maize has the largest value for the codeword E1, i.e. this codeword is representative of this class. On the contrary, classes Soy-bean+Cotton and Cotton has low values for this codeword.

• The class that has a highest value for the codeword G2 is the Soy-bean+Cotton class. Consequently, our hypotheses on both codewords correspond to the reality. It is possible to find the codewords that are the most associated with specific classes logically. D-BoTSW can thus be used for results interpretation or to check data hypotheses.

Conclusion

In this chapter, we provide two time series datasets available online that we recommend to use in association with the well-known UCR / UEA database to evaluate the performance of any algorithm. Indeed, the variety of problems represented by the UCR / UEA can be enlarged, thanks to these datasets that contains remote sensing time series. We also provide an analysis of the data in order to better understand the nature and the specificities of these datasets.

We perform a set of experiments on these datasets using time series classification algorithms. Then we show the impact of a growing amount of time series and algorithm stability using different training sets. Finally, we depict both ABS and D-BoTSW through shapelet and feature visualizations 4.6. Conclusion 119 for a better understanding of these two algorithms.

Moreover, for some applications, we have identify some additional information that can help classifying data. The creation of algorithms to take into account these informations (e.g. by detecting the beginning of cropping period) can help improve current performances.

Time revisit and/or spatial resolution are increasing for new satellites. We can differentiate satellites with high spatial resolution but low temporal resolution (e.g. SPOT-6, SPOT-7) and satellites with lower spatial resolution but high temporal resolution (e.g. Sentinel-1, Meteosat). Sentinel-2 sensors combine both high spectral and spatial resolutions (10, 20 or 60m) with a high temporal resolution, since they cover the entire Earth surface every five days [START_REF] Malenovskỳ | Sentinels for science: Potential of sentinel-1,-2, and-3 missions for scientific observations of ocean, cryosphere, and land[END_REF]. Higher spatial resolution leads to purer pixel and higher temporal resolution leads to longer time series. Both purer pixels and longer time series mean that feature-based method performances will be improved.

CONCLUSION AND PERSPECTIVES

Results Summary

Time series data can be found in many domains resulting in an explosion of interest in mining time series data in the last two decades. A wide number of algorithms have already been proposed to classify time series and for many applications.

In this thesis, our main purpose was to propose new methodologies for time series classification. Indeed, there is no classifier that is the best on all problems; it is therefore important to propose new algorithms, where a list of dataset properties, for which these algorithms are adapted, has been identified. We choose to focus on methodologies, whose learned models can be interpreted, and introduce two time series classification algorithms that outperform most state-of-the-art baselines. One of the main reason to focus on interpretable methods is the importance of results interpretation and analysis for remote sensing applications in order to better understand the dynamics related to the transformations of our planet. Source code as well as data are available online for reproducibility.

We first proposed an algorithm that builds on two well-known and powerful methods: local features which are densely extracted from time series using a SIFT-based approach and a global representation of time series using these features which is produced using the Bag-of-Words technique. We identify both strengths and weaknesses of our Dense Bag-of-Temporal-SIFT-Words algorithm (D-BoTSW). Amongst weaknesses, we have identified that it is important to have enough points for each time series. Due to the Bag-of-Words representation that causes information loss during the quantization step, D-BoTSW might not perform well on datasets where it is difficult to distinguish the different classes. Amongst strengths, D-BoTSW is robust to noise and exhibits high accuracy and high performance on many datasets. Experiments, conducted on a wide variety of time series datasets, show that D-BoTSW significantly outperforms nearly all considered standalone classifiers. Finally, a visualization of the model, that includes the codewords and the histogram representations of time series, is possible in order to check hypotheses made on the data.

We then propose an enhancement of an already existing algorithm: Learning Time series Shapelets (LTS). In order to build our improved algorithm, we first prove that LTS can be seen as an instance of a Convolutional Neural Network (CNN). Then, based on the fact that adversarial training can 122

Conclusion and Perspectives

be used to build more robust models for image classification, we demonstrate that this assumption is also valid for LTS. Finally, we implemented the Adversarially-Built Shapelets algorithm (ABS) in order to also prove experimentally that ABS performs better than LTS. Note that with adversarial training, the performance is only slightly improved (thanks to more robust shapelets), however the improvment is statistically significant. Both LTS and ABS are interpretable algorithms. Indeed, characteristics sub-series (i.e. shapelets) are used in order to discriminate the classes. These shapelets can be used in association with the corresponding logistic regression weights in order to determine the most important feature(s) for each class.

Amongst drawbacks, the current learning step of ABS implementation might be seen as not fast enough, however a fast implementation based on CNN libraries is planned. ABS has the same advantages than LTS that can be found in [START_REF] Grabocka | Learning time-series shapelets[END_REF], such as a fast prediction step. Both ABS and LTS focus on discriminative sub-series in order to predict the class labels. This is a strength point considering that time-series data often exhibit inter-class differences in terms of sub-series. Shapelets also offer interpretable features. Finally, ABS exhibit competitive performance w.r.t. time series classification baselines.

We tested our algorithms on datasets from many domains (using UEA / UCR database) in order to compare them to existing time series algorithms. However one of our purpose was to design classifiers adapted to satellite images time series. Our last contribution was to study how time series algorithms can perform on this data as well as to show how our algorithms can be used in this context. Namely, we benchmarked many time series classification algorithms on two remote sensing datasets, for which we detailed the specificities. These experiments show that shapelet-based methods are well-suited for this kind of data. Feature-based methods also show promising performance, which we expect to be improved in the future thanks to new and upcoming satellites with higher temporal and spatial resolutions. Finally, we provide a detailed explanation of the interpretability for both D-BoTSW and ABS. We believe that interpretability will be an incentive for remote sensing scientists to use these methods.

Perspectives

Our work can be seen as a step towards bringing closer remote sensing and machine learning communities. The introduction of methodologies able to use additional knowledge (e.g. pixel coordinates, calendar information) present in remote sensing data is a direction that is worth being explored. In order to propose new algorithms supporting massive amounts of data (e.g. Sentinel-2 satellite gathers over 10 trillions time series), it is necessary

Conclusion and Perspectives

123

for both communities to work together. Moreover, with the increasing number of spectral bands acquired by sensors, multivariate time series will be in the future an important topic for the time series classification community.

For satellite data it makes perfect sense to consider multivariate data since satellite sensors acquire several spectral bands, hyperspectral sensors even acquire hundreds of them. Each spectral band can bring different information that can help for the classification. Both D-BoTSW and ABS could be easily adapted to multivariate time series. It is possible for D-BoTSW to generate different codebooks (one per dimension), the new time series representation will thus correspond to the histograms concatenation. Experiments using only a sub-part of the spectral band could be easily done (by removing the corresponding histograms) in order to detect the most discriminative bands for a specific application. Concerning ABS, it is possible e.g. to generate shapelets for each dimension instead of different length shapelets. As for D-BoTSW, this approach allows an analysis of the discriminative power of spectral bands. Considering that a hyperspectral sensor deals with a large number of bands over a continuous spectral range, it is crucial for the time series classification community to develop more multivariate solutions for remote sensing applications. These solutions should allow results interpretability such as providing information on the most discriminative spectral bands SIFT features for time series used in Dense Bag-of-Temporal-SIFT-Words already serve as a basis for an algorithm that considers the temporal order of the features [START_REF] Tavenard | Efficient Temporal Kernels between Feature Sets for Time Series Classification[END_REF]. Future work on D-BoTSW can focus on considering more information such as pixel coordinates for satellite image time series in order to take into account the neighboring time series. Coordinates information can help for the prediction between similar classes. Indeed, neighboring pixels are often part of the same parcel or field, thus it can help detect misclassify time series. For instance, if a pixel is labeled as maize but all its neighbors belong to the coton class, one may assume that this pixel is misclassify and should be also labeled as coton. Finally, D-BoTSW can also be included into easily-extendable frameworks such as ensemble classifiers dedicated to time series classification (e.g. COTE).

Our Adversarially-Built Shapelets algorithm shows very promising classification results. We show that LTS is an instance of a CNN, it might thus be interesting to evaluate the impact of the CNN setup. The activation function, the impact of the number of layers, the shape and size of the filters (i.e. of the shapelets) all play an important role in the learning process of a CNN. Further investigation is required in order to better understand their influence on the model, which can lead to further improvment of the method. Moreover, several methods have been proposed to avoid overfitting for CNNs (such as dropout and early stopping), an evaluation of their impact on the LTS & ABS algorithms is relevant and might help building better algorithms. Moreover, a fast implementation of both LTS & ABS using CNN

6 )

 6 Figure 1.1 -Representation of Euclidean Distance between two Time Series

Figure 1 . 4 -

 14 Figure 1.4 -Representation of global constraints for Dynamic Time Warping

  are the most popular. The Sakoe-Chiba band narrows down the set of possible warping paths by limiting them thanks to the following condition: |j mk m | ≤ r, where r corresponds to the window length (r ∈ R + ). Basically, the Sakoe-Chiba band allows a maximum time shift of length r. As it can be observed on Figure 1.4a, the Sakoe-Chiba band forms a band around the diagonal and has a fixed width (horizontal and vertical one). Admissible warping paths are included into the grey section of the Figure 1.4a. The Itakura parallelogram is an alternative to the Sakoe-Chiba band, which also limits the number of possible warping paths. The Itakura parallelogram allows small shifts at the beginning and at the end of the time series, and a larger distortion around the middle of the time series (corresponding to the smaller diagonal of the parallelogram). See Figure 1.4b, for a representation of possible warping paths (in grey).

Figure 1

 1 Figure 1.6 -Fast Fourier Transform. A Time Series and its Fourier Approximations using the first 10 & 20 coefficients (respectively 2 nd and 3 rd line).

  [START_REF] Lines | A shapelet transform for time series classification[END_REF] proposed to use shapelets as feature extractors in order to classify time series. The outline of the Shapelet Transform algorithm is the following: 1. Extract the K best shapelets (a) Measure quality for all possible shapelets candidates (b) Sort shapelets candidates by quality (c) Return top K shapelets candidates Chapter 1. Time Series Classification State-of-the-Art 2.

  Figure 1.7 -Illustration of temporal distortion: Three time series per class (one class per line) for CBF & Gun_Point datasets

Figure 1

 1 Figure 1.8 -Illustration of temporal order importance: Two_Patterns dataset (Only one time series per class for readibility)

Figure 2

 2 Figure 2.1 -SIFT -Keypoints Detection. Top image: 1128 detected keypoints on a 512 × 512 pixels image. Bottom image: 519 detected keypoints on a 780 × 350 pixels image (Generated using OpenSIFT Library).

Figure 2 . 2 -

 22 Figure 2.2 -Match between two images, 161 matches (OpenSIFT Library)

Figure 2 .Figure 2 .

 22 Figure 2.3 -SIFT -Keypoint Description[START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]

Figure 2 . 4 -

 24 Figure 2.4 -BoTSW -Scale-Space Extrema Detection: A Time Series (top line) and its DoG representation (bottom line). The vertical lines represent the detected keypoints.

(

  D-)BoTSW is based on two powerful techniques which are the SIFT features extraction framework and the Bag-of-Words representation, it thus 54 Chapter 2. TSC based on Local Features Representation inherits advantages and drawbacks from both SIFT features and BoW representation.

Figure 2 .Figure 2

 22 Figure 2.7 -Error rates of BoTSW compared to D-BoTSW.

  Figure2.9 -Per-dimension energy of D-BoTSW vectors extracted from dataset ShapesAll. The same codebook is used for all normalization schemes so that dimensions are comparable across all three sub-figures.

Figures

  Figures 2.10 & 2.11 show that D-BoTSW performs better than 1NN combined with ED (ED-NN) or DTW (DTW-NN), BoP, LTS SAX-VSM and TSBF ; and that this difference is statistically significant. Indeed the one-sided Wilcoxon signed rank test has a p-value of p < 5% for all the methods mentioned above. D-BoTSW also performs better than SMTS, however the difference is not statistically significance (p = 0.173). We can also notice from Figure2.11 that BOSS and D-BoTSW have comparable Win/Tie/Lose performance. Note that, if D-BoTSW is not significantly better than BOSS (p = 0.862), the reverse is also true (p = 0.139).It is striking to realize that D-BoTSW not only improves classification accuracy, but might improve it considerably. Error rate on Shapelet Sim dataset drops from 0.495 (ED-NN) and 0.348 (DTW-NN) to 0 (D-BoTSW), for example. Pairwise comparisons of methods show that D-BoTSW is significantly better than almost all state-of-the-art standalone classifiers (i.e. better than 7 out of 8 tested baselines).

Figure 2 .

 2 Figure 2.10 -Error rates for D-BoTSW (SSR+L 2 ) versus standalone baseline classifiers (ED-NN, DTW-NN, BoP and LTS).

Figure 2 . 11 -

 211 Figure 2.11 -Error rates for D-BoTSW (SSR+L 2 ) versus standalone baseline classifiers (TSBF, SAX-VSM, SMTS and BOSS).

Figure 2 .

 2 Figure 2.12 -Error rates for D-BoTSW (SSR+L 2 ) versus baseline ensemble classifiers (PROP and COTE).

  class for Wine dataset

Figure 2 .

 2 Figure 2.13 -Mean profiles for OliveOil and Wine datasets per class

Chapter 3 .Figure 3 . 1 -

 331 Figure 3.1 -Schematization of a Multi-Layer Perceptron with two hidden layers

Figure 3 . 2 -

 32 Figure 3.2 -Artificial Neural Network -Zoom on a neuron

Figure 3 . 3 -

 33 Figure 3.3 -Convolutional Neural Network -Image Convolution

Figure 3 . 3 .Figure 3 . 4 -

 3334 Figure 3.4 -Convolutional Neural Network overview, minimal example with three filters, five classes, and one layer of each type (convolution, pooling, fully connected).

  i , wM i + w 0 ) with (eq. 3.3):

Figure 3 . 6 -

 36 Figure 3.6 -Learning time series shapelets algorithm as a convolution neural network, with three shapelets (filters) and five classes.

3. 3 .

 3 The proposed method 77 algorithm is to combine adversarial examples (i.e. adversarial time series) with the original training set during the model training.

Chapter 3 .

 3 Figure 3.7 -Function ζ(z) = log(1 + exp(z))

Figure 3 .

 3 Figure 3.8 -Representation of possible adversarial time series. If η ∞ < (here = 0.25 for readibility), the set of all possible adversarial time series for the blue time series (continuous line) correspond to time series that are included between the two dashed green lines.

Figure

  Figure 3.9 -Match between a time series x i and a shapelet s k (of length L = 18). Here j * k = 28, i.e. the minimal distance between x i and s k is obtained for τ

Algorithm 2 :

 2 Adversarially Built Shapelets AlgorithmBailly, Adeline. Classification de séries temporelles avec applications en télédétection -20183.4. Experiments on UEA / UCR datasets 87

Figure 3 .

 3 Figure 3.10 -Comparison of error rates obtained by LTS and ABS (with a perturbation in {0.001, 0.01, 0.1})

Figure 3 . 11 -Figure 3 .

 3113 Figure 3.11 -Error rates for ABS versus standalone baseline classifiers (ED-NN, DTW-NN, BoP and LTS-Bagnall).

Figure 3 .

 3 Figure 3.13 -Error rates for ABS versus baseline ensemble classifiers (PROP and COTE).

  formal proof that LTS is a special case of CNN, 2. A theoretical explanation and experiments showing that LTS can be regularized using adversarial training, 3. A regularization of the LTS model using adversarial training (with an easy and fast way to generate adversarial time series).

  99

Figure 4 .

 4 1 shows Reunion island localization on Earth, whereas Figure 4.2 provides an overview of the Reunion Island including the land cover 100 Chapter 4. Time Series Classification: Remote Sensing Applications ground truth.

Figure 4 .

 4 3 shows per-class average NDVI time series for the reduced version of TiSeLac dataset.

Figure 4 .

 4 4 shows a random selection of five time series for each class.

Figure 4 .

 4 Figure 4.1 -Reunion island localization (from Wikipedia)

Figure 4 . 2 -

 42 Figure 4.2 -Reunion island and the corresponding land cover classes (from Ienco [2017])

Figure 4 . 3 -

 43 Figure 4.3 -TiSeLaC mean profiles per class (NDVI)

Figure 4 . 4 -

 44 Figure 4.4 -Representation of five randomly selected time series per class from TiSeLaC dataset (NDVI)

Figure 4 . 6 -

 46 Figure 4.6 -Brazilian Amazon -Mean profiles per class (EVI)

Figure 4 . 7 -

 47 Figure 4.7 -Brazilian Amazon -Five randomly selected time series per class

  5 refer to single cropping practices whereas classes 2, 3 and 4 refer to double cropping practices. For each class, 500 pixels were randomly selected each year. Thus, we built two datasets (each of them composed of 2500 pixels described by time series of length 23) on two different years in order to assess the method's robustness by training and validating on different years. The training set corresponds to the period 2005-2006 whereas the testing set to the period2006-2007.

Figure 4 .

 4 6 shows per-class average EVI time series for cropping period2005-2006.

Figure 4 .

 4 7 shows a random selection of five time series for each class in order to illustrate high intra-class temporal variability as well as amplitude variability. The dataset is available online 5 .

Figure 4 .

 4 Figure 4.8 -TiSeLaC -Evolution of error rates for an increasing number of training time series

Figure 4 .

 4 Figure 4.12 -Brazilian Amazon -Average histogram per class (D-BoTSW)

  Introduction 5 strate that the LTS algorithm could be seen as an instance of a Convolutional Neural Network (CNN). Then, considering that CNNs can be fooled by adversarial examples (i.e. inputs generated to fool a classifier, close to the original), we prove that LTS can also be misled by adversarial examples. Finally, we propose a simple way to improve the LTS algorithm using adversarial training. Adversarial training consists in introducing adversarial examples during the training process in order to regularize the model and it has been shown that it can slightly improve the performance of a network.This work is described is Chapter 3, with experimental proofs that ABS performs better than LTS.

Table 1

 1

		ED	DTW DDTW	ERP	LCSS MSM TWED WDDTW WDTW # sign. better
	ED	-	0.999 0.846 1.000 1.000 1.000 1.000	1.000	1.000	0
	DTW	0.001	-	0.046 1.000 0.998 1.000 1.000	0.917	1.000	2
	DDTW	0.153 0.954	-	1.000 0.999 1.000 1.000	1.000	1.000	0
	ERP	0.000 0.000 0.000	-	0.976 1.000 0.841	0.259	0.849	3
	LCSS	0.000 0.002 0.001 0.023	-	1.000 0.533	0.114	0.239	4
	MSM	0.000 0.000 0.000 0.000 0.000	-	0.000	0.000	0.000	8
	TWED	0.000 0.000 0.000 0.158 0.465 1.000	-	0.057	0.605	3
	WDDTW 0.000 0.082 0.000 0.739 0.885 1.000 0.943	-	0.854	2
	WDTW 0.000 0.000 0.000 0.150 0.760 1.000 0.393	0.145	-	3

.1 -Comparison of various similarity measures Chapter 1. Time Series Classification State-of-the-Art

Table 1 .

 1 2 -Comparison of similarity measures (associated with 1-NN) using one-sided Wilcoxon Signed Rank Test p-values. The bold values indicate that the difference is significant, e.g. DTW-NN is significantly better than

ED-NN since the p-value is equal to 0.001 < 5%. The last column provides the number of times a similarity measure is significantly better than another one, e.g. DTW is significantly better than 2 other similarity measures: ED and DDTW.

  [START_REF] Bagnall | Time-series classification with COTE: the collective of transformation-based ensembles[END_REF] proposed the Collective Of Transformation-based Ensembles (COTE) for time series classification. Both PROP and COTE combine several standalone classifiers. Numerous time series classification algorithms transform the time series into new representations, which can lead to improvements in accuracy. COTE is partially based on transformations of time series into new domains (features representation), whereas PROP uses a set of elastic measures.

Table 1 .

 1

	1.5. Summary on Time Series Classification Algorithms	35
	BoP BOSS COTE DTW-NN ED-NN Fast Shapelets GAK LTS PROP SAX-VSM sDTW Shapelets ST TSBF	Temporal Distorions	Robust to Noise	Robust to Outliers	# Params 3 4 ---2 2 3 -3 -2 3 2	Performance 899 889 888 899 999 999 -899 889 999 -899 889 899

3 -Comparison of Time Series Classifiers

not evaluated since it is highly correlated with the implementation as well as the number of parameters.

Table 1 .

 1 Table 1.4 for more details. UEA / UCR datasets represent Chapter 1. Time Series Classification State-of-the-Art 4 -UEA / UCR Database in Numbersa variety of problems from image outline classification to motion classification via sensor reading classification, some datasets are also simulated ones (i.e. they do not come from real data). Each dataset is divided into a train set and a test set. Splitting into train / test sets and classifying on the same set of data enables one to compare algorithm performances.

		From	Up to
	# of Classes	2	60
	Time Series Length	20	More than 2500
	Training Set Size	Less than 20	8000
	Test Set Size	20	8000

. . . . . . . . . . . . . . . . . . . . . . . . . 89

  Chapter 3. Improving TS Shapelets based on Adversarial ExamplesShapelet-based methods, which were first introduced by Ye and Keogh

	3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . 66
	3.1.1 On Learning Time Series Shapelets	66
	3.1.2 On Convolutional Neural Networks	67
	3.1.3 On Adversarial Examples	71
	3.2 Link between CNNs and LTS . . . . . . . . . . . . . . . . 73
	3.2.1 LTS representation as a CNN	73
	3.2.2 What does it means that LTS is a specific case of
	a CNN? Which impact does it have?	74
	3.3 The proposed method . . . . . . . . . . . . . . . . . . . 75
	3.3.1 General problem formulation	75
	3.3.2 Shapelet formulation	77
	3.3.3 ABS algorithm	83
	3.4 Experiments on UEA / UCR datasets . . . . . . . . . . . 85
	3.4.1 Source code	85
	3.4.2 Impact of adding adversarial time series	85
	3.4.3 Empirical Comparison of ABS with State-of-the-
	Art Techniques	86
	3.5 Discussion

  Chapter 4. Time Series Classification: Remote Sensing Applicationsthe cities such as trees rows to provide shade and cooler areas. The greenness density of a pixel can influence its associated NDVI values.

	104
	2. Other built-up surfaces could refer to greenhouses, however this is
	an assumption. Indeed greenhouses are often established in green
	areas, thus it could explain the larger intra-class variability compared
	to urban areas.
	3. Forests. Due to the tropical climate, forests NDVI values do not fluc-
	tuate. Time series representing forests on Reunion island thus have
	high but stable NDVI values.
	4. The Sparse Vegetation class regroups pixels that do not belong to any
	of the other classes. This class thus regroups a variety of profiles with
	intermediate NDVI values.
	5. Rocks and bare soil will have by definition low NDVI values (closed
	to or below 0). For a particular pixel the NDVI value is expected to
	have little variation.
	3. Information collected from Remote Sensing Phenology website: https://phenology.
	cr.usgs.gov/ndvi_foundation.php

6. The Grassland class gathers together grazed and mowed grasslands.

Depending of the irrigation, the regrowth speed may vary resulting in different time series profiles.

Table 4 .

 4 1 (500 training time series per class for both). The experiments are carried out using only training data during the training step and error rates are reported on the test set in Table 4.2.

	Chapter 4. Time Series Classification: Remote Sensing Applications
		Brazilian-Amazon_EVI TiSeLac_NDVI
	# Classes	5	9
	Length	23	23
	# Training Time Series	2500	4500
	# Testing Time Series	2500	5000
	Table 4.1 -Remote sensing time series datasets in numbers
	4.5.1 Algorithms

•

  For ED-NN, we use the python KNeighborsClassifier function from package sklearn.neighbors associated with euclidean distance (from package scipy.spatial.distance).

	4.5. Experiments on Remote Sensing Time Series datasets	111
		Brazilian-Amazon (EVI) TiSeLaC (NDVI)
	ABS	0.285	0.415
	BoP	0.501	0.610
	BOSS	0.467	0.474
	D-BoTSW	0.295	0.583
	DTW-NN	0.457	0.457
	ED-NN	0.354	0.438
	LTS	0.285	0.428
	SAX-VSM	0.570	0.717
	Table 4.2 -Average error rates on remote sensing time series datasets (on 6
	runs)
	6. www.timeseriesclassification.com -Corresponding to 229d523 bitbucket commit 7. https://github.com/a-bailly/adversarially_built_shapelets 8. https://github.com/a-bailly/dbotsw

  .2. On Figures 4.9 and 4.8, we can observe both the average error rate (continuous line) as well as minimum and maximum error rates obtained on the different training sets. Note that for the Brazilian Amazon we only have 500 training time series which results in a small / zero variance on Figures 4.9 on a large number of time series (200 and 500 time series per class) ; for the TiSeLaC dataset we randomly select the training time series in the 81 714 original training time series.

Table 4 .

 4 3 -Weights associated with the shapelets represented on Figure4.10 for each class. We indicate the most influential weight in bold i.e. the weight which is the more related to a class. The weights with the largest absolute values correspond to most informative features. Note that due to the construction of the model, the most influential weights are not the largest positive ones but the largest negative ones.

	4.5. Experiments on Remote Sensing Time Series datasets		115
	X X X Shapelets X X X	X Classes Soybean X X X X 0.458	Soybean +Millet -0.145	Soybean +Maize 3.063	Soybean +Cotton -4.620	Cotton -0.598
			-2.967	-2.412	-1.246	1.602	4.106
			-0.592	-0.443	2.529	3.937	-2.903
			-0.447	-2.391	-3.856	2.956	2.215
			-1.045	-1.105	1.62	3.828	-3.855
			-4.545	-1.817	-0.421	0.115	4.290
	Bias	0.643	0.211	-0.545	-0.505	-1.525

Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

124

  Conclusion and Perspectiveslibraries must be implemented in the future to promote these methods. Finally, many scientific papers are currently based on CNNs and adversarial examples, which can lead to further improvment of LTS & ABS or even new shapelet-based approaches.

	name 50words Adiac MedicalImages name Meat ArrowHead MiddlePhalanxOutlineAgeGroup Beef MiddlePhalanxOutlineCorrect BeetleFly MiddlePhalanxTW BirdChicken MoteStrain Car NonInvasiveFatalECG_Thorax1 CBF NonInvasiveFatalECG_Thorax2 ChlorineConcentration D-BoTSW D-BoTSW ABS 0.218 0.1 0.15 0.167 ABS LTS -1 0.269 -1 0.27 0.307 0.328 0.189 0.193 0.403 0.409 0.126 0.143 LTS -1 0.332 0.167 0.2 0.35 0.162 0.192 0.167 0.1 0.2 0.378 0.494 0.513 0.2 0.2 0.2 0.169 0.131 0.144 0.2 0.067 0.059 -1 -1 0.15 0.183 0 0.062 -1 -1 0.009 0.01 0.45 OliveOil 0.6 0.833 0.833 0.359 0.385 CinC_ECG_torso 0.192 OSULeaf 0.07 0.256 0.24 0.105 0.137 Coffee 0 0 PhalangesOutlinesCorrect 0.23 0.198 0.217 0 Computers 0.236 Phoneme 0.718 -1 -1 0.392 0.408 Cricket_X 0.231 Plane 0 0 0 0.241 0.251 Cricket_Y 0.249 ProximalPhalanxOutlineAgeGroup 0.141 0.176 0.176 0.256 0.285 Cricket_Z 0.233 ProximalPhalanxOutlineCorrect 0.158 0.103 0.134 0.241 0.259 DiatomSizeReduction 0.085 ProximalPhalanxTW 0.203 0.2 0.185 0.02 0.026 DistalPhalanxOutlineAgeGroup 0.168 RefrigerationDevices 0.544 0.488 0.507 0.266 0.266 DistalPhalanxOutlineCorrect 0.188 ScreenType 0.445 0.589 0.568 0.214 0.214 DistalPhalanxTW 0.223 ShapeletSim 0 0.033 0.111 0.36 0.381 Earthquakes 0.205 ShapesAll 0.107 -1 -1 0.259 0.252 ECG200 0.06 0.14 SmallKitchenAppliances 0.272 0.32 0.304 0.14 ECG5000 0.056 SonyAIBORobotSurface 0.088 0.186 0.176 0.064 0.061 ECGFiveDays 0 0 SonyAIBORobotSurfaceII 0.17 0.087 0.129 0 ElectricDevices 0.333 StarLightCurves 0.023 -1 0.044 0.334 0.34 FaceAll 0.201 Strawberry 0.044 0.059 0.089 0.224 0.226 FaceFour 0.023 SwedishLeaf 0.082 0.096 0.088 0.034 0.045 FacesUCR 0.055 0.06 Symbols 0.016 0.05 0.06 0.06 FISH 0.023 synthetic_control 0.003 0.003 0.003 0.04 0.034 FordA 0.087 ToeSegmentation1 0.035 0.066 0.066 0.066 0.077 FordB 0.106 ToeSegmentation2 0.069 0.062 0.069 0.181 0.18 Gun_Point 0.02 0 Trace 0 0 0 0 Ham 0.362 Two_Patterns 0.001 0.003 0.004 0.324 0.305 HandOutlines 0.117 -1 TwoLeadECG 0.009 0.001 0.003 0.089 Haptics 0.549 uWaveGestureLibrary_X 0.208 0.201 0.198 0.549 0.545 Herring 0.406 uWaveGestureLibrary_Y 0.265 0.296 0.293 0.391 0.375 InlineSkate 0.613 -1 uWaveGestureLibrary_Z 0.26 0.258 0.258 0.629 InsectWingbeatSound 0.438 UWaveGestureLibraryAll 0.13 -1 -1 0.414 0.406 ItalyPowerDemand 0.064 wafer 0.004 0.004 0.004 0.036 0.039 LargeKitchenAppliances 0.131 Wine 0.426 0.5 0.5 0.24 0.272 Lightning2 0.115 WordsSynonyms 0.309 0.319 0.317 0.164 0.197 Lightning7 0.301 Worms 0.343 0.39 0.39 0.205 0.205 MALLAT 0.106 WormsTwoClass 0.315 0.273 0.299 0.047 0.049 yoga 0.142 0.161 0.154
	Table A.1 -Error rates from various time series classification methods from
	50words to MALLAT

Table A .

 A 2 -Error rates from various time series classification methods from Meat to yoga

Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -20182.3. Experiments on UCR/UEA datasets

Chapter 2. TSC based on Local Features RepresentationBailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

From Andrej Karpathy's blog: http://karpathy.github.io/2015/03/30/ breaking-convnets/

https://bitbucket.org/TonyBagnall/time-series-classification

https://github.com/a-bailly/adversarially_built_shapelets

Chapter 3. Improving TS Shapelets based on Adversarial Examples

https://www.eea.europa.eu/publications/COR0-landcover Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

Chapter 4. Time Series Classification: Remote Sensing Applications

Chapter 2. TSC based on Local Features Representation

MODIS EVI (date 2005209)

High : 9314

Low : -3000 any attempt to classify these classes.

Dataset

We extract two years of MODIS vegetation index time series corresponding to the cropping periods 2005-2006 and 2006-2007. The dataset is thus made of 46 MODIS images from July 2005 to July 2007, i.e. 23 MODIS images per year. This study period was chosen to match with field data in order to enable statistical validation of the method. The vegetation index time series refer to Enhanced Vegetation Index (EVI) of the MOD13Q1 product (tile h12v10), which are made freely accessible by the NASA Land Processes Distributed Active Archive Center 4 . The EVI was created in order to improve the quality of Normalized Difference Vegetation Index (NDVI) products. The computation of EVI is similar to the NDVI one, however EVI improves on NDVI's spatial resolution and has a higher sensibility which enables it to better differentiate heavily vegetated area (where NDVI saturates)

Conclusion and Perspectives

Bailly, Adeline. Classification de séries temporelles avec applications en télédétection -2018

A

ERROR RATES NUMERICAL COMPARISON

For readibility, the numerical error rate values for the UEA / UCR database are separated into two Tables: A.1 and A.2. We provide error rates for our two proposed algorithms: D-BoTSW and ABS ; as well as for LTS since the algorithm provided by [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF] has been updated and we run it on UEA / UCR database for fair comparison with ABS.

In this manuscript, we also used error rates (on 85 datasets) provided by [START_REF] Bagnall | The UEA & UCR Time Series Classification Repository[END_REF] for BoP, BOSS, COTE, DTW-NN, ED-NN, LTS, PROP, SAX-VSM and TSBF algorithms. Error rates for SMTS methods (on 45 datasets) can be found in [START_REF] Baydogan | Learning a symbolic representation for multivariate time series classification[END_REF].

Appendix A. Error Rates Numerical Comparison