Research On Discovering Frequent Episodes In Event Sequences

An episode is a collection of events that occur relatively close to each other in an event sequence in a given partial order. An event sequence consists of events that successively happen, and each event has an associated time of occurrence. Then we use the window to describe the meaning of occurring close enough in time. A window is a slice of the event sequence that meets certain requirement of time limitation. The goal of discovery of frequent episodes is to discover the set of all frequent episodes in event sequences. Then from the set we can easily find out episode rules, which indicate the relationship between the events. The episode rules play an important role in telecommunication alarm analysis and global security management of alarm. In the thesis, we first introduce the basic conceptions of episodes, and then introduce the algorithm to discover frequent episodes?Winepi. Winepi bases on sliding window. It includes two important phases: candidate generation and episode recognition. In the algorithm frequent episodes of size l from previous iterations are used to generate new seeds of candidates of size l+1, and the frequent episodes of size l+1 will be recognized from the candidates. There is another method to find frequent episodes that is called Minepi. It bases on the minimal occurrence. The minimal occurrence means that there are not other occurrences of an episode inside the given occurrence of the episode. In the thesis, a theorem is put forward to clarify how to find the minimal occurrences of length l+1 from the minimal occurrences of length l. Because episodes and sequential patterns have many similarities, how to introduce efficient sequential pattern mining algorithms to the discovery of frequent episodes is an important research subject in the thesis. Therefore, we introduce the PrefixSpan algorithm, which is a highly efficient algorithm in sequential pattern mining. The PrefixSpan algorithm uses the projection method, which makes a longer pattern grow from its prefix. In order to use PrefixSpan to the discovery of episodes, firstly,...