Awesome

k-Shape: Efficient and Accurate Clustering of Time Series

k-Shape is a highly accurate and efficient unsupervised method for univariate and multivariate time-series clustering. k-Shape appeared at the ACM SIGMOD 2015 conference, where it was selected as one of the (2) best papers and received the inaugural 2015 ACM SIGMOD Research Highlight Award. An extended version appeared in the ACM TODS 2017 journal. Since then, k-Shape has achieved state-of-the-art performance in both univariate and multivariate time-series datasets (i.e., k-Shape is among the fastest and most accurate time-series clustering methods, ranked in the top positions of established benchmarks with 100+ datasets).

k-Shape has been widely adopted across scientific areas (e.g., computer science, social science, space science, engineering, econometrics, biology, neuroscience, and medicine), Fortune 100-500 enterprises (e.g., Exelon, Nokia, and many financial firms), and organizations such as the European Space Agency.

If you use k-Shape in your project or research, cite the following two papers:

• ACM SIGMOD 2015
• ACM TODS 2017

References

"k-Shape: Efficient and Accurate Clustering of Time Series"<br/> John Paparrizos and Luis Gravano<br/> 2015 ACM SIGMOD International Conference on Management of Data (ACM SIGMOD 2015)<br/>

@inproceedings{paparrizos2015k,
  title={{k-Shape: Efficient and Accurate Clustering of Time Series}},
  author={Paparrizos, John and Gravano, Luis},
  booktitle={Proceedings of the 2015 ACM SIGMOD international conference on management of data},
  pages={1855--1870},
  year={2015}
}

"Fast and Accurate Time-Series Clustering"<br/> John Paparrizos and Luis Gravano<br/> ACM Transactions on Database Systems (ACM TODS 2017), volume 42(2), pages 1-49<br/>

@article{paparrizos2017fast,
  title={{Fast and Accurate Time-Series Clustering}},
  author={Paparrizos, John and Gravano, Luis},
  journal={ACM Transactions on Database Systems (ACM TODS)},
  volume={42},
  number={2},
  pages={1--49},
  year={2017}
}

Acknowledgements

We thank Teja Bogireddy for his valuable help on this repository.

k-Shape's Matlab Repository

This repository contains the Matlab implementation for k-Shape. For the Python version, check here.

Data

To ease reproducibility, we share our results over two established benchmarks:

• The UCR Univariate Archive, which contains 128 univariate time-series datasets.
  • Download all 128 preprocessed datasets here.
• The UAE Multivariate Archive, which contains 28 multivariate time-series datasets.
  • Download the first 14 preprocessed datasets here.
  • Download the remaining 14 preprocessed datasets here.

For the preprocessing steps check here.

Usage

Univariate Example

$ matlab
> Datasets = [cellstr('Coffee')]
> DS = LoadUCRdataset(char(Datasets(i)))
> [labels centroids] = kShape_univariate(DS.Data, length(DS.ClassNames));

Multivariate Example

$ matlab
> Datasets = [cellstr('ERing')]
> DS = LoadUAEdataset(char(Datasets(i)))
> [labels centroids] = kShape_multivariate(DS.Data, length(DS.ClassNames));

Check the Univariate and Multivariate code examples for benchmarking on the UCR and UAE datasets, respectively.

Results

The following tables contain the average Rand Index (RI), Adjusted Rand Index (ARI), and Normalized Mutual Information (NMI) accuracy values over 10 runs for k-Shape on the univariate and multivariate datasets.

Note: We collected the results using a single core implementation.

Server Specifications: Dual Intel(R) Xeon(R) Silver 4116 (24 cores/48 HT), 2.10 GHz, 196GB RAM.

Results on the 128 univariate datasets:

Results on the 28 multivariate datasets: