Adaptive event detection with time-varying poisson processes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Adaptive event detection with time-varying poisson processes

Full text

Pdf (1.22 MB)

Source

International Conference on Knowledge Discovery and Data Mining archive
Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining table of contents

Philadelphia, PA, USA

SESSION: Research track papers table of contents

Pages: 207 - 216

Year of Publication: 2006

ISBN:1-59593-339-5

Authors

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

Sponsors

ACM: Association for Computing Machinery
SIGKDD: ACM Special Interest Group on Knowledge Discovery in Data
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 48, Downloads (12 Months): 157, Citation Count: 8

Additional Information:

abstract references cited by 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/1150402.1150428 What is a DOI?

ABSTRACT

Time-series of count data are generated in many different contexts, such as web access logging, freeway traffic monitoring, and security logs associated with buildings. Since this data measures the aggregated behavior of individual human beings, it typically exhibits a periodicity in time on a number of scales (daily, weekly,etc.) that reflects the rhythms of the underlying human activity and makes the data appear non-homogeneous. At the same time, the data is often corrupted by a number of bursty periods of unusual behavior such as building events, traffic accidents, and so forth. The data mining problem of finding and extracting these anomalous events is made difficult by both of these elements. In this paper we describe a framework for unsupervised learning in this context, based on a time-varying Poisson process model that can also account for anomalous events. We show how the parameters of this model can be learned from count time series using statistical estimation techniques. We demonstrate the utility of this model on two datasets for which we have partial ground truth in the form of known events, one from freeway traffic data and another from building access data, and show that the model performs significantly better than a non-probabilistic, 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 make inferences about the detected events (e.g., popularity or level of attendance). Our experimental results indicate that the proposed time-varying Poisson model 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	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]
	2	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]
	3	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]
	4	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]
	5	S. L. Scott and P. Smyth, "The Markov modulated Poisson process and Markov Poisson cascade with applications to web traffic data," Bayesian Statistics, vol. 7, pp. 671--680, 2003.
	6	S. Scott, "Detecting network intrusion using a Markov modulated nonhomogeneous Poisson process," http://www-rcf.usc.edu/~sls/mmnhpp.ps.gz.
	7	Freeway Performance Measurement System (PeMS), "http://pems.eecs.berkeley.edu/."
	8	S. Scott, "Bayesian methods and extensions for the two state Markov modulated Poisson process," Ph.D. dissertation, Harvard University, Dept. of Statistics, 1998.
	9	H. Heffes and D. M. Lucantoni, "A Markov-modulated characterization of packetized voice and data traffic and related statistical multiplexer performance," IEEE J. Sel. Areas Comm., vol. 4, no. 6, pp. 856--868, 1984.
	10	S. Geman and D. Geman, "Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images," IEEE Trans. PAMI, vol. 6, no. 6, pp. 721--741, Nov. 1984.
	11	A. E. Gelfand and A. F. M. Smith, "Sampling-based approaches to calculating marginal densities," J. Amer. Stat. Assoc., vol. 85, pp. 398--409, 1990.
	12	L. E. Baum, T. Petrie, G. Soules, and N. Weiss, "A maximization technique occurring in statistical analysis of probabilistic functions of Markov chains," Ann. Math. Stat., vol. 41, no. 1, pp. 164--171, February 1970.
	13	A. E. Gelfand and D. K. Dey, "Bayesian model choice: asymptotics and exact calculations," J. R. Stat. Soc. B, vol. 56, no. 3, pp. 501--514, 1990.
	14	S. Chib, "Marginal likelihood from the Gibbs output," J. Amer. Stat. Assoc., vol. 90, no. 432, pp. 1313--1321, Dec. 1995.

CITED BY 8

	Tarem Ahmed , Boris Oreshkin , Mark Coates, Machine learning approaches to network anomaly detection, Proceedings of the 2nd USENIX workshop on Tackling computer systems problems with machine learning techniques, p.1-6, April 10, 2007, Cambridge, MA
	Alexander Ihler , Jon Hutchins , Padhraic Smyth, Learning to detect events with Markov-modulated poisson processes, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.3, p.13-es, December 2007
	Xiuyao Song , Chris Jermaine , Sanjay Ranka , John Gums, A bayesian mixture model with linear regression mixing proportions, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Xiuyao Song , Chris Jermaine , Sanjay Ranka , John Gums, A bayesian mixture model with linear regression mixing proportions, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
	Deokwoo Jung , Thiago Teixeira , Andreas Savvides, Sensor node lifetime analysis: Models and tools, ACM Transactions on Sensor Networks (TOSN), v.5 n.1, p.1-33, February 2009
	Xiaomeng Wan , Evangelos Milios , Nauzer Kalyaniwalla , Jeannette Janssen, Link-based event detection in email communication networks, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
	Varun Chandola , Arindam Banerjee , Vipin Kumar, Anomaly detection: A survey, ACM Computing Surveys (CSUR), v.41 n.3, p.1-58, July 2009
	Yingyi Bu , Lei Chen , Ada Wai-Chee Fu , Dawei Liu, Efficient anomaly monitoring over moving object trajectory streams, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France