Skip to content

markdregan/K-Nearest-Neighbors-with-Dynamic-Time-Warping

Repository files navigation

K Nearest Neighbors & Dynamic Time Warping

View IPython notebook

When it comes to building a classification algorithm, analysts have a broad range of open source options to choose from. However, for time series classification, there are less out-of-the box solutions.

I began researching the domain of time series classification and was intrigued by a recommended technique called K Nearest Neighbors and Dynamic Time Warping. A meta analysis completed by Mitsa (2010) suggests that when it comes to timeseries classification, 1 Nearest Neighbor (K=1) and Dynamic Timewarping is very difficult to beat [1].

This repo contains a python implementation (and IPython notebook) of KNN & DTW classification algorithm.

The following IPython notebook evaluates the KNN and DTW classifer by using it to classify human activities (sitting, walking, lying) when given timeseries data from a smart phones gyroscope and accelerometer (HAR dataset).

Human Activity Recognition Dataset

The Human Activity Recognition Dataset (HAR) dataset is chosen to test the classification performance of DTW & KNN [3].

The experiments were carried out with a group of 30 volunteers within an age bracket of 19-48 years. Each person performed six activities (walking, walking upstairs, walking downstairs, sitting, standing and laying) wearing a smartphone (Samsung Galaxy S II) on the waist. Using its embedded accelerometer and gyroscope, we captured 3-axial linear acceleration and 3-axial angular velocity at a constant rate of 50Hz. The experiments have been video-recorded to label the data manually.

References

  1. Mitsa (2010). Temporal Data Mining (Chapter on Temporal Classification).
  2. Xi (2006). Fast Time Series Classification Using Numerosity Reduction.
  3. Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra and Jorge L. Reyes-Ortiz. Human Activity Recognition on Smartphones using a Multiclass Hardware-Friendly Support Vector Machine. International Workshop of Ambient Assisted Living (IWAAL 2012). Vitoria-Gasteiz, Spain. Dec 2012. Read Paper

Credit

  • The progressbar used in the DtwKnn() class was taken from PYMC
  • The matplotlib style and IPython notebook was taken from Cameron Davidson-Pilon's excelent "Bayesian Methods for Hackers"