Methods to window data to differentiate between markov models

Jason M. Schwier, Richard R. Brooks, Christopher Griffin

    Research output: Contribution to journalArticlepeer-review

    7 Scopus citations

    Abstract

    In this paper, we consider how we can detect patterns in data streams that are serial Markovian, where target behaviors are Markovian, but targets may switch from one Markovian behavior to another. We want to reliably and promptly detect behavior changes. Traditional Markov-model-based pattern detection approaches, such as hidden Markov models, use maximum likelihood techniques over the entire data stream to detect behaviors. To detect changes between behaviors, we use statistical pattern matching calculations performed on a sliding window of data samples. If the window size is very small, the system will suffer from excessive false-positive rates. If the window is very large, change-point detection is delayed. This paper finds both necessary and sufficient bounds on the window size. We present two methods of calculating window sizes based on the state and transition structures of the Markov models. Two application examples are presented to verify our results. Our first example problem uses simulations to illustrate the utility of the proposed approaches. The second example uses models extracted from a database of consumer purchases to illustrate their use in a real application.

    Original languageEnglish (US)
    Article number5593913
    Pages (from-to)650-663
    Number of pages14
    JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
    Volume41
    Issue number3
    DOIs
    StatePublished - Jun 2011

    All Science Journal Classification (ASJC) codes

    • Control and Systems Engineering
    • Software
    • Information Systems
    • Human-Computer Interaction
    • Computer Science Applications
    • Electrical and Electronic Engineering

    Fingerprint

    Dive into the research topics of 'Methods to window data to differentiate between markov models'. Together they form a unique fingerprint.

    Cite this