[1]李成为,王 屿,郑迪威.基于 MR 框架的不确定时间序列相似性计算方法[J].计算机技术与发展,2018,28(10):27-31.[doi:10.3969/ j. issn.1673-629X.2018.10.006]
　LI Cheng-wei,WANG Yu,ZHENG Di-wei.A Similarity Computation Method of Uncertain Time Series Based on MR Framework[J].,2018,28(10):27-31.[doi:10.3969/ j. issn.1673-629X.2018.10.006]
点击复制

基于 MR 框架的不确定时间序列相似性计算方法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
28
期数:
2018年10期
页码:
27-31
栏目:
智能、算法、系统工程
出版日期:
2018-10-10

文章信息/Info

Title:
A Similarity Computation Method of Uncertain Time Series Based on MR Framework
文章编号:
1673-629X(2018)10-0027-05
作者:
李成为; 王 屿; 郑迪威
南京航空航天大学 计算机科学与技术学院,江苏 南京 211106
Author(s):
LI Cheng-wei; WANG Yu; ZHENG Di-wei
School of Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
关键词:
不确定时间序列; 相似性计算; 动态时间规整; FastDTW; MapReduce
Keywords:
uncertain time series; similarity calculation; dynamic time warping; FastDTW; MapReduce
分类号:
TP301
DOI:
10.3969/ j. issn.1673-629X.2018.10.006
文献标志码:
A
摘要:
为了更好地适应大规模不确定时间序列数据的相似性耗时多、计算效率低的问题,基于传统的动态时间规整(DTW)相似性计算算法,在 FastDTW 算法已经进行粗细粒度化剪枝节省部分运算时间的情况下,通过融入 MapReduce 计算框架,提出一种不确定时间序列的相似性计算算法 MR-FastDTW。 该算法在 FastDTW 算法执行递归返回阶段时需要计算的递归矩阵,用 MapReduce 的思想分成多个子矩阵。 同时对求得的路径周围的子矩阵进行并行计算,最后汇总范围内子矩阵的结果,得出最终路径。 实验结果表明,MR-FastDTW 算法解决了 FastDTW 在递归返回段执行到一定程度后计算量大的问题,提高了计算速度和计算准确性;相比于经典的 DTW 及其改进的 FastDTW 算法,具有更高的效率。
Abstract:
In order to better adapt to high time-consuming and inefficient computation of large-scale and indefinite time-series data,based on the traditional dynamic time warping (DTW) similarity algorithm,in the case of saving some computing time by FastDTW which has implemented the coarse-grained pruning,we propose a MR-FastDTW algorithm to calculate the similarity of uncertain time series by integrating MapReduce framework. The algorithm needs to calculate the recursive matrix when the FastDTW algorithm performs the recursive return phase,which is divided into several sub-matrices by the idea of MapReduce. At the same time,the sub-matrices around the obtained path are calculated in parallel. Finally,the results of sub-matrices in the range are summarized and the final path is obtained. Experimental shows that the MR-FastDTW algorithm can solve the problem of large amount of computation when FastDTW is executed to a certain extent in the recursion return segment,and improve the calculation speed and accuracy. Compared with the classic DTW and its improved FastDTW algorithm,it has higher efficiency.

相似文献/References:

[1]范虎,花伟伟.协同过滤推荐算法的研究与改进[J].计算机技术与发展,2013,(09):66.
　FAN Hu[],HUA Wei-wei[].Research and Improvement of Collaborative Filtering Recommendation Algorithm[J].,2013,(10):66.
[2]汤其婕,朱小萍.基于关键点的不确定时间序列线性降维方法[J].计算机技术与发展,2018,28(08):22.[doi:10.3969/ j. issn.1673-629X.2018.08.005]
　TANG Qi-jie,ZHU Xiao-ping.A Linear Dimensionality Reduction Method Based on Key Points for Uncertain Time Series[J].,2018,28(10):22.[doi:10.3969/ j. issn.1673-629X.2018.08.005]
[3]张景,牛耘. 中文微博评价对象识别研究[J].计算机技术与发展,2017,27(01):6.
　ZHANG,Jing NIU Yun. Research on Opinion Target Extraction in Chinese Microblogs[J].,2017,27(10):6.
[4]汤其婕,王玙.基于I-GARCH的不确定时间序列概率分布推算[J].计算机技术与发展,2018,28(12):23.[doi:10．3969/j． issn．1673－629X．2018．12．005]
　TANG Qijie,WANG Yu.Probability Distribution Estimation of Uncertain Time Series Based on I－GARCH[J].,2018,28(10):23.[doi:10．3969/j． issn．1673－629X．2018．12．005]
[5]王 玙,左良利.关系数据库支持的不确定时间序列存储[J].计算机技术与发展,2019,29(11):7.[doi:10. 3969 / j. issn. 1673-629X. 2019. 11. 002]
　WANG Yu,ZUO Liang-li.Research on Storage of Uncertain Time Series in Relational Databases[J].,2019,29(10):7.[doi:10. 3969 / j. issn. 1673-629X. 2019. 11. 002]

更新日期/Last Update: 2018-10-10