一种改进的DTW相似性搜索方法
|
摘要
为了更有效的对时间序列进行相似性搜索,本文从相似性度量函数的角度提出一种改进的基于下界函数的DTW (Dynamic Time Warping)相似性搜索方法NLB-FDTW。上述方法定义一种更有效的下界函数,减少DTW的计算开销,加快相似性搜索的速度。为了验证所改进的DTW相似搜索算法的有效性,对一个月的交通流量进行了相似性搜索的实验。结果表明,基于下界函数的DTW在很大程度上减少计算量,NLB-FDTW相较于基于欧氏距离或原始DTW的相似性搜索是一种高效的时间序列相似性搜索方法。
In order to search for the similarity of time series more effectively, this paper proposes an improved DTW(Dynamic Time Warping) similarity search method NLB-FDTW based on the lower bound function from the angle of similarity measure function. This method defines a more efficient lower bound function, which reduces the computation cost of DTW and speeds up the similarity search. In order to verify the effectiveness of the improved DTW similarity search algorithm, this paper conducts a similarity search experiment for one month traffic flow. The results show that the DTW based on the lower bound function reduces the computational complexity to a large extent, and the similarity search based on the Euclidean distance or the original DTW is an efficient method of searching for the similarity of time series.
In order to search for the similarity of time series more effectively, this paper proposes an improved DTW(Dynamic Time Warping) similarity search method NLB-FDTW based on the lower bound function from the angle of similarity measure function. This method defines a more efficient lower bound function, which reduces the computation cost of DTW and speeds up the similarity search. In order to verify the effectiveness of the improved DTW similarity search algorithm, this paper conducts a similarity search experiment for one month traffic flow. The results show that the DTW based on the lower bound function reduces the computational complexity to a large extent, and the similarity search based on the Euclidean distance or the original DTW is an efficient method of searching for the similarity of time series.
引文
[1] N T Son, N H Le, D T Anh. Time series prediction using pattern matching[C]. Computing, Management and Telecommunications(ComManTel), 2013 International Conference on. IEEE, 2013: 401-406
[2] 陶洋,等. 基于DTW的时间序列流相似性搜索方法[J]. 计算机工程与设计, 2017,(12):3291-3297.
[3] 白玉洁. 改进时间序列模型在降雨量预测中的应用研究[J]. 计算机仿真, 2011,28(10):141-145.
[4] 徐健锋,等. 基于弯曲距离三支决策的时序相似性算法[J]. 计算机科学, 2017,44(9): 40-44.
[5] 毛云建,杜秀华. 基于形态特征的时间序列相似性搜索算法[J]. 计算机仿真, 2008,25(1):80-83.
[6] V Kurbalija, et al. The influence of global constraints on similarity measures for time-series databases[J]. Knowledge-Based Systems, 2013.
[7] T Rakthanmanon, et al. Searching and mining trillions of time series subsequences under dynamic time warping[C]. Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012: 262-270
[8] Ada Wai-Chee Fu, et al. Scaling and Time Warping in Time Series Querying[J]. The Vldb Journal—the International Journal on Very Large Data Bases, 2008,17(4):899-921
[9] Eamonn Keogh, Shruti Kasetty. On the Need for Time Series Data Mining Benchmarks: a Survey and Empirical Demonstration[J]. Data Mining and Knowledge Discovery, 2003,7(4):349-371.
[10] Z Wang, et al. Accelerating subsequence similarity search based on dynamic time warping distance with FPGA[C]. Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays. ACM, 2013: 53-62
[11] S W Kim, S Park, W W Chu. An index-based approach for similarity search supporting time warping in large sequence databases[C]. Data Engineering, 2001. Proceedings. 17th International Conference on. IEEE, 2001: 607-614
[12] Eamonn G Keogh. Data, Mining Time Series Data[M]. Springer, 2011:339-3
[2] 陶洋,等. 基于DTW的时间序列流相似性搜索方法[J]. 计算机工程与设计, 2017,(12):3291-3297.
[3] 白玉洁. 改进时间序列模型在降雨量预测中的应用研究[J]. 计算机仿真, 2011,28(10):141-145.
[4] 徐健锋,等. 基于弯曲距离三支决策的时序相似性算法[J]. 计算机科学, 2017,44(9): 40-44.
[5] 毛云建,杜秀华. 基于形态特征的时间序列相似性搜索算法[J]. 计算机仿真, 2008,25(1):80-83.
[6] V Kurbalija, et al. The influence of global constraints on similarity measures for time-series databases[J]. Knowledge-Based Systems, 2013.
[7] T Rakthanmanon, et al. Searching and mining trillions of time series subsequences under dynamic time warping[C]. Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012: 262-270
[8] Ada Wai-Chee Fu, et al. Scaling and Time Warping in Time Series Querying[J]. The Vldb Journal—the International Journal on Very Large Data Bases, 2008,17(4):899-921
[9] Eamonn Keogh, Shruti Kasetty. On the Need for Time Series Data Mining Benchmarks: a Survey and Empirical Demonstration[J]. Data Mining and Knowledge Discovery, 2003,7(4):349-371.
[10] Z Wang, et al. Accelerating subsequence similarity search based on dynamic time warping distance with FPGA[C]. Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays. ACM, 2013: 53-62
[11] S W Kim, S Park, W W Chu. An index-based approach for similarity search supporting time warping in large sequence databases[C]. Data Engineering, 2001. Proceedings. 17th International Conference on. IEEE, 2001: 607-614
[12] Eamonn G Keogh. Data, Mining Time Series Data[M]. Springer, 2011:339-3