markdregan / k-nearest-neighbors-with-dynamic-time-warping

Python implementation of KNN and DTW classification algorithm

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"

k-nearest-neighbors-with-dynamic-time-warping's Issues

can training data is 3-D form?

I am new to Dynamic Time Warping and your note helps quite a lot. Thank you for your sharing. My input
data is 3-D, having shape of (n_samples, n_timesteps,n_features). I am not sure how to transfer it into using the model. Thank you so much!

saving the trained model

hey, thanks for the wonderful tutorial, I am wondering how to save once the model is trained, I tried using joblib (sklearn), after saving whenever I am loading the model it starts training again. can you please help me with that.

Error in executing KNN+DTW using HAR dataset - Pls help !!!

Hi Mark,

Glad to know you...am NOT a proficient python user however I'm quite familiar in writing and running few scripts in Ipython Notebook. I came across your k-NN+DTW classifier source code which is quite self-explanatory and well written on your Github page - appreciate that.

However, I seek your help in getting started running your demo script with HAR dataset first to gain understanding about implementation of some of your routines.

I encounter an error when reading the datasets at the following lines...

Loop through datasets

for x in x_train_file:
x_train.append([float(ts) for ts in x.split()])

Attached is the snapshot of my error in IPython terminal

Could you pls help me rectify & rerun this without error?

Thanks,
Bala

Very slow execution for middle to large datasets

Hi, is there any change in the code that you might recommend to speed up the execution of the algorithm?

import numpy & scipy in knn_dtw_class.py

np.shape & scipy.spatial.distance are being used w/o previous import of those modules.

running under python 3.6

First of all, thanks for this wonderful example. I have downloaded it and tried to run under python 3.6. It shows an unresolved error in the following line:
dm = squareform(dm)

May I know how to resolve this?

will it work for multivariate time series classification for example mixture of categorical and continues data?

will it work for  multivariate  time series classification for example mixture of categorical and continues data? 
for example at time t1 we have observation: red, 2.4 , 5, 12.456 and time t2: green, 3.5, 2, 45.78; time t3: black, 5.6, 7, 23.56; t4: red, 2.1, 5, 12.6 ?

AttributeError: ProgressBar instance has no attribute 'animate_noipython'

This is the error i am getting while trying to execute the code posted here. Please help me resolve that asap

DTW uses feature data instead of raw data

Hi,

Perhaps I'm not understanding your code properly, but I was hoping you could clear some things up. When performing DTW on the dataset you read in data/UCI-HAR-Dataset/train/X_train.txt - This is the feature-engineered dataset, I believe. It contains 561 columns instead of 128, which the README of the data indicates is the number of observations per window.

The part I don't understand is that the features are all dependent on the same observation window. (I checked this by adding an assertion in KnnDtw._dtw_distance()) In that case how can you perform DTW on them when there isn't a time-scale to warp? Or - more likely - am I misunderstanding DTW?