Alexandre Sahuguède
email: asahugue@laas.fr

Euriell Le Corronc

Marie-Véronique Le Lann
email: mvlelann@laas.fr

Chronicle Discovery for Diagnosis from Raw Data: A Clustering Approach

Keywords: Fault Diagnosis, Machine Learning, Clustering, Temporal Pattern Mining, Chronicle Discovery

Chronicles are temporal patterns well suited for an abstract representation of the behavior of dynamic systems. For fault diagnosis, chronicles describe the nominal and faulty behaviors of the process. Powerful algorithms allow the recognition of chronicles in the flow of observations of the system and appropriate actions can be taken when a faulty situation is recognized. However, designing chronicles is not a trivial thing to do. The increasing complexity and capacity of data generation of highly-advanced processes cause the acquisition of a complete model difficult. This paper focuses on the problem of discovering chronicles that are representative of a system behavior from direct observations. A clustering approach to this problem is considered. The chronicle discovery algorithm proposed here designs chronicles with minimal knowledge of the system to diagnose. Furthermore, unprocessed data obtained directly from the system can be used in this clustering algorithm. Finally, the chronicle discovery algorithm proposed in this paper is illustrated on a sport performance monitoring device for a diagnosis of movement deviations in the temporal domain, in the event domain, or both, considered as faults for the athlete.

INTRODUCTION

This paper focuses on the fault diagnosis of dynamic complex systems problem. The problem consists in producing a temporal model well suited for fault diagnosis from a set of observations of a complex process. The increasing complexity of modern systems and the development of data generation and storage capacities greatly increase the number of observations. This large number of observations should be processed by some automatic method in order to assist the expert in the design of such a temporal model.

The studied models are timed discrete event models called chronicles [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF]. They are temporal patterns well suited to capture the behavior of a dynamic process. Chronicles describe behaviors by means of an event abstraction of the information of interest. Within this formalism, events are partially ordered and temporally constrained one to another. Figure 1 describes such a chronicle where events of interest are a, b and c. The illustrated process is such that an event of type c must occur between 3 and 4 time units (t.u.) after an event of type b. This event must appear between 1 and 2 t.u. later than an event of type a. Another event of type c must follow a anytime bounded by 8 and 10 t.u.. In the diagnosis domain, each chronicle represents a specific behavior of the system. This behavior can be nominal or typical when a fault is present. This faulty behavior can be recognized in a temporal sequence made of timed observations generated by the system. The recognition of this specific temporal pattern leads to establish that the system is in that faulty situation [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF]. Various diagnosis applications use the chronicle approach. A chronicle based diagnosis in web services is presented in [START_REF] Pencolé | A chronicle-based diagnosability approach for discrete timed-event systems: Application to web-services[END_REF]. A multi-alarm misuse correlation component that allows the user to significantly reduce the number of alarms uses a chronicle approach in [START_REF] Morin | Correlation of intrusion symptoms: An application of chronicles[END_REF]. Chronicles could be used in the medical field as for instance in [START_REF] Carrault | A model-based approach for learning to identify cardiac arrhythmias[END_REF] where they allow identification of cardiac arrhythmia and in [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] where possible associations between hospitalizations for seizure and anti-epileptic drug switches are identified. However, as efficient a diagnosis with chronicles can be, designing chronicles is not a trivial thing to do. The design of such a complex model often requires the knowledge of an expert of the process to be diagnosed. Unfortunately, this knowledge is frequently not enough to build pertinent chronicles for diagnosis. The Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]) is a commonly used approach to try and tackle this problem. Apriori is a data mining algorithm that find frequent collections of items in sale transactions. It finds iteratively larger and larger itemsets. An itemset found to be frequent in size k will be discarded if a sub-itemset of size k -1 is not frequent. This Apriori algorithm can be used for sequential pattern mining [START_REF] Mannila | Discovering frequent episodes in sequences[END_REF] as well as temporal pattern mining [START_REF] Guyet | Extracting temporal patterns from interval-based sequences[END_REF]. Several chronicle discovery algorithms are based on the Apriori algorithm as in [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF]. In his paper, Cram presents a chronicle discovery algorithm from a temporal sequence. This algorithm is extended to the multi-sequences case by [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]. First, it builds a database of time constraints. Then, it generates a set of candidate chronicles starting with a set of chronicles that were proved to be frequent. A temporal constraint network discovery algorithm is presented in ( Álvarez et al., 2013) and uses a clustering algorithm reducing the set of candidates. This algorithm could be convenient for chronicle discovery as temporal constraint networks are similar to chronicles.

The main limitation of these Apriori -based approaches lies in the fact that a minimum frequency parameter is necessary. The choice of this parameter is not trivial and requires a good amount of knowledge of the system to obtain good results. Another limitation is that these algorithms are done from one, or several, temporal sequences, meaning that only observations of the system made of events can be used. Unfortunately, very often observations of the dynamic process behaviors are composed of sampled continuous signals obtained from sensor measurements, logs from communication networks or healthcare data. This paper tries to offer another solution with a clustering approach applied directly to raw data. Machine learning techniques and more specifically clustering, based on the density of the data such as DBSCAN (Density Based Spatial Clustering and Application with Noise [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF]) or on the fuzzy logic such as LAMDA (Learning Algorithm for Multivariate Data Analysis [START_REF] Carreté | Controlling selectivity in nonstandard pattern recognition algorithms[END_REF]), are applied to discover chronicles. First, a temporal sequence is extracted from the raw data provided by the system observations. Then, clustering techniques are used to regroup some patterns by similarity. A strong advantage of this method is that the frequency of the pattern found is deduced from the data. Clusters found are considered as the most representative patterns of the system. Chronicles discovered by the proposed algorithm are various in length (the number of events of a chronicle) and in frequency. They can be recognized on-line by a chronicle recognition algorithm. Chronicles obtained are an abstract representation of the dynamic system behavior which describes either the nominal or a faulty behavior. Contrary to the exponential algorithmic complexity of the Apriori approach, the proposed method can be done with a polynomial algorithmic complexity.

The rest of this paper is organized as follows. In Section 2, definitions of required concepts are explained. Section 3 presents the algorithm that discovers chronicles from raw data. Section 4 introduces an example with a swimming performance monitoring equipment for a health monitoring of the athlete movements. Section 5 concludes this work.

CONCEPTS AND DEFINITIONS

Chronicles

This section explains the chronicle concepts used in this work. Chronicles are ways of expressing relevant temporal patterns about a process [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF]. Definition 1. (Event). An event is defined by x = (e, t) with an event type e ∈ E, and a time instant t ∈ N. Definition 2. (Temporal sequence). A temporal sequence is a time-ordered set of events denoted S = {x i } where i ∈ N, i = 1, . . . , n with n a finite number of events, and t j < t j+1 , j = 1, . . . , n -1. The set of all event types occurring in S is called E S . Example 1. The temporal sequence S = {x 1 , x 2 , x 3 , x 4 , x 5 } where x 1 = (a, 1), x 2 = (b, 2), x 3 = (a, 12), x 4 = (a, 18), and x 5 = (b, 20), graphically represented in Figure 2, points out the difference between event and event type. That is several events can share the same event type. For instance, events x 1 , x 3 and x 4 are different occurrences of event type a. 0 1 2 4 6 8 10 12 14 16 18 20 a b a a b t Fig.

2.

A temporal sequence S = {(a, 1), (b, 2), (a, 12), (a, 18), (b, 20)} with E S = {a, b} the set of all event types in S. Definition 3. (Temporal constraint). A temporal constraint is a tuple τ ij = (x i , x j , t -, t + ), also noted

