Keywords: probability distribution, Compression and classication with Dynamic Time Warping

Part I General introduction 1

Context

In almost every scientic eld, measurements are performed over time. These observations lead to a collection of organized data called time series. Today time series data are being generated at an unprecedented speed from almost every application domain, for instance: 6 Ph.D.

• In Astronomy, telescopes scan the sky and capture light rays that are used in the study of the universe. In Large Synoptic Survey Telescope (LSST) project [lss, 2016], telescopes will capture the electromagnetic radiation of the sky during ten years to calculate the acceleration of the expansion of the universe. This will result in an astronomical catalog of time series.

• In Paleoecology, scientists study the evolution of living animal and plant species in the past. To do this, they extract cores from the soil and look for the presence of fossils at each depth, thus creating time series representing the growth or decline in the size of fauna and ora populations over time [START_REF] Lonlac | Fouille de motifs graduels fermés fréquents sous contrainte de la temporalité[END_REF].

• In Medicine, the analysis of electrocardiogram is used to prevent heart attacks [Ding, 2011]. Those electrocardiograms are long time series obtained by recording the electrical activity of the heart over a period.

• In Biomechanics, the study of human locomotion is perform using sensors that record the eorts performed and the movements of the body during the locomotion.

As a consequence, in the last decade there has been a dramatically increasing amount of interest in querying and mining such data.

Issues Time series data mining unveils numerous facets of complexity. The most prominent problem arise from the uncertainty contained in time series data, the diculty of dening a form of similarity measure based on human perception, and the high dimensionality of time series data [START_REF] Esling | Time-series data mining[END_REF]. These constraints show that three major issues are involved :

• Data representation. How can the fundamental shape characteristics of a time series be represented? What invariance properties should the representation satisfy? A representation technique should derive the notion of shape by reducing the dimensionality of data while retaining its essential characteristics.

Ph.D. Thesis

• Similarity measurement. How can any pair of time series be distinguished or matched? How can an intuitive distance between two series be formalized? This measure should establish a notion of similarity based on perceptual criteria, thus allowing the recognition of perceptually similar objects even though they are not mathematically identical.

• Uncertainty. How to compare the shape of time series without knowing their exact value? How to measure the impact of uncertainty contained in time series or to reduce the adverse eects of uncertainty?

The aim of our work is to propose algorithms to deal with thoses caracteristics of time series.

Context of the thesis

This thesis apprehends the scientic questions above from a data mining point of view, within the framework of the analysis of time series coming from Manual Wheelchair (MWC) locomotion. Also, even if the issues addressed are not limited to the eld of Biomechanics time series and concern other areas of applications, this thesis will deal with the analysis of time series recorded with the wheelchair ergometer FRET-2.

For improving the mobility of persons conned to manual wheelchairs, it is necessary to be able to assess people in their daily environment. For this purpose, a eld wheelchair ergometer (FRET-1) has been designed and manufactured [START_REF] Dabonneville | A self-contained wireless wheelchair ergometer designed for biomechanical measures in real life conditions[END_REF]. This ergometer is equipped with six component dynamometers and other sensors that measures the forces applied to the handrims as well as the movement of the FRET-1 [Couétard, 2000]. It, therefore, makes it possible to measure and calculate a large number of the mechanical parameters of manual wheelchair locomotion.

However, the time series produced have specic characteristics:

• they are long because of the acquisition frequency of the sensor (between 80 and 100 Hz),

• they are cyclic; these cycles come from the cyclical character of the locomotion in Manual Wheelchair, which consists of a succession of push phases and recovery (or freewheeling) phases,

• they are uncertain, this uncertainty is observed during the calibration of the sensor.

Our work consists of proposing algorithms to extract relevant information from these time series while taking into account their characteristics. The methods developed in this work have the aim to assist practitioners for the analysis of Manual 4 Ph.D. Thesis Wheelchair locomotion; then, special attention will be given to the readability and ease of interpretation of the results provided by the algorithms.

Plan

The thesis is organised as follows:

• Chapter 1 explains existing models in the eld of time series processing and presents strategies for the preprocessing of time series (e.g. noise reduction, length reduction), their comparisons, their exploitation through visualization, classication, clustering or prediction.

• Chapter 2 introduces an algorithm called FDTW, which aims to reduce the length of time series while preserving the information it contains. Its operating principle is based on that of GRASP, but it is original in that it denes its global search strategy. Experiments conducted on a classication task have shown that compression does not alter classication performance.

• Chapter 3 proposes a novel framework for uncertain time series clustering, which is based on the use of a clustering algorithm (UShapelet), and on the use of a dissimilarity function (FOTS), both being robust to the presence of uncertainty in time series. We tested this clustering strategy on 17 data sets from the literature, which allowed us to observe an improvement in the quality of the obtained results.

• Chapter 4 presents a novel symbolic representation of cyclic time series based on cycle properties, which we use for the analysis of cyclic time series issued by human locomotion. This symbolic representation facilitates the visualization and evaluation of cyclic time series. This chapter also gives an application of the proposed symbolic representation to data from manual wheelchair locomotion. The results allowed us to measure the asymmetry of wheelchair locomotion and to establish that this asymmetry decreases with years of practice. We have also observed that the propulsion capabilities of wheelchair users with similar levels of spinal cord injury may dier. These two results highlight the importance of monitoring manual wheelchair locomotion using measurement instruments and the need of ecient methods for quickly and correctly processing this large amount of data.

Ph.D. Thesis Introduction

Datasets can be grouped into four main categories regarding their temporality [START_REF] Roddick | A survey of temporal knowledge discovery paradigms and methods[END_REF]]:

• Static datasets: these are datasets with no temporal context. We have for example the radius of a wheel, the circumference of a circle, the gravity in a place.

• Sequences datasets: they consist of ordered sequences of events. This category includes an order but not time. As an example, we can cite a DNA sequence (GTTTTCCCAGTCACGAC).

• Time-indexed datasets: they consist of a set of temporal data sequences ; for example a set of measures taken at a more or less regular time intervals.

• Full-time data: Each tuple has one or more time components; time series belongs to this latter category.

Time series have several characteristic properties: usually, they are noisy, uncertain and they often have high dimensionality and high auto-correlation. Each of those features can interfere with the mining of time series. To remedy this, preprocessing technics have been proposed in the literature.

Preprocessing of time series

Chapter 1. Knowledge discovery on time series 1.2

Preprocessing of time series 1.2.1 Denoising time series

Several lters have been proposed in the literature to remove the noise contained in time series. In this section, the most frequently used lters are presented.

Kernel smoothing: this lter refers to a statistical technique for recovery of underlying structure in data sets. Its basic principle is to estimate a real-valued function as the weighted average of neighboring observed data. The weight is dened by a function named kernel, such that closer points to real values are given higher weights [START_REF] Wand | Kernel smoothing[END_REF].

Polynomial Regression: this lter consists in tting a nonlinear relationship between the values of an independent variable x (predictor variable) and the corresponding conditional mean of y (variable to explain), denoted E(y |x). This lter has been used to describe nonlinear phenomena. More formally, polynomial regression is dened as the problem of nding a polynomial: g(x) = β 0 + β 1 x + ... + β m x m of a certain degree m for wich E(Y -g(x)) 2 is as small as possible [Kendall, 1961].

Wiener-Kolmogorov Filtering of Short Stationary Sequences: The idea of this lter is to produce a statistical estimate of the actual signal from the noisy signal. Using the Wiener-Kolmogorov lter assumes the knowledge of stationary signal, noise spectra, and additive noise [Pollock, 2007].

Filtering in the Frequency Domain: The purpose of frequency-based lters is to remove the noise contained in a signal. To achieve this goal, the signal is initially broken down into a set of frequencies using a Fourier transform. This set of frequencies is called the signal spectrum. Depending on the application, it may be appropriate to suppress high or low frequencies, or both, in order to remove signal noise. These lters are generally named low-pass, high-pass, bandpass, or notch lter. These lters can also be combined in many ways: in cascade, in parallel, etc [Buttkus, 2012].

Kalman Filter and the Smoothing Algorithm, also known as linear quadratic estimation (LQE), is a Bayesian estimation technique used to track stochastic dynamic systems being observed with noisy sensors. The lter produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone, by estimating a joint probability distribution over the variables for each timeframe. The algorithm works in two phases: extrapolation (prediction) and update (correction). In the extrapolation step, the Kalman lter produces estimates of the current state variables, along with their uncertainties, based on the previous state variables and their uncertainties. Once the outcome of the next measurement is observed, these estimates are updated using a weighted average, with a higher weight being given to estimates with higher certainty. The algorithm is recursive. It can run in real time, using only the current input measurements and the previously calculated state and its uncertainty matrix [START_REF] Matthies | Kalman lter-based algorithms for estimating depth from image sequences[END_REF]].

Reducing uncertainty

Another important step of preprocessing time series is to reduce the uncertainty that they contained. For this purpose some transformations have been introduced in literature.

Uncertain moving average: For uncertain time series, each value is associated with a standard deviation representing uncertainty. The uncertain moving average (UMA) lter is then dened as the weighted average of the consecutive data points of a time series over a given time interval. The weights at each timestamp i are calculated from the inverse of the uncertainty. Thus, in the calculation of the mean, a weight (w) inversely proportional to the uncertainty will be given to each data point in the time series. Uncertain moving average returns times series [START_REF] Orang | Improving performance of similarity measures for uncertain time series using preprocessing techniques[END_REF]:

x U M A =< x U M A 1 , ..., x U M A m > (1.1)
for which

x U M A i = 1 2w + 1 i+w k=i-w x k σ k , 1 ≤ i ≤ m. (1.2)
Where σ k are uncertainty associated with data points x k .

Z-normalization is used with uncertain moving average to reduce the advert eect of uncertainty in time series. In general, z-normalization improves similarity search quality, because it makes similarity measures invariant to scaling and shifting. Given an uncertain time series:

X =< X 1 , ..., X m >, (1.3)
its normal form:

X =< X1 , ..., Xm > (1. 4) is dened as follows:

Xi = X i -X S X , (1.5) Ph.D. Thesis

Preprocessing of time series

Chapter 1. Knowledge discovery on time series where X and S X denote the sample mean and standard deviation of expected values of X, respectively [START_REF] Orang | Improving performance of similarity measures for uncertain time series using preprocessing techniques[END_REF]. That is,

X = 1 n n i=1 E(X i ), (1.6) S X = 1 (n -1) n i=1 (E(X i ) -X) 2 .
(1.7)

Dimensionality reduction

Time complexity of a mining time series algorithm depends on the length of the time series. Reducing dimensionality of time series allows reducing their processing time. To achieve this goal, many representations have been proposed and can be grouped into three main categories:

Non-data-adaptive: Dimension reduction methods are called non-data-adaptive because they take parameters of which value does not vary according to the considered data set. One of the rst work in this family was done by Agrawal [START_REF] Agrawal | Ecient Similarity Search In Sequence Databases[END_REF] who used a Discrete Fourier Transform to compress time series. In the same family, we can also cite the following time series representations: Discrete Wavelet Transform (DWT) [Chan and Fu, 1999a], Piecewise Linear Approximation (PLA) [START_REF] Eriksson | Piecewise linear approximation[END_REF], Piecewise Aggregate Approximation (PAA) [Keogh et al., 2001a].

Data adaptive: This family of time series representation consists of methods that take the properties of the dataset into account when choosing the method parameters. All non-data-adaptive representations can be transformed into dataadaptive representations by adding a parameter selection method to them. As examples of data-adaptive representations, there are Adaptive Piecewise Constant Approximation (APCA) [START_REF] Keogh | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF], Singular Value Decomposition (SVD) [De Lathauwer et al., 1994] and Symbolic Aggregate Approximation (SAX) [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF].

Model based:

The assumption here is that time series are described by an underlying model. Dimensionality reduction is achieved by identifying the model parameters that generate the time series. Several approaches use temporal parametric models such as statistical modeling by feature extraction [START_REF] Esling | Time-series data mining[END_REF], Auto Regressive Moving Average (ARMA) models [START_REF] Kalpakis | Distance measures for eective clustering of arima time-series[END_REF], Markov Chains (MCs) and Hidden Markov Models (HMM) [START_REF] Panuccio | A hidden markov model-based approach to sequential data clustering[END_REF].

Chapter 1. Knowledge discovery on time series

Similarity Measures

After cleaning the time series, we are now ready to extract relevant information from them. Several data mining tasks can be performed on time series.

Similarity Measures

Before performing data mining tasks, it is essential to be able to compare time series. Most often, similarity functions compare time series as humans would do. Indeed, without much of stretch, human recognition understands and looks at the likenesses between two time series based on their amplitude, scale, temporal warping, noise, and outliers. As indicated by [Fu, 2011] [Ralanamahatana et al., 2005] [ [START_REF] Esling | Time-series data mining[END_REF], any similarity measure for time series comparison ought to be reliable with human recognition and perception and have the following properties:

• It should perceive perceptually comparative datasets even if they are not mathematically identical;

• It should resemble human intuition;

• It should be able to capture global and local similarities;

• It should have a universal meaning that is not restricted to a particular type of time series datasets and do not assume some constraints on time series data;

• It should be robust to distortions and set of transformations. More specically it should be robust to amplitude shifting, uniform amplication, uniform time scaling, dynamic amplication, dynamic time scaling, adding noise and outliers transformations or any combination of these transformations.

The latter property is also known as invariance.

Time-Series invariances

In this section, we briey review common time-series distortions and their invariances. More detailed information can be found in [START_REF] Batista | Cid: an ecient complexity-invariant distance for time series[END_REF].

Scaling and translation invariances:

We should be able to perceive the similarity of sequences in spite of contrasts in amplitude (scaling) and oset (translation).

For instance, these invariances may be helpful to analyze seasonal variations in currency values on foreign trade markets without being biased by ination.

Similarity Measures

Chapter 1. Knowledge discovery on time series Shift invariance: We should be able to recognize two similar sequences even if they vary in phase (global alignment) or when there are regions of the sequences that are aligned and others are not (local alignment). For instance, heartbeats can be out of phase depending on when we start recording, and handwritings of the same sentence from various people will require alignment depending on the size of the letters and on the spaces between words (local alignment).

Uniform scaling invariance: We should be able to compare two sequences even if they have dierent lengths. To do so, sequences that dier in length require either extending of the shorter sequence or, contracting of the longer sequence. For instance, this invariance is required for heartbeats recorded at dierent sample frequencies (e.g.: 10, 50 ou 100 Hz).

Occlusion invariance: We should be able to compare two time series even if some of their sub-sequences are missing; we can also compare the sequences by ignoring the sub-sequences that do not match well. For example, suppose an archaeologist who has just found a skull in a research site, and would like to determine to which species this skull belongs. Let us also suppose that we have a database of time series corresponding to the skulls of living species. We could then compare the time series from the found skull to those stored in the database. This comparison should be possible even if the found skull is damaged. In other words, we should be able to make a comparison even if the time series extracted from the found skull has missing sub-sequences.

Complexity invariance:

We should be able to recognize time series with similar shape even if they have dierent complexity. For example, the same audio signals that were recorded indoors and outdoors might be considered similar, although outdoor signals will surely be noisier than indoor ones.

Depending on the application domain, some or all the invariances can be required for the comparison of time series. The preprocessing step can handle some of those invariances; for instance, z-normalization of time series allows their comparison to be scaling invariant. However, all invariances cannot be handled by preprocessing step and should then considered by more sophisticated distances or dissimilarities functions. In the next section, we review the most common of such distance measures.

Categories of time series similarity function

Time series similarity measures can be generally divided into following four main categories: Shape Based similarity function compares two time-series based on the sum of the distances in a Euclidian space between data points of both times series located at approximately the same timestamp. By doing so, the distance between two time series with similar shapes will be low. On the opposite, the distance between timeseries that have a dierent shapes will be high. In this family, there are Lp norm [START_REF] Yi | [END_REF]Faloutsos, 2000] [Keogh andKasetty, 2003a], and Dynamic time warping distance [START_REF] Myers | Performance tradeos in dynamic time warping algorithms for isolated word recognition[END_REF] for instance. However, those distances are sensitive to noise.

Edit Based distance allows evaluating the dissimilarity between two character strings. These dissimilarity functions are able to handle noisy regions and outliers. The principle of these similarity functions is the following: Edit based distances count the minimum number of operation necessary to transform a character string to another. Dierent edit based dissimilarity functions use dierent operations to transform one string to another. A well known edit based distance is Levenshtein distance. That uses three operations: suppression, insertion and substitution of letters. Edit based distances in time series domain are based on the same principle. Time series data points can be skipped during the comparison (deletion) or one data point can be compared to several data points of the other time series (insertion). Among the well-known edit based distances in time series domain we can cited: Longest Common SubSequence (LCSS) [START_REF] Das | Finding similar time series[END_REF], Edit Distance on Real sequence (EDR) [START_REF] Chen | Robust and fast similarity search for moving object trajectories[END_REF] and Time Warp Edit Distance (TWED) [Marteau, 2009] algorithms. LCSS distance uses a threshold parameter for point matching as well as a warping threshold for allowing gaps for matching two time series. EDR is a variant of the edit distance for real-valued series. Opposite to LCSS, EDR assigns penalties based on the length of existing gaps between two series. TWED is a dynamic programming algorithm that introduces a parameter to control the elasticity measure along the time axis.

Feature Based distance: this distance has been designed to ensure some invariances such as rotation invariance. Time series can be compared based on their properties rather than on their shape. So, Feature Based similarity measures compare two time series by computing a feature set for each time series that reects their properties1 . For example, DFT and DWT coecients can be used to compare the similarity between time series [START_REF] Shatkay | Approximate queries and representations for large data sequences[END_REF].

Structure Based similarity measures: These measures are designed to compare time series on a global scale based on their structure. The general principle of those similarity functions is to compare time series based on a high-level repre-1.4 Datamining task on time series Chapter 1. Knowledge discovery on time series sentation that captures global properties of the time series, such as histogram, for instance [START_REF] Lin | Finding structural similarity in time series data using bag-of-patterns representation[END_REF].

1.4

Datamining task on time series

Indexing time series:

The problem of indexing or query by content can be dened as follows: given a query time series Q, and some similarity/dissimilarity measure D(Q,C), nd the most similar time series in database DB. When querying time series by content, a challenge consists in nding as fast as possible a time series in the database that is similar to the query. To achieve this goal, some dimensionality reduction technics have been used: for instance, in [START_REF] Agrawal | Ecient Similarity Search In Sequence Databases[END_REF], time series have been transformed into a more compact representation using Discret Fourier Transform (DFT) before their comparison. Many other dimensionality reduction techniques have been used for the same purpose, such as Discrete Wavelet Transform (DWT) and Discrete Cosine Transform (DCT) [Chan and Fu, 1999a]. Other representation approaches used for query by content are PLA, PAA, APCA [START_REF] Keogh | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF], and SAX [START_REF] Lin | Experiencing SAX: a novel symbolic representation of time series[END_REF]. These latter authors [START_REF] Lin | Experiencing SAX: a novel symbolic representation of time series[END_REF] have shown that SAX outperforms other representations for query by content applications. Another strategy used to ensure the eectiveness of research is parallelism [START_REF] Yagoubi | Radiussketch: Massively distributed indexing of time series[END_REF].

Motif Discovery: Time series motifs are pairs of individual time series, or subsequences of a longer time series, which are very similar to each other and carry precise information about the underlying source of the time series. The idea for motif discovery in time series is inspired from DNA analysis. When they exist, motifs can be used to construct meaningful clusters when clustering time series, which is the case of unsupervised shapelet algorithm [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF]. Associating each class with a motif can speed-up the classication of time series; this idea is used by the shapelet transform algorithm2 [START_REF] Lines | A shapelet transform for time series classication[END_REF], [START_REF] Yagoubi | Parcorr: ecient parallel methods to identify similar time series pairs across sliding windows[END_REF].

Anomaly Detection: Anomaly detection refers to the problem of nding patterns in data that do not conform to the expected behavior. These nonconforming patterns are often referred to as anomalies, outliers, discordant observations, exceptions, aberrations, surprises, peculiarities, or contaminants in dierent application elds. Among these, anomalies and outliers are two terms most commonly used in the context of anomaly detection; sometimes interchangeably. Anomaly detection nds extensive use in a wide variety of applications such as fraud detection for credit cards, insurance, or healthcare, intrusion detection for cyber-security, fault detection in safety-critical systems, and military surveillance of enemy activities [START_REF] Chandola | Anomaly detection: A survey[END_REF].

Temporal Association Rule Discovery: In a transactional database, association rules allow searching for items that often appear together in the same transaction. For instance, in the database of a shop, the discovered rules will indicate, which products are often bought together. The association rules do not give any information on the precedence of the occurrence of one event concerning the other. Hence the need to dene temporal association rules, which are particularly appropriate as candidates for causal rules' analysis in temporally adorned medical data, such as in the histories of patients' medical visits. Patients are associated with both static properties, such as gender, and temporal properties, such as age or current medical treatments, any or all of which may be taken into account during mining [Vasimalla, 2017].

Summarization (Visualization):

The problem of time series visualization or summarization can be dened as follows: given a time series Q containing n data points where, n is an extremely large number, create a (possibly graphics) approximation of Q, which retains its essential features but ts on a single page, computer screen, executive summary. Summarization can be viewed as a higher level clustering of time series where clusters are associated with text or graphical descriptions. Some famous approaches of time series summarization are:

• Time searcher: it is a query by content summarization tool. Here, a user species a set of constraints (intervals) graphically to which time series data points should belong. Those constraints are called time series boxes [START_REF] Hochheiser | Interactive exploration of time series data[END_REF].

• Calendar based visualization of univariate time series data: its goal is to simultaneously identify patterns and trends on multiple time scales (days, weeks, seasons). To do so, Calendar based visualization rst clusters similar daily data patterns and visualizes the average patterns as graphs and the corresponding days on a calendar [ Van Wijk and Van Selow, 1999].

• The spiral visualization is appropriated with large data sets and supports much better than line graphs the identication of periodic structures in the data. Spiral visualization supports both the visualization of nominal and quantitative data based. The extension of the spiral visualization to 3D gives access to concepts for zooming and focusing and linking in the data set [START_REF] Weber | Visualizing time-series on spirals[END_REF].

• GrammarViz is a visualization tool that allows ecient discovery of frequent and rare patterns of variable length in time series. It is based on Ph.D. Thesis 1.4 Datamining task on time series Chapter 1. Knowledge discovery on time series the symbolic representation of time series SAX and context-free grammar [START_REF] Senin | Grammarviz 2.0: a tool for grammar-based pattern discovery in time series[END_REF].

Prediction or time series forecasting is one of the most useful data mining tasks on time series: for example, time series forecasting is used to predict the weather, the cost of an action in the stock exchange market, or early identied epidemiological risks and raised up alarms. A time series forecasting method is based on a mathematical model that capture the main characteristics of the time series like seasonality, periodicity, trend, and that can be used to guess unknown (or future) values of the time series. Many other algorithms used for time series forecasting are based on Auto-Regressive (AR) models. More sophisticated approaches are also used such as neural networks and cluster function approximation [START_REF] Mahalakshmi | A survey on forecasting of time series data[END_REF].

Classication: Classifying time series consists of assigning an unlabelled time series to one, two or more classes. Many classication algorithms for time series have been proposed in the literature and can be gathered into four main groups

• Dictionary classiers: generally, these classiers rst transform time series into characters strings that can be decomposed into a set of word or bag of words, a word being simply a subsequence of the characters string. Each time series is then described by the occurrence frequency of each word in it. The set of time series represented in the space of words is called a dictionary; The classication of time series is then based on the presence or absence of words in this dictionnary. Several algorithms of the literature are based on this principle, such as Bag of Patterns [START_REF] Lin | Rotation-invariant similarity in time series using bag-of-patterns representation[END_REF], SAX and Vector Space Model [START_REF] Senin | Sax-vsm: Interpretable time series classication using sax and vector space model[END_REF], Bag of SFA Symbols(BOSS) [Schäfer, 2015], DTW Features [Kate, 2016a], temporal-robust text classication [START_REF] Salles | A two-stage machine learning approach for temporallyrobust text classication[END_REF] .

• Classier-based on the alignment of whole time series: those classiers are based on distance functions that operate over the entire length of the time series. The dierence between the classiers of this family is based in part on the characteristics of the distance functions used. These distance functions can be based on the shape of the time series (Derivative Dynamic Time Warping [Keogh and Pazzani, 2001a], Weighted Dynamic Time Warping [START_REF] Jeong | Weighted dynamic time warping for time series classication[END_REF], Complexity-Invariant Distance [START_REF] Batista | A complexity-invariant distance measure for time series[END_REF]), on their properties, on their structures or on their symbolic representation (Time Warp Edit Distance [Marteau, 2008], Move Split Merge [START_REF] Stefan | The move-splitmerge metric for time series[END_REF]).

• Shapelets Classiers: Unlike classiers based on the comparison of the time series over their entire length, shapelets classiers look for characteristic subsequences in time series called shapelets whose presence or absence indicates whether or not a time series belongs to a class. We have for example: Shapelet Transform [START_REF] Lines | A shapelet transform for time series classication[END_REF], Learned Shapelets [START_REF] Grabocka | Learning time-series shapelets[END_REF], Fast Shapelet Tree [START_REF] Rakthanmanon | Fast shapelets: A scalable algorithm for discovering time series shapelets[END_REF] • Intervals Classiers: The idea here is to nd localized discriminatory features on time series based on some statistical properties calculated over intervals of variable length. A time series of length m will have m(m-1)/2 possible contiguous intervals. An interval associated with some statistical properties and a condition is a literal, which gives some information about what happened in an interval: for instance, is the mean of a sequence of data points greater or less than a dene threshold? The classier tries to nd a relationship between what happened in an interval and time series classes. Many classiers are based on this principle, such as: Time Series Bag of Features [START_REF] Baydogan | A bag-offeatures framework to classify time series[END_REF], Time Series Forest [START_REF] Deng | A time series forest for classication and feature extraction[END_REF], Learned Pattern Similarity [START_REF] Baydogan | Time series representation and similarity based on local autopatterns[END_REF].

Clustering: The clustering of time series consists of grouping them to build very homogeneous and well-separated groups under some similarity/dissimilarity measure D(Q, C) [START_REF] Rani | Recent techniques of clustering of time series data: a survey[END_REF]. "Homogeneous" means that the intra-group variance is small and "Well separated" means that the inter-groups variance is high. There are many ways to categorize time series clustering algorithms depending on the distance function used, the data transformation or the clustering strategy.

When considering distance function, we have two categories of time series clustering algorithms: those that operate on the whole time series and those that operates on a sub-sequence of time series.

When considering data transformation, we can gather time series clustering algorithms into three groups: raw data, feature-based and model-based clustering.

When considering clustering strategy, we have ve categories of clustering algorithms:

• Distance-based clustering, which is divided in two sub-categories:

Partitioning clustering algorithms partition the data in high dimensional space into multiple clusters. We have for example kMeans like algorithms (kMeans, kMedians, kMedoids, XMeans, KMeans++)

Hierarchical clustering algorithms are grouped into two subcategories: Agglomerative clustering algorithms rst consider each object of the dataset as a cluster and then try to merge clusters until obtainning one cluster: it is a bottom-up merging strategy. Divisive clustering algorithms rst considers that all the data points are in the same cluster and then try to split this cluster to obtain more homogenous ones: it is the top-down merging strategy.

• Density-Based clustering and grid-based clustering algorithm:

The principle of density-based clustering is the following: given a time series that will be considered as the center of the cluster, all the time series of the database that have a distance less or equal to a dened threshold to the center of the cluster are gathered. Thus, the algorithm splits the space into more or less dense regions; then small dense regions can be merged into more signicant regions. This algorithm allows to identify clusters of arbitrary shapes [START_REF] Kriegel | Density-based clustering[END_REF], Kharrat et al., 2008].

Grid-based clustering divides the data space into a grid-like structure, which allows determining the characteristics of the data [START_REF] Amini | A study of density-grid based clustering algorithms on data streams[END_REF].

• Probabilistic and generative models can be modelled with a generative process assuming the data follow a particular distribution like a mixture of Gaussian. Then the model parameters are estimated using the expectationmaximization algorithm (EM), that considers the parameters that maximize the likelihood of the model to the data. On this basis we may estimate the generative probabilities that will be used to construct the generative model [START_REF] Merugu | Privacy-preserving distributed clustering using generative models[END_REF]].

• High-dimensional clustering algorithms: time series may be set in a high dimensional feature space. To cluster them, many methods have been proposed:

Subspace clustering: Subspace clustering looks for a cluster in dierent subspaces of a dataset. A subspace is a subset of the d dimensions of a given dataset; this algorithm is used because, generally, all the dimensions of high dimensional data are not useful. Subspace clustering algorithm identies the relevant dimensions that allow nding clusters. There are two main subspace clustering branches based on their search strategy. Top-down algorithms nd an initial clustering in the full set of dimensions and evaluate the subspaces of each cluster, iteratively improving the results. Bottom-up approaches nd dense regions in low dimensional spaces and combine them to form clusters [START_REF] Parsons | Subspace clustering for high dimensional data: a review[END_REF].

Dimensionality reduction: many dimensionality reduction techniques have been proposed for clustering purpose. A well-known one is coclustering, which consists of simultaneously clustering columns (or dimensions) and rows (data points) of a matrix [START_REF] Dhillon | Information-theoretic co-clustering[END_REF].

Probabilistic latent semantic indexing (PLSI) and laten dirichlet allocation (LDA) are typical clustering techniques for text data.

Indeed, text can be clustered in multiple topics and each topic can be associated with a set of words (or dimension) or a set of rows (documents) [Hofmann, 2017].

Nonnegative matrix factorization is a kind of co-clustering algorithm. It proceeds as follows: a nonnegative matrix X ∈ R M ×N can be factorised into two lower rank matrices U ∈ R M ×L and V ∈ R L×N with L < M and L < N . The idea here is to identify clusters using the matrix U , which has a lower dimension than X [START_REF] Wang | Nonnegative matrix factorization: A comprehensive review[END_REF].

Spectral clustering: the principle is to cluster time series or data objects based on the spectrum of their similarity matrix. The spectrum is used here for dimensionality reduction [START_REF] Filippone | A survey of kernel and spectral methods for clustering[END_REF].

In the context of this thesis, the analysis of manual wheelchair locomotion implies to group manual wheelchair users with similar motor abilities, based on measurements made during their locomotion in actual conditions: this approach is equivalent to time series clustering. Several clustering algorithms proposed in the literature are harmonious compositions, consisting of a representation of time series, an adequate distance function and an appropriate clustering strategy as illustrated the Tables 1.1, 1.2 and 1.3. Detailed informations is presented in [START_REF] Rani | Recent techniques of clustering of time series data: a survey[END_REF]. Time series are ubiquitous in science and are more and more used in the analysis of human locomotion. This chapter presents a general framework for extracting knowledge from time series, starting by time series pre-processing, which allows reducing the advert eects of noise, uncertainty, and dimensionality. Then, we present strategies that are used to compare time series, and we nally present data mining tasks on time series. This chapter presents what has been already done in the literature and raises the question of extracting relevant information from time series coming from wheelchair locomotion. The following chapters present some new strategies that are adapted to the characteristics of these particular time series.

Key points

We highlight dierent models of data mining that could be useful to our work, particularly for

• Pre-processing of time series (noise reduction, dimensionality reduction)

• Comparison of time series.

• Dierent data mining tasks performed on time series.

Part III Contributions Introduction

Time series databases are often large and several transformations have been introduced in order to represent them in a more compact way. One of these transformations is Piecewise Aggregate Approximation (PAA) [START_REF] Keogh | Derivative dynamic time warping[END_REF], which consists in dividing a time series into several segments of xed length and replacing the data points of each segment with their averages. Due to its simplicity and low computational time, PAA has been widely used as a basic primitive by other temporal data mining algorithms such as SAX [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF], SAX-TD [START_REF] Sun | An improvement of symbolic aggregate approximation distance measure for time series[END_REF], ESAX [Lkhagva et al., 2006], in order to:

• Construct symbolic representations of time series; [START_REF] Camerra | isax 2.0: Indexing and mining one billion time series[END_REF] [ [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF].

• Construct an index for time series; [START_REF] Zhao | shapedtw: shape dynamic time warping[END_REF] [ Keogh andPazzani, 2000] [Kate, 2016b]. Indeed, PAA allows queries, which are shorter than length for which the index was built. This very desirable feature is impossible with Discrete Fourier Transform, Singular Value Decomposition and Discrete Wavelet Transform.

• Classify time series.

PAA and Dynamic Time Warping

Time series comparison is an important task that can be done in two main ways.

Either the comparison method considers that there is no time distortion as in Euclidian distance (ED), or it considers that some small time distortions exist between time axis of time series as in Dynamic Time Warping alignment algorithm (DTW) [START_REF] Zhang | Dynamic time warping under pointwise shape context[END_REF]. Since time distortion often exists between time series, DTW has often better results than ED [START_REF] Chen | The ucr time series classication archive[END_REF]]. An exhaustive comparison of time series algorithms [Bagnall et al., 2016a] showed that DTW is among the ecient techniques to be used. However, DTW has two major drawbacks: the comparison of two time series with this algorithm is time-consuming [Rakthanmanon et al., 2012a] and sometimes DTW produces pathological alignments [START_REF] Keogh | Derivative dynamic time warping[END_REF].

A pathological alignment occurs when, during the comparison of two time series X and Y , one datapoint of the time series X is compared to a large subsequence of datapoints of Y ; A pathological alignment causes a wrong comparison. Three categories of methods are used to avoid pathological alignments with DTW:

• The rst one adds constraints to DTW [START_REF] Ratanamahatana | Making Time-series Classication More Accurate Using Learned Constraints[END_REF] [ [START_REF] Yu | Dynamic time warping constraint learning for large margin nearest neighbor classication[END_REF]] [Candan et al., 2012] [Sakoe and Chiba, 1978] [Jeong et al., 2011] [Salvador and Chan, 2007]. The main idea of these methods is to limit the length of the subsequence of a time series that can be compared to a single datapoint of another time series.

• The second one suggests skipping data points that produce pathological alignment during the comparison of two time series [START_REF] Longin | Elastic partial matching of time series[END_REF]] [Itakura, 1975] [Myers et al., 1980a].

• The third one proposes to replace the datapoints of time series with a high-level abstraction that captures the local behavior of those time series. A high-level abstraction can be a histogram of values that captures the distribution of time series datapoints in space [START_REF] Zhang | Dynamic time warping under pointwise shape context[END_REF] or a feature that captures the local properties of time series, such as the trend with Derivative DTW (DDTW) [START_REF] Keogh | Derivative dynamic time warping[END_REF].

Another simple but yet interesting way to capture local properties of time series is to consider the mean of segments of the time series as PAA does. Indeed, the use of the mean reduces the harmful eects of singularities contained in the data and thus allows to avoid pathological alignments. However, one major challenge with PAA is the choice of the number of segments to consider especially with long time series. The accuracy is computed from the algorithm one nearest neighbor (1NN) associated with PDTW. When the number of segments considered is very small (bellow 20), there is a loss of information and the accuracy is reduced. However, considering all the points in the time series, do not produce a maximum accuracy due to the presence of noise or singularities [START_REF] Keogh | Derivative dynamic time warping[END_REF] in the data.

Choise of a segment number with PAA

If the number of segments considered with PAA is too small, the resulting representation is compact, but it contains less information. On the other hand, if the number of segments is too large, the obtained representation is less compact and more prone to the noise contained in the original time series (Fig. 2.1). Our idea is that a number of segments for PAA will be considered as good (1) if it allows obtaining a compact representation of the time series, and (2) if it preserves the quality of the alignment of time series. So when considering classication task, one of the best algorithm to use for evaluating the quality of time series alignment is one Nearest Neighbor (1NN). Indeed, its classication error directly depends on time series alignment, since 1NN has no other parameters [Wang et al., 2013].

Summary of Contributions

In this chapter,

• We dene the problem of preprocessing time series with PAA for a better classication with DTW;

• We propose a parameter free heuristic for aligning piecewise aggregate time series with DTW, which approximates the optimal value of the number of 2.2 Background and related works Chapter 2. Preprocessing of time series segments to be considered with PAA.

The rest of the chapter is organized as follows: in Section 2.2 we recall the definitions and background; Section 2.3 explains our approach; Section 2.4 presents experimental results and comparisons to other methods; Section 2.5 draws conclusions and venues for future work.

2.2

Background and related works Let's recall some denitions.

Denition 1. A time series

X = x 1 , • • • , x n is a sequence of numerical values
representing the evolution of a specic quantity over time.

x n is the most recent value.

Denition 2. A segment X i of length l of the time series X of length n (l < n) is a sequence constituted by l variables of X starting at the position i and ending at the position i + l -1. We have:

X i = x i , x i+1 , ..., x i+l-1 .
Denition 3. The arithmetic average of the data points of a segment X i of length l is noted Xi and is dened by:

Xi = 1 l l-1 j=0
x i+j .

(2.1) Denition 4. Let T be the set of time series. The Piecewise Aggregate Approximation (PAA) is dened as follows:

P AA : T × N * → T (X, N ) → P AA(X, N ) = Xk , k ∈ {i × n N + 1, i = 0, • • • , N -1} if N < |X| X otherwise (2.2) Denition 5. Let d ⊆ T be a subset of time series, N ∈ N * , P AAset(d, N ) =
{P AA(X, N ), ∀X ∈ d}.

Dynamic Time Warping algorithm

DTW [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] is an algorithm of time series alignment algorithm that performs a non-linear alignment while minimizing the distance between two time series. To align two time series:

X = x 1 , x 2 , • • • , x n ; Y = y 1 , y 2 , • • • , y m
, the algorithm constructs an n × m matrix where the cell (i, j) of the matrix corresponds to the squared distance (x i -y j ) 2 between x i and y j . Then to nd the best alignment Chapter 2. Preprocessing of time series 2.2 Background and related works between X and Y , DTW constructs the path that minimizes the sum of squared distances. This path, noted W = w 1 , w 2 , . . . , w k , . . . , w K , must respect the following constraints:

• Boundary constraint: w 1 = (1, 1) and w K = (n, m);

• Monotonicity constraint: given w k = (i, j) and : w k+1 = (i , j ) then: i ≤ i and j ≤ j ;

• Continuity constraint: given w k = (i, j) and: w k+1 = (i , j ) then: i ≤ i + 1 and: j ≤ j + 1.

The warping path is computed by an algorithm based on the dynamic programming paradigm that solves the following recurrence:

γ(i, j) = d(x i , y j ) + min{γ(i -1, j -1), γ(i -1, j), γ(i, j -1)}, (2.3)
where d(x i , y j ) is the squared distance contained in the cell (i, j) and γ(i, j) is the cumulative distance at the position (i, j) that is computed by the sum of the squared distance at the position (i, j) and the minimal cumulative distance of its three adjacent cells.

Piecewise Dynamic Time Warping Algorithm (PDTW) [START_REF] Keogh | Scaling up dynamic time warping for datamining applications[END_REF]] is the DTW algorithm applied on Piecewise Aggregate time series [START_REF] Keogh | Derivative dynamic time warping[END_REF]. Let N ∈ N * , X and Y be two time series: P DT W (X, Y, N ) = DT W (P AA(X, N ), P AA(Y, N )).

(2.4)

The number of segments N that one considers greatly inuences the quality of the alignment of the time series. However, PDTW does not give any information on the way to choose it. For making this choice, [START_REF] Chu | Iterative deepening dynamic time warping for time series[END_REF] proposes the Iterative Deepening Dynamic Time Warping Algorithm (IDDTW).

Iterative Deepening Dynamic Time Warping

For determining the number of segments, IDDTW only considers values that are power of 2 and for each value, computes an error distribution by comparing PDTW with the standard DTW at each level of compression. It takes as inputs: the query Q, the dataset D, the user's condence (or tolerance for false dismissals) user_conf , and the set of standard deviations StdDev obtained from the error distribution. Example: Let C and Q be two time series of the dataset D, let best_so_f ar be the DT W distance between two time series of the dataset. Suppose the distance D pdtw (Q, D) is 40 and the best_so_f ar is 30. The dierence between the estimated distance and the best_so_f ar is 10. Using the error distribution centred around the approximation (40), we can determine the probability that the candidate could Figure 2.2: IDDTW operating principle. Depth represents approximation levels, A represents approximate distance and B is best_so_far [START_REF] Chu | Iterative deepening dynamic time warping for time series[END_REF]. be better by examining the area beyond the location of the best_so_f ar (shown in solid black in Figure 2.2): We disqualify a candidate if this probability is less than the user's specied error acceptance, the candidate is disqualied; otherwise, a ner aproximation is used and the test is re-applied to the next depth. This process continues until the full DTW is performed.

More precisely, IDDTW proceeds as follows:

• the algorithm starts by applying the classic DTW to the rst K candidates from the dataset. The results of the best matches to the query are contained in R, with |R| = K. The best_so_f ar is determined from argmaxR;

• both the query Q and each subsequent candidate C are approximated using PAA representations with N segments to determine the corresponding PDTW;

• a test is performed to determine whether the candidate C can be pruned o or not. If the result of the test is found to have a probability that it could be a better match than the current best_so_f ar, a higher resolution of the approximation is required. Then each segment of the candidate is split into two segments to obtain a new candidate;

• the process of approximating Q and C to determine the PDTW should be reapplied and the test is repeated for all approximations levels until they fail the test or their true distance DTW is determined.

In this way, IDDTW nds the number of segments that best approximates DTW and speeds up its computation. However, IDDTW has three main limitations:

• it only considers the numbers of segments for PDTW that are power of 2;

• it requires a user-specied tolerance for false dismissals that inuences the quality of the approximation, but the algorithm does not give any indication on how to choose the tolerance;

• it considers DTW as a reference while looking for the number of segments that best aligns the time series. However, because of pathological alignments, DTW sometimes fails to align time series properly [START_REF] Keogh | Derivative dynamic time warping[END_REF].

Our goal is to nd the number of segments that best aligns the time series and also speeds up the computation of DTW.

FDTW: a GRASP based heuristic

We propose a heuristic named parameter Free piecewise DTW (FDTW) [Siyou Fotso et al., 2018] based on Greedy Randomized Adapted Search Procedure that deals with all the limitations of IDDTW: it considers all the possible values for the number of segments, it is parameter-free and it nds a number of segments for PDTW based on the quality of the time series alignment, namely the error rate for classication task. The next section introduces FDTW.

Evaluation procedures for the compression quality

Before explaining how to evaluate the quality of time series compression, we rst describe the time series datasets that we considered. They are made up of time series associated with labels that identify their shapes. For instance, in the ECG dataset, each time series traces the electrical activity recorded during one heartbeat. These time series are split in two classes: normal heartbeat and myocardial infarction. Time series classication is a classic problem, which consists in guessing the label of an unlabeled time series based on its shape. The quality of a time series classication model is evaluated from its classication error ( ), or its accuracy (a = 1 -). When considering a classication task, one of the best classication algorithm for evaluating the quality of time series alignment is one Nearest Neighbor (1NN).

Indeed, its classication error directly depends on time series alignment, since 1NN has no other parameters [Wang et al., 2013].

During this work, a compact representation of time series is considered to be good if it reduces the length of the original time series, but also if the classication error obtained by classifying the compact time series is small. The classication error is small when the time series keep their characteristic shape despite compression.

Problem denition

Let D = {d i } be a set of datasets composed of time series. We note |d i | the number of time series of the dataset d i .

Ph.D. Thesis

Let X ∈ d i be a time series of the dataset d i ; we note |X| = n the length of the time series X. For simplicity of notation we suppose that all the time series of d i have the same length. Denition 6.

1N N DT W : D → [0, 1]
(2.5)

d i → 1N N DT W (d i ) (2.6) 1N N DT W (d i )
is the classication error of one Nearest Neighbour with Dynamic Time Warping on the dataset d i .

Denition 7.

1N N P DT W : D × {1 . . . n} → [0, 1] (d i , N ) → 1N N P DT W (d i , N ) = 1N N DT W • P AAset(d i , N ) (2.7) 1N N P DT W (d i , N ) is the classication error of 1-NN with PDTW using N segments on d i .
Our goal is to nd the number of segments that allows P DT W to best align time series. P DT W gives a good alignment when its classication error with 1N N is low [Rakthanmanon et al., 2012a]. Our problem is then to nd the number of segments N that minimizes 1N N P DT W (d i , N ).

Formally, given a dataset d i , of time series that have a length n, we look for the number of segments N ∈ {1 . . . n} such that

min 1≤N ≤n {1N N P DT W (d i , N )}.
(2.8)

Brute-force search

The simplest way to nd the value for the number of segments that minimized the classication error is to test all the possible values. Obviously, this method is time consuming as it requires to test n values to nd the best one. The time complexity is:

O(|d| 2 × n 3 ), (2.9)
where C is the set of values for the number of segments.

To reduce the time of the search, FDTW proposes to look for the number of segments with the minimal classication error without testing all the possible values.

Greedy Randomized Adaptive Search Procedures

The Greedy Randomized Adaptive Search Procedures (GRASP) is a multi-start, or iterative metaheuristic proposed by [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF] [START_REF] Feo | Greedy randomized adaptive search procedures[END_REF], in which each iteration consists of two phases: rstly a new solution is constructed by a greedy randomized procedure and this solution is then improved using a local search procedure.

