TY - JOUR
T1 - Methods to window data to differentiate between markov models
AU - Schwier, Jason M.
AU - Brooks, Richard R.
AU - Griffin, Christopher
N1 - Funding Information:
Manuscript received March 31, 2009; revised January 3, 2010 and April 17, 2010; accepted August 17, 2010. Date of publication October 4, 2010; date of current version May 18, 2011. This work was supported in part by the Office of Naval Research Code 311 under Contract/Grant N00014-06-C-0022. This material is based on research sponsored by the Air Force Research Laboratory under Agreement AFD-080228-008. The work of R. Brooks was supported in part by the Air Force Office of Scientific Research under Grant FA9550-09-1-0173. The work of Dr. Griffin was performed as a Eugene P. Wigner Fellow and Staff Member with the Oak Ridge National Laboratory, managed by UT–Battelle, LLC, for the U.S. Department of Energy under Contract DE-AC05-00OR22725. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Air Force Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The authors gratefully acknowledge this support and take responsibility for the contents of this report. This paper was recommended by Associate Editor V. Murino.
PY - 2011/6
Y1 - 2011/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79957475703&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79957475703&partnerID=8YFLogxK
U2 - 10.1109/TSMCB.2010.2076325
DO - 10.1109/TSMCB.2010.2076325
M3 - Article
C2 - 20923740
AN - SCOPUS:79957475703
SN - 1083-4419
VL - 41
SP - 650
EP - 663
JO - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
JF - IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
IS - 3
M1 - 5593913
ER -