Computer Science ›› 2017, Vol. 44 ›› Issue (9): 40-44.doi: 10.11896/j.issn.1002-137X.2017.09.007

Previous Articles     Next Articles

Similarity Algorithm Based on Three Way Decision of Time Warping Distance

XU Jian-feng, HE Yu-fan, ZHANG Yuan-jian and TANG Tao   

  • Online:2018-11-13 Published:2018-11-13

Abstract: Dynamic time warping (DTW) is widely accepted as one of the most effective methods for the similarity measurement of time series,but suffers from high time complexity.Fast search method for dynamic time wrapping (FTW) is demonstrated to accelerate DTW.The core of pruning is however a typical two-way decision rather than three-way decision,which is different from actions taken with uncertain issues.By incorporating three-way decision,an optimized DTW model three-way decision DTW (3WD-DTW) is developed first.The decision thresholds α,β are derived by solving an optimization problem with the objective of minimizing error rate.A novel simulated annealing algorithm is thus proposed.Finally,similarity algorithm based on three way decision of time warping distance is presented.Experiments show that 3WD-DTW is comparable in computing complexity as compared to FTW.In terms of accuracy,3WD-DTW outperforms FTW significantly and approximates to DTW.

Key words: Three-way decision,Dynamic time warping,Simulated annealing,Decision threshold

[1] 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.
[2] WANG Q,MEGALOOIKONOMOU V.A dimensionality reduction technique for efficient time series similarity analysis[J].Information systems,2008,33(1):115-132.
[3] KEOGH E,RATANAMAHATANA C A.Exact indexing ofdynamic time warping[J].Knowledge & Information Systems,2010,7(3):358-386.
[4] LI H L,YANG L B.Extensions and relationships of some exi-sting lower-bound functions for dynamic time warping[J].Journal of Intelligent Information Systems,2014,43(1):59-79.
[5] SUN L,YANG Y J,LIU W H.Trended DTW Based on Piecewise Linear Approximation for Time Series Mining[C]∥2011 IEEE 11th International Conference on Data Mining Workshops (ICDMW).IEEE,2011:877-884.
[6] SAKURAI Y,YOSHIKAWA M,FALOUTSOS C.FTW:fastsimilarity search under the time warping distance[C]∥Procee-dings of the Twenty-fourth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.ACM,2005:326-337.
[7] YAO Y Y.An outline of a theory of three-way decisions[M]∥Rough Sets and Current Trends in Computing.Springer Berlin Heidelberg,2012:1-17.
[8] YAO Y.Three-Way Decision:An Interpretation of Rules in RoughSet Theory[M]∥ Rough Sets and Knowledge Technology.Springer-Verlag,2009:642-649.
[9] YAO Y Y.Three-Way Decisions and Cognitive Computing[J].Cognitive Computation,2016,8(4):543-554.
[10] LI F,YE M,CHEN X.An extension to Rough c -means clustering based on decision-theoretic Rough Sets model[J].International Journal of Approximate Reasoning,2014,55(1):116-129.
[11] YU H,LIU Z G,WANG G Y.An automatic method to determine the number of clusters using decision-theoretic rough set[J].International Journal of Approximate Reasoning,2014,55(1):101-115.
[12] LIU D ,LI T R,HU P,et al.Multiple-Category Classification with Decision-Theoretic Rough Sets[M]∥Rough Set and Knowledge Technology.Springer Berlin Heidelberg,2010:703-710.
[13] ZHANG Z,WANG R.Applying Three-way Decisions to Sentiment Classification with Sentiment Uncertainty[M] ∥Rough Sets and Knowledge Technology.Springer International Publishing,2014:720-731.
[14] JIA X Y,LIAO W,TANG Z,et al.Minimum cost attribute reduction in decision-theoretic rough set models[J].Information Sciences,2013,219:151-167.
[15] LI H X,ZHOU X,ZHAO J,et al.Non-Monotonic Attribute Reduction in Decision-Theoretic Rough Sets[J].Fundamenta Informaticae,2013,126(4):415-432.
[16] JIA X Y,ZHENG K,LI W W,et al.Three-Way Decisions Solution to Filter Spam Email:An Empirical Study[M]∥Rough Sets and Current Trends in Computing.Springer Berlin Heidelberg,2012:287-296.
[17] ZHOU B,YAO Y Y,LUO J G.A Three-Way Decision Ap-proach to Email Spam Filtering[C]∥Advances in Artificial Intelligence,23rd Canadian Conference on Artificial Intelligence(AI 2010).Ottawa,Canada,2010:28-39.
[18] LI F,MIAO D Q,LIU C H,et al.Image segmentation decisionrough set[J].CAAI Transactions on Intelligent System,2014(2):143-147.(in Chinese) 李峰,苗夺谦,刘财辉,等.基于决策粗糙集的图像分割[J].智能系统学报,2014(2):143-147.
[19] LI X Y,ZHANG Q Q.An image classification algorithm based on compatible granular model and three decision making[J].Computing Technology and Automation,2014,33(4):93-96.(in Chinese) 李晓艳,张倩倩.基于相容粒模型和三支决策的图像分类算法[J].计算技术与自动化,2014,33(4):93-96.
[20] JIA X Y,SHANG L.A Simulated Annealing Algorithm forLearning Thresholds in Three-way Decision-theoretic Rough Set Model[J].Journal of Chinese Computer Systems,2013,34(11):2603-2606.(in Chinese) 贾修一,商琳.一种求三支决策阈值的模拟退火算法[J].小型微型计算机系统,2013,34(11):2603-2606.
[21] LIN F T,KAO C Y,HSU C C.Applying the genetic approach to simulated annealing in solving some NP-hard problems[J].IEEE Transactions on Systems Man & Cybernetics,1993,23(6):1752-1767.
[22] YAO Y Y.Interval sets and interval-set algebras[C]∥IEEE International Conference on Cognitive Informatics(ICCI 2009).Hong Kong,China,2009:307-314.
[23] ZADEH L A.Fuzzy sets*[J].Information & Control,1965,8(3):338-353.
[24] PEDRYCZ W.Shadowed sets:representing and processing fuzzy sets[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,1998,28(1):103-109.
[25] ABDULLAH S,GOLAFSHAN L,ZAKREE M,et al.Re-heat simulated annealing algorithm for rough set attribute reduction[J].International Journal of Physical Sciences,2011(8):2083-2089.
[26] CHEN Y P,EAMONN K,HU B,et al.The UCR Time Series Classification Archive[DB/OL].

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .