计算机科学 ›› 2017, Vol. 44 ›› Issue (9): 40-44.doi: 10.11896/j.issn.1002-137X.2017.09.007
• CRSSC-CWI-CGrC 2016 • 上一篇 下一篇
徐健锋,何宇凡,张远健,汤涛
XU Jian-feng, HE Yu-fan, ZHANG Yuan-jian and TANG Tao
摘要： 动态时间弯曲距离算法(DTW)是目前公认的最有效的时间序列相似性计算方法之一,但是较高的时间复杂度一直是其主要缺点。快速弯曲距离算法(FTW)能有效提高DTW的计算速度,但是该算法对不同粒度时间序列剪枝的行为是典型的二支决策,与人类处理不确定问题时普遍采用的三支判断不同。因此,通过将三支决策理论引入到DTW算法的优化工作中,建立了DTW三支决策模型；然后对DTW三支决策模型中的决策阈值α和β进行了基于误识别率的推导,并且给出了具体求解阈值α和β的模拟退火算法；最后基于上述理论提出了基于弯曲距离三支决策的时序相似性算法(3WD-DTW)。通过对比实验表明,与FTW算法相比,3WD-DTW算法在保持较快的计算速度的前提下明显提升了计算准确度,使其接近DTW的水平。
| [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].http://www.cs.ucr.edu/~eamonn/time_series_data. |
| No related articles found! |
|
||
首页