τ ij = x i [t -, t + ]x j , where 0 < t -≤ t + . A temporal constraint τ ij = x i [t -, t + ]
x j is said satisfied by a couple of events x i = (e i , t i ), x j = (e j , t j ) if and only if (t jt i ) ∈ [t -, t + ]. Definition 4. (Chronicle). A chronicle C is a pair (X , T ) where X = {x i } is a set of partially ordered events with i ∈ N, i = 1, . . . , n, and n a finite number of events, and T = {τ ij } 1≤i<j≤n is a set of temporal constraints on X . E C denotes the set of all event types of C. A n-length chronicle is a chronicle with n events. Example 2. Let C = (X , T ) be a 4-length chronicle with X = {x 1 = (a, t 1 ), x 2 = (b, t 2 ), x 3 = (c, t 3 ), x 4 = (c, t 4 )}, and

T = {τ 12 = x 1 [1, 2]x 2 , τ 23 = x 2 [3, 4]x 3 , τ 14 = x 1 [8, 10]x 4 }. The set of all event types of C is E C = {a, b, c}.
Graphically, a chronicle is a directed graph where the nodes represent the events of X and the transitions represent the temporal constraints of T . In each temporal constraint τ ij , x i is the starting node and x j is the ending node. For instance, Figure 1 is the graphical representation of the chronicle described in Example 2.

The frequency criterion is chosen to define the relevance of a pattern required for the learning chronicle process. Such criterion needs definitions in this domain. Definition 5. (Chronicle instance). Given a chronicle C = (X , T ) and a temporal sequence S, a chronicle instance is a subset of events of S denoted I C (S) such that their event types are those of X and their time occurrences satisfy all the temporal constraints T of C. Definition 6. (Frequency of a chronicle). The frequency of a chronicle C in a temporal sequence S is the number of instances of C in S and is named f C (S).

Definition 7. (Coherent chronicle). A chronicle C is called coherent if there exists a temporal sequence S such that f C (S) > 0. A coherent chronicle has at least one chronicle instance I C (S). Example 3. Let us define a chronicle C = (X , T ) with X = {x 1 = (a, t 1 ), x 2 = (b, t 2 )}, and

T = {τ 12 = x 1 [1, 2]x 2 }.
Given the temporal sequence S seen in Figure 2, two instances of the chronicle C appear: a, 1), (b, 2)}, andI 2 C (S) = {x 4 , x 5 } = {(a, 18), (b, 20)}. The frequency of the chronicle C in S is f C (S) = 2 and corresponds to the total number of instances. This chronicle is coherent since there exists a temporal sequence S such that f C (S) = 2 > 0. Definition 8. (Occurrences of a pair). Let S be a temporal sequence and let (a, b) be a pair of event types such that a, b ∈ E S . The set O ab is the set of all the occurrences of (a, b) in S such that b follows a:

I 1 C (S) = {x 1 , x 2 } = {(
O ab = { (a, t i ), (b, t j ) | ∀i, j, t i < t j , (a, t i ), (b, t j ) ∈ S}.
(1) Definition 9. (Temporal distances of a pair). The set D ab is all the temporal distances between each occurrence of the pair (a, b):

D ab = {(t j -t i ) | (a, t i ), (b, t j ) ∈ O ab }.
(2) Example 4. Given the temporal sequence S of Figure 2, the set of all occurrences of each pair is determined: O aa = { (a, 1), (a, 12) , (a, 1), (a, 18) , (a, 12), (a, 18) }, O ab = { (a, 1), (b, 2) , (a, 1), (b, 20) , (a, 12), (b, 20) , (a, 18), (b, 20)

}, O ba = { (b, 2), (a, 12) , (b, 2), (a, 18) }, O bb = { (b, 2),
C = (X , T ) where X = {x 1 = (a, t 1 ), x 2 = (b, t 2 )}, and
T = {τ 12 = x 1 [1, 19]x 2 }. Furthermore, the in- stances of C in the original temporal sequence S are I 1 C (T ) = {(a, 1), (b, 2)}, I 2 C (T ) = {(a, 1), (b, 20)}, I 3 C (T ) = {(a,

Clustering

This section presents the clustering algorithms required in this work: LAMDA and DBSCAN. They group data samples based on the similarity or dissimilarity of the measures. The distinctive characteristics of data samples are called features while the specific pattern detected in the data are called classes. In this paper, features of interest are issued from on-line sensor measurements of dynamic process, logs of networks communications or healthcare data.

The fuzzy logic based algorithm called LAMDA2 [START_REF] Carreté | Controlling selectivity in nonstandard pattern recognition algorithms[END_REF] takes as input a sample k made up of N features. Its first step computes for each feature k an adequacy degree to each class, indexed by 1 . . . J where J is the total number of classes (not known in advance but updated along the algorithm). With the help of a fuzzy adequacy function, J vectors of N adequacy degrees are computed. They are called Marginal Adequacy Degree vectors (MAD) and can be calculated by different means (Gaussian, fuzzy binomial, centered fuzzy binomial). In a second step, a fuzzy aggregation function assembles all the MADs for a specific class into one Global Adequancy Degree (GAD). This fuzzy function has a parameter α, called exigency index. α is given in the [0, 1] interval. The α parameter has a direct impact on the number of classes found: the bigger α is, the higher the number of classes found. The J MAD vectors, composed of N MADs, become J scalar GADs. The higher the GAD, the better the adequacy to the class. The simplest way to assign the sample k to a class is to keep as result the class with the biggest GAD.

The density based clustering algorithm DBSCAN [START_REF] Ester | A density-based algorithm for discovering clusters in large spatial databases with noise[END_REF] works in two steps. First, every densityreachable points from each point of the dataset to be classified are calculated. Second, a random starting point is selected. If it is a core point, meaning that it has in its neighborhood of radius ε at least the minimal number of points minP ts, a new cluster is created. Otherwise, this point is determined as noise. This point and every points density-reachable from it with ε is added in the created cluster. This cluster is then expanded by selecting the new density-reachable point from the core point and determining if it is another core point. Then, its densityreachable points are added in the cluster. When the cluster is fully expanded, a new unvisited point is retrieved and this step is repeated, leading to the discovery of new clusters and noises.

CHRONICLE DISCOVERY FROM RAW DATA

As presented in Figure 3, the chronicle discovery algorithm proposed in this paper works in several steps. First, temporal patterns are discovered from time-ordered raw data. These data are generated by the dynamic system we want to diagnose. Data come from sensors measurements, alarm logs, healthcare data... In a complex dynamic system, unprocessed data can be corrupted by noises of various origins. Those noises are dealt with by the fuzzy logic based clusterer LAMDA. A temporal sequence is extracted from classes by defining events as the changes of classes over time. Next, 2-length chronicles are discovered by the density based clustering algorithm DBSCAN. It groups them by similar temporal distances between events. This clustering step allows to find the frequencies in the temporal sequence of those 2-length chronicles. Finally, a similar frequency criterion is used on the 2-length chronicles found in the previous step to unified them. This is done by means of the computation of a Jaccard index on the events. The algorithm provides chronicles of various lengths and frequencies. Each chronicles representing time patterns where events are abstraction of the most relevant elements of the dynamic process. These elements are temporally constrained to each other.

Step 1: Temporal sequence extraction

The first step of the algorithm is the temporal sequence extraction process given in Algorithm 1. 1. The temporal sequence extracted from this classification is S = {(e, 0), (f, 98), (e, 202), (f, 700), (e, 798)} with its set of event types given by E S = {e, f }.

(e, 0) (f, 98) (e, 202) (f, 700) (e, 798) 1 t Fig. 4. Dynamic dataset R with two features, feature 1 in black and feature 2 in gray, corresponding of two sensors in a dynamic process.

Step 2: 2-length chronicle discovery

A temporal sequence S is then generated from the timeordered raw data R thanks to the previous step. One would like to know if it is possible to gather events of S according to some criterion by mean of another clustering phase. Indeed, by calculating the temporal distances D (see Definition 8 and Equation ( 2)) of all the pairs of events of S, one can see that some distances of the same set are close whereas others are further apart. Thus, this step of the algorithm uses the density based algorithm DBSCAN to group such similar distances in clusters. During this clustering phase, D is interpreted as a dataset with one dimension feature space.

Then, by using Proposition 1, the algorithm builds 2length chronicles C from the clusters found. This is done by taking the minimum and the maximum distances of D for the temporal constraint of C. The event types of C are the event types of D. Since DBSCAN results are homogeneous clusters, meaning that there is no temporal distance that satisfies the temporal constraint that is not in D, the frequency f C (S) of the 2-length chronicle is exactly the number of temporal distances in D.

The minimum frequency of the created 2-length chronicles depends on the minimum number of points minP ts in the neighborhood. More precisely, this minimal frequency is equal to minP ts + 1. The radius parameter ε defines the dispersion of the temporal constraint, when ε grows, the dispersion grows. The 2-length chronicles discovery algorithm is presented in Algorithm 2 given a temporal sequence S. First, for each pair of event types from E S (called a and b for the explanation of this algorithm, but pair a and a is also taken), the set of temporal distances D ab is calculated by Equation (2). A cluster analysis is performed on D ab with the DBSCAN algorithm. Finally, each cluster D j ab found defines a 2-length chronicle. Example 7. Let the temporal sequence generated in Example 6 be S = {(e, 0), (f, 98), (e, 202), (f, 700), (e, 798)} with E S = {e, f }. First, let us see the pair (f, e), Algorithm 2 provides D f e = {104, 700, 98} as the set of all temporal distances for this pair. The DBSCAN parameters are set such that minP ts = 1, and ε = 7. As a result, only one cluster is found: D 1 f e = {104, 98}. The remaining temporal distance is in a low density area and is considered irrelevant. For the other pairs ((e, e), (e, f ), and (f, f )), the clustering algorithm does not find temporal distances close enough to group them. The chronicle C 1 is obtained from D 1 f e using Proposition 1 and is illustrated in Figure 5. It is a 2-length chronicle with X 1 = {x 1 = (f, t 1 ), x 2 = (e, t 2 )}, and T 1 = {τ 12 = x 1 [98,104]x 2 }. The frequency of C 1 in S is f C1 (S) = 2 and its two instances in S are: I 1 C1 (S) = {(f, 98), (e, 202)}, and I 2 C1 (S) = {(f, 700), (e, 798)}. With Proposition 2, C 1 is coherent.

t 1 f t 2 e [98, 104] Fig. 5. The 2 -length chronicle C 1 = (X 1 , T 1 ) obtained from the set D 1 f e with X 1 = {x 1 = (f, t 1 ), x 2 = (e, t 2 )}, and T 1 = {τ 12 = x 1 [98, 104]x 2 }.
Remark. The temporal sequence given as entry in this algorithm can be either obtained by the algorithm seen in Section 3.1 or directly given from observations of the system.

Step 3: Chronicle synthesis

Previous step can find several 2-length chronicles with the same frequency. One could consider that they represent different parts of the same concept to be modeled and want to group them. A systematic process is proposed in this step to combine such chronicles generated from the same temporal sequence S by a Jaccard index on events. This index first needs instances of created chronicles to find identical occurrences of events obtained by different 2-length chronicles of the same frequency. Definition 10. (Time occurrences of an event). Let S be a temporal sequence and C = (X , T ) be a chronicle. O i is the set of time occurrences of the event x i in all chronicles instances I C (S). O i is calculated by the following formula:

O i = {t i | ∀I C (S), x i = (e, t i ) ∈ X }.
(3) The size of O i is given by f C (S) and is denoted |O i |. Example 8. Given the chronicle C and the temporal sequence S seen in Example 3, the two chronicles instances I 1 C (S) and I 2 C (S) give the two occurrences of x 1 : (a, 1) and (a, 18). The set of time occurrences of

x 1 is O 1 = {1, 18} (|O 1 | = 2). For x 2 , O 2 = {2, 20} and |O 2 | = 2.
Definition 11. (Jaccard index). Let x i and x j be two events with time occurrences O i and O j determined by Equation ( 3). The Jaccard index between x i and x j is calculated by the following formula:

S(x i , x j ) = |O i ∩ O j | |O i ∪ O j | . ( 4
)
More precisely, the Jaccard index will quantify the frequency at which the occurrence of two events appears at an identical time. These are two identical events thanks to Definition 2 where an occurrence of two different events x i and x j in a temporal sequence S must be at two different time instants. This index is on a scale from 0 to 1: 0 meaning no occurrences are identical; and 1 meaning all of them are identical. Example 9. Let x 1 = (a, t 1 ) and x 3 = (b, t 3 ) be two events with O 1 = {1, 18} and O 3 = {1, 18}. Since their time occurrences are identical, their Jaccard index is then

S(x 1 , x 3 ) = |O1∩O3| |O1∪O3| = 2 2 = 1.
Remark. The restriction to have a Jaccard index equals to 1 is strong. However, there are some problems in relaxing this constraint and is the subject of on-going works. Naturally, for S(x i , x j ) to be equals to 1, O i and O j must be of the same size. Therefore, only chronicles of the same frequency can be combined.

Algorithm 3. (Chronicle synthesis). Algorithm 3 represents the synthesis of the 2-length chronicles of the same frequency generated by step 2. First, the algorithm finds the maximal frequency f max of the 2length chronicles. Next, a chronicle C fmax is created with the merging of all the 2-length chronicles of frequency f max . This merging step is explained by Algorithm 4 given below. Then, operation is repeated for frequency f maxi until all the 2-length chronicles generated were processed.

Algorithm 4. (Merge by similarity operation).

1 INPUT: chronicles to merge C 1 and C 2 2 OUTPUT: merged chronicle Cres 3 INIT chronicle Cres with chronicles C 1 and C 2 4 FOR all events x i of events set X 1 5 FOR all events x j of events set X 2 6 IF x i and x j are similar events THEN 7 UPDATE chronicle Cres with x i equal to x j 8 ENDIF 9 ENDFOR 10 ENDFOR Merge by similarity operation is presented in Algorithm 4 with this renaming operation:

C f becomes C 1 and C be- comes C 2 . First, C 1 = (X 1 , T 1 ) and C 2 = (X 2 , T 2 ) are combined in chronicle C res = (X res , T res ) with X res = {X 1 , X 2 } and T res = {T 1 , T 2 }.
Then, the Jaccard index of each events x i ∈ X 1 and x j ∈ X 2 are calculated with Equation (4). When S(x i , x j ) = 1, events x i and x j are considered identical. In this case, C res is updated, x j is removed from X res and temporal constraints on x j are now on x i . This step is repeated for all events found similar. Proposition 3. The merge by similarity of two chronicles of the same frequency generated by the 2-length chronicle discovery algorithm is a chronicle.

Proof. To prove that C res is a chronicle, it is needed to prove that X res is a partially ordered set of events. In other words, is it possible that the operation x i = x j does not produce a partially ordered set of events? Let C = (X , T ) with X = {x 1 = (e, t 1 ), x 2 = (f, t 2 )}, T = {τ 12 }, and C = (X , T ) with X = {x 3 = (f, t ), x 4 = (e, t 4 )}, T = {τ 34 }, be two 2-length chronicles of the same frequency. Let S be a temporal sequence such that I C (S) = {(e, δ 1 ), (f, δ 2 )} and I C (S) = {(f, δ 3 ), (e, δ 4 )} are instances of C and C . With temporal constraints τ 12 and τ 34 , inequality equations δ 1 < δ 2 and δ 3 < δ 4 are known. Let x 1 and x 4 , as well as x 2 and x 3 , be identical, therefore δ 1 = δ 4 and δ 2 = δ 3 . However, this implies that δ 1 is both strictly superior and strictly inferior to δ 2 . As a consequence, either x 1 and x 4 , or x 2 and x 3 are different. X res is a partially ordered set of events and C res is a chronicle. Proposition 4. The chronicle resulting from the merge by similarity of two chronicles of the same frequency generated by the 2-length chronicle discovery algorithm is coherent.

Proof. Let C 1 and C 2 be two 2-length chronicles and C res the chronicle created by the merge by similarity of C 1 and C 2 . Let S be a temporal sequence. For each couple of instance I C1 (S) and I C2 (S), there exists an instance I Cres (S). Therefore, the frequency of C res is identical to the frequency of C 1 and C 2 . As a consequence, the chronicle [98,104]x 2 }, and C 3 = (X 3 , T 3 ) where X 3 = {x 1 = (e, t 1 ), x 2 = (e, t 2 )}, T 3 = {τ 12 = x 1 [353,365]x 2 } be three 2-length chronicles. Their frequencies are f C1 (S) = 4, f C2 (S) = 4, and f C3 (S) = 6. After finding the maximal frequency, in this case f max = f C3 (S) = 6, all the chronicles of frequency equals to 6 are merged. Only C 3 is of the required frequency so C fmax = C 3 . Repeating this operation with f max -1 = 5 does not find any chronicle of this given frequency. Two chronicles of frequency equals to 4 are found, C 1 and C 2 .

C res is coherent. Example 10. Let C 1 = (X 1 , T 1 ) where X 1 = {x 1 = (e, t 1 ), x 2 = (f, t 2 )}, T 1 = {τ 12 = x 1 [255, 261]x 2 }, C 2 = (X 2 , T 2 ) where X 2 = {x 1 = (f, t 1 ), x 2 = (e, t 2 )}, T 2 = {τ 12 = x 1
As seen in Figure 6, the first step is to merge them by similarity in C res = (X res , T res ) where X res = {x 1 = (e, t 1 ), x 2 = (f, t 2 ), x 3 = (f, t 3 ), x 4 = (e, t 4 )}, and T res = {τ 12 = x 1 [255,261]x 2 , τ 34 = x 3 [98,104]x 4 }. The Jaccard index between each event is calculated: events x 2 and x 3 are found similar. They are considered identical and the chronicle C res is updated such that X res = {x 1 = (e, t 1 ), x 2 = (f, t 2 ), x 3 = (e, t 3 )}, and T res = {τ 12 = x 1 [255,261] From the three 2-length chronicles C 1 , C 2 and C 3 defined previously, two chronicles of different frequencies are generated: 353,365]x 2 }, and

C f =6 = (X f =6 , T f =6 ) where X f =6 = {x 1 = (e, t 1 ), x 2 = (e, t 2 )}, T f =6 = {τ 12 = x 1 [
C f =4 = (X f =4 , T f =4 ) where X f =4 = {x 1 = (e, t 1 ), x 2 = (f, t 2 ), x 3 = (e, t 3 )}, T f =4 = {τ 12 = x 1 [255, 261]x 2 , τ 23 = x 2 [98, 104]x 3 }.
Remark. When all the 2-length chronicles found in the previous step seen in Section 3.2 have different frequencies, this step is not required. Only chronicles of the same frequency can be combined.

Algorithmic complexity

In this section, the algorithmic complexity of the proposed algorithm is analyzed. It is shown that with the clustering algorithms used, a polynomial complexity can be done.

Let n be the number of samples in the raw data R. The algorithmic complexity of LAMDA is O(n), the generation of a temporal sequence from classes is also O(n) complex.

The algorithmic complexity of the temporal sequence extraction step is O(n).

Let l(l-1) 2 be the number of temporal distances found in the l-length temporal sequence S input in the 2length chronicle discovery. The number of discovered 2length chronicles is defined by c 2 = l(l-1)

2 . The inputs of DBSCAN is c 2 , as such, its complexity is O(c 2 log(c 2 )) that can be simplified by O(l 2 log(l 2 )). So, the algorithmic complexity of the 2-length chronicle discovery step is O(l 2 log(l 2 )) and depends on the complexity of the clustering algorithm used.

The algorithmic complexity of the merge by similarity operation between a m-length chronicle C 1 and a 2-length chronicle C 2 is given by O(m log(m)). The chronicle synthesis step will process at most c 2 merge by similarity operations. So, the complexity of this step is O(c 2 m log(m)).

The overall algorithmic complexity of the chronicle discovery from raw data algorithm is given by: O(n 2 m log(m)), with n the number of samples in the raw data R and m the length of the longest discovered chronicle. The complexity is highly dependent of the choice of the clustering algorithm parameters implemented in step 2. Badly chosen parameters can produce a high number of 2-length chronicles c 2 . This problem shows the necessity to enforce a quality check at the end of the 2-length chronicle discovery step to limit the impact of c 2 on the discovery time.

APPLICATION

In this section, an application about health monitoring of an athlete movement is detailed. More precisely, data from an instrumented glove for swimming performance monitoring [START_REF] Mangin | An instrumented glove for swimming performance monitoring[END_REF] are captured when the athlete performs a front crawl on a swimming pool.

The device consists in several sensors (accelerometers, magnetometers, gyroscopes) that allow a precise description of the device movements with a sampling rate of 50 Hz. This equipment is worn on the right hand in order to record the right arm movements in a swimming situation. The dataset R is a recording of an athlete performing a front crawl on a long course swimming pool (50 m).

The time-ordered dataset R contains 2051 samples with 16 features. The normalized features in the [0, 1] interval are divided as follows: Euler angles Roll, P itch, and Y aw; quaternions Q 1 , Q 2 , Q 3 , and Q 4 ; accelerometers Acc x , Acc y , and Acc z ; gyroscopes Gyro x , Gyro y , and Gyro z ; and magnetometers M ag x , M ag y , and M ag z . Figure 7 gives the first 1000 samples of the Euler angle features where we can see already a repetition of a pattern.

The temporal sequence extraction step is performed first on the 16 features of R. The LAMDA algorithm is used with the fuzzy centered binomial method to calculate the MADs, the probabilistic method to calculate the GADs, and the exigency level α sets to 1 and δ sets to 5. With those parameters, LAMDA finds two classes in R. These classes are interpreted as follow: in the first class, denoted under, the arm is pulling and pushing under the water; in the second class, denoted above, the arm is recovering above the water. Figure 8 gives the class of the first 1000 samples of the dataset R.

Once the temporal sequence is extracted, the next step is the 2-length chronicle discovery. With the DBSCAN parameter minP ts set to 1 and ε set to 12, a total of 62 2-length chronicles are discovered with their frequencies ranging from f min = 2 to f max = 17.

Finally, the chronicle synthesis step is processed on all the 62 2-length chronicles. One of the chronicle generated by this step called C res = (X res , T res ) with X res = {x 1 = (above, t 1 ), x 2 = (under, t 2 ), x 3 = (above, t 3 )}, and T res = {τ 12 = x 1 [48,69]x 2 , τ 13 = x 1 [106,130]x 3 , τ 23 = x 2 [52,62]x 3 } is graphically represented in Figure 9. This chronicle has a frequency of f max = 17.

Physically, this chronicle represents a complete arm movement, called stroke cycle. Taking into account the sampling rate of 50 Hz of the raw data, one could discriminate several informations: the recovering phase is done in the interval of [0.96, 1.38] seconds, represented by the temporal constraint τ 12 ; the underwater phase is done in the interval of [1.04, 1.24] seconds, represented by the temporal constraint τ 23 ; the complete stroke cycle is done in the interval of [2.12, 2.6] seconds, represented by the temporal The discovered chronicle describes the nominal arm movements of the athlete performing a front crawl and will be recognized if no discrepancy between the optimal movements of the athlete and the movements recorded in another dataset R exist. Fault diagnosis of movement deviations in the temporal domain, in the event domain, or both, considered as faults for the athlete can be done when the chronicle is not recognized when it should be.

CONCLUSION

This paper provides a clustering approach for designing chronicles with minimal knowledge from the dynamic process to diagnose. The algorithm presented uses a clustering method based on the fuzzy logic to construct a temporal sequence from raw data. Chronicles of different frequencies are then learned from this temporal sequence as a result of a density based clustering algorithm. The chronicle discovery algorithm proposed in this paper is done with a polynomial algorithmic complexity. An application of real data from a swimming performance monitoring device for a health monitoring of the athlete movements is detailed.

Further works need to be done to generalize the designed chronicles. Presently, a limitation lies in the fact that only one temporal sequence S is constructed, as a consequence, there is no guarantee that designed chronicles can be recognized in another temporal sequence S with a slightly different behavior. Another idea is to exploit the Jaccard index not only on a crisp value (0 or 1) but on a fuzzy value (a percentage of similarity). This could permit to combine chronicles with different frequencies. Finally, it could be interesting to design a chronicle discovery algorithm that could deal with domain constraints, when an event could not occur in a period of time; and event counters (added in the chronicle representation in [START_REF] Dousson | Extending and unifying chronicle representation with event counters[END_REF]), when a determined number of events must occur in a given time interval.

  Fig. 1. A chronicle where events of interest are a, b and c.

  (b, 20) }. Additionally, D aa = {11, 17, 6}, D ab = {1, 19, 8, 2}, D ba = {10, 16}, and D bb = {18}. Proposition 1. Let D ab be a set of temporal distances for a pair (a, b). A 2-length chronicle C = (X , T ) which can be obtained from D ab . X = {x 1 = (a, t 1 ), x 2 = (b, t 2 )} is given by the elements of the pair (a, b) and T = {τ 12 = x 1 [ D ab , D ab ]x j } is given by the lower and upper bounds of D ab 1 . Proof. Directly from Definitions 4 and 9. All instances I C (S) of chronicles extracted from the set of temporal distances D ab correspond to the set of their occurrences O ab . The frequency f C (S) is the size of D ab . Example 5. Let (a, b) be a pair of event types, the set of temporal distances calculated in Example 4 is D ab = {1, 19, 8, 2} and defines the following 2-length chronicle:

  12), (b, 20)}, and I 4 C (T ) = {(a, 18), (b, 20)}. These instances correspond to the occurrences of the pair (a, b).

  Fig.3. An overview of the chronicle discovery from raw data algorithm. Inputs are time-ordered raw data taken from the dynamic system. Output is a set of chronicles describing elements of its behavior.

Fig. 6 .

 6 Fig. 6. Merge by similarity of two chronicles C 1 and C 2 in one chronicle C res . The Jaccard index shows that x 2 and x 3 are similar and C res is created.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Normalized values of the first 1000 samples of the features P itch and Y aw of dataset R. R is a record of the right arm movement of a professional athlete in a swimming scenario at a sampling rate of 50Hz.

Fig. 9 .

 9 Fig.9. The 3-length chronicle C res = (X res , T res ) with X res = {x 1 = (above, t 1 ), x 2 = (under, t 2 ), x 3 = (above, t 3 )}, andT res = {τ 12 = x 1 [48, 69]x 2 , τ 13 = x 1 [106, 130]x 3 , τ 23 = x 2 [52, 62]x 3 }.constraint τ 13 ; finally, this professional athlete performed a long course in 17 stroke cycles.

  First, totally time-ordered raw data denoted R are classified by LAMDA. Since it is a clustering operation, the number of classes is not known in advance and the choice of the α parameter is left to the expert. Once each sample of the raw data has been assigned to a class, a temporal sequence S of this classification is obtained by conserving the time-ordered information. Let us define δ, a threshold that represents significant changes in the feature values over time. An event x = (class i , t i ) is created and added to S when the class of the sample i is different than all the previous samples iδ. The set E S of event types of S corresponds to the name of the classes and the time instants are the sample times. Classes with too few consecutive samples are explained as noise and are discarded. Example 6. Let us deal with a process with two recognizable behaviors. They are accurately described by the measurements of two sensors. An evolution of those sensors over a duration of 1100 t.u. with a sampling rate of one sample by t.u. is compiled in the dataset R. This dataset has two features that are interpreted as the measurements of the sensors.

	1 INPUT: totally time-ordered raw data R
	2 OUTPUT: temporal sequence S
	3 INIT S at empty
	4 COMPUTE classes of R with LAMDA algorithm
	5 FOR each data sample i of R
	6	IF the class of i is different than all the classes of i -1 to
		i -δ THEN
	7	ADD event x = (class i , t i ) in S
	8	ENDIF
	9 ENDFOR

R is illustrated in Figure 4. The LAMDA clusterer discriminates two behaviors in the dataset by taking α = 0.2 and δ = 1. Each behavior corresponds to a class: class e with feature 1 decreasing and feature 2 equal to 0; class f with feature 1 increasing and feature 2 equal to Algorithm 1. (Temporal sequence extraction).

  , the set of temporal distances D are also not empty. The frequency of the designed chronicles f C (S) is more than 1. The created 2-length chronicle is coherent.

	Algorithm 2. (2-length chronicle discovery).
	1 INPUT: temporal sequence S
	2 OUTPUT: 2-length chronicles C i
	3 FOR each pair of event types a and b of E S
	4	CALCULATE temporal distances D ab in S
	5	CALCULATE clusters in D ab with DBSCAN
	6 7	FOR each clusters found D j ab TRANSFORM D j ab in a 2-length chronicle
	8	ENDFOR
	9 ENDFOR

Proposition 2. A 2-length chronicle C designed from a set of temporal distances D itself obtained from a temporal sequence S is coherent.

Proof. Clusters found by DBSCAN are not empty, otherwise, they would be considered as noise. As clusters are not empty

  x 2 , τ 23 = x 2 [98, 104]x 3 }.

		C 1					C 2
	t 1 e	[255, 261]	t 2 f		t 1 f	[98, 104]	t 2 e
			x 2 and x 3 similar
	C res	t 1 e	[255, 261]	t 2 f	[98, 104]	t 3 e

When D ab contains only one element, the lower and upper bounds of I ij are identical.

The LAMDA algorithm is implemented in the software called P3S (Process Sensor Selection & Situation assessment) available in the DIagnosis and Supervisory COntrol (DISCO) team of the LAAS-CNRS.

ACKNOWLEDGEMENTS

We are very grateful to Aurélien Valade, Pascal Acco, Georges Soto-Romero, and the members of the Smart Sensing and SystemS Monitoring (S4M) team of the LAAS-CNRS for allowing us to use their data presented in Section 4 of this paper.


Keywords: Timed Discrete Event Systems, Chronicles, Random Projection, Euclidean Space

This paper is concerned with an innovative strategy that maps chronicles, that are timed discrete event models, to a k-dimensional Euclidean space via random projections. The proposed approach is a projection that takes into account both characteristics of events, namely event types, and temporal constraints of chronicles. This will lead to an unbounded convex polytope in the Euclidean space that contains all the possible instances of the corresponding chronicle. It allows to easily and efficiently compare chronicles. Such comparisons are useful in a fault diagnosis purpose to discriminate chronicles representing behaviors of dynamic processes. Examples and preliminary results are provided in this paper to introduce the proposed methodology.

Mapping Chronicles to a k-dimensional Euclidean Space via Random Projections Alexandre Sahuguède * , Soheib Fergani * , Euriell Le Corronc * and Marie-Véronique Le Lann *

I. INTRODUCTION

In the recent years, both academic and industrial communities have been interested in the study of the timed discrete event models called chronicles for a fault diagnosis purpose (see [START_REF] Subias | Diagnosis from chronicles: an overview of related challenges[END_REF] for a recent survey, [START_REF] Morin | Correlation of intrusion symptoms: An application of chronicles[END_REF], [START_REF] Pencolé | A chronicle-based diagnosability approach for discrete timed-event systems: Application to web-services[END_REF]). Indeed, chronicles are temporal patterns where events are partially ordered which are well-suited to capture dynamic processes with an event abstraction of the information of interest. Namely, to encapsulate the nominal behavior, only necessary data are captured in one or several chronicles whereas another set of chronicles encapsulates the faulty behaviors. Then, from on-line timed observations of the system, a pattern recognition of the chronicles expressing a faulty situation can be done efficiently and leads to detect that it is in that faulty situation [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF].

Recently, many studies have been achieved on chronicles, more particularly on discovering chronicles in data generated by a specific process. Although diagnosis is more efficient with chronicles, their design is not trivial. Indeed, for complex systems it is necessary to achieve it automatically. An interesting chronicle discovery algorithm that finds chronicles in a temporal sequence on a frequency criterion is proposed in [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF]. An extension to multiple temporal sequences is presented in [START_REF] Subias | Learning chronicles signing multiple scenario instances[END_REF]. The chronicle discovery process is discussed in healthcare applications in [START_REF] Huang | On mining clinical pathway patterns from medical behaviors[END_REF] and in [START_REF] Dauxais | Discriminant chronicles mining -application to care pathways analytics[END_REF] where clinical pathways are analyzed. However, these algorithms provide a large number of chronicles that the expert must then sort, analyze and compare. For instance, some learned chronicles are irrelevant when only few well defined chronicles are enough to obtain an efficient fault diagnosis. Similar chronicles are close representations of the same dynamic behavior of a complex process and should be reduced to improve the diagnosis. For this sake, solutions have to be provided.

In this paper, we propose to project chronicles in a kdimensional Euclidean space in order to compare and classify them easily and efficiently. In [START_REF] Mannila | Finding similar situations in sequences of events via random projections[END_REF], a method based on random projections is used to map timed event sequence to a point in this space for finding similar situations in large sequence of events. Here, we use this mathematical projection method on a chronicle. The proposed method allows to map chronicles to an unbounded polytope in an Euclidean space. In this space, it is easier and faster to compare values than a direct comparison of chronicles where both event and time must be taken into account.

The rest of the paper is organized as follows. Section II gives the definition of the required chronicle concepts with a first simple mapping of the chronicle's temporal constraints. Section III presents the projection of chronicles into polytopes in a k-dimensional Euclidean space. Section IV explains some properties of the obtained polytopes in the Euclidean space and how they relate to the reference chronicles. Section V analyzes the impact of the value of k. Section VI concludes this work and discusses interesting perspectives.

II. CHRONICLE CONCEPT

A. Background on chronicle

This section explains the chronicle concepts used in this work. Chronicles are a way to express temporal patterns of a specific process [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF]. Common temporal properties of chronicles are easily checked by means of graph theory. Chronicles are then represented as Temporal Constraint Networks [START_REF] Dechter | Temporal constraint networks[END_REF].

Definition 1 (Event): An event is defined by x = (e, t) with an event type e ∈ E, and a time instant t ∈ R.

Definition 2 (Temporal sequence): A temporal sequence is a time-ordered set of events denoted S = {x 1 , . . . , x n } with n a finite number of events, and t j < t j+1 , j = 1, . . . , n -1. The set of all event types occurring in S is called E S .

Example 1: The temporal sequence S = {x 1 , x 2 , x 3 , x 4 , x 5 } where x 1 = (a, 1), x 2 = (b, 4), x 3 = (b, 8), x 4 = (a, 16), x 5 = (b, 18), is graphically represented in Figure 1. This sequence points out the difference between event and event type that is several events can share the same event type. For instance, events x 1 and x 4 are different occurrences of event type a at different times. Definition 3 (Temporal constraint): A temporal constraint is a tuple τ ij = (x i , x j , t -, t + ), also noted τ ij = x i [t -, t + ]x j , where 0 < t -≤ t + . A temporal constraint τ ij = x i [t -, t + ]x j is said satisfied by a couple of events x i = (e i , t i ), x j = (e j , t j ) if and only if

(t j -t i ) ∈ [t -, t + ].
Definition 4 (Chronicle): A chronicle C is a pair (X , T ) where X = {x 1 , . . . , x n } is a set of partially ordered events with n a finite number of events, and T = {τ ij } 1≤i<j≤n is a set of temporal constraints on X . E C denotes the set of all event types of C. An n-length chronicle is a chronicle with n events.

A chronicle can be graphically represented by a directed graph where the nodes are the events of X and the transitions are the temporal constraints of T . In each temporal constraint τ ij , x i is the starting node and x j is the ending node.

Example 2: Figure 2 is the graphical representation of the 3-length chronicle C = (X , T ) where [START_REF] Morin | Correlation of intrusion symptoms: An application of chronicles[END_REF][START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchization[END_REF]x 3 } is illustrated Figure 3. This chronicle points out the partial order between events in the chronicle formalism. Definition 5 (Chronicle instance): Given a chronicle C = (X , T ), a chronicle instance is a set of events denoted I C such that their event types are those of X and their time occurrences satisfy all the temporal constraints T of C.

X = {x 1 = (a, t 1 ), x 2 = (b, t 2 ), x 3 = (c, t 3 )} and T = {τ 12 = x 1 [10, 20]x 2 , τ 13 = x 1 [25, 35]x 3 , τ 23 = x 2 [10, 20]x 3 }. An- other 3-length chronicle C 2 = (X 2 , T 2 ) where X 2 = {x 1 = (a, t 1 ), x 2 = (b, t 2 ), x 3 = (b, t 3 )} and T 2 = {τ 12 = x 1 [1, 3]x 2 , τ 13 = x 1
Example 3: Let us define a chronicle C = (X , T ) with X = {x 1 = (a, t 1 ), x 2 = (b, t 2 )} and T = {τ 12 = x 1 [START_REF] Subias | Diagnosis from chronicles: an overview of related challenges[END_REF][START_REF] Pencolé | A chronicle-based diagnosability approach for discrete timed-event systems: Application to web-services[END_REF]x 2 }. Given the temporal sequence S = {(a, 1), (b, 4), (b, 8)(a, 16), (b, 18)}, two instances of the chronicle C appear:

I 1 C = {x 1 , x 2 } = {(a, 1
), (b, 4)}, and

I 2 C = {x 4 , x 5 } = {(a, 16), (b, 18)}.
The number of chronicle instances I C of a consistent chronicle C is infinite. A consistent chronicle is a chronicle that have at least one instance [START_REF] Dechter | Temporal constraint networks[END_REF]. In a chronicle, events are temporally constrained to each other but they are not constrained themselves. The first event could occur anytime between -∞ and +∞.

B. Mapping chronicles with time

This subsection shows that an n-length chronicle can be represented by an unbounded convex polytope 1 , a geometrical volume in an n-dimension Euclidean space. Chronicle can be easily mapped to this geometrical volume by a simple orthogonal projection along each corresponding timeline. For instance, [START_REF] Guyet | Mining temporal patterns with quantitative intervals[END_REF] uses this orthogonal projection on simpler temporal patterns than chronicles where only time is of interest.

Given an n-length chronicle C = (X , T ), its temporal constraints T define a polytope P in R n . Each dimension of R n is associated with a time occurrence of the events of X . The polytope P is defined by the following formula:

∀τ ij ∈ T , P = {-t i + t j ≥ t - ij , t i -t j ≥ -t + ij }.
(1) P can be rewritten as the following linear constraint 2 :

At ≥ b (2)
with A ∈ R m×n , t ∈ R n , and b ∈ R m , where m is the number of inequalities and n the length of the chronicle C. Vector b contains the bounds of all the temporal constraints, and matrix A defines events on which those constraints take effect. Solutions of Equation ( 2) are the time occurrences of all the acceptable instances I C of C. As there is an infinite number of chronicle instances I C , the polytope P will always be unbounded [START_REF] Toth | Handbook of Discrete and Computational Geometry[END_REF].

Example 4: Let C = (X , T ) be the chronicle of Example 2 and Figure 2. This chronicle defines the polytope P shown in Figure 4 such that A ∈ R 6×3 , t ∈ R 3 and b ∈ R 6 with:

A =         -1 1 0 1 -1 0 -1 0 1 1 0 -1 0 -1 1 0 1 -1         and b =         10 -20 25 -35 10 -20         .
One solution of Equation ( 2), highlighted in Figure 4 by a black square, is:

t = 8 21 33
and corresponds to the projection of the instance I C = {(a, 8), (b, 21), (c, 33)}. This representation in R n has several limitations: the dimension of the Euclidean space is the length n of the chronicle, so comparisons between chronicles of different lengths is not easily done in this representation; the projection is done only on time occurrences of the events and the 1 In the rest of this paper, convex polytopes will be called polytopes. 2 Let us note that P can also be seen as a Difference Bound Matrix [START_REF] Dill | Timing assumptions and verification of finite-state concurrent systems[END_REF]. event types are not considered. We aims to try and tackle these limitations in the next section by adapting a technique proposed in [START_REF] Mannila | Finding similar situations in sequences of events via random projections[END_REF]. This technique, originally used with timed event sequences, is applied here to project a chronicle in an Euclidean space.

III. MAPPING CHRONICLES TO A k-DIMENSIONAL

EUCLIDEAN SPACE Chronicles can be easily mapped to a Euclidean space by a simple orthogonal projection along each corresponding timeline as seen in Section II-B. However, in such a simple projection, only temporal constraints are taken into account whereas event types are not used. Event types can bring more information when an objective of comparison and classification of projected chronicles is needed. In the work presented here, in addition to temporal constraints, event types are considered in the chronicle projection by means of methods coming from the pattern recognition domain, such as random projection [START_REF] Bingham | Random projection in dimensionality reduction: applications to image and text data[END_REF]. Let us start by the fingerprint of an event type e in the k-dimensional Euclidean space.

Definition 6 (Fingerprint of an event type): Let e be an event type of E. Let ρ(e) be a k-dimensional vector filled with k normally distributed random variables with mean 0 and variance 1. The random k-dimensional vector ρ(e) is the fingerprint of the event type e in the k-dimensional Euclidean space.

Since a chronicle has several events containing several event types, each of them will have its own fingerprint. Those fingerprints are compiled in the fingerprint matrix.

Definition 7 (Fingerprint matrix of a chronicle): Let C be a n-length chronicle, ρ ∈ R n×k is the matrix containing the fingerprints of all the event types e 1 , . . . , e n of the set X = {x 1 , . . . , x n } of C:

ρ = ρ(e 1 ) ρ(e 2 ) . . . ρ(e n ) . (3)
Thanks to the use of the chronicle fingerprint matrix in addition to the simple orthogonal projection, both event and time information contained in a chronicle instance I C can be considered in the projection proposed here. Indeed, time occurrences are easily taken into account by an orthogonal projection whereas event types are considered by means of their fingerprints. So, the random projection of a chronicle instance I C in the Euclidean space is the fingerprint matrix ρ of C weighted by its time occurrences t.

Definition 8 (Random projection of a chronicle instance): The random projection x ∈ R k of a chronicle instance I C to the k-dimensional Euclidean space is the product between the fingerprint matrix ρ ∈ R n×k of C and the time occurrences t ∈ R n of I C :

x = ρt. ( 4
)
Example 5: For the sake of simplicity in this example, we have set k to 3 even though it is clear that some problems occur when k is set too low as discussed in Section V. The random projection x of I C in this 3-dimension space is highlighted in Figure 5 by a black square. It is obtained by means of the linear projection seen in Equation ( 4): Since the fingerprint matrix of a chronicle is randomly generated, the random projection of instances of different chronicles must be done in the same k-dimensional Euclidean space. This means that fingerprint matrices of different chronicles should be computed coherently. Indeed, when chronicles share event types, the fingerprints are also shared. For instance, event types a and b are common to both chronicles C and C 2 of Example 2. When event types or use of event types are not seen in fingerprint matrices previously processed, a new fingerprint is generated. For instance, this is the case for the second use of the event type b in chronicle C 2 . Thus, the fingerprint matrix ρ 2 of C 2 is obtained in the same k-dimensional Euclidean space than C (k = 3):

Let I C = {(a, 8
ρ 2 = ρ(a) ρ(b 1 ) ρ(b 2 ) , =   -0.
. ρ(b) of C is the same than ρ(b 1 ) of C 2 whereas ρ(b 2 ) of C 2 is new.
By means of the fingerprint matrix ρ, x is a representation in the k-dimensional Euclidean space of an instance I C . Applying this fingerprint matrix directly on the polytope P of a chronicle C allows to project all its acceptable chronicle instances I C . This leads to a new polytope P in R k . However, the size k of the Euclidean space should be higher than the size n of the chronicle to obtain ρ left invertible. The solutions of the linear constraint defined by the polytope P are all the instances I C of the chronicle C projected in the Euclidean space.

Proposition 1: Let At ≥ b be the linear constraint defined by a chronicle C, and let x = ρt be the projection of an instance I C in the k-dimensional Euclidean space. There exists a matrix A ∈ R m×k , iff k ≥ n, such that:

A x ≥ b, (5)
Proof: As ρ is filled with random variables that are independent and identically distributed, each row and each column are linearly independent. The pseudo-inverse ρ + ∈ R k×n can be computed [START_REF] Penrose | A generalized inverse for matrices[END_REF]. When k ≥ n, ρ + is a left inverse and is given by:

ρ + = (ρ ρ) -1 ρ .
Equation (4) becomes:

ρ + x = t.

With Equation (2):

Aρ + x ≥ b.

Finally, with A = Aρ + , A x ≥ b.
Example 6: Let At ≥ b be the projection in R 3 of the 3length chronicle C seen in Example 4 (n = 3). Let x = ρt be the projection of an instance I C in the k-dimensional space with k = 3 detailed in Example 5. First, the pseudo-inverse ρ + ∈ R 3×3 is computed: Then, the matrix A ∈ R 6×3 is computed with A = Aρ + :

ρ + =   -1.7670 -
A =         1.
  ≥         10 -20 25 -35 10 -20         .
Remark 1: Let us remark that the chronicle projection depends on the partial order of the events x i in the set X of the chronicle. Thus, similar chronicles for which the only difference is the arbitrary choice of the numbering of the events may have different projections. For instance, the following chronicles have a different mapping whether their events are numbered as in Figure 6a or as in Figure 6b. Indeed, their fingerprint matrices will be identical but the difference in the temporal constraints will have a different result on the projection. More work needs to be done to take into account this phenomenon due to the partial order of the events.

t 1 a t 2 b t 3 b [1, 3] [2, 4]
(a) First configuration.

t 1 a t 3 b t 2 b [ 1, 3] [2, 4] (b) Second configuration.
Fig. 6: Two configurations of the numbering of the events of the same chronicle that can be mapped differently.

Remark 2: When mapping several chronicles of different lengths in the same k-dimensional Euclidean space, k should be greater than the length of the longest chronicle.

IV. ANALYSIS OF THE PROJECTED CHRONICLE

Properties of the random mapping of a chronicle in the k-dimensional Euclidean space are closely related to the studied chronicle model. In this section, some of these relations are explained.

A. Geometry of a projected chronicle

The projected chronicle is a polytope where all the edges are parallel and share the same direction vector. This direction vector v could be easily computed in the polytope P defined in Equation [START_REF] Morin | Correlation of intrusion symptoms: An application of chronicles[END_REF]. For all n ∈ N, consider the n-length chronicle C defined by At ≥ b. The kernel of the linear map A is the set of equations At = 0:

ker(A) = {t ∈ K n |At = 0}.
As all time occurrences t i of an event are constrained to a time occurrence t j of another event, At = 0 can be rewritten as follows:

∀i, j, -x i + x j = 0.

So, the rank of the kernel of a n-length chronicle C is always 1. For all n ∈ N, the direction vector v ∈ R n of a n-length chronicle C is unique and defined by:

v = 1 1 • • • 1 . (6)
In the k-dimensional Euclidean space, the direction vector v of the polytope P can be deduced from v by means of the fingerprint matrix ρ:

v = ρ v. (7)
Therefore, the direction vector v is a representation of the set of event types present in the chronicle C.

Another relation between temporal constraints of the chronicle and the projected chronicle exists. Let us define V as the volume of the section between the polytope P of a projected chronicle and the hyper-plan orthogonal to its direction vector v . The bounds of the temporal constraints define the vector b and is associated with V. With narrow temporal constraints, a smaller set of acceptable time occurrences leads to a smaller V. While with wide temporal constraints, much more time occurrences are acceptable for the instances and lead to a larger V. Furthermore, low values of lower and upper bounds of the temporal constraints generate a small offset for the edges, the projected chronicle is then close to the origin. High values for the bounds of the temporal constraints will have the opposite effect.

B. Intersection of two projected chronicles

A common way to compare chronicles is through their instances. For example, two chronicles are said equivalent when they share the exact same set of instances [START_REF] Dechter | Temporal constraint networks[END_REF]. In the Euclidean space, instances that are common to two chronicles means an intersection of two polytopes.

Let [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF][START_REF] Mannila | Finding similar situations in sequences of events via random projections[END_REF]x 4 } be two 2-length chronicles. Some instances of these chronicles are identical, e.g. I C1 = I C2 = {(a, 3), (b, 8)} is an instance of both C 1 and C 2 . In the Euclidean space, the random projections of I C1 and I C2 will be equal and both polytopes P 1 and P 2 will contain this projection. The intersection of these polytopes, shown in Figure 7, are all the equal projected instances of C 1 and C 2 .

C 1 = {X 1 , T 1 } with X 1 = {x 1 = (a, t 1 ), x 2 = (b, t 2 )}, T 1 = {τ 12 = x 1 [2, 6]x 2 }, and C 2 = {X 2 , T 2 } with X 2 = {x 3 = (a, t 3 ), x 4 = (b, t 4 )}, T 2 = {τ 34 = x 3
As expected, direction vectors v 1 and v 2 of the polytopes P 1 and P 2 are similar. Indeed, both C 1 and C 2 have the same set of events X 1 = X 2 with the same set of event types E C1 = E C2 . The value of V of these polytopes are similar as the temporal constraints τ 12 of C 1 and τ 34 of C 2 have the same width. P 2 is farther from the origin than P 1 since the lower bound of temporal constraint of C 2 is higher than C 1 .

V. IMPACT OF k The choice of the value of k is very important and must get a particular attention as described in this section. An approximation of the information contained in the event types is expected due to the use of random projection. In the Johnson-Lindenstrauss Theorem [START_REF] Johnson | Extensions of Lipschitz maps into a Hilbert space[END_REF], this approximation can be quantified by a value in the interval [0, 1]. A high value of , obtained by setting k to a high value, will reduce the approximation achieved. A value of k set too low leads to an increased approximation. This can be seen in the following example.

Let C 3 and C 4 be two 2-length chronicles with E C3 = {a, b} and E C4 = {c, d}. Let us project both chronicles in R k , with k = 2. This projection gives the two polytopes P 3 and P 4 shown in Figure 8. In this plot, it can be seen that P 3 and P 4 are intersecting. The intersecting part means that the projection of some instances I C3 of C 3 and some instances I C4 of C 4 are equal. However, C 3 and C 4 can not have common instances as they have different sets of event types. This intersection can happen because of the random projection approximation. A k set too low will increase the probability of this undesirable effect.

Moreover, with a statistical analysis, it can be shown that the value of k will have an impact on how far from the origin the chronicles will be in the Euclidean space. To do so, let us consider the squared distance from the origin to a vector obtained by mapping an instance of a n-length chronicle in the k-dimensional Euclidean space, that is:

d 2 = k j=1 x (j) 2 .
Equation (4) defines the vector x and x (j) 2 is the square of each element of x :

x (j) 2 = n i=1 ρ(e i , j)t i 2 . P 3 P 4 x 1 x 2
Fig. 8: An undesirable effect when k is set too low.

Since vector x is filled with normally distributed random variables with a mean value equal to 0 and variance 1, E ρ(e i , j) 2 = 1 and E (ρ(e i , j)) = 0. The expected value of x (j) is:

E x (j) 2 = n i=1 t 2 i .
So the expected value of d 2 is given by:

E(d 2 ) = k j=1 E x (j) 2 = k n i=1 t 2 i .
This means that a high value of k will have an important effect on the dispersion of chronicles mapped in the Euclidean space. In other words, an n-length chronicle will be farther from the origin with a high value of k than with a low value of k. For the variance, it is given by:

V AR d 2 = E d 4 -E d 2 2
= k E x (j) 4 -E x (j)

VI. CONCLUSION AND DISCUSSION

This paper provides a new method based on random projections to map chronicles in a k-dimensional Euclidean space. This approach leads to an unbounded polytope that contains all the possible instances of the corresponding chronicle. Some simple relations between properties of polytopes in the Euclidean space and the chronicle model have been established. The impact of the value of k has been discussed and it was shown that this parameter should be chosen carefully.

The new chronicle representation will improve the chronicle discovery algorithm results, especially for fault diagnosis objectives. Indeed, comparison and analysis of the chronicles obtained by such algorithms can be easily achieved when they are projected in an Euclidean space using directly distances between polytopes. Computations of distances between polytopes is commonly used in geo-spatial applications [START_REF] Atallah | Computing some distance functions between polygons[END_REF]. However, a bounded polytope is required for these distances. As seen in Section III, a chronicle will always be mapped to an unbounded polytope. A possible solution to try and tackle this problem is to define the distance between chronicles as the distance between the dual of their mapped polytopes. The dual of a polytope always exists and is bounded [START_REF] Coxeter | Regular polytopes[END_REF].

A well defined distance is crucial for defining a notion of similarity of chronicles. Similar chronicles are close representations of the same dynamic behavior of a process. Similarity is useful for fault diagnosis as the less similar chronicles are, the more accurate the diagnosis will be.

Fig. 1 :

 1 Fig. 1: A temporal sequence S.

Fig. 2 :

 2 Fig. 2: A 3-length chronicle C = (X , T ).

Fig. 3 :

 3 Fig. 3: Another 3-length chronicle C 2 = (X 2 , T 2 ).

3 Fig. 4 :

 34 Fig. 4: Polytope P of Example 4. Each axis corresponds to the timeline of each event. The projection of I C = {(a, 8), (b, 21), (c, 33)} is highlighted with a black square.

  ), (b, 21), (c, 33)} be the instance detailed in Example 4 and ρ = ρ(a) ρ(b) ρ(c) be the fingerprint matrix of C randomly obtained such that: ρ(a) = -0.1220 -1.0868 0.6843 , ρ(b) = -1.0752 0.0333 0.7448 , ρ(c) = 0.0336 -0.5266 0.4625 .

x 3 Fig. 5 :

 35 Fig. 5: Polytope P where the projection of I C = {(a, 8), (b, 21), (c, 33)} is highlighted with a black square.

P 1 P 2 I C1 = I C2 x 1 x 2 Fig. Polytopes P 1

 2121 Fig. Polytopes P 1 and P 2 in R k with k = 2. Projection of I C1 = I C2 is highlighted with a black square.

  The polytope P defined by A x ≥ b is shown in Figure5. The projection of the instance I C detailed in Example 5 is a solution of A x ≥ b. So:

			1501	2.6083	2.8863	
			-1.1501 -2.6083 -2.8863 5.3745 5.0594 7.5322 -5.3745 -5.0594 -7.5322 4.2244 2.4511 4.6459       	.
			-4.2244 -2.4511 -4.6459
		1.1501	2.6083	2.8863	
	       -1.1501 -2.6083 -2.8863 5.3745 5.0594 7.5322 -5.3745 -5.0594 -7.5322 4.2244 2.4511 4.6459	      	  -22.4457 -25.3749 36.3794
	-4.2244 -2.4511 -4.6459