k-Shape: 高效精确的时间序列聚类

k-Shape 是一种高度精确和高效的无监督方法，用于单变量和多变量时间序列聚类。k-Shape 首次亮相于 ACM SIGMOD 2015 会议，被评为（2篇）最佳论文之一，并获得了首届 2015 ACM SIGMOD 研究亮点奖。其扩展版本发表在 ACM TODS 2017 期刊上。此后，k-Shape 在单变量和多变量时间序列数据集上都取得了最先进的性能（即，k-Shape 是最快和最准确的时间序列聚类方法之一，在包含 100 多个数据集的权威基准测试中排名靠前）。

k-Shape 已被广泛应用于多个科学领域（如计算机科学、社会科学、空间科学、工程、计量经济学、生物学、神经科学和医学）、财富 100-500 强企业（如 Exelon、诺基亚和许多金融公司）以及欧洲航天局等组织。

如果您在项目或研究中使用 k-Shape，请引用以下两篇论文：

• ACM SIGMOD 2015
• ACM TODS 2017

参考文献

"k-Shape: 高效精确的时间序列聚类"
John Paparrizos 和 Luis Gravano
2015 ACM SIGMOD 数据管理国际会议（ACM SIGMOD 2015）

@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}
}

"快速精确的时间序列聚类"
John Paparrizos 和 Luis Gravano
ACM 数据库系统学报（ACM TODS 2017），第 42(2) 卷，第 1-49 页

@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}
}

致谢

我们感谢 Teja Bogireddy 对本仓库的宝贵帮助。

我们还要感谢最初的贡献者 Jörg Thalheim 和 Gregory Rehm。初始代码被用于 Sieve。

k-Shape 的 Python 仓库

本仓库包含 k-Shape 的 Python 实现。Matlab 版本请查看这里。

数据

为了便于复现，我们分享了我们在两个权威基准上的结果：

• UCR 单变量档案，包含 128 个单变量时间序列数据集。
  • 在这里下载所有 128 个预处理过的数据集。
• UAE 多变量档案，包含 28 个多变量时间序列数据集。
  • 在这里下载前 14 个预处理过的数据集。
  • 在这里下载剩余 14 个预处理过的数据集。

预处理步骤请查看这里。

安装

我们的代码依赖以下 Python 包：

• numpy
• pytorch

从 pip 安装

$ pip install kshape

从源代码安装

$ git clone https://github.com/thedatumorg/kshape-python
$ cd kshape-python
$ python setup.py install

基准测试

我们展示了在改变时间序列数量、聚类数量和时间序列长度时 k-Shape 的运行时性能。（所有结果都是 5 次运行的平均值。）

使用方法

单变量示例：

import numpy as np
from kshape.core import KShapeClusteringCPU 
from kshape.core_gpu import KShapeClusteringGPU 

univariate_ts_datasets = np.expand_dims(np.random.rand(200, 60), axis=2)
num_clusters = 3

# CPU 模型
ksc = KShapeClusteringCPU(num_clusters, centroid_init='zero', max_iter=100, n_jobs=-1)
ksc.fit(univariate_ts_datasets)
labels = ksc.labels_ # 或 ksc.predict(univariate_ts_datasets)
cluster_centroids = ksc.centroids_

# GPU 模型
ksg = KShapeClusteringGPU(num_clusters, centroid_init='zero', max_iter=100)
ksg.fit(univariate_ts_datasets)

labels = ksg.labels_
cluster_centroids = ksg.centroids_.detach().cpu()

多变量示例:

import numpy as np
from kshape.core import KShapeClusteringCPU 
from kshape.core_gpu import KShapeClusteringGPU 

multivariate_ts_datasets = np.random.rand(200, 60, 6)
num_clusters = 3

# CPU 模型
ksc = KShapeClusteringCPU(num_clusters, centroid_init='zero', max_iter=100, n_jobs=-1)
ksc.fit(univariate_ts_datasets)

labels = ksc.labels_
cluster_centroids = ksc.centroids_

# GPU 模型
ksg = KShapeClusteringGPU(num_clusters, centroid_init='zero', max_iter=100)
ksg.fit(univariate_ts_datasets)

labels = ksg.labels_
cluster_centroids = ksg.centroids_.detach().cpu()

另请参阅示例了解 UCR/UAE 数据集聚类

结果

下表包含 k-Shape 在单变量和多变量数据集上进行 10 次运行的平均兰德指数(RI)、调整兰德指数(ARI)和归一化互信息(NMI)准确度值。

注意：我们使用单核实现收集了这些结果。

服务器规格：AMD Ryzen 9 5900HX 8核 3.30 GHz，16GB RAM。

GPU规格：NVIDIA GeForce RTX 3070，8GB显存。

单变量结果:

多变量结果：