PaperlayerView exact revision on arXiv

Source-linked AI summary

Multivariate Time Series Classification Using Dynamic Time Warping Template Selection for Human Activity Recognition

Skyler Seto, Wenyu Zhang, Yichen Zhou

arXiv:1512.06747v1cs.AI

TL;DR

The paper addresses smartphone human activity classification without complex feature extraction or HAR domain knowledge. It modifies Dynamic Time Warping and builds activity templates for classification, achieving comparable or sometimes better accuracy than feature extraction on real and synthetic data.

  • Problem

    The paper seeks accurate and computationally efficient smartphone motion classification without requiring HAR domain knowledge or complex feature extraction.

  • Method

    The approach modifies DTW and uses clustered time-series templates to classify activities by similarity rather than extracting complex features.

  • Results

    The approach achieved comparable overall accuracy to feature extraction on real data, higher accuracy on synthetic data, and 0.977 accuracy for four-category classification with DTW-DBA and DTWsubseq-DBA.

  • Takeaways & Limitations

    Template-based classification can avoid domain knowledge and extend beyond HAR to multidimensional time-series datasets.

Abstract

from arXiv · show

Accurate and computationally efficient means for classifying human activities have been the subject of extensive research efforts. Most current research focuses on extracting complex features to achieve high classification accuracy. We propose a template selection approach based on Dynamic Time Warping, such that complex feature extraction and domain knowledge is avoided. We demonstrate the predictive capability of the algorithm on both simulated and real smartphone data.

I. INTRODUCTION

The paper targets smartphone-based human activity classification that is accurate, computationally efficient, and usable without HAR domain knowledge. It proposes modified DTW with activity templates instead of complex feature extraction.

  • Smartphone accelerometers and gyroscopes offer convenient motion data for applications including health monitoring and activity recognition, despite lower accuracy than professional sensors.
  • The objective is offline smartphone motion classification with accuracy and computational efficiency comparable to current techniques, without HAR domain knowledge.
  • The method modifies DTW for similarity measurement, then uses clustering, template construction, and classification for motion data.
  • The primary contributions are a modified DTW similarity measure and template extraction in place of feature extraction.
  • The implementation is reported to improve prediction quality, avoid high dimensionality, and remain robust to noise on real and synthetic activity data.
  • Feature extraction can require domain expertise, many features, and computationally intensive autoregression coefficients.

III. DEFINITIONS

The paper defines equally sampled multivariate time series and DTW as an alignment procedure based on an optimal path through a pointwise-distance matrix. A bandwidth restricts computation near the diagonal to reduce runtime.

  • A. Time Series: A p-dimensional multivariate time series is a sequence of m data points in R^p indexed by increasing times within T = [a, b].
  • A. Time Series: The training and test series are assumed to have equal length and uniform sampling, although the DTW algorithms can be extended to unequal lengths.
  • B. Dynamic Time Warping (DTW): DTW computes alignment and distance by evaluating paths through a pointwise-distance matrix and selecting the optimal warping path.
  • B. Dynamic Time Warping (DTW): A warping path begins at (1,1), ends at (m,m), is monotonic, and advances through (1,0), (0,1), or (1,1) steps.
  • B. Dynamic Time Warping (DTW): DTWD is the sum of pointwise distances along the optimal path and is returned as D[m,m].
  • B. Dynamic Time Warping (DTW): FastDTW uses bandwidth bw to compute only matrix values near the diagonal, bringing runtime closer to O(m) when series share shape and frequency.

IV. SUBSEQUENCE DTW (DTWSUBSEQ)

Subsequence DTW addresses DTWD’s overstated dissimilarity for horizontally displaced copies by relaxing endpoint constraints. A displacement window limits candidate paths, while bandwidth further reduces computation.

  • DTWD can overstate dissimilarity when one copy of a time series is horizontally displaced, such as sampled sine and cosine curves from one sinusoid.
  • Subsequence DTW relaxes the requirement that the optimal path start at D[1,1] and end at D[m,m].
  • The displacement window dw restricts paths to those starting and ending within a maximum horizontal displacement estimated from common landmarks or periodicity.
  • At each displacement, both series are truncated to equal length and the resulting distance is weighted proportionately to the original length.
  • Fast DTWsubseq further optimizes subsequence DTW by imposing a bandwidth.

A. Overview

The paper replaces intensive feature extraction with activity templates built from training time series and classifies test data by DTWsubseqD similarity. The procedure is presented as a full template-selection and classification pipeline.

  • A. Overview: The approach works directly with raw time-domain motion data to avoid intensive feature extraction.It is motivated by the standard pipeline of extracting features before classification.
  • A. Overview: The method builds time-series templates for each activity from training data, then classifies test samples by similarity to those templates using DTWsubseqD.The authors state that template-based classification is intended to handle speed and style variation in subjects’ motions.
  • A. Overview: Figure 2 presents the overall template-selection and classification procedure.

B. Cluster

For each activity, the method computes pairwise DTWsubseqD distances, applies hierarchical clustering, and controls cluster formation with a cut parameter. Flat clusters are removed by restricting within-cluster pairwise distances.

  • B. Cluster: Clustering begins by computing DTWsubseqD between every pair of points within each activity.
  • B. Cluster: Hierarchical clustering forms activity clusters using distances calculated between pairs of clusters.
  • B. Cluster: The method removes flat clusters by restricting pairwise distances within a cluster below a specified threshold.
  • B. Cluster: Decreasing the cut parameter increases the number of clusters produced for each activity.The paper evaluates different cut values in Section VII.

C. Build Templates

The template-building stage averages time series within each activity cluster using either DPA or DBA, while classification compares samples with the resulting templates through DTWsubseqD vectors.

  • C. Build Templates: After clustering each activity, the method computes average time series as candidate templates using DPA or DBA.
  • C. Build Templates: The implementation provides an algorithm for DPA and includes DBA for comparison.
  • C. Build Templates: DPA selects the series with minimum distance to the others, aligns all series to it, and computes their pointwise average.
  • C. Build Templates: DBA iteratively updates an average series to minimize the sum of squared DTW distances to the cluster series.
  • C. Build Templates: The template algorithm maps clusters C1, ..., Cn to templates T1, ..., Tn.
  • C. Build Templates: Both averaging procedures use DTW rather than DTWsubseq so the averaged series retain the input-series length.
  • D. Classify: Each sample is compared with every template using DTWsubseqD, producing a distance vector that can be reduced and classified with methods such as PCA and SVM.

A. UCI HAR Data

The evaluation uses real UCI HAR smartphone data and synthetic noisy data. The real dataset covers six activities and six sensor dimensions, while the synthetic setup tests classification across subjects under short noise bursts.

  • A. UCI HAR Data: The UCI HAR dataset contains 10,299 samples from 30 subjects performing six activities, split into 7,352 training and 2,947 test samples.
  • A. UCI HAR Data: Each UCI reading has six dimensions: acceleration and angular velocity along the x, y, and z axes.
  • A. UCI HAR Data: The UCI data are noise-filtered and segmented into 2.56-second windows with 50% overlap, yielding 128 readings per window.
  • A. UCI HAR Data: Flat multidimensional curves are removed when every dimension’s range falls within the 5% quantile of ranges for that dimension.
  • A. UCI HAR Data: Figure 3 shows x-, y-, and z-axis curves for three dynamic and three static activities, with colors identifying activities.
  • B. Synthetic Data: The synthetic dataset tests classification for new subjects under short bursts of noise such as jerky motions, sensor shifts, and sensor noise.
  • B. Synthetic Data: Synthetic training data use one Accx dimension from activity templates, while test data use different random templates to represent another subject.
  • B. Synthetic Data: The synthetic set contains 800 training samples and 200 test samples across four activities, with noise injected in the frequency domain before sampling 128-point series.

