Balázs Hidasi

Data Mining Researcher

ShiftTree

Overview

ShiftTree is an unique, model-based approach for time series classification. The basic idea is that we assign a cursor (or eye) to each series and move this to certain positions on the time axis. We generate dynamic attributes by answering two questions: (1) Where to look? (2) What to look at?. The answer to the first question tells us where to move the cursor (e.g.: forward 100 steps, to the previous local maxima, etc), while the second answer defines the calculation of the dynamic attributes (e.g.: value at that point, the weighted avarage of the values around the position, the difference in the current and previous cursor position, etc). These dynamic attributes then used in a binary decision tree.
Numerous extensions were added to this basic idea, that resulted in a model-based time series classifier that has several advantages over nearest neighbour based approaches. The accuracy of classification of this method is usually better than NN approaches when the number of training examples per number of class labels is sufficiently highy; and is usually worse otherwise.
The research of ShiftTree is currently suspended, because the basic algorithm is quite developed. Although there are a lot of different new research directions connecting to the ShiftTree, I'm currently focusing on the research of recommender algorithms and my PhD. I will continue the research later eventually.

Main advantages

  • Faster labeling
  • Generalization ability
  • Interpretable model
  • Domain independent method
  • Experts' knowledge can be included

Main drawbacks

  • Larger training set required
  • Selection of an initial operator set is required

Detailed description

Coming soon!
Until it's done you can read more about the ShiftTree in the papers/presentations listed below.

Resources

Paper for ECML/PKDD 2011

The draft version of the paper about ShiftTree that was presented at ECML/PKDD 2011. Contains the description of the model, its learning, some extensions and of course the results.

Slideshow for ECML/PKDD 2011

The slideshow I used at ECML/PKDD 2011. The only english slideshow about the ShiftTree until this time.
SlideShare version

Poster for ECML/PKDD 2011

Poster about the ShiftTree, that summarizes its key aspects. Great for taking an overview of the method.

Slideshow for ML@BP (HUN)

The most complete slideshow about the ShiftTree introducing all aspects and some of the unused features that were cut during the developement of the method. It was presented at ML@BP, 20. February 2012. The presentation was about 1.5 hours long, so it's quite a long slideshow. Contains some longer animation sequences.
SlideShare version (in Hungarian)

M.Sc. Thesis (HUN)

Probably the most complete dissertation about the ShiftTree. Originally it is about the extension and developement of the method thus some important aspects are only cited but not explained in this work (e.g.: interpretability).

B.Sc. Thesis (HUN)

This dissertation is about an early version of the method and thus some of its statements are outdated. Unfortunately it contains some minor errors as well.

Implementation

Although I implemented ShiftTree twice, neither of them is suitable for public release. I planned to do a third implementation that can be used by others, but I never really started it because I was and am busy with other stuff. Thats why there is no implementation available for now. I am willing to make it, but I don't think that it will be finished any time soon.