弹性粗粒度动态弯曲时序相似性算法

doi:10.11772/j.issn.1001-9081.2016.06.1639

计算机应用 ›› 2016, Vol. 36 ›› Issue (6): 1639-1644.DOI: 10.11772/j.issn.1001-9081.2016.06.1639

弹性粗粒度动态弯曲时序相似性算法

陈明威¹, 孙丽华¹, 徐健锋^1,2

1. 南昌大学软件学院, 南昌 330047;
2. 同济大学计算机科学与技术系, 上海 201804

收稿日期:2015-11-10 修回日期:2016-01-18 出版日期:2016-06-10 发布日期:2016-06-08
通讯作者: 陈明威
作者简介:陈明威(1990-),男,河南安阳人,硕士研究生,主要研究方向:流数据挖掘、粒计算、数据分析、深度学习;孙丽华(1955-),女,江西南昌人,教授,博士,主要研究方向:流数据挖掘、粒计算、人工智能;徐健锋(1973-),男,江西南昌人,副教授,博士研究生,CCF会员,主要研究方向:流数据挖掘、粒计算、数据挖掘、深度学习。
基金资助:
国家自然科学基金资助项目(61070139,61273304)。

Temporal similarity algorithm of coarse-granularity based dynamic time warping

CHEN Mingwei¹, SUN Lihua¹, XU Jianfeng^1,2

1. Software College, Nanchang University, Nanchang Jiangxi 330047, China;
2. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China

Received:2015-11-10 Revised:2016-01-18 Online:2016-06-10 Published:2016-06-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61070139, 61273304).

摘要/Abstract

摘要： 针对动态时间弯曲(DTW)算法在提高计算速度同时不能兼顾分类正确率的问题,提出了一种基于朴素粒计算思想的弹性粗粒度动态时间弯曲(CG-DTW)算法。首先,通过计算时序方差特征的方法来获取较优的时序粒度,用粒度特征代替原始序列;其次,再代入执行DTW算法,允许动态调整被比较时序粒间的弹性大小,从而获得相对最优的时序对应粒;最后,在对应最优粒的情况下计算DTW距离。同时引入下界函数的提前终止策略进一步提高CG-DTW算法效率。实验结果表明,所提算法要比经典算法运行速率提高21.4%左右,比降维策略算法正确率提高近32.3个百分点,尤其是长序列的分类,CG-DTW能够在保持正确率的情况下兼顾较高的运行效率。CG-DTW在实际应用中能适应不确定长序列分类。

关键词: 时序, 时间粒, 动态弯曲, 弹性

Abstract: The Dynamic Time Warping (DTW) algorithm cannot keep high classification accuracy while improving the computation speed. In order to solve the problem, a Coarse-Granularity based Dynamic Time Warping (CG-DTW) algorithm based on the idea of naive granular computing was proposed. First of all, the better temporal granularities were obtained by computing temporal variance features, and the original series were replaced by granularity features. Then, the relatively optimal corresponding temporal granularity was obtained by executing DTW with dynamically adjusting intergranular elasticity of granularities compared. Finally, the DTW distance was calculated in the case of the corresponding optimal granularity. During this progress, an early termination strategy of lower bound function was introduced for further improving the CG-DTW algorithm efficiency. The experimental results show that, the proposed algorithm was better than classical algorithm in running rate with increasing by about 21.4%, and better than dimension reduction strategy algorithm in accuracy with increasing by about 32.3 percentage points.Especially for the long time sequences classification, CG-DTW takes consideration into both high computing speed and better classification accuracy. In actual applications, CG-DTW can adapt to long time sequences classification with uncertain length.

Key words: time series, time grain, dynamic bending, elastic

中图分类号:

TP301.6

陈明威, 孙丽华, 徐健锋. 弹性粗粒度动态弯曲时序相似性算法[J]. 计算机应用, 2016, 36(6): 1639-1644.

CHEN Mingwei, SUN Lihua, XU Jianfeng. Temporal similarity algorithm of coarse-granularity based dynamic time warping[J]. Journal of Computer Applications, 2016, 36(6): 1639-1644.

