Streaming changepoint detection for transition matrices
File(s)
Published version
Author(s)
Plasse, Joshua
Helfer Hoeltgebaum, Henrique
Adams, Niall
Type
Journal Article
Abstract
Sequentially detecting multiple changepoints in a data stream is a challenging task. Difficulties relate to both computational and statistical aspects, and in the latter, specifying control parameters is a particular problem. Choosing control parameters typically relies on unrealistic assumptions, such as the distributions generating the data, and their parameters, being known. This is implausible in the streaming paradigm, where several changepoints will exist. Further, current literature is mostly concerned with streams of continuous-valued observations, and focuses on detecting a single changepoint. There is a dearth of literature dedicated to detecting multiple changepoints in transition matrices, which arise from a sequence of discrete states. This paper makes the following contributions: a complete framework is developed for adaptively and sequentially estimating a Markov transition matrix in the streaming data setting. A change detection method is then developed, using a novel moment matching technique, which can effectively monitor for multiple changepoints in a transition matrix. This adaptive detection and estimation procedure for transition matrices, referred to as ADEPT-M, is compared to several change detectors on synthetic data streams, and is implemented on two real-world data streams – one consisting of over nine million HTTP web requests, and the other being a well-studied electricity market data set.
Date Issued
2021-07-01
Date Acceptance
2021-03-05
Citation
Data Mining and Knowledge Discovery, 2021, 35, pp.1287-1316
ISSN
1384-5810
Publisher
Springer Verlag
Start Page
1287
End Page
1316
Journal / Book Title
Data Mining and Knowledge Discovery
Volume
35
Copyright Statement
© The Author(s) 2021. ThisarticleislicensedunderaCreativeCommonsAttribution4.0InternationalLicense,which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
License URL
Identifier
https://link.springer.com/article/10.1007/s10618-021-00747-7
Subjects
Science & Technology
Technology
Computer Science, Artificial Intelligence
Computer Science, Information Systems
Computer Science
ADEPT-M
Continuous monitoring
Forgetting factor
Markov chain
Moment matching
Artificial Intelligence & Image Processing
0801 Artificial Intelligence and Image Processing
0804 Data Format
0806 Information Systems
Publication Status
Published
Date Publish Online
2021-04-11