K Nearest Neighbors & Dynamic Time Warping
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
- Mitsa (2010). Temporal Data Mining (Chapter on Temporal Classification).
- Xi (2006). Fast Time Series Classification Using Numerosity Reduction.
- 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"