论文阅读：加速时间序列聚类的新策略

Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy

研究的问题

本文提出了一种新的策略，来应对海量数据下DTW对时间序列的聚类问题。本文提出的新方法TADPole（Time-series Anytime DP）通过一种可接受的剪枝策略，避免昂贵的距离计算成本，从而加速聚类进程。

研究动机

对时间序列的聚类仍然在很多领域有重要应用价值，人们普遍认为DTW在大多数领域是最好的，几乎总是优于欧氏距离。然而有研究指出，面对海量数据，基于欧式距离的动态时间规整策略无法展现出其优越性，也就是说DTW对时间序列的有效聚类仍然是个挑战。因此本文创造性的提出一种新的策略，来加速时间序列聚类任务的进程。

先进性与贡献

  1. 扩充DP框架来解决大型时间序列的聚类问题
  2. 增加DP框架来解决大型时间序列聚类问题
  3. 结合DTW与上下限修剪策略，修剪不必要的计算，避免了昂贵的距离计算成本
  4. 用启发式算法来将不可避免的计算排序成一个最有效的优先顺序
  5. 可以很容易的扩展和应用到多元时间序列的聚类问题

具体方法

  1. 计算数据集DTW距离的上下界矩阵
  2. 采用上下限修剪策略计算局部密度
  3. 用上下限修剪策略计算高密度样本的NN距离
  4. 结合DP算法完成聚类任务
  5. 扩展到多元时间序列只需对所有维度的相应计算求和

优缺点与思考

本文提出的新策略是在DP聚类算法的基础上，扩展得到一个基于DTW和上下限修剪策略的DP聚类框架，目的就是应对海量的数据集，只将计算资源放在真正需要的过程中，有效节省了计算成本，同时也能很好地完成聚类任务。