VII. RESULTS

The results evaluate template construction and classification on UCI HAR and synthetic data, comparing DTW variants, averaging methods, cut parameters, and feature extraction. The experiments also examine computational and dimensionality advantages of templates over feature-based methods.

  • Template construction: The template-selection procedure constructs activity templates by clustering time series and averaging each cluster with either DPA or DBA.The results section visualizes templates for both real and synthetic data.
  • Evaluation setup: The experiments evaluate DTW and DTWsubseq with DPA and DBA across cut parameters 0.25 and 0.5 on UCI HAR and synthetic data.Classification accuracy is reported for all four distance-and-averaging combinations at both cut values.
  • Feature-extraction benchmark: The procedure is benchmarked against feature extraction using 568 handcrafted features, PCA, and a linear SVM classifier.The feature set includes statistical, frequency-domain, autocorrelation, and autoregression features.
  • Comparison with feature extraction: Template methods avoid domain knowledge, use around 220 templates versus over 500 features at comparable accuracy, and have dimensionality controlled by the number of templates.The paper also states that feature extraction can become computationally intensive as sequence length and point dimension increase.

B. UCI HAR Data

On UCI HAR, template-based classification reaches competitive accuracy with feature extraction, while results vary by averaging method, distance, and cut threshold. Lowering the cut generally improves accuracy but can increase template count and expose flat-template or overfitting issues.

  • Template comparison: DBA and DPA templates capture activity-curve shapes similarly, with no clear overall improvement from choosing one averaging method over the other.The broader UCI summary reports similar accuracy for six activities and better accuracy for four compared with feature extraction.
  • Averaging and distance methods: DTW performs better with DBA at both cut values, while DTWsubseq favors DBA at cut = 0.25 but DPA at cut = 0.5.The reported DTW accuracies are 0.797 over 0.781 and 0.860 over 0.841; DTWsubseq reports 0.855 over 0.838 and 0.789 over 0.777.
  • Cut threshold: Lowering cut from 0.5 to 0.25 increases accuracy for original DTW from 0.781 to 0.841 with DPA and to 0.860 with DBA.The number of templates rises from around 50 to over 500, and the paper notes that this may primarily reflect overfitting.
  • UCI HAR accuracy: 0.860 is the highest six-activity accuracy, achieved by DTW-DBA with cut = 0.25, compared with 0.890 for feature extraction.Residual flat templates in static activities are identified as a possible source of classification error.
  • UCI HAR accuracy: 0.977 is achieved by both DTW-DBA and DTWsubseq-DBA for four-category classification, exceeding feature extraction’s 0.965 after static activities are combined.This comparison is made when the flat-template issue is circumvented.
  • Synthetic-data comparison: Synthetic experiments show DBA is more robust to sporadic noise, but it can overfit when test data come from a different template representing a new subject.Under this setting, DPA reaches 0.700 with DTWsubseq and cut = 0.25, versus 0.67 for feature extraction.

D. Summary of Results

The template-selection algorithm achieved accuracy comparable to feature extraction and often performed better, with stronger results on synthetic data and dynamic activities. The approach also supports feature extraction without domain knowledge and is intended for sequential data beyond HAR.

  • Comparable accuracy to feature extraction was observed overall, with better performance in most cases.The comparison is summarized in Table V, where feature-extraction accuracy appears in parentheses.
  • Synthetic data produced higher accuracy, indicating robustness to noise and classification of new test subjects.
  • On real data, the approach had comparable overall test accuracy and better accuracy within dynamic activities.
  • The template-based approach extracts features without domain knowledge and can extend beyond HAR to other multidimensional sequential datasets.
  • Future improvements include modeling more complex activities, cross-validating clustering and DTW parameters, reducing redundant templates, and limiting overfitting.
Loading 1512.06747v1…