k-Shape: Efficient and Accurate Clustering of Time Series
研究的问题
本文提出一种新的时间序列聚类算法k-Shape，该方法基于一种考虑时间序列形状的距离度量和聚类质心计算方法，实现了独立于领域的时间序列聚类问题的高准确性和高稳健性。
研究动机
大量的时间序列几乎出现在所有的学科中，时间序列的聚类研究十分广泛。大多数聚类算法的性能取决于距离测量的度量，而且不同领域对时间序列的聚类要求差异巨大，同时传统方法无法扩展到大数据时代下的海量数据集。因此本文提出一种新的时间序列聚类方法，该方法基于时间序列形状，高效且独立于领域。
先进性与贡献
基于互相关度量提出了一种新的距离度量——平移和位移不变度量，以及新的聚类质心的计算方法。提出了k-Shape方法，一种基于质心的时间序列聚类方法。。
具体方法：
- 准备工作：
- 基于互相关测量得出的新的距离度量算法SBD（x，y），该算法将得到时间序列x和y的不相似度dist，以及y针对x的对齐序列y’
- 基于SBD得出的新的聚类质心计算算法ShapeExtraction（X，C），该算法将得到聚类质心序列
- 对于包含n个时间序列（每个序列m个数据点）的数据集X，和目标聚类数k，在k-Shape算法内进行多次循环迭代，迭代内容如下
- 通过ShapeExtraction方法对每个聚类更新聚类质心序列，得到k个类更新后的聚类质心序列
- 通过SBD方法对聚类质心序列和n个时间序列的距离度量，得到n个不相似度和n个序列针对于质心序列的对齐序列
- 当不相似度满足要求时，对该时间序列归类标记处理
优缺点及思考
本文提出的新的时间序列聚类方法，独立于研究领域，高效且稳健，比现有的其他时间序列的聚类算法都更实用，其可扩展性和鲁棒性也很高。通过与常用的距离度量：ED、DTW、cDTW做比较，证明了本文基于互相关测量提出的距离度量SBD方法的优越性。同时实验也通过与其他扩展聚类算法做比较，证明了k-Shape方法的优越性。
本文提出的基于互相关测量的距离度量SBD同DTW等同样优越，但更高效。本文着重关注高效且与领域无关的时间序列聚类，能够保留时间序列的形状，并在缩放和位移不变性下有效计算聚类质心，具有很强的聚类性能。本文研究重点是针对于单变量时间序列的聚类问题，但目前在大数据时代，海量数据集往往都是多属性多变量的，在这种情况下，如何有效地拓展该方法以满足多元时间序列聚类问题的需要，具有很重要的意义。
2018.10.7