The greediness criterion establishes that candidates with the best quality are added to a restricted list of candidates. Then, one of the candidate of the restricted list is chosen at random when building up the solution. The candidates obtained by greedy algorithms are not necessarily optimal, but they are used as initial solutions to be explored by local search. The heuristic we proposed is build upon GRASP and strengthened with an inclusion of specic global search component.

Parameter free heuristic

The idea of our heuristic is the following:

1. We choose N c candidates number of segments, distributed in the space of possible values to ensure that we are going to have small, medium and large values as candidates. The candidates values are: n, n-n Nc , n-2× n Nc , ..., n-N c × n Nc . For instance, if the length of time series is n = 12 and the number of candidates is N c = 4, we are going to select the candidates 12, 9, 6, 3. 1 2 3 4 5 6 7 8 9 10 11 12 2. We evaluate the classication error with 1N N P DT W for each chosen candidate, and we select the candidate that has the minimal classication error: it is the best candidate. In our example, let us suppose that we get the minimal value with the candidate 6: it is thus the best candidate at this step. 1 2 3 4 5 6 7 8 9 10 11 12 3. We respectively look between the predecessor (i.e., 3 here) and successor (i.e., 9 here) of the best candidate for a number of segments with a lower classication error: this number of segments corresponds to a local minimum. In our example, we are going to test values 4, 5, 7 and 8 to see if there is a local minimum. 4. We restart at step one while choosing dierent candidates during each iteration to ensure that we return a good local minimum. We x the number of iterations to k ≤ log(n) . At each iteration, the rst candidate is n -(number_of _iteration -1).

In short, in the worst case, we test the rst M candidates to nd the best one. Then, we test 2n

M other candidates to nd the local minimum. We nally perform nb(M ) = M + 2n

M tests. The number of tests to be performed is a function of the number of candidates. Hence, how many candidates should we consider to reduce the number of tests? The rst derivative of nb function vanishes when M = √ 2n and its second derivative is positive; so the minimal number of tests is obtained when the number of candidates is : M = √ 2n. At each iteration, the heuristic tests nb( √ 2n) = √ 8n number of segments. As we have k iterations the number of candidates tested is:

|C| = k √ 8n.
The details of the heuristic are presented in Algorithm 1.

Time complexity:

We use the training set to nd the number of segments that should be considered with PDTW. For that purpose, we applied 1N N on the training set that costs

O(|d| 2 × n 2 √ n). (2.10)
where |d| 2 comes from 1N N algorithm and n 2 √ n comes from P DT W .

Lemma 1:

For a given dataset d i , the quality of the alignment of our heuristic is better than that of DTW:

F DT W (d i ) ≤ 1N N DT W (d i ).
Proof:

1N N DT W (d i ) = 1N N P DT W (d i , n). Then, 1N N DT W (d i )
is one of the candidates considered by the heuristic F DT W . Since F DT W returns the minimal classication error from all candidates, the classication error of 1N N DT W is always greater than or equal to F DT W .

Nevertheless, a heuristic does not always give the optimal value. To ensure that it gives a result not far from the optimal value, one approach is to guarantee that the result of the heuristic always lies within an interval with respect to the optimal value [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF].

In our case, we are looking for the number of segments that allows a good alignment of time series. The alignment is good when the classication error with 1NN is minimal or when the accuracy is maximal.

Let d i be a dataset:

Algorithm 1: Parameter Free Dynamic Time Warping Input: training_set, length of a time serie : n, number of iterations : nb_rep

Output: The number of segments to be used N

The accuracy associated to N

1 function FDTW(training_set, n, nb_rep) 2 l ← f loor(n/sqrt(2 * n)) 3 tab_N ← ones(n) 4 forall i ∈ {0, 1, . . . , (nb_rep -1)} do 5 tab_N _possible_candidates ← seq(f rom = (n -i), to = 1, by = -l) 6 nb_candidats ← |tab_N _possible_candidates| 7 for i in {1, 2, . . . , nb_candidates} do 8 if tab_N [tab_N _possible_candidates[i]] = 0 then 9 tab_N _candidates[j] ← tab_N _possible_candidates[i] 10 tab_N [tab_N _candidates[j]] ← 0 11 j ← j + 1 12 mat_r ← 1N N P DT W (training_set,
i ) = 1 -min 1≤α≤n {1N N P DT W (di, α)} is the maximal accuracy for the dataset d i , acc DT W = 1 -1N N DT W (d i )
is the accuracy obtained with d i and 1NNDTW, and

acc F DT W = 1 -F DT W (d i )
is the accuracy of our heuristic.

To ensure the quality of our heuristic FDTW, we hypothesized that 1N N DT W is better than Zero Rule classier. Zero Rule classier is a simple classier that predicts the majority class of test data (if nominal) or average value (if numeric). Zero Rule is often used as baseline classier [START_REF] Cu°ín | Meeting state recognition from visual and aural labels[END_REF]. The minimal value of the accuracy of Zero Rule is 1 c where c is the number of classes of the dataset.

Proposition 1.:

For a given dataset d i that has c i classes, c i ∈ N * , if acc DT W ≥ 1 c i then 1 c i × acc max ≤ acc F DT W ≤ acc max
Proposition 1 shows that 1NN associated with DTW has a better accuracy than the baseline classier Zero Rule; the FDTW heuristic is a parametric approximation.

Proof:

By denition, acc F DT W ≤ acc max We look for β ∈ N such that

1 β × acc max ≤ acc F DT W ⇔ acc max acc F DT W ≤ β (2.11) However, acc max acc F DT W ≤ 1 acc F DT W because acc max ≤ 1 (2.12)
And,

1 acc F DT W ≤ 1 acc DT W because acc DT W ≤ acc F DT W (2.13) So, 1 acc DT W ≤ c i because 1 c i ≤ acc DT W by hypothesis (2.14) 2.

Experiment and results

Throughout the experiments described in this chapter, FDTW performs three iterations (k=3) when searching for the appropriate number of segments for a dataset.

To evaluate the ability of FDTW heuristic to propose a good number of segments for PAA, it has been compared to IDDTW algorithm in terms of:

• Execution speed;

• Time series compression ratio;

• Classication error associated with the number of segments found by the heuristic.

Case studies

PAA is widely used in time series data mining and often as a primitive by other algorithms such as those allowing to construct a symbolic representation of time series, those allowing to index a time series or even those allowing to classify time series. In this section, we present some algorithms for which the preprocessing performed by FDTW allows to improve the nal results.

Compression

Compression ratio: An immediate way to evaluate the quality of the segmentation is to compare compression ratios. A segment number N 1 will be better than a segment number N 2 if it allows to obtain a more compact representation with PAA.

The compression ratio is given by:

r = n -N n ,
where n is the length of the time series and N is the number of segments considered with PAA. The closer r is to 1 the better is the compression.

The numbers of segments used here are shown in Table 2.1. For the considered datasets, the mean compression ratio of IDDTW (r = 0.654) is slightly higher than that of FDTW (r = 0.605). However, this dierence is not signicant. Indeed, the wilcoxon test gives a p-value greater than 0.1 (p > 0.1). Therefore, we cannot reject the hypothesis that the compression ratios of IDDTW and FDTW are equal.

Application: PAA used with a suitable segment number allows compression of the time series of the Coee dataset without loss of information. Although they are more compact, the obtained time series capture the main variations of the original time series (gure 2.3).

Classication

PAA is used by ShapeDTW [START_REF] Zhao | shapedtw: shape dynamic time warping[END_REF] and DTW_F [Kate, 2016b] to classify time series. However, to evaluate the actual impact of the segment number considered on the classication, we tested FDTW to choose the number of segments to use with 1NN and PDTW.

PDTW was designed to speed up the calculation of DTW without degrading the accuracy. In our experiments, we observe that when the number of segments is chosen, this may even lead to an improvement of the results of the classication.

Quality of the number of segments:

A segment number N 1 is better than a segment number N 2 if the classication error associated with N 1 is smaller than that associated with N 2 . So, to evaluate the quality of our heuristic FDTW, we compared its classication errors with that of IDDTW. The classication error was computed from the results of the 3 fold cross validation applied on the training set. IDDTW tested all the values of N that were equal to a power of two and kept the one that had a minimum classication error (Table 2.1).

Application:

According to the announcement in Lemma 1, the classication error of FDTW during the learning phase (training error) is less than or equal to that of DTW for Ph.D. Thesis all the considered datasets. We used Wilcoxon signed rank test with continuity correction to test the signicance of FDTW against IDDTW. The Wilcoxon signed rank test gives a p-values, p < 0.01, which demonstrates that FDTW achieves a signicant reduction of the classication error of IDDTW. This also demonstrates that FDTW allows to nd segment numbers for PAA that are of better quality than those found by IDDTW during the learning phase.

Comparison with IDDTW:

To evaluate the quality of FDTW, we compared its classication errors with that of IDDTW and the minimal one. The minimal classication error was nd by applying Brute-force search (BF) on both training set and testing set. FDTW and IDDTW used the training set to nd the segment number N with minimal training error using 3 fold cross validation, and then used this number of segments on the testing set to compute the classication error. The value of the segment number N found on the training set may in some cases not be appropriate for the testing set. It is a generalization error, which is due to the representativeness of the training set (Table 2.

2).

If two numbers of segments N 1 and N 2 are associated with the same training error, we retain the largest. IDDTW tested all the values of N that were equal to a power of two during the learning phase and kept the one that had a minimum classication error. [START_REF] Chen | The ucr time series classication archive[END_REF] Our experiments N is the number of segments selected and is the number of data points in a segment

N • 1NN 1NN 1-NN Brute N( ) IDDTW N( ) FDTW N( ) Eucli DTW DTW (
(l = n N ).
The generalization error is computed on the testing set. Note : DTW (r) is a constraint version of DTW where the number of consecutive data points that can be compared to a single point during the warping is bounded. r represents the size of the warping windows The results of our experiments showed that FDTW is more performant than IDDTW. Actually, FDTW resulted in a lower generalization error than IDDTW on 22 datasets and the same generalization error than IDDTW on 8 datasets. The Wilcoxon signed rank test gives a p-values, 0.01 < p ≤ 0.05, which demonstrates that FDTW achieved a signicant reduction of the generalization error of IDDTW. Results also showed that FDTW was able to nd the minimum error for 9 datasets (Coee, ECGFiveDays, Gun-point, ItalyPowerDemand, OliveOil, Plane, Synthetic control, Trace, Two patterns) and outperforms the smallest classication error reported in the literature on dataset CBF (N • 5).

Heuristic execution speed 1 :

As already suggested by the time complexity of both FDTW and IDDTW heuristics, IDDTW tests fewer candidates than FDTW and is therefore faster. However, the number of candidates tested by FDTW reduces exponentially with the length of the time series (Figure 2.4). Actually, the number of candidates to be tested ranges from 1 to n, n being the length of time series, and FDTW considers √ n candidates for each iteration.

In average, FDTW is 8 times faster than Brute-force search with an average execution time of 176 minutes against 1386 minutes for Brute-force search. IDDTW is 7 times faster than FDTW and remains the fastest with an average execution time of 24 minutes. The execution time increases with the length of the time series (Figure 2.5). The increase of Brute-force search execution time is much more important than that of FDTW and IDDTW, particularly on datasets that contain more than 600 points (e.g. Lightning-2).

Comparison with other classication algorithms:

To evaluate the quality of FDTW, we compared its classication errors (generalization error) with that of 35 other classication algorithms [START_REF] Bagnall | The great time series classication bake o: a review and experimental evaluation of recent algorithmic advances[END_REF] of the literature on 84 datasets of UCR archive. The performances of the algorithms are compared using the Nemenyi test that compares all the algorithms pairwise and provides an intuitive way to visualize the results (Fig. 2.6). The Nemenyi test allows ranking classication algorithms according to their average accuracy on 84 datasets. FDTW obtained good results on the simulated datasets in terms of average accuracy (3rd / 37 algorithms) because data of the training set and of the testing set are generated by the same models.

However, to evaluate the signicance of the dierence between the 35 classi-Ph.D. Thesis cation algorithms on 84 datasets, we used the Wilcoxon signed rank test with continuity correction, which has a higher statistical power than Nemenyi test. The results of these tests show that despite data compression,

• FDTW had a better performance than Naive Bayes (NB), C45, logistic regression (Logistic), BN;

• FDTW had a similar performance as 26 other algorithms in the literature, namely: SVMQ, RANDF, ROTF, MLP, EUCLIDEAN_1_NN, DDTW_R1_1NN, DDTW_RN_1NN, ERP_1NN, LCSS_1NN, MSM_1NN, TWE_1NN, WD-DTW_1NN, WDTW_1NN, DD_DTW, DTD_C, LS, BOP, SAXVSM, TSF, TSBF, LPS, PS, CID_DTW, SVML, FS, ACF;

• Only ve algorithms DTW_F, Shapelet Transform (ST), BOSS, Elastic Ensemble (EE) and COTE performed better overall than FDTW.

These results demonstrate the competitiveness of FDTW. Moreover, this algorithm outperforms the best result reported in the literature on UWaveGestureLi-braryAll dataset (Fig. 2.7). The challenge with this dataset is to recognize the gesture made by a user from measurements made by accelerometers. As reported in [Bagnall et al., 2016a] the best accuracy obtained on this dataset is 83.44% with TSBF algorithm; FDTW outperforms this result and allows to obtain 91.87% of accuracy.

Additional experiments are available here [Siyou Fotso et al., 2016]. It is possible to consider the internal properties of time series to choose the compression ratio to use with them. However, this approach gives less good results (Appendix B).

Conclusion and perspective

This chapter deals with the problem of choosing an appropriate number of segments to compress time series with PAA in order to improve the alignment with DTW. In this aim, we proposed a parameter Free heuristic named FDTW, wich approximates Ph.D. Thesis the optimal number of segments to use. The experiments showed that, FDTW increased the quality of alignment of time series especially on synthetic datasets where DTW associated with PAA performed better than any other variant of DTW on a classication task. FDTW was rank 3/37 behind two ensemble classication algorithms COTE and EE. In general, FDTW is faster than Brute force search but run lower than IDDTW. However, FDTW gives a better result than IDDTW on classication task. FDTW also allows reducing the storage space and the processing time of time series while increasing the quality of the alignment of DTW.

As a perspective, the problem we have dealt with in this chapter could be modeled as a multi-objective optimization problem where one objective function would be compression and the other the classication of time series.

Another crucial aspect of time series knowledge discovery is the comparison of time series especially when those time series are uncertain. This aspect will be discussed more in-depth in the next chapter.

Key points

• We proposed a heuristic for time series compression with Piecewise Aggregate Approximation for classication purpose.

• We experimentally showed that in addition to reducing the length and the processing time of time series, compression can improve the classication of time series.

Communications:

-Siyou Fotso All measurements performed by a mechanical system contain uncertainty. Indeed, the uncertainty principle is partly a statement about the limitations of mechanical systems ability to perform measurements on a system without disturbing it [START_REF] Folland | The uncertainty principle: a mathematical survey[END_REF]. Thus, time series obtained from sensors are unavoidably uncertain. These time series constitute a vast proportion of the data used in science, as in medicine with ECGs, in physics with measurements recorded by telescopes, or in computing with the Internet of Things and so on. Ignoring the uncertainty of the data during their analysis can lead to rough or inaccurate conclusions, hence the need to implement uncertain data management techniques.

Several recent studies have focused on the processing of uncertainty in data mining. Two main approaches allow to take uncertainty into account in data mining tasks: either it is taken into account during the comparison by using appropriate distance functions [START_REF] Rizvandi | A study on using uncertain time series matching algorithms for MapReduce applications[END_REF], Hwang et al., 2014, Rehfeld and Kurths, 2014, Orang and Shiri, 2014, Wang et al., 2015, Orang and Shiri, 2017], or its impact is reduced by transformations performed on the data [START_REF] Orang | Improving performance of similarity measures for uncertain time series using preprocessing techniques[END_REF]. This latter strategy is used natively by the u-shapelet algorithm.

Review of u-shapelets

Let us consider a data set consisting of 6 time series corresponding to two birds' calls: 3 time series corresponding to Olive-sided Flycatcher (green) and three time series corresponding to calls of White-crowned Sparrow (blue). When these time series are classied using Euclidean distance as a measure of dissimilarity the groups obtained are not homogeneous (Fig. 3.1 left); in other words, it's not possible to recognize the bird from its calls. However, if characteristic sub-sequences (u-shapelets) are considered to classify time series, we obtain more homogeneous groups than with Euclidean distance (Fig. 3.1 right). Olive-sided Flycatcher; blue: White-crowned Sparrow) using on the one hand the Euclidean distance(left), and on the other hand the u-shapelet (right) [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF] Once this feature has been observed, the natural question is how to nd the subsequences that characterize a group of times series, that is, the sub-sequences that are observed only in a time series subgroup. The u-shapelet discovery algorithm answers this question and proceeds as follows: (a) The algorithm takes the length of the pattern as a parameter. (b) On each time series of the base, a window of the same length as the pattern is dragged, each new sub-sequence obtained by this process is a candidate pattern. (c) The candidate consider as a pattern is the subsequence capable of dividing the time series data set into two subsets D a and D b such that D a contains all the time series which possess the pattern and D b all those which do not contain the pattern.

Two other constraints are taken into account in the discovery of patterns:

• The rst is the ability of the pattern to build subsets that are well separated.

• The second is the ability of employers to build subsets that are not unbalanced.

Introduction

That is, the size of D a must be at most k times larger than that of D b and vice versa.

Denition 8. Two datasets D A and D B are said to be r-balanced if only if

1 r < |D A | |D B | < (1 -1 r ), r > 1
Denition 9. An Unsupervised-Shapelet is any sub-sequence that has a length shorter than or equal to the length of the shortest time series in the dataset, and that allows dividing the dataset into two r-balanced groups D A and D B ; where D A is the group of time series that contains a pattern similar to the shapelet and D B is the group of time series that does not contain the shapelet.

The similarity between a time series and a shapelet is evaluated using a distance function.

Denition 10. The sub-sequence distance sdist(S, T) between a time series T and a sub-sequence S is the minimum of the distances between the sub-sequence S and all possible sub-sequences of T of length equal to the length of S.

This denition raises the question of which distance measure to use for sdist. In general, the ubiquitous Euclidean distance (ED) is used, but it is not appropriate for uncertain time series [START_REF] Orang | An experimental evaluation of similarity measures for uncertain time series[END_REF]]. In the following section, we introduce a dissimilarity function that is more adapted to uncertainty.

Computing the sdist between a u-shapelet candidate and all time series in a dataset creates an orderline: Denition 11. An orderline is a vector of sub-sequence distances sdist(S, Ti) between a u-shapelet and all time series Ti in the dataset.

The computation of the orderline is time-consuming. An orderline for a single u-shapelet candidate is O(N M log(M )) where N is the number of time series in the dataset and M is the average length of the time series. The brute force algorithm for U-shapelets discovery requires K such computations, where K is the number of subsequences. The strategy used by [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF] in Scalable Unsupervised Shapelet algorithm consists in ltering the K candidate segments by considering only those allowing to build r-balanced groups. This selection is eciently made using a hash algorithm.

The assessment of a u-shapelet quality is based on its separation power which is calculated as follows :

gap = µ B -σ B -(µ A -σ A ), (3.1)
where µ A (resp. µ B ) denotes mean(sdist(S, D A )) (resp. mean(sdist(S, D B ))), and σ A (resp. σ B ) represents the standard deviation of sdist(S, D A ) (resp. standard deviation of sdist(S, D B )). If D A or D B contains only one element (or an insignificant number of elements that cannot represent a separate cluster), the gap score is assigned to zero. This ensures that a high gap scored for a u-shapelet candidate corresponds to a true separation power.

U-shapelets algorithm for clustering Uncertain Time Series

U-shapelets clustering is a framework introduced by [START_REF] Zakaria | Clustering time series using unsupervised-shapelets[END_REF]] who suggested clustering time series from the local properties of their sub-sequences rather than using their global features [START_REF] Zhang | Unsupervised feature learning from time series[END_REF]. In that aim, u-shapelets clustering rst seeks a set of sub-sequences characteristic of the dierent categories of time series and classies a time series according to the presence or absence of these typical sub-sequences in it.

Clustering time series with u-shapelets has several advantages. Firstly, u-shapelets clustering is dened for datasets in which time series have dierent lengths, which is not the case of most techniques described in the literature. Indeed, in many cases, the equal length assumption is implied, and the trimming to equal length is done by exploiting expensive human skill [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF]. Secondly, u-shapelets clustering is much more expressive regarding representational power. Indeed, it allows clustering only time series that can be clustered and do not cluster those that do not belong to any cluster.

Furthermore, it is very appropriate to use u-shapelets clustering with uncertain time series because it can ignore irrelevant data and thus, reduce the adverse eects of the presence of uncertainties in the time series. Nevertheless, it is highly desirable to take into account the adverse impact of uncertainty during u-shapelet discovery.

Uncertainty and u-shapelets discovery issue

Traditional measurement of similarity like Euclidean distance (ED) or Dynamic Time Warping (DTW) do not always work well for uncertain time series data. Indeed, they aggregate the uncertainty of each data point of the time series being compared and thus amplify the negative impact of uncertainty. However, ED plays a fundamental role in u-shapelet discovery because it is used to compute the gap, i.e. the distance between the two groups formed by a u-shapelet candidate. The discovery of u-shapelet on uncertain time series could thus lead to the selection of a wrong u-shapelet candidate or to assign a time series to the wrong cluster.

In this study, our goal is not to dene an uncertain u-shapelet algorithm, but rather to use a dissimilarity function robust to uncertainty to improve the quality of the u-shapelets discovered and thus the clustering quality of uncertain time series.

Summary of contributions

• We review the state of the art on similarity functions for uncertain time series and evaluate them for the comparison of small, uncertain time series.

• We introduce the Frobenius cOrrelation for uncertain Time series u-shapelet discovery (FOTS), a new dissimilarity score based on local correlation, which has interesting and useful properties for comparison of small, uncertain time series and that makes no assumption on the probability distribution of uncertainty in data.

• We put the source code at the disposal of the scientic community to allow extension of our work [START_REF] Fots-Sush | FOTS-SUSh[END_REF]].

3.2

Background and Related works

Background

An Uncertain Time Series (UTS) X =< X 1 , . . . , X n > is a sequence of random variables where X i is the random variable modeling the unknown real value number at timestamp i. There are two main ways to model uncertain time series: multisetbased model and PDF-based model.

In Multiset-based model, each element In PDF-based model, each element

