Learning to detect events with Markov-modulated poisson processes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Learning to detect events with Markov-modulated poisson processes

Full text

Pdf (1.16 MB)

Source

ACM Transactions on Knowledge Discovery from Data (TKDD) archive
Volume 1 , Issue 3 (December 2007) table of contents

Article No. 13

Year of Publication: 2007

ISSN:1556-4681

Authors

Alexander Ihler	University of California, Irvine, CA
Jon Hutchins	University of California, Irvine, CA
Padhraic Smyth	University of California, Irvine, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 218, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1297332.1297337 What is a DOI?

ABSTRACT

Time-series of count data occur in many different contexts, including Internet navigation logs, freeway traffic monitoring, and security logs associated with buildings. In this article we describe a framework for detecting anomalous events in such data using an unsupervised learning approach. Normal periodic behavior is modeled via a time-varying Poisson process model, which in turn is modulated by a hidden Markov process that accounts for bursty events. We outline a Bayesian framework for learning the parameters of this model from count time-series. Two large real-world datasets of time-series counts are used as testbeds to validate the approach, consisting of freeway traffic data and logs of people entering and exiting a building. We show that the proposed model is significantly more accurate at detecting known events than a more traditional threshold-based technique. We also describe how the model can be used to investigate different degrees of periodicity in the data, including systematic day-of-week and time-of-day effects, and to make inferences about different aspects of events such as number of vehicles or people involved. The results indicate that the Markov-modulated Poisson framework provides a robust and accurate framework for adaptively and autonomously learning how to separate unusual bursty events from traces of normal human activity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baum, L. E., Petrie, T., Soules, G., and Weiss, N. 1970. A maximization technique occurring in statistical analysis of probabilistic functions of Markov chains. Ann. Math. Statis. 41, 1 (Feb.), 164--171.
	2	Buntine, W. 1994. Operations for learning with graphical models. J. Artif. Intell. Res. 2, 159--225.
	3	Chen, C., Petty, K., Skabardonis, A., Varaiya, P., and Jia, Z. 2001. Freeway performance measurement system: Mining loop detector data. In the 80th Annual Meeting of the Transportation Research Board. Washington, D.C. http://pems.eecs.berkeley.edu/.
	4	Chib, S. 1995. Marginal likelihood from the Gibbs output. J. Amer. Statis. Assoc. 90, 432 (Dec.), 1313--1321.
	5	Gelfand, A. E. and Dey, D. K. 1990. Bayesian model choice: Asymptotics and exact calculations. J. Royal Statis. Soc. Series C 56, 3, 501--514.
	6	Gelfand, A. E. and Smith, A. F. M. 1990. Sampling-Based approaches to calculating marginal densities. J. Amer. Statis. Assoc. 85, 398--409.
	7	Geman, S. and Geman, D. 1984. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 6 (Nov.), 721--741.
	8	Valery Guralnik , Jaideep Srivastava, Event detection from time series data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.33-42, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312190]
	9	Heffes, H. and Lucantoni, D. M. 1984. A Markov-modulated characterization of packetized voice and data traffic and related statistical multiplexer performance. IEEE J. Selected Areas Commun. 4, 6, 856--868.
	10	Alexander Ihler , Jon Hutchins , Padhraic Smyth, Adaptive event detection with time-varying poisson processes, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150428]
	11	Michael I. Jordan, Learning in graphical models, MIT Press, Cambridge, MA, 1999
	12	Eamonn Keogh , Stefano Lonardi , Bill 'Yuan-chi' Chiu, Finding surprising patterns in a time series database in linear time and space, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775128]
	13	Jon Kleinberg, Bursty and hierarchical structure in streams, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775061]
	14	Papoulis, A. 1991. Probability, Random Variables, and Stochastic Processes, 3rd ed. McGraw-Hill, New York.
	15	Marko Salmenkivi , Heikki Mannila, Using Markov chain Monte Carlo and dynamic programming for event sequence data, Knowledge and Information Systems, v.7 n.3, p.267-288, March 2005 [doi>10.1007/s10115-004-0157-6]
	16	Scott, S. 1998. Bayesian methods and extensions for the two state Markov modulated Poisson process. Ph.D. thesis, Harvard University, Department of Statistics.
	17	Scott, S. 2002. Detecting network intrusion using a Markov modulated nonhomogeneous Poisson process. http://www-rcf.usc.edu/~sls/mmnhpp.ps.gz.
	18	Scott, S. L. and Smyth, P. 2003. The Markov modulated Poisson process and Markov Poisson cascade with applications to Web traffic data. In Bayesian Statistics, vol. 7, M. J. Bayarri et al., eds. Oxford University Press, Oxford, UK, 671--680.
	19	Svensson, A. 1981. On a goodness of fit test for multiplicative Poisson models. Ann. Statis. 9, 4, 697--704.