Searching for similar semiqualitative temporal patterns in time-series databases

Searching for similar semiqualitative temporal patterns i n time-series database s J .A . Ortega, R .M . Gasca, M . Tor o Departamento de Lenguajes y Sistemas Informaticos . Universidad de Sevill a Avda . Reina Mercedes s/n . Sevilla (Spain ) {ortega,gasca,mtoro}@Isi .us .e s Abstrac t A way to obtain behaviour patterns of semiqualitative models of dynamic systems automatically is proposed in this paper . Th e temporal evolution of these models is stored into a database. This is a time series database . This database may be obtained a s is explained in [Ortega et al . 1999] or by means of sensor data . In any way, the database contains the values of state variable s and parameters . Searching for similar patterns in such database is essential, because it helps in predictions, hypothesis testing and, in general , in data mining and rule discovery . A language to carry out queries about the qualitative and temporal properties of this time-series database is also proposed . This language allows us to study all the states of a dynamic system : the stationary and the transient states . The language i s also intended to classify the different qualitative behaviours of our model . This classification may be carried out according t o a specific criterion or automatically by means of clustering algorithms. The semiqualitative behaviour of a system is expresse d by means of hierarchical rules obtained by means of machine learning algorithms . The methodology is applied to a logistics growth model with a delay . Keywords : Knowledge acquisition, Semiqualitative models, Qualitative behaviours pattern s 1 Introductio n In real systems studied in science and engineering, i t is difficult to find mathematical models that represen t them in an appropriate way . The modeling technique s should obviate certain aspects of the system . The simulation of these models helps us to study the evolution o f the real system . A way to carry out these simulation s is described in [Ortega et al . 1999] in depth . On the other hand, it is not always possible to obtai n a mathematical model of a system . Thus, it is necessar y to apply other techniques in order to carry out its study . A possibility may be placing data sensors in the rea l system . The analysis of these data allows to study th e system evolution . Knowledge about dynamic systems may be quantitative, qualitative, and semiqualitative . Whe n these models are studied all this knowledge shoul d be taken into account .  Different levels of nu - meric abstraction have been considered : purel y qualitative [Kuipers 1994], semiqualitative [Kay 1996] , [Berleant and Kuipers 1997] and [Ortega et al . 1998], and quantitative . Different approximations have been developed in th e literature when qualitative knowledge is taken int o account : distributions of probability, transformation o f non-linear to piecewise linear relationships, MonteCarl o method, fuzzy sets [Bonarini and Bontempi 1994] , causal relations [Bousson and Trave-Massuyes 1994] , and combination of all levels of qualitative and quantitative abstraction [Kay 1996] . In this paper, a technique to carry out the analysis of dynamic systems with qualitative and quantitative knowledge is proposed . The idea follows : th e quantitative behaviours of a real system are stored int o a database and techniques of Knowledge Discovery i n Databases (KDD) are applied to study the system . Th e way to obtain the behaviours does not matter : by mean s of the simulation of a model or by means of the data sensors . The term KDD [Adriaans and Zantinge 1996] is use d to refer to the overall process of discovering usefu l knowledge from data . The problem of knowledge ex - traction from databases involves many steps, ranging from data manipulation and retrieval to fundamenta l mathematical and statistical inference, search and reasoning . Although the problem of extracting knowledg e from data (or observations) is not new, automation i n the context of databases opens up many new unsolve d problems . KDD has evolved, and continues to evolve, from th e confluence of research in such fields as databases, ma - chine learning, pattern recognition, artificial intelligenc e and reasoning with uncertainty, knowledge acquisitio n for expert systems, data visualization, software discovery, information retrieval, and high-performance computing . KDD software systems incorporate theories, algorithms, and methods from all of these fields . The term data mining is used most by statisticians , database researchers and more recently by the busines s community . Data mining is a particular step in the KD D process . The additional steps in KDD process are dat a preparation, data selection, data cleaning, incorporatio n of appropriate prior knowledge and proper interpretation of the results of mining ensure the useful knowledg e is derived from the data [Rastogi99] . A detailed descriptions of these steps may be found in [Ortega 2000] . On the other hand, historical, temporal and spatia l databases have been profusely studied in the bibliography [Agrawal et al . 1995] . Specific applications includ e financial, marketing and production time series, such a s stock prices, sales numbers, and also scientific database s with time series of sensor data . For example, in weathe r data, geological, environmental, etc . In this paper, w e are interested in time-series databases corresponding t o the evolution of semiqualitative dynamic systems . Databases theories and tools provide the necessary infrastructure to store, access, and manipulate data . I n this paper, a new way to study dynamic systems tha t evolve in the time is proposed merging " data mining " , "time-series" and "databases engine" . The propose d perspective tries to discover the underlying model in th e database by means of a query/classification language . It is also possible to obtain the behaviour pattern s of these systems automatically by means of clusterin g techniques . Clustering is a discovery process in dat a mining . It groups a set of data in a away that maximizes the similarity within clusters and minimizes th e similarity between two different clusters . These discovered clusters can help to explain the features of the under - lying data distribution . The semiqualitative behaviou r of a system is expressed by means of hierarchical rule s obtained by means of machine learning algorithms . The paper is organized as follows : firstly, our approac h is explained and the concept of semiqualitative model i s defined . Secondly, the kind of qualitative knowledge w e are using in the language is introduced . Thirdly, the sea . Simulati o on of a mane ] Figure 1 : Our approac h query/classification language on the database is described . Next, the clustering algorithms is described in de - tail and, finally, the way to obtain the hierarchical rule s of the systems is explained . The proposed methodolog y is applied to a logistics growth model with a delay . 2 Our approac h There is enough literature that studies stationary state s of dynamic systems, however, the study of transien t states is also necessary . Stationary and transient state s of a semiqualitative dynamic system may be studie d with the proposed approach . It is shown in figure 1 . We begin with a time-series database . It ma y be obtained by means of semiqualitative simulation s [Ortega et al . 1999] or by means of data sensors . Thi s is a trajectory database . A trajectory is a time-serie an d it contains the values of the parameters and the value s of all state variables from their initial value until thei r final value . Therefore, every trajectory stores the value s of the transient and the stationary states of these variables of the system . Every trajectory is set of time-serie s of state variables . We propose a language to carry out queries about th e qualitative properties of the set of trajectories include d in the database. A labelled database is obtained whe n these trajectories are classified according to some criteria . It is also possible to classify the database by mean s of an automatically process . In such case, it is necessar y apply clustering techniques . Qualitative behaviours patterns of the system ma y be automatically obtained from this database b y Labelle d Database 112 applying rule discovery based on genetic algorithm s [Aguilar et al . 1998] . The steps of our approach are de - tailed in the following sections . 3 Semiqualitative model s In this paper, we focus on those dynamic systems wher e there may be qualitative knowledge in their parameters , initial conditions and/or vector field . They constitut e the semiqualitative differential equations of the system . A semiqualitative model S is represented by means o f el> (x, x, q, t ),  x ( t o) = x o,  1 o( q , x o)  ( 1 ) being x E 1R' the state variables, q the parameters, t th e time, ± the derivative of the state variables with respec t to the time, constraints among x, x, q, t, and (Po constraints with the initial conditions . These constraint s may be composed of qualitative knowledge, arithmeti c and relational operators, intervals, predefined functions , (In, exp, sen, . . .) and numbers . 4 Qualitative knowledg e Qualitative knowledge about a model may be composed of qualitative operators, qualitative labels, envelope functions and qualitative continuous function s [Ortega et al . 1999] . In this paper, we are intereste d in applying this knowledge to carry out queries wit h the language . Therefore, the representation and trans - formation techniques of this qualitative knowledge ar e described bellow . The representation of the qualitative knowledge is carried out by means of operators which have associate d real intervals . It simplifies the integration of qualitative and quantitative knowledge, and it also facilitate s the incorporation of expert knowledge in the definitio n of the range of qualitative variables and parameter s [Gasca 1998] . Every qualitative operator op is defined by means o f an interval l o , which is supplied by the experts . 4 .1 Unary qualitative operator s Every magnitude of the problem with qualitative know - ledge has its own unary operators defined . Let U~ be the unary operators for a variable x, i . e . , U,, = {VN N , MN X ,LN X ,APO x ,LP X ,MP X ,VP X } . The y denote for x its qualitative labels : very negative, moderately negative, slightly negative, approximately zero, slightly positive, moderately positive, and very positiv e respectively . The transformation rule for a unary operator i s opu(e)  e — a = 0  (2 ) a E l w being a a new generated variable, and I, . the interval associated with operator op t , , which is establishe d in accordance to [Trave-Massuyes et al . 1997] . 4 .2 Binary qualitative operator s Let e l , e2 be two arithmetic expressions . A binary qualitative operator b(e l , e 2 ) denotes the qualitative orde r relationship between e l and e 2 . These operators ar e classified int o • Operators related to the difference >, _, < . Th e following transformation rules are applie d Table 1 : Transformation rule s • Operators related to the quotient <<, — <, —, ti, » , V o, Ne, . . . . The applied transformation rule i s e l —e 2 *a= 0 aEl b being a a new variable and lb the interval associated t o op b in accordance to [Trave-Massuyes et al . 1997] . 5 Query/classification languag e We propose a language to carry out queries and t o classify with labels a time-series database T obtaine d with the quantitative simulations of a family of model s [Ortega et al . 1999] . Therefore, this language allows u s to classify the behaviour patterns of the system . 5 .1 Abstract Syntax of the languag e Let T be the time-series database and let r be ever y trajectory in this database . The abstract syntax of th e proposed language is A query Q on the database T ma y - e2 = 0 e l —e 2 —a= 0 a E [—oo, 0 ] el — e2 — a = 0 a E [0,00 ] e l op b (e l , e 2 ) (3 ) 113 Q : VrEC• P 3rECeP P : I P b P A P P V P P P b : P d O T e b (O L ([F], {L})) P d : E Q C L Or always F sometime F always F before F always F until F sometime F be f ore F sometime F until F always F after F O L : ~ ~ increas e decreas e periodi c maxi m minimu m constan t lengt h F : F b F&F F b : ~ ~ e b ee l u (e ) b ( e i, e 2 ) 1  F I F F = F !F Table 2 : Queries abstract synta x be a quantifier V, 3 applied to T . This query try to determine if all the trajectories (V) or if there is at leas t one (3) verify the property P . This property may b e formulated by means of the composition of other properties using the Boolean operators A, V, --, and its resul t is the application of these operators among the partia l properties . A basic property P b may be : a predefined propert y P d , a P tolean expression e b applied to a list operato r OL([F], ZL}) applied to a list L of points or interval s which verify the formula F, or a temporal operator O T . A list operator O L ([F], {L}) returns the list L o f points or intervals of the trajectory which verify the for - 'ula F . A temporal operator O T is used to describe proper - ties in a concrete time of a trajectory, or to compar e among different times of a trajectory, or to establis h a sequence of behaviours of a trajectory . We hav e chosen a set of temporal operators from the temporal logic . The chosen had been those whose definitio n would be obtained by means of a final recursive definition [Lipeck and Saake 1987] . A defined property P d is one whose formulation is au - ,ratic . They are queries commonly used in dynamica l systems . There are two predefined : EQ, which is verified when the trajectory ends up in a stable equilibrium ; and CL that it is verified when it ends up in a limit cycle . A formula F may be composed of other formulas combined by means of Boolean operators &,I, ! and its result is the application of these operators among the partia l formulas . A basic formula F b may be : a Boolean expression e b , or if a numeric expression e belongs to an interval I, o r a unary u or binary b qualitative operator . Classificatio n A classification rule is formulated as a set of basi c queries with labels and possibly other expressions . A classification problem is proposed in accordance to th e following abstract syntax : Table 3 : Classification abstract synta x 5 .2 Semantics of the languag e The semantics of every proposed statement is translate d into a query of the database. A query V r E C• P i s true when all trajectories r E C verifies property P . T o prove that an 3 statement is true, it is necessary to fin d at least one trajectory r E Tthat verifies the propert y P . A property P which is formulated bmeans of th e application of Boolean operators A, \  is true whe n the result of the application of these  erators amon g the partial properties is true . The result of the evaluation of a temporal operato r OT depends on its semantics . For example, always F returns a true value if all the values of r verify F . I f this operator is sometime F returns a true value whe n at least a value of r verifies F . The semantic of al l these temporal operators are described in accordance t o [Lipeck and Saake 1987] . Let eb(OL([F], {L})) be a basic property . This property is true if the Boolean expression applied to th e list operator O L returns a true value . The operator O L returns the intervals or points of a trajectory which verify a formula F . In order to evaluate a formula F, it is necessary t o substitute its variables by their values . These values ar e obtained from T . Let [r, P A ] A, cAr be a classification rule . A tr" . - jectory r E T is classified wit ii the label A if it verifie s property P A . It is also included into the database fo r this trajectory the result of the evaluation of e A r . Thi s [r E C, automatic ] [r E C, P A ]  A,e n r, ... [r E C,P B ]  B , e n2, . . . C : 11 4  Q i VrEC•P, 'rue , 3rEC•P i  f(ll ., , &V y process is repeated with every classification rule . Whe n the classification rule is [r E C, automatic], it is nec i ry to apply clustering techniques in order to classify th e database automatically . 5 .3 Implementation detail s The semantics of all queries and classification rules i s translated into an algorithm . The execution of this algorithm yic ,is the answers to the queries and labelle d the databa e, and it is only necessary go once throug h the dat, This algorithm is automatically generated . Let Q = { Q 1 , . . ., Q l } be a set of m queries on a subse t C C T . Let b = {b i ,. . ., b ., n } be them answers to Q . Th e template algorithm to obtain b follows : 1. QueryClassifyQ(Q, C) return b 2.  b := e 3.  for i := 1 to i < Card(C ) 4.  t :=t f 5.  y :=y o 6.  while —,(t = to ) 7.  t :=t — A t being p = ( y 1 , . . ., y,) auxiliary variables .  Ever y Boolean variable b accumulates the result of the qu o on the database and Boolean variable y accumulat c ., t res  tf the qu  on the trajectory . The initial vu . . of b (line 2) is the neutral element of the operation tha t it accumulates . The initial value for y (line 5) is c culated by applying the operation to the last instani , the trajectory . In order to modify these variables (line s 8 and 11) the operations f t and T y to the y variable s and the operation T b to the b are applied . The functio n f evaluated at time t denoted by f t . The algorith m proceeds backwards in time due to the transforrriatio . . of the temporal operators [Ortega 2000] . The execution of this algorithm returns  Boole : — value true or false as result of every query . The cc •tplexitv of the algorithm is lineal, sine : e ach trajector : . read once for all the queries . This algorithm can b e ways obtained . The algorithm is instantiat  'ependin g on the language sentences as follows . 5 .3 .1 Querie s Table 4 collects the generated code for a query . where every fiery Qi generates at least an auxiliary Table 4 : Qu . .  . formatio n variable y to contain the evaluation of P on the trajectory . 5 .3.2 Propertie s 5 .3 .3 List operator s Let e b (O L ([F], {L})) be a Boolean expression applie d to a list operator . The generated code contains a lis t 1 to store the intervals of the trajectory that verify th e formula F and a flag a to indicate when the formula F is activated . A record is generated for every interval o f each trajectory r that verifies consecutively the form ' F . This record contains the initial and final tin], of th e interval :uid the result of the -aluation in e time t of the expressions that appear in L, and it is (lentil ec l as L t . The operator OL is applied on the obtai ; ; a d 1 . The Boolean expression e b is appli""-' • he result o f this applica :' in . The gen rated code is in table 6 . List operator P t ,(O L ([1 t line cod e 5  l :_ { } 8  if F t then l := L t U i 10  y := e b (O L (1) ) Table 6 : List operator transformatio n where F t denotes the evaluation of formula ' tant t . 8 . 9 . 10 . 11 . 12 . Table 5 collects the generated code for a property . Property P i line cod e P 1 A P 2 10 y := yp 1 A yp 2 P 1 VP 2 10 y :=yp 1 Vyp 2 -,P 10 y :_ —,y p Table 5 : Properties transformatio n y  ft( y , C(i) t ) being y an auxiliary variable to store the rest of P i , end while and yp to store the result of the elemental aper - y :=T y (y) ties, and y is obtained by applying the A, V, rato r b := T b (b, y) among the yp variables . end for 5 .3 .4 Temporary operators  5 .3 .6 Formula s The table 7 collects the generated code for tempora l operators . Linea Temporary operator O T codigo generad o 5 8 always F y :=F t y :=F t A y 5 8 sometimes F y :=F t y :=F t V y 5 8 always F before G y :=F t VG t y :=F t V ( G t Ay ) 5 8 always F until G ,y :_( F tAGt) VF t y := (Ft A Gt) V ( F t A y ) 5 8 sometime F before G y := ( F t A - , Gt) V (- , Gt ) y :_ ( F t A -C t) V ( ,G t A y) Table 7 : Temporary operators transformatio n This algorithm has been obtained in accordanc e to the definition of temporal operators provided i n [Lipeck and Saake 1987] . 5 .3 .5 Predefined propertie s Predefined properties are queries whose formulation i s automatic . They are queries commonly used on dynamic systems . A trajectory ends in a stable equilibrium EQ whe n the states variables do not oscillates in the end of the si - mulation . Therefore the derivative of the state variables may be approximately equals to zero . EQ = always (t E RF  0)  (4 ) where R F denotes the final range of the simulation, ± i s the derivative of the state variable x and is a binar y qualitative operator . The generated algorithm is th e corresponding to this temporal operator always . A trajectory ends in a limit cycle CL when it oscillate s in the final time of the simulation . CL - periodic([t E RF A± = 0 A > 0], {x})  (5 ) This predicate obtains a list with the relative maxim a (or minima) in the final range of the trajectory . A limi t cycle appears when these maxima are periodically repeated . Formulas study specific features of a concrete instant i n a trajectory . A formula F t applied to r is verified whe n F is satisfied in the instant t . Transformation instructions depend on F, and they are in table 8 . In orde r Formula F line cod e F t A G t 8 Eval (F t ) A Eval (G t ) F t V G t 8 Eval(F t ) V Eval(G t ) F t z G t 8 Eval(F t )  Eval(G t ) -Ft 8 -Eval(F t ) F t 8 Eval(F t ) Table 8 : Formulas transformatio n to evaluate a formula F, it is necessary to substitut e its variables for their values. These values are obtaine d from T . 6 Behaviour pattern s A behaviour pattern is each one of the possible behaviours that may appears in a dynamic system fro m its initial state until its final state . A qualitative mode l has a group of qualitative behaviours . Each one of the m is a behaviour pattern . In figure 2 there are three different quantitative trajectories but they follow the sam e qualitative pattern : begins with a value next to zero , then it goes growing until it reaches a maximum an d next it oscillates until arriving to a positive value wher e it remains stable . ------------ - time ' Figure 2 : Similar qualitative behaviour s It is possible, that there are different ways to reach a stationary state . If the study is only limited to the stationary, it is not possible to recognize these difference s and we would conclude that all the trajectories hav e the same behaviour . It is therefore necessary to furthe r out the study with the transient state to discover thes e behaviours . In order to obtain the patterns, the database must b e labelled . Once the database is labelled, the technique s 11 6 to obtain the behaviour patterns are applied . 7 Labelling of the databas e The labelling of the database assigns one or more label s to every trajectory . These labels may be assigned by a certain criterion provided by the user or by means of a n automatic process . The data normalization is necessar y to classify automatically the database . This normaliza - tion helps us to assign the labels to the trajectories b y means of clustering algorithms . 7 .1 Labelling with specific criteri a Let T be the database for the following classificatio n rules : C = {C 1 , C 2 , C 3i . . .}, being : C 1 - [r E T, P L ,] . Li, e 1 C 2 = [rET,P L2 ]=L 2 C3 = [r E T, P L3]  L 3, e 31, e32 8 Normalizatio n Two trajectories with a similar behaviour may have a distance next to 0 . In figure 2, the three trajectories fo - llow the same qualitative pattern, but if we apply amon g them a distance like the Euclidean, it is concluded tha t they follow different behaviours . It is necessary to nor - malize these data to obtain the same pattern for simila r qualitative behaviours . Therefore, these data will b e scaled, translated and weighted . 8 .1 Scalin g Let r be a trajectory, and let be the value s stored in the database of the state variables of r . Thes e values will be scaled to the interval [0,1]. For every va - riable x E r is necessary to obtain its maximum an d minimum values xmax, x,,, ,in respectively . The valu e x v = x,nax — x,nin is the range of values of x . Let x t b e the value of x at time t . Let x' t be the escalated value . It is obtained by means of the expressio n ( 6 ) x t — x mi n x t = (7 ) x, . being r the trajectories of T, P E , the i-th predicate o f the classification rule C i , L i labels and e expressions . A label L is assigned to trajectory r when it verifie s the property P . In order to apply the behaviour patter n algorithms, it is necessary that all trajectories have a t least one label, otherwise, an empty label is assigned . 7 .2 Automatic labellin g The automatic labelling classifies the database in accordance to the different behaviours of the dynamic system . It is necessary to supply the similarity degree to carr y out this classification . It is a number in the interval [0,1 ] and its functionality is explained bellow . Let T be the trajectories database . The idea is to fin d the different patterns that appear in T. Every trajector y is classified with a label L in accordance to its behaviou r pattern . Each trajectory r E T contains a temporal sequenc e for every state variable, therefore, a trajectory is a vector of time sequences . It is necessary to apply a clustering algorithm on these time series of the database t o discover the behaviours . These sequences may be previously normalized . Any clustering algorithm needs t o define a metric among the elements to be classified . Thi s metric is provided by the similarity degree . 8 .2 Translatio n The trajectories r2, . . ., r N are translated to the first trajectory r 1 . Let s be a trajectory s E {r 2 , . . ., r N } . Fo r each trajectory s is defined T S = s 2— s 1 (figure 3) . Hm s Figure 3 : Translation and periodicit y The translation of s is obtained by solving the following system : t 1 = a * s 1 + b  ( g ) t2 =a*s2+ b being a the homotecy between both trajectories and b the translation . Solving this system, it is obtained that 117 the values of a, b are : t2 — tl  T l  tls2 — t2s1  t1s2 — t2s 1 S 2 — 81  Ts  8 2 — s1  Ts ( 9 ) By substituting (9) in (8) and operating, we obtain th e translation t 1 s 2 +t2S1 —t 1 T s t s  (10 ) T 1 8 .3 Weightin g Once every trajectory has been translated, it is no t possible to compare them directly . Therefore, it is necessary to interpolate these values . Let r be a fixed trajectory and let s be the one tha t will be interpolated . Let is be the value obtained by th e translation (10) . Let t i , t j be where t i = to + kzt an d t j = t i + At where k is a natural number that verifie s that is E [t i , t j ] . Let y i , y j be the translated value s stored in the database for t i ,tj respectively . We ar e interested in calculating the value t s . There are severa l ways to calculate it: linear approximations, 0-splins, . . . In this paper, the value ys is calculated by means of a linear approximation as follows : ys = yi + yJyi (ts — t i)  ( 11 ) being At = t j — t i . This is the value of trajectory s that may be compared with the corresponding on th e trajectory r . 9 Distance among trajectorie s Let T be a database with N normalized trajectories . I t is calculated a distance matrix Damong these trajectories . It is a triangular matrix with its main diagona l equal to zero . This matrix is necessary for the clusterin g algorithm . Let 6(r i ,r j ) be the distance between two trajectories . A possibility consists of calculating 6 by mean s of the Euclidean distance . However, we know that trajectories are time series, therefore is better to calculate 6 by means of the Fourier coefficient s There are several reasons to elect the Fourier coefficient s [Agrawal et al . 1995] : the distance is preserved, the y are easy to calculate, they concentrate the signal energy in a few coefficients and there is an algorithm Fas t Fourier Transform (FFT) that calculate this coefficient s efficiently . Therefore, Fourier transform is an appropriate way to calculate the distance in time series . In this i per the distance 6 between two trajectories r i , r j is defined by means of : pol a oi —a oj 1 z + plIali — a ijI 2 + pz nazi — a zj 1 z + P3 f x i (t) — x j (t)1 2 dt + P4 1 lx i (t) — x' j (t)l 2 dt + P5 J ( x z ' (t ) — x ~ ( t )I 2d t being x the state variables, po, pi, . . .,P5 weights, a u „ th e u-th Fourier coefficient, x i , x j normalized values store d in the database for the trajectories i, j respectively, an d x' i , x' j and x' i ', x l first and second derivative of x i , x j values respectively . This distance (12) is defined as an expression depending on: Fourier coefficients, weights, variable magnitude and first and second variable derivatives . The jr . . tification is as follows : • In accordance to [Agrawal et al . 1995] only with a few Fourier coefficients the features of the original trajectory are obtained . Therefore, the ter m p 3 f Ix, — x j 1 2 dx provides the same information a s the three first Fourier coefficients . • Besides the magnitude, there are other features tha t are interesting to take into account from a quali t tive perspective : the shape (first derivative) any . the concavity (second derivative) . • Weights are introduced to take precedence over th e magnitudes, the shapes or the concavity of the trajectories . We had not study the relation and relevance among these weiol :s and the distance . A l the tests have been carried out with a weight o f A distance matrix D is obtained using the proposed definition of 6 . The completeness of the algorithm to obtai n D is exponential . 10 Clustering and decision rule s Clustering is a discovery process in data mining . I t groups a set of data in a away that maximizes th e similarity within clusters and minimizes the similarit y between two different clusters . These discovered clu s ters can help to explain the features of the underlyin g data distribution . In recent years, a number of clustering algorithms for databases have been proposed : DBScan [Ester et al . 1996], CURE [Guha et al . 1998] . Chameleon [Karypis et al . 1999], . . . A scalable clustering algorithm is proposed in this pa - per . Its execution puts together a trajectory and a label . This label determines the behaviour pattern of the trajectory . 6a (ri, r j (12 ) 118 1. Clustering(D, M) return M E 2.  dmean = Mean(D ) 3.  G := Graph(D, dmean ) 4.  M E := Clusters(G, a ) being a the similarity degree previously commented . This algorithm begins obtaining the distance matrix D among trajectories . Next, it calculates the mean of D . This mean distance dmean is calculated to know th e magnitude of the distance . A weighted graph G is obtained with the k-neighbour s of every trajectory . The vertex of G are the trajectories . The arcs are weighted with the relationship between dmeans and the distance between two trajectories . Figure 4 shows examples of graphs building : original (a ) and with 1- (b), 2- (c) and 3-(d) neighbours . 11 Application to a logistic s growth model with a dela y It is very common to find growth processes in which a n initial phase of exponential growth is followed by another phase of approaching to a saturation value asymptotically (figure 5) . These are given the following generi c names : logistic, sigmoidal, and s-shaped processes . exponential  avymtotic behavio r growt h Figure 5: Logistics growth curv e a) b ) • ' •• • '' L . c) d) Figure 4 : Graph with k-neighbour s It is applied an algorithm to the k-neighbours graph . The algorithm breaks those arcs between neighbour s vertices whose weight w is less tha n a * d mea n 10 0 being a the similarity degree . The connected graphs represent every different behaviour pattern of the dynamic system . All the trajectories of every connected graph are classified with the sam e lake This is carried out by the function Clusters(G, a) . Once the database has been labelled, the pattern behaviour of the system is represented by means of a se t of hierarchical decision rules . These rules are obtaine d using the program COGITO [Aguilar et al . 1998] to th e bidimensional dynamic array described in the section 7 of this paper . This growth is exhibited by systems for which exponential expansion is truncated by the limitation of th e resources required for this growth . This behaviour i s due to a positive feedback that is dominant in the initial phase, and a negative feedback that is dominant i n the final phase . In literature, these models have been profusely studied . They abound both in natural processes, and i n social and socio-technical systems . They appear in th e evolution of bacteria, in mineral extraction, in worl d population growth, and in economic development . Lear - ning curves also show this type of behaviour . The same thing happens with some diffusion phenomena within a given population, such as epidemics o r rumors . Other examples of this behaviour are a population that grows in a habitat with limited resources , a technological innovation that is being introduced, o r a new product that is being put on the market . In al l these cases, their common behaviours are shown in figure 6 . There is a bimodal behaviour pattern attractor : A stands for normal growth, and 0 for decay . It ca n be observed how it combines exponential with asymptotic growth . This phenomenon was first modeled b y the Belgian sociologist P . F . Verhulst in relation wit h human population growth . Nowadays, it has a wide variety of applications, and some of them have just bee n mentioned . Let S be the qualitative model . If we add a delay i n the feedback paths of S, then its differential equation s are x=x(nr—m) , y = delay,(x), x > 0, r = h i (y) , h l  {(—oo, —oo), +, (do, 0), +, (0, 1) , +, (dr, eo), —, (1, 0), —(+oo, —oo) } being n the increasing factor, m the decreasing fac - w < 11 9