X i (1 ≤ i ≤ n) of an UTS X =< X 1 , . . . , X n > is represented as a set {X i,1 , . . . , X i,N i } of
X i , (1 ≤ i ≤ n) of UTS X =< X 1 , . . . , X n >
is represented as a random variable X i = x i + X e i (Fig. 3.3), where x i is the exact but unknown value and X e i is a random variable representing the error. It is this model that we consider in this work. Several similarity measures have been proposed for uncertain time series. They are grouped into two main categories: • Uncertain similarity measures use additional statistical information that quanties the uncertainty associated with each approximation of the real value : this is the case of DUST, PROUD, MUNICH [START_REF] Dallachiesa | Uncertain time-series similarity: return to the basics[END_REF]. [START_REF] Orang | Improving performance of similarity measures for uncertain time series using preprocessing techniques[END_REF] demonstrated that the performances of uncertain similarity measures associated with pre-processing of data are higher than those of traditional similarity measurements.

State of the art on uncertain similarity functions

Uncertain similarity measures can be grouped into two broad categories : deterministic similarity measurements and probabilistic similarity measurements.

Deterministic Similarity Measures

Like traditional similarity measures, deterministic similarity measures return a real number as the distance between two uncertain time series. DUST is an example of deterministic similarity measure.

DUST [START_REF] Murthy | Generalized notion of similarities between uncertain time series[END_REF] Given two uncertain time series

X =< X 1 , . . . , X n > and Y =< Y 1 , . . . , Y n > , the distance between two uncer- tain values X i , Y i is dened as the distance between their true (unknown) values r(X i ), r(Y i ): dist(X i , Y i ) = |r(X i ) -r(Y i )|. (3.2)
This distance is used to measures the similarity of two uncertain values.

ϕ(|X i -Y i |)
is the probability that the real values at timestamp i are equal, given the observed values at that instant :

ϕ(|X i -Y i |) = P r(dist(0, |X i -Y i |) = 0). (3.3)
This similarity function is then used inside the dust dissimilarity function: .4) The distance between uncertain time series X and Y in DU ST is then dened as follows:

dust(X i , Y i ) = -log(ϕ(|X i -Y i |)) + log(ϕ(0)). ( 3
DU ST (X, Y ) = n i=1 dust(X i , Y i ) 2 . (3.5)
The disadvantage of DUST is that it breaks the triangle inequality for small distances. Triangular inequality is a desirable property of dissimilarity functions because it makes it possible to speed-up the comparison of time series. For example, for density based clustering two time series A and B are considered similar if the distance between them is less than . Thus, if the sum of the distances d (A, B) and d (B, C) is less than , we deduce that the distance d (A, C) is also without calculating it. The triangular inequality is also used for the exact indexing of time series [START_REF] Keogh | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF].

To remedy this, we introduce a new deterministic distance function based on the Hellinger distance that evaluate the dissimilarity between uncertain time series and respects triangular inequality.

Hellinger Based Distance To evaluate the similarity between two probability distributions, we can measure the area of intersection between these two probability distributions (Figure 3.4) . If the area of this intersection is zero, then the probability distributions are disjoint, if it is 1 then the probability distributions are identical. The area of this intersection can be calculated using the Bhattacharyya coecient (B) [START_REF] Patra | A new similarity measure using bhattacharyya coecient for collaborative ltering in sparse data[END_REF].

The Hellinger distance, based on the use of the Bhattacharyya coecient, allows to measure the dissimilarity between two probability distributions. It is dened as follows:

Denition 12. The Hellinger distance between two probability measures P and Q that are absolutely continuous relative to some σ-nite measure µ on a measurable space (x, β) is dened by the formula: Theorem 1. The Hellinger distance satisfy the triangle inequality [START_REF] Ibragimov | Statistical estimation: asymptotic theory[END_REF].

H(P, Q) = {2[1 -B(P, Q)]} 1 2 , ( 3
Based on Hellinger distance we dene the HBD distance (Hellinger Based Distance) which measures the dissimilarity between two uncertain time series: Denition 13. The distance between uncertain time series X =< X 1 , . . . , X n > and Y =< Y 1 , . . . , Y n > under Hellinger Based Distance is then dened as follows:

HBD(X, Y ) = n i=1 H(X i , Y i ) 2 .
(3.8) Theorem 2. HBD distance satisfy the triangle inequality.

Proof

. Let X =< X 1 , . . . , X n >, Y =< Y 1 , . . . , Y n >, Z =< Z 1 , .
. . , Z n > be three uncertain time series, we want to proof that

n i=1 H(X i , Y i ) 2 + n i=1 H(Y i , Z i ) 2 ≥ n i=1 H(X i , Z i ) 2 .
(3.9)

First, let us show that:

  n i=1 H(X i , Y i ) 2   ×   n i=1 H(Y i , Z i ) 2   ≥ n i=1 H(X i , Y i )H(Y i , Z i ) (3.
H(X i , Y i ) 2 × n i=1 H(Y i , Z i ) 2 ≥ n i=1 H(X i , Y i )H(Y i , Z i ) 2 (3.11) i.e. n i=1 H(X i , Y i ) 2 × n i=1 H(Y i , Z i ) 2 (3.12) - n i=1 H(X i , Y i )H(Y i , Z i ) 2 ≥ 0 (3.13)
by developing and reducing the expression(3.13), we obtain i.e.

i,j {1,...,k} and i =j

(H(X i , Y i ) -H(Y j , Z j )) 2 ≥ 0 (3.14)
This shows that the inequality (3.10) is true. Let us now show that HBD satises the triangular inequality : according to Theorem 1,

H(X i , Y i ) + H(Y i , Z i ) ≥ H(X i , Z i ) (3.15)
By squaring the two members of the inequality, we obtain .18) according to inequality 3.10, we obtain

H(X i , Y i ) 2 + H(Y i , Z i ) 2 + 2H(X i , Y i )H(Y i , Z i ) ≥ H(X i , Z i ) 2 . (3.16) i.e. n i=1 H(X i , Y i ) 2 + n i=1 H(Y i , Z i ) 2 + 2 n i=1 H(X i , Y i )H(Y i , Z i ) (3.17) ≥ n i=1 H(X i , Z i ) 2 . ( 3
n i=1 H(X i , Y i ) 2 + n i=1 H(Y i , Z i ) 2 (3.19) +2   n i=1 H(X i , Y i ) 2   ×   n i=1 H(Y i , Z i ) 2   ≥ n i=1 H(X i , Z i ) 2 . (3.20) i.e.   n i=1 H(X i , Y i ) 2 + n i=1 H(Y i , Z i ) 2   2 ≥ n i=1 H(X i , Z i ) 2 . (3.21) i.e. n i=1 H(X i , Y i ) 2 + n i=1 H(Y i , Z i ) 2 ≥ n i=1 H(X i , Z i ) 2 . (3.22)
This is what had to be demonstrated

In general, the problem with the deterministic uncertain distances like DU ST or HBD is that their expression varies as a function of the probability distribution of uncertainty, and the probability distribution of the uncertainty is not always available in time series datasets.

Probabilistic Similarity Measures

Probabilistic similarities measures do not require knowledge of the uncertainty probability distribution. Furthermore, they provide the users with more information about the reliability of the result. There are several probabilistic similarity functions, as MUNICH, PROUD, PROUDS or Local Correlation.

MUNICH [START_REF] Aÿfalg | Probabilistic similarity search for uncertain time series[END_REF]: This distance function is suitable for uncertain time series represented by the multiset based model. The probability that the distance between two uncertain time series X and Y is less than a threshold ε is equal to the number of distances between X and Y , which are less than ε, over the possible number of distances:

P r(distance(X, Y )) ≤ ε = |{d ∈ dists(X, Y )|d ≤ ε}| |dists(X, Y )| . (3.23)
The computation of this distance function is very time-consuming.

PROUD [START_REF] Yeh | Proud: a probabilistic approach to processing similarity queries over uncertain data streams[END_REF] Let X and Y be two UTS each one modeled by a sequence of random variables, the PROUD distance between

X and Y is d(X, Y ) = n i=1 (X i -Y i ) 2 .
According to the central limit theorem [START_REF] Homann-Jørgensen | The law of large numbers and the central limit theorem in banach spaces[END_REF], the cumulative distribution of the distances approaches asymptotically a normal distribution:

d(X, Y ) ∝ N ( i E[(X i -Y i ) 2 ], i V ar[(X i -Y i ) 2 ]). (3.24)
Chapter 3. Uncertain time series u-shapelet discovery

Background

As a consequence of that feature of PROUD distance, the table of the normal centered reduced law can be used to compute the probability that the normalized distance is lower than a threshold: P r(d(X, Y ) norm ≤ ).

(3.25)

A major disadvantage of PROUD is its inadequacy for comparing time series of small lengths like u-shapelets. Indeed, the calculation of the probability that the PROUD distance is less than a value is based on the assumption that PROUD distance follows asymptotically a normal distribution. Thus, this probability will be all the more accurate as the compared time series are long (i.e. contain more than 30 data points).

PROUDS [START_REF] Orang | Improving performance of similarity measures for uncertain time series using preprocessing techniques[END_REF] is an enhanced version of PROUD, which suppose that random variables coming from time series are independent and identically distributed.

Denition 14. The normal form of a standard time series X =< X 1 , . . . , X n > is dened as X =< X1 , . . . , Xn > in which for each timestamp i (1 ≤ i ≤ n), we have: .26) PROUDS denes the distance between two normalized time series X =< X1 ... Xn > and Ŷ =< Ŷ1 ... Ŷn > (Denition 14) as follows:

Xi = X i - X S X , X = n i=1 X i n , S X = n i=1 (X i -X) 2 (n -1) . ( 3
Eucl( X, Ŷ ) = 2(n -1) + 2 n i=1 Xi Ŷi . (3.27)
For the same reasons as PROUD, PROUDS is not suitable for the comparison of short time series. Another disadvantage of PROUDS is that it assumes that the random variables are independent: this hypothesis is strong and particularly inappropriate for short time series like u-shapelets. A more realistic hypothesis with time series would be to consider that the random variables constituting the time series are M -dependent. Random variables of a time series are called M -dependent if X i , X i+1 , ..., X i+M are dependent (correlated) and the variables X i and X i+M +1 are independent. However, the M -dependent assumption could make PROUDS writing more complex and its use more dicult because of the choice of the parameter M .

Uncertain Correlation [START_REF] Orang | Correlation analysis techniques for uncertain time series[END_REF]: Correlation analysis techniques are useful for feature selection in uncertain time series data. Indeed, correlation indicates the degree of dependency of a feature on other features. Using this information, redundant features can be identied. The same strategy can be useful for u-shapelet discovery. Uncertain correlation is dened as follows : Denition 15. (Uncertain time series correlation) Given UTS X =< X 1 , . . . , X n > and Y =< Y 1 , . . . , Y n >, their correlation is dened as:

Corr(X, Y ) = n i=1 Xi Ŷi /(n -1), (3.28)
where Xi and Ŷi are normal forms of X i and Y i (Denition 14), respectively. X i and Y i are supposed to be independant continous random variables.

If we know the probability distribution of random variables, it is possible to determine the probability density function associated with the correlation, which will subsequently be used to calculate the probability that the correlation between two time series is greater than a given threshold.

Uncertain correlation has however some drawbacks :

• It is too sensitive to transient changes, often leading to widely uctuating scores;

• It cannot capture complex relationship in timeseries;

• It requires to know the probability distribution function of the uncertainty or to make some assumption on the independence of the random variables contained in time series.

Because of all theses drawbacks, uncertain correlation cannot be used as it is for u-shapelet discovery. The next paragraph presents a generalisation of correlation coecient that is not an uncertain similarity function but is still interesting for u-shapelet discovery. Local Correlation [START_REF] Papadimitriou | Local correlation tracking in time series[END_REF] x τ,w ⊗ x τ,w .

(3.29) where x τ,ω is a sub-sequence of the time series of length w and started at τ , x ⊗ y = xy T is the outer product of x and y. The sample set of m windows is centered around time t. The number of windows is typically xed to m = w.

Given the estimates Γt (X) and Γt (Y ) for the two time series, the next step is how to compare them and extract a correlation score. This goal is reached using the spectral decomposition. The eigenvectors of the autocorrelation matrices capture the key aperiodic and oscillatory trends, even in short time series. Thus, the subspaces spanned by the rst few (k) eigenvectors are used to locally characterize the behavior of each series. Denition 17 formalizes this notion: Denition 17. (LoCo score). Given two series X and Y , their LoCo score is dened by

t (X, Y ) = 1 2 ( U T X u Y + U T Y u X ) (3.30)
where U X and U Y are the k rst eigenvector matrices of the local autocorrelation Γt (X) and Γt (Y ) respectively, and u X and u Y are the corresponding eigenvectors with the largest eigenvalue.

Intuitively, two time series X and Y will be considered as close when the angle α formed by the space carrying the information of the time series X and the vector carrying the information the time series Y is zero. In other words X and Y will be close when the value of cos(α) will be 1 (Fig. 3.5). The only assumption made for the computation of LoCo similarity is that the mean of time series data point is zero. This could be easily achieved with znormalization. LoCo similarity function has many interesting properties and does not require to:

Ph.D. Thesis

• Know the probability distribution of the uncertainty,

• Assume the independence of the random variables or the length of u-shapelets.

LoCo is therefore interesting for feature selection, but we still need a dissimilarity function to be able to discover u-shapelet. In the next paragraph, we dene a dissimilarity function that has the same properties as LoCo and that is robust to the presence of uncertainty.

3.3

Frobenius cOrrelation for uncertain Time series u-Shapelet discovery (FOTS)

Dissimilarity function

The LoCo similarity function dened on two multivariate time series X and Y approximately corresponds to the absolute value of the cosine of the angle formed by the eigenspaces of X and Y (|cos(α)|). A straightforward idea would be to use the sin(α) or α-value as a dissimilarity function but this approach does not work so well, because the sine and the angle are not discriminant enough for eigenvector comparison for clustering purpose. We thus proposed a new dissimilarity measure named Frobenius cOrrelation for uncertain Time series u-Shapeletdiscovery (FOTS) and based on the following denition (Denition. 18):

Denition 18. Given two series X and Y , their FOTS score is dened by

F OT S(X, Y ) = U X -U Y F = m i=1 k j=1 (U X -U Y ) 2 ij (3.31)
where F is the Frobenius norm, m is the length of time series and k is the number of eigenvectors.

Because FOTS computation is based on the comparison of the k-rst eigenvectors of the autocorrelation matrices of the time series, it has the same desirable properties of the LoCo similarity function, that is:

• It allows to capture complex relationships in time series like the key oscillatory (e.g., sinusoidal) as well as aperiodic (e.g., increasing or decreasing) trends that are present;

• It allows to reduce the sensibility to transient changes in time series;

• It is appropriate for the comparison of short time series. Theorem 3. (HomanWielandt) [START_REF] Bhatia | A generalization of the Homan-Wielandt theorem[END_REF] If X and X + E are n × n symmetric matrices, then :

n i=1 (λ i (X + E) -λ i (X)) 2 ≤ ||E|| 2 F , (3.32)
where λ i (X) is the ith largest eigenvalue of X, and ||E|| 2 F is the squared of the Frobenius norm of E.

The next section explains how FOTS is integrated in the Scalable Unsupervised Shapelet discovery algorithm [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF].

Scalable u-shapelets Algorithm with FOTS score

In this section we do not dene a new SUShapelet algorithm [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF]], but we explain how we use SUShapelet algorithm with FOTS score (FOTS-SUSh) to deal with uncertainty.

The gap is an essential criterion for the selection of u-shapelets candidate. It is subject to uncertainty because its calculation is based on the Euclidean distance.

To remedy this, we propose to use the FOTS score instead of a simple Euclidean distance when calculating the gap in the Scalable u-shapelet algorithm.

• Algorithm 2 presents how we compute the orderline using FOTS score,

• Algorithm 3 calculates the orderline and sorts the time series according to their proximity to the u-shapelet candidate (line 2 and 3). A u-shapelet is considered present in a time series if its distance to it is less than or equal to a given threshold. Thus, algorithm select thresholds to build a cluster Da whose size varies between lb and ub (line 5). The algorithm then searches among the selected thresholds the one that has a maximum gap (line 6 to 11).

Denition 19. The sub-sequence FOTS dissimilarity sd f (S, T ) between a time series T and a sub-sequence S is the minimum FOTS score between the sub-sequence S and all possible sub-sequences of T of length equal to the length of S.

Clustering with u-shapelets

There are many ways to cluster time series data described by u-shapelets. This approach is a direct implementation of the u-shapelet denition. The algorithm iteratively splits the dataset with each discovered u-shapelet into two groups D A and D B . The time series that belong to D A are considered as members of the cluster formed by the u-shapelet and are then removed from the dataset. A new u-shapelet search continues with the rest of the data until there is no more time series in the dataset or until the algorithm is no more able to nd u-shapelet. As a stopping criterion for the number of u-shapelets extracted, the decline of the u-shapelet gap score is examined: the algorithm stops when the gap score of the newly-found u-shapelet becomes less than half of the gap score of the rst discovered u-shapelet.

Choosing the length N of a u-shapelet: The choice of the length of ushapelet is directed by the knowledge of the domain to which the time series belongs. As part of these experiments, we tested all numbers between 4 and half the length of the time series. We considered as length of u-shapelet the one that allows to better cluster the time series.

Choosing the length w of the windows : The use of overlapping windows for calculating the autocorrelation matrix makes it possible to capture the oscillations present in the time series. During these experiments, we considered that the size of the window is equal to half the length of the u-shapelet.

Choosing the number k of eigenvectors: A practical choice is to x k to a small value; we used k = 4 throughout all experiments. Indeed, key aperiodic trends are captured by one eigenvector, whereas key oscillatory trends manifest themselves in a pair of eigenvectors.

2 dis ← ComputeOrderline(s, D) 3 dis ← sort(dis) gap ← 0 4 for i ← lb to ub do 5 D A ← dis ≤ dis(i), D B ← dis > dis(i) 6 m A ← mean(D A ), m B ← mean(D B ) 7 s A ← std(D A ), s B ← std(D B ) 8 currGap ← m B -s B -(m A + s A ) 9 if currGap > gap then 10 gap ← currGap 11 return gap

Evaluation Metrics

To evaluate the quality of the u-shapelets found, we use them for a clustering task. Dierent measures for time series clustering quality have been proposed, including Jaccard Score, Rand Index, Folkes and Mallow index, etc. In our case we had ground truth class labels for the datasets, we could use this external information to evaluate the true clustering quality by using Rand Index. Moreover, Rand Index appears to be the quality measure most commonly used [START_REF] Zakaria | Clustering time series using unsupervised-shapelets[END_REF] [ [START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF]] [Zhang et al., 2016], and many of the other measures can be seen as minor variants of it [START_REF] Halkidi | On clustering validation techniques[END_REF]. The Rand Index [Rand, 1971] is calculated as follows:

Let Lc be the cluster labels returned by a clustering algorithm and Lt be the set of ground truth class labels. Let A be the number of time series that are placed in the same cluster in L c and L t , B be the number of time series in dierent clusters in L c and L t , C be the number of time series in the same cluster in Lc but not in L t and D be the number of time series in dierent clusters in L c but in same cluster in L t . The Rand Index is computed as follows:

Rand Index = (A + B)/(A + B + C + D).
(3.33)

Comparison with u-shapelet

Similarly to [START_REF] Dallachiesa | Uncertain time-series similarity: return to the basics[END_REF], we tested FOTS-SUSh on 17 real world datasets coming from UCR archive [START_REF] Chen | The ucr time series classication archive[END_REF] and representing a wide range of appli-cation domains1 . The training and testing sets have been joined to obtained bigger datasets. Table 3

Comparison with k-Shape and USLM

k-Shape and USLM are two u-shapelets based clustering algorithms for time series presented in [START_REF] Zhang | Unsupervised feature learning from time series[END_REF]. In this section, we have compared the Rand Index obtained by FOTS-SUShapelet and the one obtained by k-Shape and USLM on 5 datasets (Table 3.3). The results of k-Shape and USLM was previously reported in [START_REF] Zhang | Unsupervised feature learning from time series[END_REF]. This comparison shows that in general, FOTS-SUShapelet perform better than k-Shape and USLM.

Discussion

The

Time complexity analysis

ED can be computed in O(n) and FOTS score is computed in O(n ω ), 2 ≤ ω ≤ 3 due to the time complexity of the eigenvector decompositions [START_REF] Pan | The complexity of the matrix eigenproblem[END_REF]].

The computation of FOTS score is then more expensive in time than that of ED (Fig. 3.6). However, its use remains relevant for u-shapelets research as they are often small.

Robustness to uncertainty

In order to assess the robustness of FOTS to the presence of uncertainty, we selected two time series from the ItalyPowerDemand dataset and compared them using the Euclidean Distance on the one hand and the FOTS score on the other. We then added a white noise that follows a normal distribution of zero mean and 0.1 variance

Conclusion and Future Work

The purpose of this chapter was to discover u-shapelets on uncertain time series. In that aim, we have proposed a dissimilarity score (FOTS) adapted to the comparison of short time series, of which computation is based on the comparison of the eigenvector of the autocorrelation matrices of the time series. This score is robust in the presence of uncertainty, it is not very sensitive to transient changes, and it allows capturing complex relationships between time series such as oscillations and trends.

The FOTS score was used with the Scalable Unsupervised Shapelet Discovery algorithm for clustering 17 literature datasets and show that FOTS-SUShapelet consumes more time than UShapelet, but has better performances regarding clustering Rand Index. FOTS-SUSh denes a new framework for clustering uncertain time series because it combines the benets of the u-shapelets algorithm, which reduces the adverse eects of uncertainty, and the benets of the FOTS score, which is robust to the presence of uncertainty.

As a perspective to this work, we plan to use the FOTS score for fuzzy clustering of uncertain time series. Another important aspect of time series coming from wheelchair locomotion is that they are cyclic, and the analysis of this movement is based on those cycles. The next chapter explains how we have captured this important feature.

Key points

• We proposed a correlation-based measure of dissimilarity that captures time series properties and is robust to the presence of uncertainties.

•We experimentally showed that this measure of dissimilarity improves the quality of clustering with UShapelets.

DR( C, Q) = n N N i=1 (c i -qi ) 2 . (4.1)
The main objective of PAA was to reduce the length of the time series. However, as it computes the segments means, it also allows us to compare two time series C and Q from the properties of their segments (Equation 4.1 ).

