MENU: Home Bio Affiliations Research Teaching Publications Videos Collaborators/Students Contact FAQ ©2007-14 RSS

Thesis David Minnen PhD (2008): “Unsupervised Discovery of Activity Primitives from Multivariate Sensor Data”

June 18th, 2008 Irfan Essa Posted in Activity Recognition, David Minnen, PhD, Thad Starner No Comments »

Unsupervised Discovery of Activity Primitives from Multivariate Sensor Data

Abstract

 

This research addresses the problem of temporal pattern discovery in real-valued, multivariate sensor data. Several algorithms were developed, and subsequent evaluation demonstrates that they can efficiently and accurately discover unknown recurring patterns in time series data taken from many different domains. Different data representations and motif models were investigated in order to design an algorithm with an improved balance between run-time and detection accuracy. The different data representations are used to quickly filter large data sets in order to detect potential patterns that form the basis of a more detailed analysis. The representations include global discretization, which can be efficiently analyzed using a suffix tree, local discretization with a corresponding random projection algorithm for locating similar pairs of subsequences, and a density-based detection method that operates on the original, real-valued data. In addition, a new variation of the multivariate motif discovery problem is proposed in which each pattern may span only a subset of the input features. An algorithm that can efficiently discover such “subdimensional” patterns was developed and evaluated. The discovery algorithms are evaluated by measuring the detection accuracy of discovered patterns relative to a set of expected patterns for each data set. The data sets used for evaluation are drawn from a variety of domains including speech, on-body inertial sensors, music, American Sign Language video, and GPS tracks.

AddThis Social Bookmark Button

Paper: IEEE Data Mining Conference 2007 “Detecting Subdimensional Motifs: An Efficient Algorithm for Generalized Multivariate Pattern Discovery”

October 28th, 2007 Irfan Essa Posted in Activity Recognition, Charles Isbell, David Minnen, Papers, Research, Thad Starner No Comments »

