留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于多模型的不等长序列数据关联算法

孙贵东 关欣 衣晓 赵骏

孙贵东, 关欣, 衣晓, 等 . 基于多模型的不等长序列数据关联算法[J]. 北京航空航天大学学报, 2017, 43(8): 1640-1646. doi: 10.13700/j.bh.1001-5965.2016.0658
引用本文: 孙贵东, 关欣, 衣晓, 等 . 基于多模型的不等长序列数据关联算法[J]. 北京航空航天大学学报, 2017, 43(8): 1640-1646. doi: 10.13700/j.bh.1001-5965.2016.0658
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)
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)

基于多模型的不等长序列数据关联算法

doi: 10.13700/j.bh.1001-5965.2016.0658
基金项目: 

国家自然科学基金 61032001

新世纪优秀人才支持计划 NCET-11-0872

详细信息
    作者简介:

    孙贵东   男, 博士研究生。主要研究方向:智能数据挖掘、多属性决策

    关欣   女, 博士, 教授, 博士生导师。主要研究方向:多源信息融合、智能信息处理

    衣晓   男, 博士, 教授, 博士生导师。主要研究方向:无线传感器网络、多源信息融合

    通讯作者:

    关欣, E-mail:gxtongwin@163.com

  • 中图分类号: TN95

Data association algorithm for unequal length sequence based on multiple model

Funds: 

National Natural Science Foundation of China 61032001

Program for New Century Excellent Talents in University NCET-11-0872

More Information
  • 摘要:

    单模型在处理不等长序列数据关联时不能兼顾计算精度、复杂度和抗扰性,为此提出了基于多模型(MM)的不等长序列数据关联算法。将基于滑动窗口和动态时间弯曲(DTW)的不等长序列相似度度量模型作为MM的输入模型,以2种模型计算得到的时似变化比作为模型判断指标进行模型转换,实现了2种模型的优势互补,并得到模型的应用条件,最后输出MM作用后的不等长序列相似度,以此作为关联指标进行关联判定。仿真实验验证了MM关联算法在处理不等长序列数据关联的有效性,并对序列长度和突变率变化对关联效果的影响进行了分析。

     

  • 图 1  突变点示意图

    Figure 1.  Schematic diagram of fluctuant point

    图 2  模型转换流程图

    Figure 2.  Model transformation flowchart

    图 3  2种模型计算时间对比

    Figure 3.  Comparison of calculation time between two models

    图 4  模型相似度随序列长度变化

    Figure 4.  Variation of model similarity with sequence length

    图 5  模型相似度随突变率变化

    Figure 5.  Variation of model similarity with fluctuant rate

    图 6  时似变化比随序列长度的变化

    Figure 6.  Variation of rate of change between time and similarity with sequence length

    图 7  不同突变点条件下的模型转换临界点变换

    Figure 7.  Change of model transformation critical point under different fluctuant points

    表  1  不等长序列组的相似度

    Table  1.   Similarity of unequal length sequence group

    序列相似度
    Q1Q2Q3Q4
    S10.212 50.696 60.105 60.010 2
    S20.126 40.075 90.730 60.078 7
    下载: 导出CSV
  • [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.
  • 加载中
图(7) / 表(1)
计量
  • 文章访问数:  488
  • HTML全文浏览量:  11
  • PDF下载量:  400
  • 被引次数: 0
出版历程
  • 收稿日期:  2016-08-10
  • 录用日期:  2016-10-28
  • 刊出日期:  2017-08-20

目录

    /

    返回文章
    返回
    常见问答