[ [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF] were based on the PAA method to provide a symbolic representation of time series called Symbolic Aggregate Approximation (SAX). The objective of SAX is to assign a letter to each segment. To do this, the domain of the values of the time series is divided into intervals so that every point of the temporal series has approximately the same probability to belong to an interval and a letter is associated with each of these intervals. Then each segment of the time series is associated with the letter of the interval to which belongs its average (Fig. 4.4).

With SAX, the distance M IN DIST between two strings Q and Ĉ of length N is calculated from the distance between the borders of the intervals represented by each character in the string (Equation 4.2).

Introduction

M IN DIST ( Q, Ĉ) = n N N i=1 (dist(q i , ĉi )) 2 . (4.2)
qi et ĉi are characters and dist() is the distance between the borders of the intervals which represent these characters [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF]. However, two segments with very dierent shapes can have the same average and be represented by the same letter: the mean is not enough to dene a segment. In order to solve this problem, [Lkhagva and Kawagoe, 2006] proposed the ESAX model that considers three properties for each segment: its mean, its minimum and maximum (Fig. 4.5).

Thereafter, [START_REF] Sun | An improvement of symbolic aggregate approximation distance measure for time series[END_REF] proposed the SAX-TD model that takes into account two properties for each segment: its mean and trend. They then adjust the distance used by the SAX method for it to take into account the trend (Fig. 4.6).

Both methods provide better results than the SAX method [START_REF] Sun | An improvement of symbolic aggregate approximation distance measure for time series[END_REF]. However, they have the disadvantage of increasing the number of symbols required to represent the time series. Indeed, the method ESAX triple the size of the representation of a time series provided by the SAX method, while the SAX-TD method the double. In addition, the previous four methods have two major drawbacks: they consider xed-size segments, while the cycles are variable-sized segments, and they do not take into account the characteristic properties of cycles such as the duration and the surface under a cycle. Our goal is to provide a symbolic representation that takes into account several properties for each cycle, but without increasing the number of symbols used for the representation.

The symbolic representations obtained have another advantage; they allow to [START_REF] Begum | Rare time series motif discovery from unbounded streams[END_REF], clustering, classication, indexing and also some interesting algorithms for text processing or the bio-informatics community [START_REF] Aach | Aligning gene expression time series with time warping algorithms[END_REF], Papapetrou et al., 2011, Dietterich, 2002].

SAX-P

A prerequisite to be able to build a symbolic representation based on the cycles of the cyclic time series is to be able to segment the cyclic time series into consecutive cycles.

Segmentation of cyclic time series

The principle used to segment cyclic time series is as follows: A cycle contains all the data points between the beginning of two consecutive peaks. To locate the peaks, we set a threshold (Fig. 4.8). The threshold considered can be the rst or the second quartile of the time series data point.

If the current value of the time series is below this threshold, then it is a peak. It is then necessary to turn back to nd the moment of the beginning of the peak. The gure (Fig. 4.9) presents the results obtained after segmentation of a cyclic time series.

From cycles to letters

The method SAX-P is based on SAX and works as follows:

1. A cyclic time series is split in successive segments using a threshold for identifying the beginning and the end of cycles, which have variable durations;

2. Several parameters (properties) are computed on each segment: cycle time, push time, mean, median, standard deviation, minimum and maximum values, and the area under the time series curve. As all these parameters have dierent units, they must be normalized (i.e. centered and reduced) (Fig. 4.10 );

3. Segments are then gathered in clusters using a classication algorithm [START_REF] Esling | Time-series data mining[END_REF] and each cluster is named by a capital letter (Fig. 4.11); Each segment is replaced by the letter of the cluster to which it belongs, so that the initial cyclic time series is then represented by a string of characters (Fig. 4.12);

The distance between two strings, which may have dierent numbers of characters, is computed using Dynamic Time Warping [START_REF] Petitjean | Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classication[END_REF] which is known as the best distance measure for several domains [START_REF] Ding | Querying and mining of time series data[END_REF]. The distance between two characters is the euclidean distance between the centers of the classes represented by those characters.

Unlike SAX, ESAX and SAX-TD methods that require to x the length of segments to consider when building the symbolic representation of a time series, SAX-P considers the cycles which constitute basic unit of analysis of time series recorded during cyclic movements and also allows taking into account several characteristic features for each cycle. Figure 4.12 presents the symbolic representations obtained with the SAX method (in small letters) and SAX-P (in capital letters). It illustrates that SAX-P unlike SAX considers cycles of the time series during the construction of the symbolic representation. The data sets used throughout these tests have been obtained from experiments conducted with 12 subjects1 with disabilities in the aim to understand MWC locomotion. The measurements produced cyclic, uncertain and noisy time series (Fig. 4.13). All subsequent processing and analyses are performed on z-moment time series measured on both rear wheels of the FRET-2.

The data recorded have four main characteristics:

Length of time series: the length of the time series is due to the high acquisition frequency (100 Hz) of the force and torque sensor. For instance, a 10-minute recording generates a time series of:

100 Hz × 60 s × 10mn = 60, 000 data points.

The maximum length (107, 227 data points) of the time series analysed here was reached by the z-moment of the left wheel of subject S02 (Fig. 4.13). The length of time series is a crucial issue because their processing time is highly dependent on their length. As an illustration, the time complexity of comparing two time series using the DTW alignment algorithm is O(n 2 ) where n is the length of the time series.

Cycles in time series: The cyclic aspect of the time series comes from the cyclic nature of wheelchair propulsion. Indeed, this movement consists in a succession of Uncertainty in time series: The presence of uncertainty in sensor measurements is intrinsic to the calibration process of sensors in general, and of the sixcomponent dynamometer used in this work. When a force is applied to a piezoresistive sensor, it causes a deformation of the sensing element, which consists in strain gauges2 stuck on a small metallic beam and connected as a Wheatstone bridge 3 This deformation induces a change in the resistance of the strain gauges and thus a change in the output voltage of the Wheatstone bridge. According to Hooke's law, this is proportional to the force intensity. Thus, when using a calibrated sensor, the user is to measure a variation in sensor signal and uses the proportionality relationship (Hooke's law) to infer the intensity of the force that has been applied. Calibrating a sensor consists in constructing this proportionality relationship by applying a wide range of forces on the sensor, within the limits of the mechanical characteristics of the sensing element. Doing so, we record a sequence of couples of force intensity and electrical voltage, which is used to compute a regression line which will then be used to deduce the applied force intensity knowing the voltage variation. However, the regression line generally does not dene a perfect proportionality relationship; in fact, it minimizes the error made but does not cancel it. This error (Fig. 4.15) introduces uncertainty into the estimation of the applied force intensity. It is thus essential to take this error into account when evaluating time series to extract relevant information from them. Characterization of uncertainty is a time-consuming task (Appendix C) and is not always possible because sensor calibration data are generally not available.

Noise in time series: n the time series analysed here, the noise comes from the sensitivity of the dynamometer, which has been designed to measure low-intensity forces applied to the handrim during wheelchair locomotion. These forces can come from the texture of the ground (e.g. granular road),unexpected contacts of the user's hands and arms with the handrim during the ecovery phase or other. In cyclic time series, noise is problematic because it inuences the division into cycles, the computation of properties that characterize a propulsion cycle and the calculation of the distance between two time-series. In the following sections, we explain how we used these data for analysing wheelchair locomotion.

The symmetry of Manual Wheelchair Locomotion

For a long time, experts have assumed that wheelchair locomotion was symmetrical, which made it possible to construct measuring instruments consisting of a single wheel [START_REF] Brouha | Continuous recording of cardiac and respiratory functions in normal and handicapped people[END_REF]. Subsequently, the conclusions that were drawn from the measurements made with one wheel were generalized to both upper limbs of the subject. Then, [Langbein and Fehr, 1993] built a roller ergometer able of separately measuring the speed and resistance of the left and right wheels of the MWC during its use. The measurements made with this roller ergometer revealed a dierence between the properties measured by the left and right wheels and exhibited the asymmetric character of wheelchair locomotion. In this paragraph, we used the SAX-P symbolic representation and the additional information we had on the subjects to carry out a new analysis of the symmetry of wheelchair locomotion. Even if a MWC user performs the same number of pushes on both rear wheels during a straight displacement, these cycles may have dierent properties, which in our case is expressed by dierent letters in the character strings representing the propulsion cycles applied by the user to the right and left rear wheels. This asymmetry of wheelchair locomotion can be evaluated by calculating a relative Edit distance that counts the number of dierent letters between the characters strings of the right and left wheels during a same straight displacement (lap).

D(X, Y

) = 1 n n i=1 [X i = Y i ].
Where X, and Y are character strings. In all the laps analysed in this study (Table 4.1), almost all subjects showed a propulsion asymmetry during their displacements, and this asymmetry was dierent for all subjects. Indeed, it is almost null for subject S02 who has only performed Atype pushes throughout his displacements, whereas it is quite high (0.7) for subject S05. In order to identify which factors might inuence propulsion asymmetry, we cross-referenced the previous results with the number of years of wheelchair locomotion practice of the subjects who participated in the experiment (Table 4.2). We observed that subject S05 who has the least experience in wheelchair locomotion (2 months) has a very asymmetric propulsion (Edit distance = 0.7) whereas subject S02 who has a long experience of wheelchair practice (33 years) has a very symmetric propulsion (Edit distance = 0.05). The Pearson's correlation coecient (r = -0.93) between asymmetry and number of years of wheelchair practice showed that the longer is the subjects' experience in wheelchair locomotion, the more symmetrical is their propulsion during a straight displacement.

... S02_e1_RD_H4-Cycle-C AAAAAAAAAAA 0 S02_e1_RG_H4-Cycle-C AAAAAAAAAAA S02_e1_RD_H4-Cycle-D AAAAAAA 0 S02_e1_RG_H4-Cycle-D AAAAAAA Moyenne 0,05 S03_E3_T_RD-Cycle-A EEBCB 0,40 S03_E3_T_RG-Cycle-A EEECC S03_E3_T_RD-Cycle-B BBBBCB 0,33 S03_E3_T_RG-Cycle-B EBBBCC S03_E3_T_RD-Cycle-C EBBBBBC 0,17 S03_E3_T_RG-Cycle-C EBBBBCC S03_E3_T_RD-Cycle-D EBCBC 0,86 S03_E3_T_RG-Cycle-D EEECBCC S03_E3_T_RG-Cycle-E EBBBBBC 0,29 S03_E3_T_RD-Cycle-E EBEBBCC S03_E3_T_RD-Cycle-F EEEBBCC 0,43 S03_E3_T_RG-Cycle-F EEECCCD S03_E3_T_RG-Cycle-G EEBCCC 0,57 S03_E3_T_RD-Cycle-G BEECBCC S03_E3_T_RD-Cycle-H EEBCBCC 0,29 S03_E3_T_RG-Cycle-H EBBBBCC S03_E3_T_RG-Cycle-I CC 1,00 S03_E3_T_RD-Cycle-I BBD Moyenne 0.48 S04_E1_T_RD-Cycle-A EEDBBCCC 0,38 S04_E1_T_RG-Cycle-A DEEBBCCA S04_E1_T_RG-Cycle-B EEBDACC 0,63 S04_E1_T_RD-Cycle-B BBBBCCCC S04_E1_T_RD-Cycle-C ECBCCCC 0,57 S04_E1_T_RG-Cycle-C BBECCC S04_E1_T_RG-Cycle-D EBBCC 0,57 S04_E1_T_RD-Cycle-D EBBBBBC S04_E1_T_RD-Cycle-E EBBC 0,50 S04_E1_T_RG-Cycle-E EBC S04_E1_T_RD-Cycle-F EBC 0,33 S04_E1_T_RG-Cycle-F BBC Moyenne 0.5 Continue to the next page Subject Straight displacement Relative Edit Distance Following ... S05_E3_T_RD-Cycle-A BBBBCDD 0,86 S05_E3_T_RG-Cycle-A EEBDBCA S05_E3_T_RD-Cycle-B BBCDCDBC 0,63 S05_E3_T_RG-Cycle-B BBBCCA S05_E3_T_RD-Cycle-C EDDDDDCAD 0,78 S05_E3_T_RG-Cycle-C BBBCBCA S05_E3_T_RD-Cycle-D BBCCDCA 0,29 S05_E3_T_RG-Cycle-D BBCBCCA S05_E3_T_RD-Cycle-E BBBCDCCD 0,75 S05_E3_T_RG-Cycle-E BCDDCDA S05_E3_T_RD-Cycle-F BCBDCDCD 0,63 S05_E3_T_RG-Cycle-F DBBCDDAD S05_E3_T_RD-Cycle-G BC 1,00 S05_E3_T_RG-Cycle-G DA Moyenne 0.70 S07_e1_T_RD-Cycle-A AEDBDA 0,33 S07_e1_T_RG-Cycle-A EEBBD S07_e1_T_RG-Cycle-B BBCCC 0,00 S07_e1_T_RD-Cycle-B BBCCC S07_e1_T_RD-Cycle-C ECDADAA 0,71 S07_e1_T_RG-Cycle-C EBCCD S07_e1_T_RG-Cycle-D BBBCCD 0,57 S07_e1_T_RD-Cycle-D EBCCADA S07_e1_T_RD-Cycle-E EBCCCAD 0,57 S07_e1_T_RG-Cycle-E BBBCCC S07_e1_T_RD-Cycle-F BC 1,00 S07_e1_T_RG-Cycle-F EC Moyenne 0.53 S08_e3_T_RD-Cycle-A DDDDDAD 0,29 S08_e3_T_RG-Cycle-A DDDDDDA S08_e3_T_RD-Cycle-B DDDADDDDAA 0,

Subject Edit distance

Group Manual Wheelchair users according to their motor skills

In the context of the Paralympic Games, for instance, it is essential to be able to group wheelchair users according to their motor abilities. Indeed, this classication allows to form teams based on functional and not physiological criteria and thus to guarantee fairness of competitions. However, the assessment of motor skills can be subjective, as it is sometimes based on observation of matches, or on a test set oered to the subject in a MWC. In both cases, subjects' mobility is appreciated by an expert who scores this ability on a scale.

In this section, we present a dierent, more objective approach for comparing subjects' mobility based on measurements made during their actual use of the instrumented MWC (FRET-2). Our aim was that the method used for the evaluation of motor abilities remains understandable by clinical and practical experts in the eld. The experiments presented in this section were performed by 11 subjects with dierent anthropometric and physiological characteristics who propelled the FRET-2 (Table 4.

Ph.D. Thesis

First, we applied the SAX-P symbolic representation to the z-moments (Mz) measured on the right and left wheels of FRET-2 during subjects' displacements. This method allowed to compare the propulsion cycles performed by the subjects during their displacements. Next, we compared subjects based on the relative occurrence frequency of each cycle type in each subject's displacements (Table 4.4) A B C D E S02 64 0 0 0 0 S03 7 43 35 2 28 S04 2 25 26 3 13 S05 9 30 25 25 3 S07 7 17 21 9 7 S08 26 2 1 49 0 S09 29 0 1 39 0 S10 6 21 31 5 10 S11 13 9 0 38 0 S12 22 2 0 42 0 S13 35 11 0 80 0 Table 4.4: Occurrence frequency of each cycle type in each subject's displacements. This comparison is based on cosine similarity, a method that is used in the literature to compare text documents using the frequency with which words appear in these documents. Cosine similarity is dened as follows:

Let V 1 and V 2 be two integer vectors,

cos(V 1 , V 2 ) = V 1 .V 2 V 1 × V 2 .
Where . is the dot product and d is the norm of the vector d.

For example, we will evaluate the similarity between subjects S02 and S03.

V S02 = (64, 0, 0, 0, 0), (7,43,35,2,28).

V S03 =
First we calculate the dot product between V S02 and V S03 :

V S02 .V S03 = 64 × 7 + 0 × 43 + 0 × 35 + 0 × 2 + 0 × 28 = 448.
Then we calculate the vector norm V S02 , and V S03 .

V S02 = √ 64 × 64 + 0 × 0 + 0 × 0 + 0 × 0 + 0 × 0 = 64, V S03 = √ 7 × 7 + 43 × 43 + 35 × 35 + 2 × 2 + 28 × 28 = 62.54.
The cosine similarity is then equal to cos(V S02 , V S03 ) = 448 64 × 62.54 = 0.112.

The similarity matrix between all wheelchair users is dened using the same method (Table 4.5). The cosine similarity of any subject with himself is logically equal to 1. S02 S03 S04 S05 S07 S08 S09 S10 S11 S12 S13 S02 1.000 0.112 0.052 0.190 0.232 0.468 0.597 0.152 0.316 0.464 0.398 S03 The denition of a good representation and a good distance function are the most critical step in any distance based clustering method. Having doing so, we use a hierachical clustering algorithm for the ease of interpretation of the results as suggested in [START_REF] Kumar | Clustering seasonality patterns in the presence of errors[END_REF]. The clustering algorithm starts with each subject being in a singleton cluster and at each stage combine the closest pair of clusters into a single cluster until a threshold value is reached or a predened number of clusters is obtained. In this experiment, we would like to distinguish subject with high, middle and low locomotion capabilities, we then consider three clusters (Fig.

4.16).

The results of this classication showed that only subject S02 is classied in cluster C1 and he is also the only subject who mainly performed A-type cycles. Subjects S03, S04, S07 and S10 were classied in cluster C2 and all of them performed a majority of B-and C-type cycles. Subjects S05, S08, S09, S11, S12, and S13 were classied in cluster C3 and these subjects mainly performed A-and D-type cycles. Subject S05 is a particular case because he also performed B-and C-type cycles, and he could thus have been classied in cluster C2. He was nally classied in cluster C3 because of the signicant occurrence of D-type cycles during his displacements. These results allow us to deduce that the subjects who are in the same cluster have similar motor abilities, and that subjects belonging to cluster C2 have higher motor abilities than those belonging to cluster C3, who have higher motor abilities than Ph.D. Thesis those belonging to cluster C1 (C2 > C3 > C1). We also infer that the majority presence of B-and C-type cycles characterize the propulsion of subjects with a signicant motor capacity, that D-type cycles characterize the propulsion of subjects with an average motor capacity, and that A-type cycles characterize subjects with a weak motor capacity.

The additional information on wheelchair users (Table 4.3) indicates that the lonely subject in cluster C2 (S02) has indeed reduced physical abilities, but has been using his MWC once a week for 33 years. This long experience has allowed him to acquire a symmetrical propulsion technique, but not to increase his propulsion capacity. Subjects gathered in cluster C2 had either a thoracic lesion (S03 and S04) or a lumbar lesion (S07 and S10), whereas subjects gathered in cluster C3 had either a cervical lesion (S08) or a thoracic lesion (S11, S12 and S13). In this analysis, we wanted to establish that the data measured during locomotion with a wheelchair eld-ergometer (FRET-2) provides a dierent but relevant view of wheelchair locomotion. [START_REF] Athanasiou | A bayesian network model for the diagnosis of the caring procedure for wheelchair users with spinal injury[END_REF] established that motor abilities of wheelchair users primarily depend on their level of spinal cord injury. However, through these experiments, we show that assessing motor skills based on measurements made makes it possible to carry out a more detailed analysis of the motor skills of Manual Wheelchair users.

Conclusion

In this ongoing work, we proposed a method of symbolic representation of cyclic time series called SAX-P. This method is used to represent a cyclic time series as a string, each character representing a class of the cycles of the considered time series. The character strings obtained were then compared using Edith Distance and cosine similarity. Those comparisons allowed us to highlight the asymmetrical character of manual wheelchair locomotion, but also to show that manual wheelchair locomotion became more and more symmetrical with years of practice. The experiments also showed that knowledge of the physiological characteristics of subjects in manual wheelchairs was not sucient for an evaluation of the motor abilities of manual wheelchair users and that an evaluation of locomotion requires measurements to be made in the actual situation of use of the manual wheelchair (Appendix A).

Ongoing research is devoted to the evaluation of the robustness of the symbolic representation (SAX-P) to the presence of uncertainty in the data and on applying SAX-P to a supervised classication of cyclic time-series in bio-mechanics.

Key points

• We propose a symbolic representation of cyclic time series based on the properties of the cycles.

• We show that this symbolic representation improves the visualization and processing of cyclic time series from manual wheelchair locomotion.

Communications :

-Siyou Fotso VS, Mephu-Nguifo E, Vaslin Ph. Symbolic representation of cyclic time series: application to biomechanics. Constructive Machine Learning workshop at International Conference on Machine Learning , France, July 2015 -Siyou Fotso VS, Mephu-Nguifo E, Vaslin Ph. Représentation symbolique de séries temporelles cycliques basée sur les propriétés des cycles : application à la biomécanique . Treizièmes Rencontres des Jeunes Chercheurs en Intelligence Articielle (RJCIA 2015), Rennes, France, Jun 2015 -Siyou Fotso VS, E. M. Nguifo, and P. Vaslin, "Symbolic representation of propulsion cycles in manual wheelchair locomotion," Comput. Methods Biomech. Biomed. Engin., vol. 18, no. sup1, pp. 20602061, 2015. -C. Sauret, Siyou Fotso VS, J. Bascou, H. Pillet, E. Mephu-Nguifo, P. Fodé, and P. Vaslin, "Cluster analysis to investigate biomechanical changes during learning of manual wheelchair locomotion: a preliminary study," Comput. Methods Biomech. Biomed. Engin., vol. 18, no. sup1, pp. 20582059, 2015. Ph.D. Thesis General conclusion and Future works Aims Our primary objective throughout this work was to analyze manual wheelchair locomotion using measurements made by the sensors when using the wheelchair. This primary objective is divided into three specic goals: how to pre-treat time series to reduce their length and therefore their processing time, how to take into account the existence of uncertainty in the time series during their analysis and nally how to base the exploitation of time series on the cycles that constitute them. Each of these specic objectives has resulted in proposed models.

Summary of contributions

Reduce the length of time series with FDTW We proposed a heuristic named FDTW that nd a suitable parameter to use with the piecewise aggregate approximation algorithm with the aim to reduce the length of time series for classication purpose. This heuristic is based on Greedy Randomized Adaptative Search Procedure but denes a specic global search strategy. Extensive experimentation has been run out and shows that the compression with FDTW allows reducing the length of time series while keeping their main shape. Moreover, the compression with FDTW can enhance the accuracy of classication because it will enable avoiding pathological alignment with Dynamic Time Warping algorithm this amelioration is particularly perceptible with synthetic datasets.

Dealing with uncertainty using FOTS score

We introduce a novel dissimilarity score for the comparison of time series named FOTS for Frobenius Correlation for Time series uShapelet discovery. This dissimilarity score is based on local correlation and allows to capture internal properties of the time series while being robust to uncertainty because its computation is based on the comparison of eigenvectors of the autocorrelation matrices of time series. This score has been used for clustering purpose with UShapelet clustering algorithm an shows a signicant improvement of the quality of clustering according to the rand Index.

Taking into accounts cycles with a symbolic representation Time series coming from wheelchair locomotion are cyclic due to the cyclic aspect of the wheelchair locomotion. The analysis of the wheelchair locomotion is based on those cycles, but none of the data mining models of the literature consider this aspect. We then proposed a symbolic representation of cyclic time series based on the properties of cycles that allow better visualization of the data and a better comprehension of the results obtained after the data mining process. We use this symbolic representation for the analysis of the wheelchair locomotion of eleven users, and this symbolic representation allows establishing that the wheelchair locomotion is asymmetric but this asymmetry get lower and lower with the years' of practice. This symbolic representation also allows a more precise evaluation of motor capabilities of manual wheelchair mainly based on the eort measure during their use of the manual wheelchair.

Future works

Compression with FDTW

