Discovering Multivariate Motifs using Subsequence Density Estimation and Greedy Mixture Lea.pdf

Discovering Multivariate Motifs using Subsequence Density Estimation and Greedy Mixture Learning David Minnen and Charles L. Isbell and Irfan Essa and Thad Starner Georgia Institute of Technology College of Computing / School of Interactive Computing Atlanta, GA 30332-0760 USA {dminn,isbell,irfan,thad}@ Abstract The problem of locating motifs in real-valued, multivariate time series data involves the discovery of sets of recurring patterns embedded in the time series. Each set is composed of several non-overlapping subsequences and constitutes a mo- tif because all of the included subsequences are similar. The ability to automatically discover such motifs allows intelli- gent systems to form endogenously meaningful representa- tions of their environment through unsupervised sensor anal- ysis. In this paper, we formulate a unifying view of motif discovery as a problem of locating regions of high density in the space of all time series subsequences. Our approach is efficient (sub-quadratic in the length of the data), requires fewer user-specified parameters than previous methods, and naturally allows variable length motif occurrences and non- linear temporal warping. We evaluate the performance of our approach using four data sets from different domains includ- ing on-body inertial sensors and speech. Introduction Our goal is to develop intelligent systems that understand their environment by autonomously learning new concepts from their perceptions. In this paper, we address one form of this problem where the concepts correspond to recur- ring patterns in the sensory data captured by the intelligent agent. Such recurring patterns are often referred to as per- ceptual primitives ormotifs and correspond to sets of similar subsequences in the time-varying sensor data. For exam- ple, a motif discovery system could find unknown words or phonemes in speech data, learn common gestures in video of sign language, or allow a mobile robot to learn endonge- nously meaningful rep