An extended chronicle discovery approach to find temporal patterns between sequences
Abstract
Sequences of events describing the behavior and actions of users or systems can be collected in several domains. An episode is a collection of events that occurs relatively close to each other in a given partial order. Also, chronicles are a special type of temporal patterns, where temporal orders of events are quantified with numerical bounds and reflect the temporal evolution of the system over the time. In this paper, the problem of finding rules for describing or predicting the behavior of the sequences with the intention of characterizing some interesting tasks is considered. Obtaining these patterns is the main objective of this work, where an automatic method to learn relevant and discriminating chronicles is proposed. The method extends existing algorithms that have been proposed to find frequent episodes/chronicles in a single event sequence to the case of multiple sequences.
Full text
An extended chronicle discovery approach to find temporal patterns between sequences Alvarez, M.A.a; Subias, A.b,c; Trav´ e-Massuy` es, L.b,c; Gonzalez-Abril, L.d; Ortega, J.A.a aDepartment of Computer Science, University of Seville, 41500 Seville, Spain bCNRS, LAAS, 7, avenue du Colonel Roche, F-31400 Toulouse, France cUniv de Toulouse, INSA, LAAS, F-31400 Toulouse, France dDepartment of Applied Economics I, University of Seville, 41500 Seville, Spain maalv[email protected], {subias, louise}@laas.fr, {luisgon, jortega}@us.es Abstract Sequences of events describing the behavior and actions of users or systems can be collected in several domains. An episode is a collection of events that occurs relatively close to each other in a given partial order. Also, chronicles are a special type of temporal patterns, where temporal orders of events are quantified with numerical bounds and reflect the temporal evolution of the system over the time. In this paper, the problem of finding rules for describing or predicting the behavior of the sequences with the intention of characterizing some interesting tasks is considered. Obtaining these patterns is the main objective of this work, where an automatic method to learn relevant and discriminating chronicles is proposed. The method extends existing algorithms that have been proposed to find frequent episodes/chronicles in a single event sequence to the case of multiple sequences. 1 Introduction In some application areas of knowledge like data mining or machine learning, the data to be analyzed is made up of a sequence of events. So, the data can be viewed as a sequence of events, where each event has an associated time of occurrence. An example of an event sequence is shown in Figure 1. Here A to F are events and they are represented on a time line. In the last years, there have been many authors interest in knowledge discovery from sequential data [Dousson et al., 2008; Le Guillou et al., 2008; Pencol´ e and Subias, 2009; Bertrand et al., 2009; Saddem et al., 2010; Bauer et al., 2011] because the technology have been applied in a lot of areas. Analysing human activities is required in many domains, like ergonomics, safety diagnosis, process design, and more generally for understanding cognitive and social processes. In this article, we propose an approach to support the process of activity analysis with the help of interactive discovery of temporal patterns named chronicles. The first task for describing the behavior of systems from sequences of events is to find frequent episodes, i.e., collections of events occurring frequently together. In the Figure 1, the event E is followed by F several times and it is an episode, and ordered set of events. From the same sequence in the figure, the observation that whenever A and B occur, in either order, C occurs soon can be done. Taking into account the last definition, a set of maximum episode rules can be obtained from a event sequence. The main motivation of this paper is to find a minimal set of rules from some event sequences. This set must contain the maximum episode rules that have been found in all sequences, i.e. the set is an intersection of the set of each one. In this paper the following problem is considered. Given some input sequences of events, find all episodes that occur frequently in all sequences. To achieve this goal some extended techniques from [Mannila et al., 1997],[Mannila and Ronkainen, 1997]and [Cram et al., 2011]are proposed. The rest of this paper is organized as follows: first, the main problem and the motivation of this paper are presented in Section 2. Later, the definition of the problem is presented in Section 3 to establish the notation of the rest of the paper. In Section 4, the existing algorithms to discover chronicles in a sequence are explained. Section 5 contains the Mannila’s approach to get chronicles and Section 6 presents a methodology to discover chronicles that must be exist in all event sequences. Section 7 reports the obtained results of applying the methodology. The paper is finally concluded with a summary of the most important points in Section 8. 2 Problem and motivation This work aims to reach an estimation of the state of a network from chronicle recognition. The chronicles describe behaviors or situations to be recognized from temporal patterns. The main difficulty of this approach focuses on how to develop chronicles. One of the possible solutions can be obtained from learning, so in this paper, one of the principal chronicle learning approaches existing in the literature is studied. From this approach, a solution to the problem of the adaptation of the communication protocols is proposed. These problems can be network congestions or packet loss. These patterns are based on generated signals from routers. 3 Definitions An input as a sequence of events is considered where each event has a tag and a time stamp represented by an integer. Given a set Eof event types, an event eis a pair (A, t)where $ FWDVGH;,9-RUQDGDVGH$5&$ 6LVWHPDV&XDOLWDWLYRV\VXV$SOLFDFLRQHVHQ ' LDJQRVLV5REyWLFDH,QWHOLJHQFLD$PELHQWDO ) -5XL]1$JHOO-$2UWHJD(GV F
Figure 1: A sequence of events A∈Eis an event type and tis the time of the event. e=(A, t |A∈E) A sequence sis a list of events between an interval of time stamps s(Ts,T e)=((A1,t 1),(A2,t 2),...,(An,t n))(1) where Ai∈E,∀i=1,2,...,n ti≤ti+1,∀i=1,2,...,n Ts≤ti<T e,∀i=1,2,...,n A event sequence s(29,68) is represented in Figure 1. s(29,68) =((E,31),(D,32),(F,33),(A, 35),(B,37), (C, 38),...,(D,67)) A window ωon a sequence is defined as a set of events between an interval of time stamps ω(ts,t e)={(A, t)∈s|ts≤t<t e}(2) where ts<T eand te>T s. Also, two windows ωaand ωbare similar if |ωa|=|ωa| and |(Ai,t i)|=|(Aj,t j)|where Ai=Aj,∀Ai∈ωa,∀Aj∈ ωb. A width can be defined as the difference between two time stamps. In Figure 1, the width of the sequence is the difference between the start time stamp and the end time stamp: width(s)=Te−Ts= 68 −29 = 39 Also, the width of a window ωcan be defined as width(ω)=te−ts. Now, from 1 and 2, the set of all windows with the same width in a sequence is represented below: W(s, win)={ω(ts,t e)∈s|width(ω)=win} For example, in Figure 1, the number of windows with the width equals to 5 is 43, |W(s, 5)|= 43, and (∅,25,30) and (((D,67)),25,30) are the first and the last windows of W(s, 5). Finally, an episode αis a set of nodes with a partial order and a relation between them: α=(V,≤,g:V→E) Also, an episode βis a subepisode of αif the following conditions are fullfiled: β=(V!,≤!,g!:V!→E)!α=(V,≤,g:V→E)(3) ∃f:V!→V|g!(ν)=g(f(ν)),∀ν∈V! ν≤!%,∀ν,%∈V! f(ν)≤f(%),∀ν,%∈V! In the other hand, an episode αis a superepisode of β, if and only if β!α. From 3, an episode rule is defined as β⇒αif β!α. In Figure 2, α,βand γare episodes and γis a subepisode of β. Figure 2: Three different episodes 4 State of the art on discovering chronicles [Dousson and Ghallab, 1994]defines chronicle as a temporal pattern intended to represent a pattern of evolution of a system, it is mainly composed of a set of events and temporal constraints between their dates of occurrences. A chronicle Cis presented as C=S, T where Srepresents all the events and Trepresents all the constraints. In Figure 3, the e3event occurs between 3and 6time units after the e1event or between 3and 9time units after the e2 event. This chronicle is represented below: C={S, T} S={e1,e 2,e 3} T={t1<t 3∧t2<t 3|3≤t3−t1≤6∧3≤t3−t2≤9} Some considerations are needed to taking into account to recognize a chronicle: iA set of dated events: this set is the input of the recognition system. ii A set of constraints: these constraints are time intervals between the dates of occurrences of events. iii A set of formulas or a general scheme: it is the chronic patterns without considering timing constraints between their dates of occurrence. Recognizing is to explain the input events (i) using the temporal patterns (iii) while respecting the constraints of the field (ii). So, a chronicle is a set of constraints on events with their dates of occurrence, where each characteristic of a chronicle situation is based on the observed consequences. In our context, an abnormal communication system is characterized by a set of chronicles, where each chronicle describes the situation of interest according to the evolution of the system. For example, a situation of data loss has many causes, such as network congestion, loss of connectivity or changing access interface. Each of these situations or states must be represented by at least one chronicle. 0 $ÈOYDUH]HWDO$QH[WHQGHGFKURQLFOHGLVFRYHU\DSSURDFKWRILQGWHPSRUDOSDWWHUQVEHWZHHQ 6HTXHQFHV
1 2 3 [3, 6] [3, 9] Figure 3: A chronicle with three events 5 Mannila’s approach Mannila’s approach finds all episodes that occur frequently in a event sequence. It is based on the idea of first finding small frequent episodes and then progressively looking for larger frequent episodes. Apart from the definitions in Section 3, Mannila defines the frequency fr of an episode as the fraction of windows in which the episode occurs. That is, given an event sequence s and a window width win, the frequency of an episode αin s is fr(α, s, win)=|w∈W(s, win)|αoccurs in w| |W(s, win)| Furthermore, αis frequent if fr(α, s, win)≥min fr where min fr is a frequency threshold. The main objective is to discover all frequent episodes from a set of episodes. Mannila denotes the collection of frequent episodes with respect to s,win and min fr by F(s, win, min fr). From episode rule, the confidence is defined as fr(γ,s,win) fr(β,s,win). The next Mannila algorithm describes how rules and their confidences can be computed from the frequencies of episodes where the input is a set Eof event types, a sequence s, a set of Eof episodes, a window width win, a frequency threshold min frand a confidence threshold min conf; and the output is the episode rules that hold in swith respect to win,min fr and min conf. /*Find frequent episodes */ compute F(s, win, min fr) /*Generate rules */ for all α∈F(s, win, min fr)do for all β≺αdo if fr(α)/fr(β)≥min conf then output the rule β→αand the confidence fr(α)/fr(β); 6 Discovering episodes common to several sequences In this section, a methodology to discover episodes in some sequences is developed. It is based on Mannila’s approach because it finds the episode with the maximum width that occurs in all sequences. The similarity between two windows is necessary to understand the developed approach. Two windows are similar if the number of all existing event types in the windows is equal. For example, in the next sequences, the windows ω(0,2) over sequences s1and s2are not similar, but ω(1,4) yes. s1=((A, 0),(B,1),(B,2),(C, 3),(C, 4),(B,5),(D,6)) s2=((A, 0),(C, 1),(B,2),(C, 3),(B,4),(B,5),(D,7)) s3=((A, 1),(B,2),(B,3),(C, 4),(C, 6),(D,8)) Let Sa set of sequences, lan integer and Wa set of episodes. /*Set variables */ S={s1,s 2,...,s n}; l=min{width(s1),width(s2),...,width(sn)}; W=∅; /*Get maximum similar windows */ while |W|=0and l>0do W={ω(ts,t e)∈s|∀s∈S, width(ω)=l}; l=l−1; if |W|=0then there is not a common episode else /*Construct chronicle */ k=width(ω0); nodes =∅; while k>0do nodes =∅; for all ω∈Wdo nodes =nodes ∩event(ω, k); episode =episode ∩nodes; k=k−1; In the above code, nodes =nodes ∩event(ω,k)adds events to existing in serial and episode =episode ∩nodes adds events to existing in parallel. Furthermore, event(ω,k) gets the event in the ith position. Note that the time constraints between two related events is the minimum between all similar pairs of events in the same position. 7 Experimentation The algorithm does not been applied over a real data set, but it has been proven over the sequences s1,s2and s3in Section 6. The maximum similar windows are below: ω1(0,4) = {(A, 0),(B,1),(B,2),(C, 3),(C, 4)} ω2(0,4) = {(A, 0),(C, 1),(B,2),(C, 3),(B,4)} ω3(1,6) = {(A, 1),(B,2),(B,3),(C, 4),(C, 6)} Finally, the chronicle can be viewed in Figure 4. 0 $ÈOYDUH]HWDO$QH[WHQGHGFKURQLFOHGLVFRYHU\DSSURDFKWRILQGWHPSRUDOSDWWHUQVEHWZHHQ 6HTXHQFHV
1 1 2 1 1 1 1 Figure 4: The generated chronicle 8 Conclusions We have studied a method to find all episodes that occur frequently in a event sequence, Mannila’s approach, whose objective is to find small frequent episodes at first and then progressively looking for larger frequent episodes. After that, we have developed a methodology to discover episodes in some sequences based on Mannila’s approach. Thus, a new similarity between two windows has been defined to determine the maximum chronicle. To test the development of the methodology, it has been applied to three sample sequences to obtain the maximum common chronicle. Nevertheless, we think that this approach can be satisfactorily applied to data sets that it is the next step to complement this development. Acknowledgments This research is partially supported by the projects of the Spanish Ministry of Economy and Competitiveness ARTEMISA (TIN2009-14378-C02-01) and Simon (TIC- 8052) of the Andalusian Regional Ministry of Economy, Innovation and Science. References [Bauer et al., 2011]A. Bauer, A. Botea, A. Grastien, P. Haslum, and J. Rintanen. Alarm processing with modelbased diagnosis of event discrete systems. In Proceedings of the AI for an Intelligent Planet, page 2. ACM, 2011. [Bertrand et al., 2009]O. Bertrand, P. Carle, and C. Choppy. Modelling chronicle recognition for distributed simulation processing with coloured petri nets. In Proceedings of the 2nd International Conference on Simulation Tools and Techniques, page 42. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2009. [Cram et al., 2011]D. Cram, B. Mathern, and A. Mille. A complete chronicle discovery approach: application to activity analysis. Expert Systems, 2011. [Dousson and Ghallab, 1994]C. Dousson and M. Ghallab. Suivi et reconnaissance de chroniques. Revue dintelligence artificielle, 8(1):29–61, 1994. [Dousson et al., 2008]C. Dousson, F. Clerot, and F. Fessant. Method for the machine learning of frequent chronicles in an alarm log for the monitoring of dynamic systems, June 17 2008. US Patent 7,388,482. [Le Guillou et al., 2008]X. Le Guillou, M.O. Cordier, S. Robin, and L. Roz´ e. Chronicles for on-line diagnosis of distributed systems. In Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, pages 194–198. IOS Press, 2008. [Mannila and Ronkainen, 1997]H. Mannila and P. Ronkainen. Similarity of event sequences. In Temporal Representation and Reasoning, 1997.(TIME’97), Proceedings., Fourth International Workshop on, pages 136–139. IEEE, 1997. [Mannila et al., 1997]H. Mannila, H. Toivonen, and A. Inkeri Verkamo. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1(3):259–289, 1997. [Pencol´ e and Subias, 2009]Y. Pencol´ e and A. Subias. A chronicle-based diagnosability approach for discrete timed-event systems: Application to web-services. Journal of Universal Computer Science, 15(17):3246–3272, 2009. [Saddem et al., 2010]R. Saddem, A. Toguyeni, and M. Tagina. Consistency’s checking of chronicles’ set using time petri nets. In Control & Automation (MED), 2010 18th Mediterranean Conference on, pages 1520–1525. IEEE, 2010. 0 $ÈOYDUH]HWDO$QH[WHQGHGFKURQLFOHGLVFRYHU\DSSURDFKWRILQGWHPSRUDOSDWWHUQVEHWZHHQ 6HTXHQFHV