Citation: | SUN Guidong, GUAN Xin, YI Xiao, et al. Data association algorithm for unequal length sequence based on multiple model[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43(8): 1640-1646. doi: 10.13700/j.bh.1001-5965.2016.0658(in Chinese) |
When dealing with data association for unequal length sequence, single model cannot balance computational accuracy, complexity and disturbance rejection. So a data association algorithm for unequal length sequence based on multiple model (MM) was proposed. The two unequal length sequence similarity measurement model based on sliding window and dynamic time warping (DTW) were selected as the input model of MM, which uses the rate of change between time and similarity of two model as the index to realize the transformation of the two models. It combines both advantages of two models and gets the models' application condition.The unequal length sequence similarity is output after MM as the index to judge the association of the sequence data. Simulation results show the effectiveness of the proposed algorithm for unequal length sequence and analyze the effect of sequence length and fluctuant rate on association result.
[1] |
AGRAWAL R, FALOUTSOS C, SWAMI A.Efficient similarity search in sequence databases[C]//Proceedings of 4th International Conference on Foundations of Data Organization and Algorithms.Berlin:Springer, 1993:69-84.
|
[2] |
RAFIEI D, MENDELZON A O.Querying time series data based on similarity[J].IEEE Transactions on Knowledge and Data Engineering, 2000, 12(5):675-693. doi: 10.1109/69.877502
|
[3] |
WANG C Z, WANG X Y.Multilevel filtering for high dimensional nearest neighbor search[C]//Proceedings of ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.New York:ACM Press, 2000:37-43.
|
[4] |
KORN F, JAGADISH H V, FALOUTSOS C.Efficiently supporting ad hoc queries in large datasets of time sequences[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York:ACM Press, 1997:289-300.
|
[5] |
HUHTALLA Y, KRKKINEN J, TOIVENEN H.Mining for similarities in aligned time series using wavelets[C]//Proceedings of Data Mining and Knowledge Discovery:Theory, Tools, and Technology.Orlando:[s.n.], 1999:150-160.
|
[6] |
张海勤, 蔡庆生.基于小波变换的时间序列相似模式匹配[J].计算机学报, 2003, 26(3):373-377. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200303015.htm
ZHANG H Q, CAI Q S.Time series similarity querying based on wavelets[J].Computer Journal, 2003, 26(3):373-377(in Chinese). http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX200303015.htm
|
[7] |
KEOGH E.Data mining and machine learning in time series database[C]//Proceedings of the 5th Industrial Conference on Data Mining (ICDM).Leipzig:[s.n.], 2005.
|
[8] |
KEOGH E, CHAKRABARTI K, PAZZANI M, et al.Dimensionality reduction for fast similarity search in large time series databases[J].Journal of Knowledge and Information Systems, 2001, 3(3):263-286. doi: 10.1007/PL00011669
|
[9] |
SANG W K, SANGH Y P, WEALEY W C.An Index-based approach for similarity search supporting time warping in large sequence databases[C]//Proceedings 17th International Conference on Data Engineering.Washington, D.C.:IEEE Computer Society, 2001:607-614.
|
[10] |
THANNWIN R, BILSON C, KEOGH E.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 Press, 2012:262-270.
|
[11] |
KEOGH E.Exact indexing of dynamic time warping[C]//Proceedings of the 28th International Conference on Very Large Databases.San Francisco:Morgan Kaufmann, 2002:406-417.
|
[12] |
RATHT M, MANMATHA R.Lower bounding of dynamic time warping distances for multivariate time series:Technical ReportMM-40[R].Amherst:Center for Intelligent Information Retrieval Technical Report, University of Massachusetts, 2003.
|
[13] |
KEOGT E, PAZZANI M.Derivative dynamic time warping[C]//Proceedings of the 1st SIAM International Conference on Data Mining.Chicago:SIAM Press, 2001:209-211.
|
[14] |
KEOGH E, CHAKRABARTI K, PAZZANI M.Locally adaptive dimensionality reduction for indexing large time series databases[J].ACM Transactions on Database Systems, 2002, 27(2):188-228. doi: 10.1145/568518.568520
|
[15] |
BERNDT D, CLIFFORD J.Using dynamic time warping to find patterns in time series[C]//AIAA 94 Workshop on Knowledge Discovery in Databases.Reston:AIAA, 1994:359-370.
|
[16] |
BAR-SHALOM Y, FORTMANN T E.Tracking and data association[M].San Diego:Academic Press, 1988:125-127.
|