基于动态时间弯曲的时序数据聚类算法的研究

Novel Algorithm for Time Series Data Mining Based on Dynamic Time Warping

时间序列是一类重要的复杂类型数据 ,时间序列知识发现正成为知识发现的研究热点之一。欧几里的距离及其扩展作为相似测度被广泛应用于时间序列的比较中 ,但是这种距离测度对数据没有好的鲁棒性。动态时间弯曲技术是基于非线性动态编程的一种模式匹配算法。该文提出了基于动态时间弯曲技术的相似搜索算法 ,通过计算时序数据之间的最短弯曲路径来获得序列的匹配。对综合控制时序数据进行基于不同距离测度的聚类分析对比结果表明该文提出的算法有很高的精度和对振幅差异、噪声和线性漂移有强的鲁棒性 。

Time series are important kinds of complex data, while a growing attention has been paid to mining time series knowledge recently. Typically Euclidean distance measure and its variation or extensions are used for comparing time series. However, it may be a brittle distance measure because of less robustness. Dynamic time warp (DTW) is a patter matching algorithm based on nonlinear dynamic programming technique. In this paper, we present a similarity searching algorithm based on DTW, which searches matching sub series by computing the minimization of warp path. Experiments about cluster analysis for two different distance measure are implemented on synthetic control chart time series. The results shows that the measure, presented in this paper, has stronger robustness to amplitude scaling, noise and linear drift for time series, so that it has good value for applications.