One perspective is to model the time series compression problem using a multiobjective optimization problem where one objective function would be compression and the other the classication of time series. Another problem we want to explore is that of multi-dimensional time series compression.

Uncertainty -FOTS

One perspective to this work consists in testing FOTS-SUSh on the 85 data sets of the UCR database, we also plan to use the FOTS score for classication and for fuzzy clustering of uncertain time series. It is also important to speed-up the computation of FOTS based on sequential learning principles [Calandriello, 2017]. We also propose to use the FOTS score for the multidimensional time series shapelet discovery.

SAX-P

Another important perspective is to evaluate the robustness of the symbolic representation (SAX-P) to the presence of uncertainty in the data and on applying Application the perspectives on the application to wheelchair locomotion are as follows :

Multidimensionality for a better characterization of the propulsion technique

The analyses in this thesis are based on the Z moment of the wheels of the manual wheelchair. However, several measurements, including seat, back and footrest forces, were taken during the locomotion of the manual wheelchair users. Considering these signals could allow a better analysis of the subjects' movement and therefore suggests that we propose multidimensional data mining models that would simultaneously take into account all the measurements and their characteristics, namely their length, the presence of uncertainty, and the cyclical nature of specic measures.

Fuzziness for a more realistic categorization

As we saw in Chapter 6 with subject S05, a subject can be very likely to belong to two or more groups. It would, therefore, be wise to associate each assignment with a degree of trust about the subject's group member. This data mining amounts to considering fuzzy approaches in the analysis of time series from manual wheelchair locomotion. Introduction Wheelchair locomotion concerns many people, for dierent reasons: genetic (myopathy), accidental (spinal cord injury, lower extremity amputee), degenerative (multiple sclerosis, poliomyelitis) or just related to the natural aging of locomotor functions (muscle degeneration, arthritis of the lower limbs, etc.). Then, in the 34 developed countries, it is estimated that 1% or 10,000,000 people require a wheelchair. In the 156 developing countries, it is estimated that at least 2% or 121,800,000 people require a wheelchair. Overall, of the 7,091,500,000 people in the world, approximately 131,800,000 or 1.85% need a wheelchair [START_REF] Needs | Analysis of Wheelchair Need -Wheelchair Foundation[END_REF]. However, the use of manual wheelchair is not without risk.

A.2

The problem of locomotion manual wheelchair locomotion Although the wheelchair use improves the mobility of its users, doctors quickly realized that it often leads to sedentarization, and to related problems of obesity, diabetes, etc. Also, to promote daily physical activity, sport has been strongly encouraged [START_REF] Machida | Resilience in competitive athletes with spinal cord injury: the role of sport participation[END_REF]. However, intensive and prolonged sports practice in Manual WheelChair (MWC) can lead to specic injuries and pains [START_REF] Johnson | Sport for athletes with physical disabilities: injuries and medical issues[END_REF], especially in the shoulder, and at the elbow, wrist and hand. For instance in [START_REF] Pentland | The weightbearing upper extremity in women with long term paraplegia[END_REF], the authors claimed that 73% of paraplegic individuals suered from shoulder pain. In addition, prolonged sitting of users causes dermatological problems such as bedsores or pressure ulcers, due to immobility, loss of sensitivity and incontinence. These symptoms are recognized as a major cause of discontinuation of wheelchair use [Van der Woude et al., 2006] [Ville andWinance, 2006], thus the sedentarization of users. [START_REF] Lundqvist | Spinal cord injuries. clinical, functional, and emotional status[END_REF] showed that upper limb pain was the main factor correlated with poor quality of life in MWC users. The challenge for the therapist is then to encourage a daily practice of physical activity adapted to wheelchair users, for limiting orthopedic problems, and thus to promote the use of the MWC over time.

Given the problems faced by manual wheelchair users at the level of their autonomy and health, van der [START_REF] Van Der | Wheelchair propulsion: a straining form of ambulation[END_REF] [ [START_REF] Woude | Wheelchair ergonomics and physiological testing of prototypes[END_REF] summarized the issues of manual wheelchair locomotion research into three main areas:

• Improving the interface between the subject and his manual wheelchair, that is, the ergonomy and the adequacy of the system {subject + MWC} with the external physical environment (ramps, lifts, corridor widths, etc.).

• The improvement of the MWC regarding the design and the mechanical principles of propulsion;

• Improving the subject's physical abilities, that is, improving propulsion techniques, as well as rehabilitation techniques and training programs.

After the construction of a measuring tool, a wheelchair eld ergometer ??, biomechanical works has been conducted in LIMOS to identify and quantify traumatic factors such as [De Saint Remy, 2005] [Sauret, 2010].

A.3 Tools to evaluate manual wheelchair locomotion This section summarises dierent tools designed over the last 60 years to measure the eorts made by subjects moving in a MWC. We put a particular emphasis on the wheelchair ergometer designed and manufactured at LIMOS, which is at the origin of the time series that are the subject of our analysis throughout this thesis.

A.3.1 Crank Ergometers

Crank ergometers allow a subject to manually operate a crankset connected to the ywheel of an ergo-cycle. The speed is determined by measuring the rotation speed of the ywheel, whose diameter is known, or by imposing a cadence, in which case the rotation speed is considered constant. Crank ergometers established that the mechanical work of the upper limbs is less ecient than that of the lower limbs and also that the physical capacities evaluated by the maximum oxygen consumption of MWC users depended on their level of spinal injury (cervical, thoracic or lumbar injury) 1 . One of the main limitations of crank ergometers is that the motion measured from a crank ergometer is not representative of the MWC propulsion motion, most of which is propelled by handrims [0Åstrand and [START_REF] Åstrand | [END_REF]] [Bergh et al., 1976] [Stenberg et al., 1967].

A.3.2 Roller Ergometers

To reproduce more precisely the specicities of MWC locomotion, Brouha and Krobathc [START_REF] Brouha | Continuous recording of cardiac and respiratory functions in normal and handicapped people[END_REF], as early as 1967, used a roller ergometer to measure cardiac and respiratory responses during continuous MWC exercice. This tool consisted of a platform on which were xed two rollers, each rotating around an axis and on which rested the rear wheels of a real MWC. The MWC frame was attached to the ergometer, and the subjects simulated locomotion by applying forces to the handrims, causing the rear wheels of the MWC and the rollers to rotate.

In 1971, [START_REF] Stoboy | Workload and energy expenditure during wheelchair propelling[END_REF], using an ergometer inspired by that of Brouha and Krobath, quantied the mechanical power (in watts) produced by the user from the relationship between oxygen consumption and mechanical power calculated during an incremental exercise on a crank ergometer.

The problem with roller ergometers of [Brouha andKrobath, 1967] [Stoboy et al., 1971] was that they did not take into account the inuence of the inertia of translation encountered by the Subject when he moves. To take this phenomenon into account, the rollers have been connected to a small ywheel. However, both rear wheels were on the same rollers, which did not allow to measure the dierences in propulsion between the right and left wheels to be explored [Brouha andKrobath, 1967] [Stoboy et al., 1971].

Then [Langbein and Fehr, 1993] [Langbein et al., 1993] [Langbein et al., 1994] designed a new roller ergometer called the Wheelchair Aerobic Fitness Trainer (WAFT), which had an access ramp to facilitate subject and MWC installation (Figure A.1). When the latter was attached to the ergometer, its rear wheels rested on three rollers each, which made it possible to dierentiate the forces applied to the right and left wheels 2 .

Other roller ergometers have also been developed over the last four decades and particularly in the last fteen years: Eagle Wheelchair Roller [START_REF] Kerk | Eect of an abdominal binder during wheelchair exercise[END_REF], Bromking Turbo Trainer [START_REF] Goosey-Tolfrey | A kinetic analysis of trained wheelchair racers during two speeds of propulsion[END_REF]] [Goosey-Tolfrey et al., 2001] [Price and Campbell, 1999] or very recently the "Computer Monitored Wheelchair Dynamometer" [START_REF] Cooper | Wheelchair racing eciency[END_REF]] [DiGiovine et al., 2001]. Other braking systems have been used, such as mechanical braking using a friction belt on a ywheel [START_REF] Goosey | The relationship between three-dimensional wheelchair propulsion techniques and pushing economy[END_REF]] [Kulig et al., 2001] [Rodgers et al., 1994](Figure A.2), an electric motor creating a frictional moment around the roller rotation axes [START_REF] Coutts | Aerobic and anaerobic power of canadian wheelchair track athletes[END_REF]] [Kerk et al., 1995] [Patterson and Draper, 1997] Wheelchair Aerobic Fitness Trainer (WAFT) photograph [Langbein and Fehr, 1993]. [START_REF] Vanlandewijck | Field test evaluation of aerobic, anaerobic, and wheelchair basketball skill performances[END_REF] or an isokinetic apparatus [START_REF] Ruggles | Biomechanics of wheelchair propulsion by able-bodied subjects[END_REF]. To determine the speed, angular position sensors [START_REF] Brouha | Continuous recording of cardiac and respiratory functions in normal and handicapped people[END_REF] [ [START_REF] Coutts | Aerobic and anaerobic power of canadian wheelchair track athletes[END_REF]] [Coutts, 1990] [Patterson and Draper, 1997] [Rodgers et al., 1994], optical encoders [Devillard, 1999] [Devillard et al., 2001] [Langbein et al., 1993] [Langbein et al., 1994] [Newsam et al., 1996] [Theisen et al., 1996], tachometers [Cooper, 1990] [Kerk et al., 1995] [Masse et al., 1992] [Vanlandewijck et al., 1999] or speedometers [START_REF] Goosey | The relationship between three-dimensional wheelchair propulsion techniques and pushing economy[END_REF]] [Rodgers et al., 1994] were used. [START_REF] Rodgers | Biomechanics of wheelchair propulsion during fatigue[END_REF].

The main advantage of roller ergometers is that they allow subjects to be studied with their own MWC. Moreover, they occupy a little space in the laboratory and allow the MWC to be completely immobilized, thus ensuring the stability of the subject on the MWC and facilitating the measurement of various physiological parameters. However, the various methods for estimating external mechanical power used up to now still need to be rened to better evaluate this parameter. Furthermore, the comparison between the results of studies carried out with dierent roller ergometers and dierent mechanical models must be done with caution since the parameters neglected or taken into account are not all the same. A.3.3 Treadmill Like roller ergometers, the main advantage of treadmills is that they allow subjects to be studied with their own MWC. Since the four wheels of the MWC roll on the belt, the rolling friction forces are most certainly equivalent to those existing on the ground. Unlike roller ergometers, treadmills allow to dene a rolling speed of the belt and also a slope, that is, an inclination of the treadmill with respect to the horizontal. The main disadvantage of a treadmill comes from the steering problem related to the control of the trajectory: indeed, a subject could drift and be ejected from the treadmill; to remedy this, railings have been installed on both sides using a surface strip that limits lateral movements [START_REF] Claremont | A model treadmill adaptation for wheelchair ergometry. Canadian journal of applied sport sciences[END_REF]. However, it has still not been demonstrated that the propulsion technique used was identical on a treadmill and on the ground.

A.3.4 Wheelchair simulators

To overcome the problems related to rolling resistance, some researchers chose to x the rear wheels of the MWC without contact with the ground, on a rigid and xed chassis on which the Subject could sit. The advantage of MWC simulators is that they can test dierent settings such as seat position or rear wheel camber angle, for example. The mechanical propulsion model is also simplied compared to roller ergometers and conveyor belts, which allows a better quantication of work and external mechanical power. However, the inuence of the Subject's movements on the seat is not taken into account. This aspect is the major disadvantage of the simulators because neither the forces of resistance to the advance nor the kinematics of the MWC is modied according to the movements of the Subject on the seat. [START_REF] Brattgård | Energy expenditure and heart rate in driving a wheel-chair ergometer[END_REF]) To analyse the eciency of wheelchair propulsion, a Wireless Wheelchair Ergometer (WWE or FRET-1) equipped with several sensors has been manufactured [START_REF] Dabonneville | A self-contained wireless wheelchair ergometer designed for biomechanical measures in real life conditions[END_REF]. The sensors installed on the wheelchair measure the physical stresses applied to the MWC during actual use and record them.

The sensors are located on the right and left wheels of the MWC, on the footrest, on the seat and the backrest. These sensors measure the torques applied to each of the systems mentioned above. Other sensors installed on the FRET-2 are used to measure the kinematic parameters (speed, acceleration) of the movement of the MWC (Figure A.5).

The measurements recorded by the sensors, which are the prupose of our analysis, consist of 41 attributes; of which 30 represent the dynamic parameters (Fx, Fy, Fz, Mx, My, Mz = 6 components x 5 dynamometers). The 11 other attributes represent the kinematic parameters of the MWC and its position relative to the Earth's magnetic North. The force and torque dynamometer

A "torsor" is a mathematical object that characterizes the eorts applied on or by a solid. It is composed of two vectors, which have three components each: the three components (Fx, Fy, Fz) of the resulting force (F) and the three components (Mx, My, Mz) of the resulting moment (M) that are applied to this solid along three orthogonal axes (x, y, z). To measure the six components of the "torsor" applied by wheelchair users on both handrims during their actual displacements on the ground, an original force and torque dynamometer has been designed, built and installed on both rear wheels of the FRET-1 and then the ). This dynamometer is composed of three bidirectional force sensors that measure all the forces applied to the handrim which are then used to compute the three components of the resulting force and the three components of the resulting moment.

The wheel dynamometer used in that study is based on a mechanical principle already applied for the design of a six-component dynamometer used for the measurement of the forces and torques applied by the pole-and-vaulter system in the vaulting box during the pole vault.

According to that principle, the handrim is assumed to be rigid and rmly xed on three two-component force transducers designed to measure the handrim displacement with respect to the wheel. In that approach, the handrim is considered as hanging on the wheel through the force transducers. Each transducer measures one component of the resulting propulsive force in the tangential direction of the wheel and one in the direction perpendicular to the plane of the wheel. The vectorial sum of all these components is equal to the resulting propulsive force in the moving Legend

• • • • • • • • • R * (O,
x, y, z): moving reference frame linked to the wheel;

• O : centre of the wheelchair rear wheel;

• R : radius of the wheelchair rear wheel;

• A, B, C : locations of the three two-component force tranducers;

• u1, ..., u6 : unit vectors of the six force transducers;

• F ext : external force applied by the user on the handrim;

• P : point of application of Fext on the handrim;

• Angles: a = (u x , F ext ); b = (u z , F ext ); q = (u x , OP ) reference frame R * linked to the wheel. This derives from the fact that the handrim is static in R * with respect to the wheel.

When an external force Fext is applied on the handrim, it is instantaneously transmitted to the six force transducers so that each of them simultaneously measures a local force F i (i = 1 to 6). As the transducers behave as springs, which stiness k i are determined through the calibration procedure, the measurement of the displacements m i by the strain gauges allows to compute the values of F i using Hooke's law (equation A.1)

F i = k i m i . (A.1)
Finally, the force and torque components created by F ext are calculated by equa-tion A.2

- → F ext = 6 i=1 F i ⇐⇒ [F ext ] = [k i ] [m i ] ⇐⇒ [F ext ] =         F x F y F z M x M y M z         (A.2)
Where [F ext ] is a column matrix containing the six components of the torsor applied on the dynamometer; [k i ] is the sensitivity matrix of the dynamometer; [m i ] is the column matrix containing the signals measured by the six forces transducers of the dynamometer. Several mechanical and kinetic parameters can be computed from the forces and torques measured by the six-component dynamometers mounted on the MWC eld ergometer [Sauret, 2010]. All of them have a specic and useful meaning as their relationships are dened by a complete mechanical (i.e. dynamic and kinematic) model of wheelchair propulsion. However, because of their number and their complexity, these parameters can only be analysed and interpreted by specialists in biomechanics. To overcome this drawback, in the present study, relevant mechanical information has been extracted from only some dynamic data (z-moments M z ) recorded by both rear wheel dynamometers of the instrumented MWC (FRET-2) [This information have then been used to group subjects in homogeneous clusters, which have been compared to clinical injury levels.

A. 4 Knowledge discovery on wheelchair time series

After the construction of these measuring instruments (FRET-1 and FRET-2), they have been used to measure the eorts made by MWC uses in actual conditions of wheelchair locomotion. Thus, several experiments have been conducted with several subjects, where the eorts produced during actual wheelchair locomotion were measured with the FRET-2. The abundance of the recorded measurements highlighted the problem of the exploitation of these measures for knowledge extraction. Two main and complementary approaches can be used to analyze measurements from MWC locomotion. The rst is to use mechanical models to calculate the physical parameters of motion and the second is to use data mining models to exploit measurements. In this section, we present the contributions of these two approaches, which will allow us to position our work.

Manual wheelchair locomotion causes signicant mechanical stresses in the upper limbs [START_REF] Desroches | Expression of joint moment in the joint coordinate system[END_REF]. To remedy this problem, biomechanical studies have been conducted to identify and quantify traumatic factors such as:

• The doctoral thesis of Nicolas DE SAINT REMY (2005) [De Saint Remy, 2005] who proposed a mechanical model relating the forces applied to a MWC and its displacement ( Figure A.7 ). This work particularly highlighted the fact that wheelchair acceleration is a function of subject's movements. • The doctoral thesis of Christophe SAURET (2010) [Sauret, 2010] who proposed a method of calculating the mechanical power developed by manual wheelchair users to move. This model analyzes the kinetics of the {subject + MWC} system. For that purpose, the author developped a detailed kinematic model of the {subject + MWC} system (Figure A.8) allowing to record their movements with a 3D motion analysis system during actual locomotion on the ground.

More and more works in the literature suggest using the tools developed in data mining for a better understanding of human locomotion. For example, in [van der Slikke et al., 2017], the authors ask whether advances in data science and technology could provide a dierent and perhaps more objective view of the analysis of wheelchair users' motor abilities. On one hand, technical advances have made it possible to measure the eorts made by wheelchair users during their movement using sensors. On the other hand, datamining models have been proposed and allow to perform several task on the data (clustering, classication, . . . ).

In [START_REF] Faria | Patient classication and automatic conguration of an intelligent wheelchair[END_REF] the authors explained how they used robotics and data mining knowledge to build an Intelligent Manual Wheelchair, which can be controlled from multiple interfaces: joysticks, facial expressions, voice commands, head Figure A.8: Locations of passive markers for the kinematic analysis of manual wheelchair locomotion [Sauret, 2010] movements. Since Intelligent Wheelchair users have various characteristics, a series of tests have been carried out to classify them and to dene proles that allow the MWC to be appropriately adjusted for each user.

In [START_REF] Athanasiou | A bayesian network model for the diagnosis of the caring procedure for wheelchair users with spinal injury[END_REF] the authors presented a model based on Bayesian networks to improve the medical treatment of patients in wheelchairs with a spinal cord injury. Indeed, the treatment of these patients is based on the level of spinal cord injury and symptoms. A lesion in the spine has three consequences: an inconsistency of the bowel, an inconsistency of the bladder, a loss of the skin sensitivity. The higher the lesion, the more widespread its eects on patients are. Thus a patient with a low lesion will aect the patient's legs and a patient with a high lesion will see his four limbs aected. Because of this loss of sensitivity, symptoms observed in the patient are often incomplete, which introduces uncertainty into the diagnosis that is captured by Bayesian networks and conditional probabilities.

A.5 Conclusion

Throughout this chapter, we showed that there is a large number of MWC users in the world and that it is crucial to analyze this particular means of locomotion to improve the living conditions of people moving in a MWC. We have presented the main tools designed and manufactured for wheelchair locomotion analysis and some previous works that used data mining mechanics models to improve the study of wheelchair locomotion or to help physicians to diagnose its the adverse eects.

In the scientic literature, mechanical or data mining models are used for manual wheelchair locomotion analysis. In this thesis, however, we want to design data mining models that are able to take into account both the specicities of MWC locomotion data and their use to analyze wheelchair locomotion from a new point of view. Introduction Time series databases are often huge. This is particularly the case of the Large Synoptic Survey Telescope (LSST) database which records data from of telescopes [lss, 2016]. It has billions of time series (10 Petabytes). Another example is the SACR-FRM project that uses sensors to measure the eorts of a manual wheelchair user at a sample frequency of 100 Hz [START_REF] Sac | Projet SACR-FRM (Approches de la Sociologie, de la Biomécanique et de l'Intelligence Articielle[END_REF]. For instance : ten minutes recording produce time series of 60 000 measurements. Faced to this, several scientic works were carried out with the aim of reducing the storage space of time series and accelerating their treatment. A widely used approach is to change the representation of time series to reduce their length. This technique was introduced by Agrawal et al. [START_REF] Agrawal | Ecient Similarity Search In Sequence Databases[END_REF]; he uses the discrete Fourier transform to obtain a compact representation of the time series. Other methods have also been used: the decomposition in eigenvalue [START_REF] Wu | Ecient retrieval for browsing large image databases[END_REF], the discrete wavelet transform [Chan and Fu, 1999b] and the Piecewise Aggregate Approximate (PAA) [START_REF] Keogh | Locally adaptive dimensionality reduction for indexing large time series databases[END_REF]. This last method has shown its eectiveness compared to the previous three ones because it is easier to understand, to implement, but also faster to execute and it allows to build indexes in linear time. PAA suggests to split the time series into segments of the same length, then to replace each segment by the average of its points. This method generates a compact representation, of time series composed with as few segments as possible that reduces space storage and processing time of time series. However, a too compact representation distorts the time series and causes a loss of information. How then to choose the right number of segments to consider? Our work is based on a simple observation: the use of the arithmetic average is relevant when the variance of the population is small as illustrated in gure B.1.

We dene here a minimal bound for the number of segments to be considered, and we propose an algorithm which allows choosing the number of segments which minimizes their mean squared error, with the aim to reduce the length of the time series without altering the information they contain.

The rest of this appendix is organized as follows: the section B.2 presents a formal denition of our problem and an algorithm to solve it; the section B.3 presents and comments the results of the experiments and the section B.4 concludes the appendix and presents some perspectives for this work. is a sequence consisting of l consecutive variables X beginning at the position i and ending at the position i + l -1. We have:

X i = x i , x i+1 , ..., x i+l-1
Denition 21. The arithmetic mean of the data points of a segment X i of size l is

B.2.2 Information theory and minimum number of segments

To mitigate the eects of noise during time series processing, Keogh and Kasetty [START_REF] Keogh | On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration[END_REF] recommend that they are normalized. Normalizing the time series makes them compatible with a normal distribution [START_REF] Lin | Experiencing SAX: a novel symbolic representation of time series[END_REF].

According to this method, 95 % of the points in the time series are between plus and minus two times the standard deviation (σ) and twice the standard deviation of the points, and thus 5 % of the points of the series are outside this range. These points correspond to the ends of the series as shown in the gure B.2.

B.2.3 Notations and denitions

Denition 22. The arithmetic mean of the data points of a segment X i of size l is denoted Xi and is dened by :

Xi = 1 l l-1 j=0 x i+j . (B.2)
To solve this problem, we propose an algorithm that proceeds as follows:

1. For each value of W, with α(n) ≤ W ≤ β(n) (a) Calculate the squared error of each segment X i = x i , x i+1 , ..., x i+l-1 ;

(b) Calculate the mean of the quadratic errors;

2. The value of W returned is the one that produces a minimum average squared error.

These conditions are implemented in algorithm 4: The number of segments varies from n 20 , n 19 . . . n 2 . There are 19 possible divisions in segments. The time complexity of calculating the value of W which minimizes the error mean squared is:

19 × O(n) = O(n).
To exploit the compact representations of the time series, we must be able to compare them. The next subsection presents how to compare compact time series that we get.

Algorithm 5: sum_SSE Input: v : a time series.

nbPoints : the length of a segment

Output: The sum of squares error associated with a segment length 1 function sum_SSE(v, nbP oints)

2 n ← length(v) 3 ind_debut ← 1 4 aux_se ← c() 5 tab_indices_debut ← c() 6 i ← 0 7 while (ind_debut + nbP oints) ≤ n do 8 tab_indices_debut[i] ← ind_debut 9 ind_debut ← ind_debut + nbP oints 10 i ← i + 1 11 m ← length(tab_indices_debut) 12 forall i ∈ {1, ..., m} do 13 aux_se[i] ← SSE_segment(v, nbP oints, tab_indices_debut[i]) 14 return sum(aux_se)

B.2.5 Dynamic Time Warping Algorithm and comparison of compact representations

The Dynamic Time Warping algorithm (DTW) [START_REF] Keogh | Exact indexing of dynamic time warping[END_REF] allows to carry out a non-linear correspondence between two time series by minimizing the distance between them. It proceeds as follows: Let X and Y be two time series;

X = x 1 , x 2 , • • • , x n ; (B.6) Y = y 1 , y 2 , • • • , y m . (B.7)
To align them, the algorithm constructs a matrix n × m where the element (i, j) of the matrix corresponds to the square distance (x i -y j ) 2 , which is the alignment between x i and y j . To nd the best alignment between the two time series, we build the path in the matrix that minimizes the sum of the square distances. This path is calculated by dynamic programming from the following recurrence:

γ(i, j) = d(x i , y j ) + min{γ(i -1, j -1), γ(i -1, j), γ(i, j -1)}, (B.8)
where d(x i , y j ) is the square of the distance contained in the cell (i, j) and γ(i, j) is the cumulative distance at the position (i, j), which is calculated by the sum of the square of the distance to the position (i, j) and the minimum cumulative distance of its three adjacent cells.

Piecewise Aggregate Approximation(PAA) provides Euclidean-based distance measurement to compare compact representations. However, we chose to use the Dynamic Time Warping algorithm for the following reasons: 1. PAA of the time series leads to temporal deformation. Indeed, with two time series of length n, we can apply our algorithm to the rst time series, then reduce it to N 1 segments and reduce the second to N 2 segments with N 1 < N 2 .

2. The DTW algorithm is known to have the best performance for sequence alignment in several : in robotics, biometrics, music, climatology, aviation, gesture recognition, cryptanalysis, astronomy, exploration space [START_REF] Rakthanmanon | Searching and mining trillions of time series subsequences under dynamic time warping[END_REF].

B.3 Results and Discussion

First, we present the datasets used during the experiment. Then we evaluate the performances of the proposed methods in terms of length reduction of time series and classication errors.

B.3.1 Datasets

We performed tests on 85 datasets that come from the UCR database [START_REF] Chen | The ucr time series classication archive[END_REF] . Detailed information on the datasets is presented in the 4), 1-NN, associated with the DTW algorithm using a constraint (a deformation window) (col.5), 1-NN associated with the algorithm of unconstrained dynamic time warping (DTW) applied to the raw data ( 6) and the 1-NN algorithm associated with DTW applied to the data pre-processed by our algorithm (7). The (col.4) algorithm gives the best results that are to say ((col.4) ≤ (col.5) and (col.4) ≤ (col.6) and (col.4) ≤ (col.7)) on 20 datasets, the algorithm (col.5) is the best on 47 datasets, the (col.6) algorithm is the best on 21 datasets, the (col.7) algorithm is the best on 21 datasets. Although none of these algorithms have the best performance on all datasets, the algorithm (col.5) averaged the smallest misclassication 0.237 and the most expensive (col.4) algorithm the largest average error 0,288. The (col.6) and (col.7) algorithms have relatively close average error rates equal to 0,256 and 0,258 respectively.

To evaluate the eects of the change of representation of the time series on their classication, we compared the length of the time series and the errors of classication presented by the columns (6) and (7) of Table B.2. Indeed, these two columns use the same 1-NN classication algorithm and the same distance function DTW. The only dierence between these columns is the nature of the data: the (6) column uses the raw data and the column (7) the compacted data with the method described above. The result of the comparison between these two columns can be resumed as follows:

• Regarding the length of the time series; the (6) algorithm uses all the points of the time series. On the other hand, the (7) algorithm uses compact representations whose length varies between 15 % and 34 % of the initial length of the time series. On average, the compact representations have a length equal to 20 % of the initial time series

• For classication errors, the error (7) > (6) on 40 datasets, the error of (7) = (6) on 3 datasets and the error of (7) < (6) on 42 datasets.

These results are encouraging because, despite the reduction in the length of the time series errors, the classication error with the compact representation is less (1) (2) (3) (4) (5) (6) (7) (3) is the ratio of the length of the reduced time series over the length of the initial time series. Column ( 4) designates the 1-Nearest Neighbor algorithm, associated to the Euclidean distance. Column (5) designates the algorithm of 1-Nearer Neighbor, associated with the algorithm of dynamic dynamic temporal deformation using a constraint called deformation window that allows to stop the comparison of time series when one perceives that they are very dierent. Column (6) represents 1-Nearest Neighbor algorithm associated to the unconstrained dynamic time warping applied to the raw data. Column (7) represents the algorithm. 1-Nearest Neighbor associated with the dynamic time warping algorithm without constraints, applied on the compact representations produced by our algorithm. We rstly compare, the classication error of the algorithms of columns( 6) and ( 7) the smallest error is in bold. Then we compare the classication errors of algorithms of columns( 4), ( 5), ( 6) and ( 7) the smallest error is put italics.

End B.4 Conclusion

The purpose of this appendix was to propose an algorithm for choosing the number of segments to consider for the compact representation of a time series. In that aim, we have dened a minimum bound for the number of segments to be considered which is equal to 5 % of the length of the time series. We have proposed an algorithm that chooses the number W of segments minimizing the mean squared error. Results of experiments conducted on 42 datasets have shown that the number of segments chosen allows two improvements:

• IT signicantly reduces the length of the time series; time series of reduced size have a length which varies between 15% and 34% of the initial time series length

• It improves supervised classication results on a set of 85 datasets used in the literature.

As a perspective for this work, we plan to vary the number of segments W from 2 to n 2 to see if our value of W is optimum for a task classication. We also plan to compare the results of this compact representation to those of other representations used in the literature. We also plan to parallelize our algorithm to calculate the right number of segments in linear time. This work allows reducing the storage space and the processing time of the time series. It also allows choosing the number of segments to consider when designing symbolic representation of time series. Indeed, several symbolic representations of series of the literature (SAX [START_REF] Lin | A symbolic representation of time series, with implications for streaming algorithms[END_REF], ESAX [Lkhagva et al., 2006], 1d-SAX [START_REF] Malinowski | 1d-SAX: A Novel Symbolic Representation for Time Series[END_REF], SAX-TD [START_REF] Sun | An improvement of symbolic aggregate approximation distance measure for time series[END_REF], SAX-P [Siyou [START_REF] Fotso | [END_REF]) use the division into segments recommended by PAA. we used statistical tests. The principle of statistical tests is as follows: we assume that the residues follow a dened probability law, and we calculate a p-value. If it is less than 0.05, the above hypothesis is rejected. Another method is to hypothesize that the data follow a particular law and to estimate the parameters that best t the law. If the theoretical probability density function estimated is closed to the empirical one, we assume that the probability law follows by residuals is found.

C.2 Theorical probability distribution

Residuals are real values between minus innity and plus innity. The probability laws that residuals can follow are therefore:

• A normal law;

• A law of Cauchy;

• A Student's law t;

• A general exponential law;

• A double exponential law;

• Generalized error distribution (GED);

• A Pearson law type 4;

• A generalization of the Student's law. Les mesures ainsi eectuées sont des séries temporelles ayant les caractéristiques spéciques suivantes : elles sont longues, incertaines et cycliques. En nous appuyant sur ces mesures ainsi que sur leurs propriétés, l'objectif de cette thèse est d'eectuer une analyse objective de la locomotion en fauteuil roulant manuel. À cet eet, nous proposons trois modèles. Le premier modèle est une heuristique permettant de trouver le nombre judicieux de segment à considérer pour la compression des séries temporelles avec l'algorithme d'approximation par morceau, tout en concevant l'information contenue dans les séries temporelles. Si le principe de fonction de cette heuristique est similaire à celui de la recherche gloutonne randomisée, elle a la particularité de proposer une stratégie spécique de recherche globale. Le deuxième modèle est une mesure de similarité qui permet de capturer la structure fondamentale des séries temporelles et qui est robuste à la présence d'incertitude. Cette mesure de similarité est basée sur la comparaison à l'aide de la norme de Frobenius des vecteurs propres des matrices d'autocorrélation des séries temporelles. Le troisième modèle est une représentation symbolique de séries temporelle cycliques basée sur les propriétés de cycles qui utilise un algorithme de segmentation des séries temporelles cycliques en cycle et un algorithme de classication non supervisée pour comparer les cycles en fonction de leurs propriétés. Cette représentation symbolique permet une meilleure visualisation et une meilleure analyse basée sur les propriétés des cycles des séries temporelles cycliques. Nos modèles permettent de mettre en évidence le caractère asymétrique de la locomotion en fauteuil roulant manuel et d'établir que l'asymétrie de la locomotion diminue avec les années de pratique. Ils permettent également d'évaluer de manière objective et intelligible les capacités motrices des utilisateurs de fauteuil roulant manuel. The assessment of the motor skills of manual wheelchair users is often subjective because it is based on expert opinion. Therefore, a manual eld ergometer wheelchair was conceived and constructed. It records the eorts made by manual wheelchair users during their locomotion. The measurements made are time series with the following specic characteristics: they are long, uncertain and cyclical. Based on these measurements and their properties, the objective of this thesis is to perform an objective analysis of manual wheelchair locomotion. To this, we proposed three models. The rst model is a heuristic to nd the appropriate number of segments to consider for time series compression with the piece aggregate approximation algorithm while keeping the information they contained. If the principle of this heuristic is similar to that of greedy randomized adaptive search, it has the particularity of proposing a specic global search strategy. The second model is a similarity measure that captures the fundamental structure of time series and is robust to the presence of uncertainty. This similarity measure is based on the comparison using the Frobenius norm of eigenvectors of time series autocorrelation matrices. The third model is a symbolic representation of cyclic time series based on cycle properties that utilises a segmentation algorithm of cyclic time series in cycles and an unsupervised classication algorithm to compare cycles according to their properties. This symbolic representation allows better visualization and analysis based on the cycle properties of cyclic time series. Our models highlight the asymmetrical nature of manual wheelchair locomotion and establish that the asymmetry of locomotion decreases with years of practice. They also provide an objective and intelligible assessment of the motor abilities of manual wheelchair users.

Figure 2 . 1 :

 21 Figure 2.1: Relation between Accuracy and the number of segment on FISH dataset.The accuracy is computed from the algorithm one nearest neighbor (1NN) associated with PDTW. When the number of segments considered is very small (bellow 20), there is a loss of information and the accuracy is reduced. However, considering all the points in the time series, do not produce a maximum accuracy due to the presence of noise or singularities[START_REF] Keogh | Derivative dynamic time warping[END_REF] in the data.

Figure 2 . 3 :

 23 Figure 2.3: Visual comparison of two time series from the two classes of the coee dataset. Left: the original time series (286 data points), right: representation using PAA with 88 segments

Figure 2 . 4 :

 24 Figure 2.4: Comparison of the number of tested values of the parameter number of segments with the FDTW and IDDTW. Datasets are sorted according to the length of the time series (x-axis).

Figure 2 .

 2 Figure 2.5: Comparison of the execution time of the Brute-force search algorithm, FDTW and IDDTW.

Figure 2 .Figure 2 . 7 :

 227 Figure 2.6: Critical dierence diagram for FDTW and 36 other classication algorithms on 6 simulated datasets. FDTW is ranked 3rd / 37 algorithms

Figure 3 .

 3 Figure 3.1: Example of classication of time series of two birds' calls (green:Olive-sided Flycatcher; blue: White-crowned Sparrow) using on the one hand the Euclidean distance(left), and on the other hand the u-shapelet (right)[START_REF] Ulanova | Scalable clustering of time series with u-shapelets[END_REF]

  observed values and N i denotes the number of observed values at timestamp i (Fig.3.2).

Figure 3 . 2 :

 32 Figure 3.2: Multiset-based model of uncertain time series.

Figure 3 . 3 :

 33 Figure 3.3: PDF-based model of uncertain time series

  Figure 3.4: Bhattacharyya

Figure 3 . 5 :

 35 Figure 3.5: Geometric representation of LoCo similarity.

  FOTS dissimilarity function is robust to the presence of uncertainty due to the spectral decomposition of the autocorrelation matrices of the time series. The robustness of FOTS to uncertainty is conrmed by the theorem of HomanWielandt:

Figure 3 . 6 :

 36 Figure 3.6: The execution time of ED and FOTS score is a function of the length of time series. The computation time of ED is smaller than that of FOTS.

Figure 3 . 7 :

 37 Figure 3.7: Sensitivity of Euclidean Distance and FOTS to the presence of uncertainty.

Figure 4 . 1 :

 41 Figure 4.1: Cyclic time series form manual wheelchair locomotion

Figure 4 . 2 :

 42 Figure 4.2: Properties of a cycle

Figure 4 . 3 :Figure 4 . 4 :

 4344 Figure 4.3: Piecewise aggregate approximation of a cyclic time series

Figure 4 .

 4 Figure 4.5: Extended Symbolic Aggregate approXimation of a cyclic time series

Figure 4

 4 Figure 4.7: Properties of a cycle

Figure 4 Figure 4 .

 44 Figure 4.9: Segmentation

Figure 4 .

 4 Figure 4.11: Classication of cycles based on properties

Figure 4 .

 4 Figure 4.12: Symbolic representation of cyclic time series

Figure 4 .

 4 Figure 4.13: Example of a z-moment (Mz) time series measured on the [left/right] rear wheel of the FRET-2.

Figure 4 .

 4 Figure 4.14: Time series recorded by torsor sensor are noisy

  Straight displacement in manual wheelchair End

Figure 4 .

 4 Figure 4.15: Plot of Mz residues, which represent the dierences between Mz values measured by the sensor and real values applied during the calibration process.

3 :

 3 Anthropometric and physiological characteristics of the subjects who participated in this study.

Figure 4 .

 4 Figure 4.16: Classication tree of wheelchair users based on their propulsion abilities.

  to a supervised classication of cyclic time-series in bio-mechanics.

Figure

  Figure A.1:

Figure A. 2 :

 2 Figure A.2: Picture of a wheelchair on a roller ergometer with mechanical braking by friction belt on a ywheel.[START_REF] Rodgers | Biomechanics of wheelchair propulsion during fatigue[END_REF].

Figure

  Figure A.3: Exercise testing on a motor driven treadmill [Van derWoude et al., 2006]

Figure A. 4 :

 4 Figure A.4: Photograph of an experiment on a simulator connected to a ywheel ([[START_REF] Brattgård | Energy expenditure and heart rate in driving a wheel-chair ergometer[END_REF]

Figure A. 5 :

 5 Figure A.5: Captioned picture of the adjustable wireless wheelchair ergometer (FRET-2).

Figure

  Figure A.6: Schematic principle of the six-component force and torque sensor (patent WO 1995001556 A1) mounted of both rear wheels of the MWC eld ergometer used in this study (FRET-2).

Figure A. 7 :

 7 Figure A.7: Balance of forces applied to a manual wheelchair during propulsion.For the clarity of the gure, the analysis of the movement of the {subject + MWC} system is reduced to that of the system's centre of gravity, G [De SaintRemy, 2005]

  Figure B.1: These gures show the average of two segments. In the rst case (a) the data points of the segment are far from the average, in the second case (b) they are close to the average. Replacing data points of a segment by their average introduces an error that the can be measured from the gap between the points and the average.

  A time series or time series X = x 0 , x 1 , • • • , x m is a sequence of numerical values representing the evolution of a specic quantity over time. x m is the most recent value. Denition 20. A segment X i of length l of the time series X of size m (l < m)

Figure B. 2 :

 2 Figure B.2:This gure shows the rst 100 points of the rst time series of the fordA dataset available in the UCR[START_REF] Chen | The ucr time series classication archive[END_REF] database. Time series are normalized. The two horizontal lines delimit the interval corresponding to twice the standard deviation and minus two times the standard deviation of the points of the time series. We can observe that the points outside this range are at the ends of the time series.

3 n

 3 Algorithm 4: optimalNumberOfSegment Input: length_min, length_max : repectively the minimal and the maximal length of a segment. v : a time series Output: The optimal number of segment to be use with Piecewise Aggregate approXimation 1 function optimalNumberOfSegment(length_min, length_max, v) 2 len_v ← length(v) ← length_max -length_min + 1 4 forall i ∈ {length_min, ..., length_max} do 5 x[j, 1] ← i 6 z[j, 1] ← (1/len_v) * sum_SSE(v, i) 7 computation of the error j ← j + 1 8 ind_min ← indice_minimun(z) 9 return f loor(len_v/x[ind_min, 1]) Complexity of the algorithm The calculation of the squared error of a segment is done in O( n W ). The time complexity of calculating the mean squared error for segment splitting is O(n).

  Figure B.3: Two-by-two comparison of the classication errors of the algorithm 1-Nearest Neighbor (1-NN) using Euclidean distance with 1-NN using two variations of the temporal warping algorithm on raw data and compact data

Figure C. 2 :

 2 Figure C.2: Estimated probability density of data

  Cauchy's Law Test : The Q-Qplot line does not match correctly with the data particularly the two extremities of the diagram (Fig. C.3); we can say that the data probably do not follow a Cauchy's law.

Figure C. 3 :

 3 Figure C.3: Estimated probability density of data for Cauchy's law

Figure C. 4 :

 4 Figure C.4: Estimated probability density of data for Student's law

  Extraction de connaissances de séries temporelles cycliques et incertaines : application à l'analyse de la locomotion en fauteuil roulant manuel Résumé L'évaluation des capacités motrices des utilisateurs de Fauteuil roulant manuel est souvent subjective, car elle se base sur l'avis d'un expert. C'est pourquoi, un fauteuil roulant manuel ergomètre de terrain a été fabriqué. Il permet d'enregistrer les eorts eectués par les utilisateurs de fauteuil roulant manuel pendant leur déplacement.

Table 1

 1

	.1: Temporal-Proximity-Based Clustering Approach	Author Distance Measure Algorithm Application	Based on the assumed independent	M. Kumar Gaussian models of Agglomerative Hierarchical Seasonality pattern in retails	data errors	T.-W. Liao version of KullbackLiebler K-Means Euclidean and symmetric and Fuzzy C-Means distance Battle simulations	T.-W. Liao Dynamic Time Warping K-Medoids Based Genetic Clustering Battle simulations	C.S. Möller-Levet Short time series (STS) distance Modied Fuzzy C-Means DNA microarray	Shumway KullbackLeibler discrimination information measure Agglomerative Hierarchical Earthquakes and mining explosions	Vit Niennattrakul Dynamic Time Warping K-Means, K-Medoids Multimedia time series	Pooya Sobhe Pearson Correlation Bidari K-Means, Fuzzy C-Means Pattern extraction in genes	Hardy Kremer Dynamic Time Warping Subsequence Detecting climate Density Based change Clustering	Jian Yin Grey Relation Hierarchical Clustering Change trend of trac ow data	S. Chandrakala Euclidean Kernal DBScan Multivariate time series clustering	Aurangzeb Khan Euclidean K-Mean+ MFP(Most Frequent Pattern) Stock and inventory data	Mengfan Zhang Theory) CVT(Computational Verb K-Means Stock market data	S.R.Nanda Euclidean K-Means Portfolio management	Jianfei Wu N/A K-Means Stock data
	22														Ph.D. Thesis

Table 2 .

 2

	N • Datasets	DTW IDDTW N	FDTW N
		(training set)
	1	50Words	0.349	0.340	256 0.318	80
	2	Adiac	0.462	0.426	128 0.426	140
	3	ArrowHead	0.250	0.167	16	0.111	14
	4	Beef	0.567	0.900	8	0.567	169
	5	Car	0.400	0.233	8	0.217	385
	6	CBF	0.000	0.000	128 0.000	22
	7	Coee	0.033	0.133	64	0.000	88
	8	Cricket_X	0.210	0.244	256 0.190	84
	9	Cricket_Y	0.279	0.285	256 0.272	214
	10 Cricket_Z	0.267	0.272	256 0.249	250
	11 DistalPhalanxOutlineAgeGroup 0.570	0.541	16	0.534	14
	12 DistalPhalanxTW	0.375	0.339	16	0.317	40
	13 Earthquakes	0.266	0.266	512 0.223	101
	14 ECG	0.240	0.170	8	0.170	11
	15 ECGFive Days	0.387	0.220	32	0.220	7
	16 Face (all)	0.875	0.873	128 0.870	50
	17 Face (four)	0.208	0.125	32	0.083	140
	18 Fish	0.343	0.314	16	0.303	27
	19 Gun-point	0.201	0.039	32	0.020	38
	20 Ham	0.650	0.512	32	0.512	32
	21 Haptics	0.587	0.536	64	0.516	239
	22 InlineSkate	0.519	0.519	64	0.499	48
	23 ItalyPower Demand	0.045	0.060	8	0.045	20
	24 Lightning-2	0.183	0.150	16	0.100	179
	25 Lightning-7	0.315	0.344	64	0.200	155
	26 Medical Images	0.286	0.307	64	0.278	94
	27 MiddlePhalanxTW	0.429	0.442	32	0.429	80
	28 MoteStrain	0.246	0.246	16	0.190	46
	29 OliveOil	0.367	0.367	32	0.333	423
	30 OSU leaf	0.310	0.335	32	0.270	33
	31 Plane	0.000	0.000	32	0.000	32
					continued on next page
	Ph.D. Thesis

1: Classication errors associated with the number of segments N chosen by the heuristics IDDTW and FDTW. When two numbers of segments N 1 and N 2 are associated with the same classication error, the smallest is considered. The classication error is calculated based on the 3 fold cross validation applied on the training set.

Table 2 .

 2

			r) force
	dean			search
	distance
	0.369 0.310	0.242 (6)	0.262	251(1)	0.268	256(1) 0.268	258(1)
	0.389 0.396	0.391 (3)	0.379	162(1)	0.432	128(1) 0.414	143(1)
	0.333 0.367	0.333 (0)	0.233	286(2)	0.3	8(59)	0.367	94(5)
	0.425 0.274	0.288 (5)	0.192	150(2)	0.301	64(5)	0.301	170(2)
	0.26	0.25	0.253 (5)	0.233	27(2)	0.283	2(40)	0.283	385(2)
	0.148 0.003	0.004 (11) 0	118(1)	0.003	128(1) 0.001	128(1)
	0.000 0.000	0.000 (0)	0	13(22)	0	64(4)	0.000	286(1)
	0.423 0.246	0.228 (10) 0.228	142(2)	0.256	256(1) 0.269	84(4)
	0.433 0.256	0.238 (17) 0.231	271(1)	0.241	256(1) 0.244	294(1)
	0.413 0.246	0.254 (5)	0.221	249(1)	0.223	256(1) 0.233	276(1)
	0.218 0.208	0.228 (1)	0.2	78(1)	0.225	16(5)	0.223	80(1)
	0.273 0.29	0.272 (0)	0.263	35(2)	0.288	16(5)	0.278	80(1)
	0.326 0.258	0.258 (22) 0.198	176(2)	0.258	512(1) 0.276	101(5)
	0.120 0.230	0.120 (0)	0.13	38(3)	0.19	8(12)	0.180	11(9)
	0.203 0.232	0.203 (0)	0.117	11(12)	0.289	32(4)	0.117	11(12)
	0.286 0.192	0.192 (3)	0.091	79(2)	0.194	128(1) 0.148	99(1)
	0.216 0.170	0.114 (2)	0.08	107(3)	0.352	32(11) 0.102	140(3)
	0.217 0.177	0.154(4)	0.154	149(3)	0.257	16(29) 0.177	27(17)
	0.087 0.093	0.087 (0)	0.02	38(4)	0.073	32(5)	0.020	38(4)
	0.4	0.533	0.400 (0)	0.343	21(20)	0.026	32(13) 0.432	32(13)
	0.630 0.623	0.588 (2)	0.549	328(3)	0.588	64(17) 0.594	948(1)
	0.658 0.616	0.613 (14) 0.578	1770(1) 0.627	64(29) 0.622	171(11)
	0.045 0.050	0.045 (0)	0.033	20(1)	0.043	8(3)	0.033	24(1)
	0.133 0.167	0.133 (0)	0.1	191(3)	0.167	32(18) 0.100	234(2)
	0.267 0.267	0.233 (1)	0.183	52(11)	0.367	8(72)	0.367	377(1)
	0.038 0	0.000 (6)	0	35(4)	0	128(1) 0	135(1)
	0.439 0.416	0.419 (2)	0.398	27(2)	0.414	32(2)	0.416	80(1)
	0.121 0.165	0.134 (1)	0.135	14(6)	0.197	16(5)	0.165	84(31)
	0.246 0.131	0.131 (6)	0.082	70(9)	0.246	16(40) 0.180	524(1)
	0.479 0.409	0.388 (7)	0.364	31(14)	0.372	32(13) 0.409	35(12)
	0.316 0.263	0.253 (20) 0.255	95(1)	0.271	64(2)	0.280	34(3)
	0.292 0.263	0.263 (6)	0.24	75(1)	0.288	4(20)	0.288	4(20)
	0.461 0.35	0.300 (3)	0.083	54(9)	0.239	64(7)	0.122	48(10)
	0.305 0.275	0.305 (0)	0.206	37(2)	0.208	16(4)	0.304	26(3)
	0.141 0.169	0.141 (0)	0.14	5(13)	0.197	16(4)	0.178	45(1)
							continued on next page
	Ph.D. Thesis

2: Comparison of generalization errors. In italics, the smallest generalization error. In bold, the smallest generalization error between IDDTW and FDTW.

  VS, Mephu-Nguifo E, Vaslin Ph. Parameter Free Piecewise Dynamic Time Warping. ROADEF, France, Febuary 2017 -Siyou Fotso VS, Mephu-Nguifo E, Vaslin Ph. Parameter free piecewise Dynamic Time Warping for time series classication. Time Series workshop at International Conference on Machine Learning, Sydney, Australia, August 2017 -Siyou Fotso VS, Mephu Nguifo E, Vaslin Ph. Grasp heuristic for time series compression with piecewise aggregate approximation, Journal RAIRO : Operations Research, accepted. In press. Introduction

  .1 present detailed information about tested datasets.

	Data-set	Size of	Length No. of	Type
		dataset		Classes
	50words	905	270	50	IMAGE
	Adiac	781	176	37	IMAGE
	Beef	60	470	5	SPECTRO
	Car	120	577	4	SENSOR
	CBF	930	128	3	SIMULATED
	Coee	56	286	2	SPECTRO
	ECG200	200	96	2	ECG
	FaceFour	112	350	4	IMAGE
	FISH	350	463	7	IMAGE
	Gun_Point	200	150	2	MOTION
	Lighting2	121	637	2	SENSOR
	Lighting7	143	319	7	SENSOR
	OliveOil	60	570	4	SPECTRO
	OSULeaf	442	427	6	IMAGE
	SwedishLeaf	1125	128	15	IMAGE
	synthetic_control	600	60	6	SIMULATED
	FaceAll	2250	131	14	IMAGE

Table 3 .

 3

1: Datasets.

Table 3.2 presents the comparison of the two algorithms.

Table 3 .

 3 use of the FOTS score associated with the SUShapelet algorithm allows to discover dierent u-shapelets than those found by the Euclidean distance. The FOTS-SUSh improves the results of time series clustering because the FOTS score takes into account the intrinsic properties of the time series when searching for

	Datasets	RI_SUSh RI_FOTS
	50words	0.811	0.877
	Adiac	0.796	0.905
	Beef	0.897	0.910
	Car	0.708	0.723
	CBF	0.578	0.909
	Coee	0.782	0.896
	ECG200	0.717	0.866
	FaceFour	0.859	0.910
	FISH	0.775	0.899
	Gun_Point	0.710	0.894
	Lighting2	0.794	0.911
	Lighting7	0.757	0.910
	OliveOil	0.714	0.910
	OSULeaf	0.847	0.905
	SwedishLeaf	0.305	0.909
	synthetic_control	0.723	0.899
	FaceAll	0.907	0.908

2: Comparison of the Rand Index of SUSH (RI_SUSh) and FOTS-SUSh (RI_FOTS). The best Rand Index is in bold u-shapelets and is robust to the presence of uncertainty. This improvement is particularly signicant when the FOTS score is used for the clustering of time series containing several small oscillations. Indeed, these oscillations are not captured by the Euclidean distance whereas they are by the FOTS score whose calculation is based on the autocorrelation matrix. This observation is illustrated by the result obtained on the SwedishLeaf dataset.

Table 3 . 3

 33

	Rand Index	k-Shape USLM FOTS-SUShapelet
	CBF	0.74	1	0.909
	ECG200 0.70	0.76	0.866
	Fac.F.	0.64	0.79	0.910
	Lig2	0.65	0.80	0.911
	Lig.7	0.74	0.79	0.910
	OSU L. 0.66	0.82	0.905

: Comparison between k-Shape, USLM and FOTS-SUShapelet.

Table 4 .

 4 2: Asymmetry (Edit distance) of subjects' propulsion with regard to their number of years of practice.

	Duration of practice

Table 4 .

 4 5: Similarity matrix between all wheelchair users.

		1.000 0.984 0.798 0.917 0.116 0.104 0.938 0.215 0.109 0.160
	S04	1.000 0.841 0.950 0.129 0.107 0.977 0.230 0.120 0.173
	S05	1.000 0.942 0.588 0.548 0.863 0.686 0.582 0.635
	S07	1.000 0.405 0.392 0.977 0.472 0.396 0.434
	S08	1.000 0.988 0.216 0.971 1.000 0.993
	S09	1.000 0.208 0.929 0.987 0.967
	S10	1.000 0.281 0.205 0.242
	S11	1.000 0.973 0.992
	S12	1.000 0.994
	S13	1.000

  Adjustable Wireless Wheelchair Ergometer (FRET-2)

		Six-component
	Adjustable Backrest	Dynamometer (Left Wheel)	Six-component
	Six-component		Dynamometer
	Dynamometer		(Seat)
	(Backrest)
			Adjustable Seat
	Six-component
	Dynamometer (Right Wheel)		Adjustable Legrest
	Embedded PC (WiFi)		Six-component Dynamometer (Footrest)
	Adjustable Width
	6 d.o.f. I.M.U.
	Angular Potentiometer
	Adjustable Height and Wheelbase	Power supply

  TableB.1. In the UCR database, each data set is divided into a learning set and a test set. Datasets contain between 2 and 60 classes and the time series of these datasets have lengths that range from 24 to 2709 points. The TableB.1 presents a detailed description of the datasets. The following paragraph presents the assessment of the performance of our algorithm on these datasets.

	N	Name N Name	Nb. of Nb. of Size	Size	of	Size of	Size	of	of
			classes classes training training	testing set testing set
				set	set
	Following ... Following ...
	10 11 12 13	CinC_ECG_torso Coee Table B.1: 85 UCR datasets used for experimental validation. The full list is avail-4 40 2 28 Computers 2 able in [Chen et al., 2015] 250 Cricket_X 12 390 End
	14 15	Cricket_Y Cricket_Z B.3.2 Comparison of algorithm performance 12 390 12 390
	16 17 18	DiatomSizeReduction DistalPhalanxOutlineAgeGroup Table B.2 presents the comparison of the classication error of 1-Nearest Neighbor 4 16 3 139 DistalPhalanxOutlineCorrect 2 276 (1-NN) algorithms associated with Euclidean distance (col.
	19	DistalPhalanxTW	6	139
	20	Earthquakes	2	139
	21	ECG	2	100
	22	ECG5000	5	500
	23	ECGFiveDays	2	23
	24	ElectricDevices	7	8926
	25	Face (all)	14	560 1
	26	Face (four)	4	24
	27	FacesUCR	14	200
	28	Fish	7	175
	29	FordA	2	1320
	30	FordB	2	810
	31	Gun-Point	2	50
	32	Ham	2	109
	33	HandOutlines	2	370
	34	Haptics	5	155
	N Herring Name InlineSkate InsectWingbeatSound 1 50Words ItalyPowerDemand 2 Adiac LargeKitchenAppliances 3 ArrowHead Lightning-2 4 Beef Lightning-7 5 BeetleFly MALLAT 6 BirdChicken Meat 7 Car MedicalImages 8 CBF MiddlePhalanxOutlineAgeGroup 3 2 7 11 2 3 2 7 8 3 10 9 ChlorineConcentration . . . . . . Continue to the next page Continue to the next page 35 36 37 38 39 40 41 42 43 44 45 . . .	Nb. of classes 64 100 220 50 67 37 375 3 60 5 70 2 55 2 60 4 381 3 154 3 . . .	Size training set 450 390 36 30 20 20 60 30 467	of . . .	Size testing set of 455 391 175 30 20 20 60 900 3840

Table B .

 B 2: Column (1) presents numbers of the datasets. Column (2) the reduced length of the time series. Column

	(1) (2) (1) (2) (1) (2)	(3)	(3) (3)	(4)	(4) (4)	(5)	(5) (5)	(6)	(6) (6)	(7)	(7) (7)
	Following ... 7 8 Following ... 45 0,25 Following ... 84 150 9 46 0,25 47 0,25 85 71 X	0,17 0,25 0,17 0,20 0,17	0,26 0,247 0,439	0,267 0,148 0,253 (5) 0,233 (1) 0,004 (11) 0,25 0,414 0,414 (9) 0,35 0,35 (0) 0,318 (1) 0,352 0,419 (2) 0,17 0,155 (2) 0,416 0,419 0,267 0,003 0,268 0,337 0,352 0,268 0,217 0,320 0,002 0,414 0,164 0,174 0,288 0,237 0,256 0,258
	53 54 55 56 51 52 50 49 48	10 11 12 13 14 15 16 17 18 σ	0,25 0,17 0,25 0,25 0,17 0,17 0,17 0,17 0,25	0,14 0,20 0,17 0,20 0,20 0,20 0,20 0,25 0,25	0,239 0,891 0,038 0,215 0,133 0,479 0,12 0,171 0,121	0,103 0 0,424 0,423 0,433 0,413 0,065 0,218 0,248 0,239 (0) 0,07 (1) 0,000 (0) 0,380 (13) 0,228 (10) 0,238 (17) 0,254 (5) 0,065 (0) 0,228 (1) 0,232 (2) 0,272 0,349 0,246 0,256 0,246 0,033 0,072 0,285 0,036 0,416 0,277 0,208 0,198 0,232 0,255 0,273 0,773 (14) 0,000 (6) 0 0,215 (0) 0,195 0,249 0,000 0,772 0,809 0,244 0,133 (0) 0,167 0,167 0,388 (7) 0,409 0,355 0,241 0,129 (1) 0,135 0,146 0,3 0,185 (1) 0,209 0,222 0 0,134 (1) 0,165 0,133 0,175 0,161 0,166 0,160
	57 58 59 60	19 20 21 22	0,25 0,25 0,17 0,17	0,25 0,17 0,25 0,25	0,192 0,292 0,605 0,64	0,273 0,326 0,12 0,075 0,210 (1) 0,272 (0) 0,258 (22) 0,120 (0) 0,075 (1) 0,216 0,29 0,258 0,276 0,310 0,23 0,180 0,076 0,251 0,263 (6) 0,263 0,280 0,560 (8) 0,536 0,501 0,072 0,589 (17) 0,603 0,645
	61 62 63 64	23 24 25 26	0,17 0,17 0,17 0,24	0,25 0,25 0,24 0,20	0,461 0,248 0,659 0,305	0,203 0,45 0,286 0,300 (3) 0,203 (0) 0,376 (14) 0,192 (3) 0,35 0,198 (4) 0,232 0,216 0,114 (2) 0,328 (15) 0,357 0,305 (0) 0,275	0,232 0,399 0,339 0,259 0,438 0,210 0,192 0,253 0,17 0,170 0,349 0,250
	65 66 67 68 69 70 71	27 28 29 30 31 32 33	0,25 0,17 0,20 0,25 0,20 0,25 0,20	0,24 0,17 0,17 0,17 0,20 0,16 0,14	0,141 0,151 0,062 0,211 0,1 0,12 0,32	0,231 0,217 0,341 0,442 0,141 (0) 0,088 (12) 0,154(4) 0,341 (0) 0,414 (1) 0,169 0,095 0,177 0,438 0,406 0,189 0,095 (16) 0,093 0,124 0,062 (0) 0,06 0,055 0,177 0,263 0,359 0,360 0,087 0,087 (0) 0,093 0,047 0,4 0,400 (0) 0,533 0,419 0,199 0,197 (1) 0,202 0,206 0,154 (2) 0,208 0,184 0,062 (8) 0,05 0,048 0,017 (6) 0,007 0,017 0,250 (8) 0,228 0,193
	1 2 3 4 72 73 74 75 76 77 78 79 80 81 5 6 82 83 Continue to the next page 54 0,20 35 0,20 50 0,20 78 0,17 34 0,17 35 0,17 36 0,14 37 0,20 38 0,33 39 0,17 0,20 0,20 0,25 0,24 0,20 40 0,17 0,20 41 0,20 0,20 42 0,17 43 0,17 0,17 0,20 0,20 85 0,17 85 0,17 44 0,24 0,20 0,17 Continue to the next page 0,369 0,389 0,2 0,333 0,192 0,24 0,09 0,253 0,261 0,338 0,35 0,052 0,005 0,389 0,25 0,45 0,382 0,635 Continue to the next page	0,242 (6) 0,391 (3) 0,200 (0) 0,333 (0) 0,588 (2) 0,484 0,63 0,469 (5) 0,658 0,613 (14) 0,31 0,396 0,297 0,367 0,623 0,279 0,425 0,246 0,623 0,469 0,500 0,616 0,615 0,438 0,422 (2) 0,645 0,611 0,045 0,045 (0) 0,05 0,048 0,507 0,205 (94) 0,205 0,092 (5) 0,162 0,154 0,010 (3) 0 0,070 0,002 (4) 0 0,000 0,132 (5) 0,096 0,283 0,227 (4) 0,273 0,252 0,203 0,246 0,131 (6) 0,301 (4) 0,366 0,346 0,131 0,164 0,425 0,288 (5) 0,274 0,322 (6) 0,342 0,334 0,219 0,086 0,086 (0) 0,066 0,097 0,067 0,067 (0) 0,067 0,034 (4) 0,108 0,067 0,005 (1) 0,02 0,021 0,389 (0) 0,426 0,315 0,433 0,300 (7) 0,3 0,300 0,300(6) 0,25 0,067 0,316 0,253 (20) 0,263 0,288 0,252 (8) 0,351 0,320 0,586 (3) 0,536 0,508 0,250

Table C .

 C 2: normality test show that residues (uncertainty) do not follow normal law.Normality test : For each tests in (TableC.2), the p-value is signicant, so the sample does not follow a normal distribution.

	Test	Kolmogorov-Smirnov Anderson-Darling Shapiro-Wilk
	p-value <2.2e-16	<2.2e-16	<2.2e-16

Ph.D. Thesis

Ph.D. Thesis

We will use this type of distance later when analyzing manual wheelchair locomotion (Chap. 4).Ph.D. Thesis

We will use this type of distance later when analyzing manual wheelchair locomotion (Appendix D ).

1.5 ConclusionChapter 1. Knowledge discovery on time series

Note: The experiments were conducted on a PC with an Intel Core i7 processor, 16GB of RAM and a Windows 7 64-bit operating system.

In this preliminary work, we evaluated the performance of FOTS on 17 datasets, ongoing executions will provide results on the 85 datasets in the UCR database.

The measurements made with subject S01 being of very low intensity, they were not considered during our analysis.

https://fr.wikipedia.org/wiki/Jauge_de_d%C3%A9formation

https://fr.wikipedia.org/wiki/Pont_de_Wheatstone

This assertion will be commented later in chapter 4

This separation is essential to establish the dissymmetry of wheelchair locomotion and is discussed in more details in chapter 4

Chapter 4

Symbolic representation of cyclic time series based on properties of cycles Abstract :

The analysis of cyclic time series from bio-mechanics is based on the comparison of the properties of their cycles. As usual algorithms of time series classication ignore this particularity, we propose a symbolic representation of cyclic time series based on the properties of cycles, named SAX-P. The resulting character strings can be compared using the Dynamic Time Warping distance. The application of SAX-P to propulsive moments of three subjects (S1, S2, S3) moving in Manual Wheelchair highlight the asymmetry of their propulsion. The symbolic representation SAX-P facilitates the reading of the cyclic time series and the clinical interpretation of the classication results.

Introduction

Generally, during his locomotion, the human being performs cyclic movements (e.g. : walking, running, swimming, cycling). The bio-mechanical analysis of these movements is performed with various measuring instruments (eg force and acceleration sensors, kinematic analysis systems) that enable continuous recording over long periods of many kinematic and dynamic parameters. These recordings produce long time series composed of many cycles or patterns, representative of the movements made and eort produced by the subject during his displacement (Fig. 4.1). These cycles are the time series analysis units and have several characteristic properties such as the minimum value, the area under the cycle [Vegter et al., 2014] (Fig. 4.2).

For comparing time series, several previous studies suggested to break them into small segments and then to compare the properties of their segments. A segment of a time series is a sequence of consecutive values belonging to it [START_REF] Abonyi | Fuzzy clustering based segmentation of time-series[END_REF].

[ [START_REF] Keogh | Derivative dynamic time warping[END_REF] proposed replacing each segment of a time series X = Appendix A

Analysis of manual wheelchair locomotion

A.1

Appendix B

An optimal approach for time series segmentation: Application to the supervised classication

B.1 Also, information theory tells that the amount of information relating to an event is equal to -log 2 (p) where p is the probability of the event [Shannon, 2001] . In other words, a very likely event (p -→ 1) brings less information than an unlikely event (p -→ 0). Therefore, a point outside the interval [-2σ, +2σ] provides more information than a point within that range. Indeed, the probability that one point is in the range is 0.95 while the probability that one point is out of range is 0.05 = 1 20 .

If we choose a minimum number (α) of segments less than 5 % of the length of the time series, we risk to aggregate the data points within the interval [-2σ, 2σ] and those outside this range. This will have two consequences: rstly, this aggregation will alter the information carried by data points. Secondly, this aggregation will increase the variance of the segments obtained. So we chose to consider 5% of the number of points in the time series as the minimum number of segments. This allows us to dene the following functions of N → N:

β gives the maximum number of segments. Indeed, a segment is made up of at least 2 points, so there is at most n 2 segments. The number of segments W that we will consider is greater than or equal to α(|X|) and less than or equal to β(|X|). The next subsection explains how we choose the value of W.

B.2.4 Minimize the squared error to choose the number of segments

After dividing a time series into segments, we replace each segment by the average of the data points that constitute it. The variance between the points of each segment can be measured from the mean squared error. Our problem is therefore the following:

is minimal, where Xi is the arithmetic mean of a segment of length k.

Training and changes on propulsion technics

In this section, we want to evaluate the eect of the experiment on the propulsion technique used by manual wheelchair users. We assume that the shape of the M z moment of the left and right wheels reects the propulsion technique used. Thus, in this paragraph, rather than using an approach that uses cycle properties, we directly compared time series from a distance function while taking into account the presence of uncertainty in measurements. To do this, we applied FOTS-UShapelet to the measurements made and we deliver here the analysis we made of the results obtained.

FOTS-UShapelet was applied to the time series from the measurement of eorts made by eight valid subjects during the rst week of use and after three weeks of use of the Manual Wheelchair. Table D.1 details the obtained results. From the shape of the time series, we could form three large groups that correspond to three techniques that we have named T1, T2 and T3. For each subject of the experiment, we observe a dierence between the propulsion techniques used at the beginning of the trial period and after three weeks. For example the subject SA01 uses the T1 technique 83% and the T3 technique 17% of the time during the rst week. However, after three weeks of using the Manual Wheelchair, he uses the T1 technique 33% of the time and the T3 technique 67% of the time. So there is a change in the way he moves. However, the observed changes vary according to the subjects (Table D.1). The variations in the evolution of propulsion techniques require personalized monitoring of locomotion and highlight the importance of using a Wheelchair Ergometer when learning locomotion in a Manual Wheelchair.

Subject Week

Trial wheel technic T1 T2 T3 6) and ( 7) the smallest error is in bold. Then we compare the classication errors of algorithms of columns( 4), ( 5), ( 6) and ( 7) the smallest error is put italics.