参考文献

[1] LIAO T W. Clustering of time series data-a survey[J]. Pattern Recognition, 2005, 38(11): 1857-1874.
[2] ZHANG X H, LIU J Q, DU Y, et al. A novel clustering method on time series data[J]. Expert Systems with Applications, 2011, 38(9): 11891-11900.
[3] JEONG Y S, JEONG M K, OMITAOMU O A. Weighted dynamic time warping for time series classification[J]. Pattern Recognition, 2011, 44(9): 2231-2240.
[4] GULLO F, PONTI G, TAGARELLI A, et al. A time series representation model for accurate and fast similarity detection[J]. Pattern Recognition, 2009, 42(11): 2998-3014.
[5] WANG Q, MEGALOOIKONOMOU V. A dimensionality reduction technique for efficient time series similarity analysis[J]. Information Systems, 2008, 33(1): 115-132.
[6] FALOUTSOS C, BANGANATHAN M, MANOLOPOULOS Y. Fast subsequence matching in time series databases[J]. ACM SIGMOD Record, 1994, 23(2): 419-429.
[7] RAFIEI D, MENDELZON A. Similarity-based queries for time series data[J]. ACM SIGMOD Record, 1997, 26(2): 13-25.
[8] CHAN K P, FU A W C. Efficient time series matching by wavelets[C]//Proceedings of the IEEE 29th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 1999: 126-133.
[9] LI H L, YANG L B. Extensions and relationships of some existing lower-bound function for dynamic time warping[J]. Journal of Intelligent Information Systems, 2014, 43(1): 59-79.
[10] JAIN B J. Generalized gradient learning on time series[J]. Machine Learning, 2015,100(2): 587-608.
[11] IZAKIAN H, PEDRYCZ W, JAMAL I. Fuzzy clustering of time series data using dynamic time warping distance[J]. Engineering Applications of Artificial Intelligence, 2015, 39: 235-244.
[12] KEOGH E. Exact indexing of dynamic time warping[C]//Proceedings of the 28th International Conference on Very large Data Bases. San Jose, CA: VLDB Endowment, 2002: 406-417.
[13] KEOGH E, RATANAMAHATANA C A. Exact indexing of dynamic time warping[J]. Knowledge and Information Systems, 2005, 7(3): 358-386.
[14] KIM S W, PARK S, CHU W W. An index-based approach for similarity search supporting time warping in large sequence databases[C]//Proceedings of the 200117th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2001: 607-614.
[15] YI B K, JAGADISH H V, FALOUTSOS C. Efficient retrieval of similar time sequences under time warping[C]//Proceedings of the 14th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 1998: 201-208.
[16] KIM S W, YOON J, PARK S, et al. Shape-based retrieval of similar subsequences in time-series databases[C]//SAC'02: Proceedings of the 2002 ACM Symposium on Applied Computing. New York: ACM, 2002: 438-445.
[17] PARK S, KIM S W, CHU W W. Segment-based approach for subsequence searches in sequence databases[C]//SAC'01: Proceedings of the 2001 ACM Symposium on Applied Computing. New York: ACM, 2001: 248-252
[18] KREMER H, GUNNEMANN S, LVANESCU A M, et al. Efficient processing of multiple DTW queries in time series databases[C]//SSDBM 2011: Proceedings of the 23rd International Conference on Scientific and Statistical Database Management. Berlin: Springer, 2011: 150-167
[19] KEOGH E, ZHU Q, HU B, et al. The UCR time series classification/clustering[EB/OL].[2015-09-12]. http://www.cs.ucr.edu/*eamonn/time_series_data/.
[20] RAKTHANMANON T, CAMPANA B, MUEEN A, 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. New York: ACM, 2012: 262-270.
[21] 李俊奎.时间序列相似性问题研究[D].武汉:华中科技大学,2008:33-65.(LI J K. Research on similarity of time series[D]. Wuhan: Huazhong University of Science and Technology, 2008: 33-65.)
[22] ZHANG Z, TANG P, DUAN R B. Dynamic time warping under point wise shape context[J]. Information Sciences, 2015, 315: 88-101.
[23] SUN L, YANG Y J, LIU W H. Trended DTW based on piecewise linear approximation for time series mining[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops. Washington, DC: IEEE Computer Society, 2011: 877-884.
[24] JAMBHALE S S, KHAPARDE A. Gesture recognition using DTW & piecewise DTW[C]//Proceedings of the 2014 International Conference on Electronics and Communication Systems. Piscataway, NJ: IEEE, 2014: 1-5.
[25] HILLS J, LINES J, BARANAUSKAS E, et al. Classification of time series by shapelet transformation[J]. Data Mining and Knowledge Discovery, 2014, 28(4): 851-881.
[26] CAI Q L, CHEN L, SUN J L. Piecewise statistic approximation based similarity measure for time series[J]. Knowledge-Based Systems, 2015, 85(C): 181-195.
[27] SAKURAI Y, YOSHIKAWA M, FALOUTSOS C. FTW: fast similarity search under the time warping distance[C]//Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2005: 326-337.

弹性粗粒度动态弯曲时序相似性算法

Temporal similarity algorithm of coarse-granularity based dynamic time warping

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	孟凡, 陈广, 王勇, 高阳, 高德群, 贾文龙. 基于多粒度时序结构表示的异常检测算法在储层含油性检测中应用[J]. 计算机应用, 2021, 41(8): 2453-2459.
[2]	武维, 李泽平, 杨华蔚, 林川, 王忠德. 融合内容特征和时序信息的深度注意力视频流行度预测模型[J]. 计算机应用, 2021, 41(7): 1878-1884.
[3]	姚杰, 程春玲, 韩静, 刘峥. 云工作流中基于多任务时序卷积网络的异常检测方法[J]. 计算机应用, 2021, 41(6): 1701-1708.
[4]	杨鲜, 赵计生, 强保华, 米路中, 彭博, 唐成华, 李宝莲. 基于改进的BSMOTE和时序特征的风机故障采样算法[J]. 计算机应用, 2021, 41(6): 1673-1678.
[5]	田志强, 邓春华, 张俊雯. 基于骨骼时序散度特征的人体行为识别算法[J]. 计算机应用, 2021, 41(5): 1450-1457.
[6]	张凌哲, 黄向东, 乔嘉林, 勾王敏浩, 王建民. 面向时序数据的两阶段日志结构合并树文件合并框架[J]. 计算机应用, 2021, 41(3): 618-622.
[7]	任媛媛, 汪传建. 数据异常情况下遥感影像时间序列分类算法[J]. 计算机应用, 2021, 41(3): 662-668.
[8]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.
[9]	温雯, 刘芳, 蔡瑞初, 郝志峰. 面向群组用户时序行为的动态推荐算法[J]. 计算机应用, 2021, 41(1): 60-66.
[10]	张晓晗, 冯爱民. 基于经验模态分解和长短期记忆神经网络的短期交通流量预测[J]. 计算机应用, 2021, 41(1): 225-230.
[11]	律睿慜, 梅莉琳, 邢红姹, 孟磊, 昃跃峰. 基于马尔可夫链的书画时序感量化方法[J]. 计算机应用, 2021, 41(1): 295-299.
[12]	钱斌, 郑楷洪, 陈子鹏, 肖勇, 李森, 叶纯壮, 马千里. 基于残差连接长短期记忆网络的时间序列修复模型[J]. 计算机应用, 2021, 41(1): 243-248.
[13]	肖勇, 郑楷洪, 郑镇境, 钱斌, 李森, 马千里. 基于多尺度跳跃深度长短期记忆网络的短期多变量负荷预测[J]. 计算机应用, 2021, 41(1): 231-236.
[14]	苟子安, 张晓, 吴东南, 王艳秋. 分布式存储系统中的日志分析与负载特征提取[J]. 计算机应用, 2020, 40(9): 2586-2593.
[15]	单晓欢, 张志国, 宋宝燕, 任成林. 事件社交网中基于有向标签图及用户反馈的活动推荐方法[J]. 计算机应用, 2020, 40(2): 448-453.