Detecting Subdimensional Motifs: An Efficient Algorithm for Generalized Multivariate Pattern Discovery

  • Minnen, Essa, Isbell, and Starner (2007), “Detecting Subdimensional Motifs: An Efficient Algorithm for Generalized Multivariate Pattern Discovery,” in Proceedings of IEEE International Conference on Data Mining (ICDM), 2007. [PDF] [DOI]
    [BIBTEX]

    @inproceedings{2007-Minnen-DSMEAGMPD,
      Author = {D. Minnen and I. Essa and C. Isbell and T. Starner},
      Booktitle = {Proceedings of IEEE International Conference on Data Mining (ICDM)},
      Doi = {10.1109/ICDM.2007.52},
      Month = {October},
      Pdf = {http://www.cc.gatech.edu/~irfan/p/2007-Minnen-DSMEAGMPD.pdf},
      Title = {Detecting Subdimensional Motifs: An Efficient Algorithm for Generalized Multivariate Pattern Discovery},
      Year = {2007}}

Abstract

ICDMPaper Discovering recurring patterns in time series data is a fundamental problem for temporal data mining. This paper addresses the problem of locating subdimensional motifs in real-valued, multivariate time series, which requires the simultaneous discovery of sets of recurring patterns along with the corresponding relevant dimensions. While many approaches to motif discovery have been developed, most are restricted to categorical data, univariate time series, or multivariate data in which the temporal patterns span all of the dimensions. In this paper, we present an expected linear-time algorithm that addresses a generalization of multivariate pattern discovery in which each motif may span only a subset of the dimensions. To validate our algorithm, we discuss its theoretical properties and empirically evaluate it using several data sets including synthetic data and motion capture data collected by an on-body inertial sensor.

AddThis Social Bookmark Button

Paper: AAAI 2007: “Discovering Multivariate Motifs using Subsequence Density Estimation and Greedy Mixture Learning”

July 24th, 2007 Irfan Essa Posted in Activity Recognition, Charles Isbell, David Minnen, Papers, Research, Thad Starner No Comments »

Discovering Multivariate Motifs using Subsequence Density Estimation and Greedy Mixture Learning

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 motif because all of the included subsequences are similar. The ability to automatically discover such motifs allows intelligent systems to form endogenously meaningful representations of their environment through unsupervised sensor analysis. 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 nonlinear temporal warping. We evaluate the performance of our approach using four data sets from different domains including on-body inertial sensors and speech.

AddThis Social Bookmark Button

Paper: IEEE ISWC (2006) “Discovering Characteristic Actions from On-Body Sensor Data”

October 14th, 2006 Irfan Essa Posted in Activity Recognition, Charles Isbell, David Minnen, Papers, Research, Thad Starner No Comments »

Discovering Characteristic Actions from On-Body Sensor Data (IEEEXplore)

Minnen, D. Starner, T. Essa, I. Isbell, C.
College of Computing, Georgia Institute of Technology, Atlanta, GA 30332 USA.
This paper appears in: Wearable Computers, 2006 10th IEEE International Symposium on
Publication Date: Oct. 2006
On page(s): 11 – 18
Number of Pages: 11 – 18
Location: Montreux, Switzerland
ISSN: 1550-4816
ISBN: 1-4244-0598-x
Digital Object Identifier: 10.1109/ISWC.2006.286337
Posted online: 2007-01-22 09:58:15.0

Abstract

We present an approach to activity discovery, the unsupervised identification and modeling of human actions embedded in a larger sensor stream. Activity discovery can be seen as the inverse of the activity recognition problem. Rather than learn models from hand-labeled sequences, we attempt to discover motifs, sets of similar subsequences within the raw sensor stream, without the benefit of labels or manual segmentation. These motifs are statistically unlikely and thus typically correspond to important or characteristic actions within the activity. The problem of activity discovery differs from typicalmotif discovery, such as locating protein binding sites, because of the nature of time series data representing human activity. For example, in activity data, motifs will tend to be sparsely distributed, vary in length, and may only exhibit intra-motif similarity after appropriate time warping. In this paper, we motivate the activity discovery problem and present our approach for efficient discovery of meaningful actions from sensor data representing human activity. We empirically evaluate the approach on an exercise data set captured by a wrist-mounted, three-axis inertial sensor. Our algorithm successfully discovers motifs that correspond to the real exercises with a recall rate of 96.3% and overall accuracy of 86.7% over six exercises and 864 occurrences.

AddThis Social Bookmark Button

Paper: IEEE CVPR (2004) “Propagation networks for recognition of partially ordered sequential action”

June 2nd, 2004 Irfan Essa Posted in Aaron Bobick, Activity Recognition, Aware Home, David Minnen, Papers, Yan Huang, Yifan Shi No Comments »

Yifan Shi, Yan Huang, Minnen, D., Bobick, A., Essa, I. (2004), “Propagation networks for recognition of partially ordered sequential action” In Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004 (CVPR 2004). Volume: 2, page(s): II-862 – II-869 Vol.2, ISSN: 1063-6919, ISBN: 0-7695-2158-4, INSPEC Accession Number:8161557, Digital Object Identifier: 10.1109/CVPR.2004.1315255, 27 June-2 July 2004 (IEEEXplore)

Abstract

We present propagation networks (P-nets), a novel approach for representing and recognizing sequential activities that include parallel streams of action. We represent each activity using partially ordered intervals. Each interval is restricted by both temporal and logical constraints, including information about its duration and its temporal relationship with other intervals. P-nets associate one node with each temporal interval. Each node is triggered according to a probability density function that depends on the state of its parent nodes. Each node also has an associated observation function that characterizes supporting perceptual evidence. To facilitate real-time analysis, we introduce a particle filter framework to explore the conditional state space. We modify the original condensation algorithm to more efficiently sample a discrete state space (D-condensation). Experiments in the domain of blood glucose monitor calibration demonstrate both the representational power of P-nets and the effectiveness of the D-condensation algorithm.

AddThis Social Bookmark Button