基于系数矩阵弧微分的时间序列相似度量
|
摘要
传统时间序列相似度量算法在时间序列发生平移、时间轴伸缩等情况下,需要时间对齐等人工干预,并且时间复杂度较高,不利于后续数据挖掘处理。为此,基于系数矩阵弧微分提出时间序列相似度量算法。引入回归分析中的最小二乘思想,通过构建系数矩阵获取时间序列形态属性向量基,实现序列曲线的连续化。在此基础上,应用连续函数的弧微分与曲率半径的关系进行时间序列的相似度量。实验结果表明,该算法具有较强的鲁棒性,不仅能实现微观意义上序列之间的相似度量(距离相近),而且能够完成宏观意义上的相似度量(形态相近)。
The traditional similarity measurement algorithm of time series needs human intervention such as time alignment,which has higher time complexity and is bad for following data mining. For the problems above,this paper puts forward similarity measurement algorithm of time series based on coefficient matrix arc differential. It introduces the thought of least-square method in regression analysis,obtains vector basement of time series form attribution by constructing matrix and achieves the continuous sequence curve simultaneously. On this basis,it implements similarity measurement of time series finally by using the relationship of arc differential and curvature radius of the continuous function. Experimental results showthat the proposed algorithm has stronger robustness,which can not only achieve similarity measurement in microscopic(lies in distance proximity),but also achieve similarity measurement in macroscopic(lies in same configuration).
The traditional similarity measurement algorithm of time series needs human intervention such as time alignment,which has higher time complexity and is bad for following data mining. For the problems above,this paper puts forward similarity measurement algorithm of time series based on coefficient matrix arc differential. It introduces the thought of least-square method in regression analysis,obtains vector basement of time series form attribution by constructing matrix and achieves the continuous sequence curve simultaneously. On this basis,it implements similarity measurement of time series finally by using the relationship of arc differential and curvature radius of the continuous function. Experimental results showthat the proposed algorithm has stronger robustness,which can not only achieve similarity measurement in microscopic(lies in distance proximity),but also achieve similarity measurement in macroscopic(lies in same configuration).
引文
[1]ZHAI Yuanzheng,WAHG Jinsheng,TENG Yangguo,et al.Water Demand Forecasting of Beijing Using the Time Series Forecasting M ethod[J].Journal of Geographical Science,2012,22(5):919-932.
[2]FCUHS E,GRUBER T,NITSCHKE J,et al.On-line Segmentation of Time Series Based on Polynomial Least-squares Approximation[J].IEEE Transactions on Pattern Analysis and M achine Intelligence,2010,32(12):2232-2245.
[3]MACIEJ K,GRAZYNA S.An Approach to Dimensionality Reduction in Time Series[J].Information Science,2014,26(6):15-36.
[4]GUERRERO J L,BERLANGA A,GARCIA J,et al.Piecewise Linear Representation Segmentation as a Multiobjective Optimization Problem[M]//JANUSZ K.Advances in Intelligent and Soft Computing.Berlin,Germany:Springer,2010:267-274.
[5]MUEEN A,DING H,TRAJCEVSKI G,et al.Experimental Comparison of Representation Method and Distance Measures for Time Series Data[J].Data Mining and Knowledge Discovery,2012,26(2):275-309.
[6]EHMKE J F,MEISEL S,MATTFELD D C.Floating Car Based Travel Times for City Logistics[J].Transportation Research,Part C:Emerging Technologies,2012,21(1):338-352.
[7]AGRAWAL R,FALOUTSOS C,SWAMI A.Efficient Similarity Search in Sequence Databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms.Washington D.C.,USA:IEEE Computer Society,1993:69-84.
[8]KEOGH E,PAZZANI M.Derivative Dynamic Time Warping[C]//Proceedings of the 1st SIAM International Conference on Data M ining.Chicago,USA:SIAM,2001:1-11.
[9]LIN J,KEOGH E,LONARDI S,et al.A Symbolic Representation of Time Series,w ith Implications for Streaming Algorithms[C]//Proceedings of the 8th ACM SIGM OD Workshop on Research Issues in Data M ining and Know ledge Discovery.New York,USA:ACM Press,2003:2-11.
[10]KEOGH E,LONARDI S,RATANAMAMATANA C A,et al.Compression-based Data M ining of Sequential Data[J].Data M ining and Know ledge Discovery,2007,14(1):99-129.
[11]潘定,沈钧毅.时态数据挖掘的相似性发现技术[J].软件学报,2007,18(2):246-258.
[12]NOPIAH Z M,KHAIRIR M I,ABDULLAH S,et al.Peakvalley Segmentation Algorithm for Kurtosis Analysis and Classification of Fatigue Time Series Data[J].European Journal of Scientific Research,2009,29(1):113-125.
[13]SAKOE H,CHIBA S.Dynamic Programming Algorithm Optimization for Spoken Word Recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1):43-49.
[14]GUESTRINT C,BODIKZ P,THIBAUXT R,et al.Distributed Regression:An Efficient Framew ork for M odeling Sensor Netw ork Data[C]//Proceedings of ACM International Conference on Sensor Netw orks.New York,USA:ACM Press,2004:1-10.
[15]DELIGIANNAKIS A,KOTIDIS Y,ROUSSOPOULOS N.Compressing Historical Information in Sensor Networks[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2004:527-538.
[16]张智广,赵学敏.平面曲线相似性初探[J].天津师范大学学报,1998,18(2):65-72.
[17]BECKOUCHE S,MA Jianwei.Simultaneous Dictionary Learning and Denoising for Seismic Data[J].Geophysics,2014,79(3):27-31.
[18]SONG Jun,LIU Yu,WANG Xudong.Improved Denoising Algorithm for Narrow-band Signal and Its Application[J].Journal of Vibration and Shock,2013,32(16):59-62.
[19]詹艳艳,徐荣聪,陈晓云.基于斜率提取边缘点的时间序列分段线性表示方法[J].计算机科学,2006,33(11):139-142.
[2]FCUHS E,GRUBER T,NITSCHKE J,et al.On-line Segmentation of Time Series Based on Polynomial Least-squares Approximation[J].IEEE Transactions on Pattern Analysis and M achine Intelligence,2010,32(12):2232-2245.
[3]MACIEJ K,GRAZYNA S.An Approach to Dimensionality Reduction in Time Series[J].Information Science,2014,26(6):15-36.
[4]GUERRERO J L,BERLANGA A,GARCIA J,et al.Piecewise Linear Representation Segmentation as a Multiobjective Optimization Problem[M]//JANUSZ K.Advances in Intelligent and Soft Computing.Berlin,Germany:Springer,2010:267-274.
[5]MUEEN A,DING H,TRAJCEVSKI G,et al.Experimental Comparison of Representation Method and Distance Measures for Time Series Data[J].Data Mining and Knowledge Discovery,2012,26(2):275-309.
[6]EHMKE J F,MEISEL S,MATTFELD D C.Floating Car Based Travel Times for City Logistics[J].Transportation Research,Part C:Emerging Technologies,2012,21(1):338-352.
[7]AGRAWAL R,FALOUTSOS C,SWAMI A.Efficient Similarity Search in Sequence Databases[C]//Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms.Washington D.C.,USA:IEEE Computer Society,1993:69-84.
[8]KEOGH E,PAZZANI M.Derivative Dynamic Time Warping[C]//Proceedings of the 1st SIAM International Conference on Data M ining.Chicago,USA:SIAM,2001:1-11.
[9]LIN J,KEOGH E,LONARDI S,et al.A Symbolic Representation of Time Series,w ith Implications for Streaming Algorithms[C]//Proceedings of the 8th ACM SIGM OD Workshop on Research Issues in Data M ining and Know ledge Discovery.New York,USA:ACM Press,2003:2-11.
[10]KEOGH E,LONARDI S,RATANAMAMATANA C A,et al.Compression-based Data M ining of Sequential Data[J].Data M ining and Know ledge Discovery,2007,14(1):99-129.
[11]潘定,沈钧毅.时态数据挖掘的相似性发现技术[J].软件学报,2007,18(2):246-258.
[12]NOPIAH Z M,KHAIRIR M I,ABDULLAH S,et al.Peakvalley Segmentation Algorithm for Kurtosis Analysis and Classification of Fatigue Time Series Data[J].European Journal of Scientific Research,2009,29(1):113-125.
[13]SAKOE H,CHIBA S.Dynamic Programming Algorithm Optimization for Spoken Word Recognition[J].IEEE Transactions on Acoustics,Speech,and Signal Processing,1978,26(1):43-49.
[14]GUESTRINT C,BODIKZ P,THIBAUXT R,et al.Distributed Regression:An Efficient Framew ork for M odeling Sensor Netw ork Data[C]//Proceedings of ACM International Conference on Sensor Netw orks.New York,USA:ACM Press,2004:1-10.
[15]DELIGIANNAKIS A,KOTIDIS Y,ROUSSOPOULOS N.Compressing Historical Information in Sensor Networks[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2004:527-538.
[16]张智广,赵学敏.平面曲线相似性初探[J].天津师范大学学报,1998,18(2):65-72.
[17]BECKOUCHE S,MA Jianwei.Simultaneous Dictionary Learning and Denoising for Seismic Data[J].Geophysics,2014,79(3):27-31.
[18]SONG Jun,LIU Yu,WANG Xudong.Improved Denoising Algorithm for Narrow-band Signal and Its Application[J].Journal of Vibration and Shock,2013,32(16):59-62.
[19]詹艳艳,徐荣聪,陈晓云.基于斜率提取边缘点的时间序列分段线性表示方法[J].计算机科学,2006,33(11):139-142.