Paper Info
Title
Discovering Frequent Episodes and Learning Hidden Markov Models: A Formal Connection
Abstract
This paper establishes a formal connection between two common, but previously unconnected methods for analyzing data streams: discovering frequent episodes in a computer science framework and learning generative models in a statistics framework. We introduce a special class of discrete Hidden Markov Models (HMMs), called Episode Generating HMMs (EGHs), and associate each episode with a unique EGH. We prove that, given any two episodes, the EGH that is more likely to generate a given data sequence is the one associated with the more frequent episode. To be able to establish such a relationship, we define a new measure of frequency of an episode, based on what we call nonoverlapping occurrences of the episode in the data. An efficient algorithm is proposed for counting the frequencies for a set of episodes. Through extensive simulations, we show that our algorithm is both effective and more efficient than current methods for frequent episode discovery. We also show how the association between frequent episodes and EGHs can be exploited to assess the significance of frequent episodes discovered and illustrate empirically how this idea may be used to improve the efficiency of the frequent episode discovery.
Year
DOI
Venue
2005
10.1109/TKDE.2005.181
IEEE Trans. Knowl. Data Eng.
Keywords
Field
DocType
data mining,hidden Markov models,sequences,statistical analysis,data sequence,data streams,formal connection,frequent episode discovery,generative model,hidden Markov model,statistical significance,temporal data mining,Hidden Markov Models,Index Terms- Temporal data mining,frequent episodes,sequential data,statistical significance.
Data mining,Sequential data,Data stream mining,Computer science,Information extraction,Temporal database,Artificial intelligence,Generative grammar,Hidden Markov model,Temporal data mining,Machine learning,Statistical analysis
Journal
Volume
Issue
ISSN
17
11
1041-4347
Citations 
PageRank 
References 
52
2.58
12
Authors
3
Name
Order
Citations
PageRank
Srivatsan Laxman142121.65
P. S. Sastry274157.27
K. P. Unnikrishnan329923.21