系统工程与电子技术 ›› 2018, Vol. 40 ›› Issue (7): 1639-1645.doi: 10.3969/j.issn.1001-506X.2018.07.32

• 软件、算法与仿真 • 上一篇    下一篇

基于PSO的不确定时间序列模体发现算法

王菊1,刘付显1,靳春杰2   

  1. 1. 空军工程大学防空反导学院, 陕西 西安 710051;
    2. 中国人民解放军93527部队, 河北 张家口 075000
  • 出版日期:2018-06-26 发布日期:2018-06-28

Motif discovery algorithm for uncertain time series based on PSO

WANG Ju1, LIU Fuxian1, JIN Chunjie2   

  1. 1. College of Air and Missile Defense, Air Force Engineering University, Xi’an 710051, China;
    2. Unit 93527 of the PLA, Zhangjiakou 075000, China
  • Online:2018-06-26 Published:2018-06-28

摘要:

针对不确定时间序列(uncertain time series, UTS)的模体发现(motif discovery,MD)问题,提出了基于粒子群(particle swarm optimization, PSO)的UTS MD算法。该算法根据UTS的特点,设计了基于PSO的UTS MD的研究框架,并通过对时间序列片段的起始时刻和持续时间进行编码和修正,实现了在该框架下对UTS的MD。在实验中,针对所提出的算法,验证了其可行性,比较了其与MK、MOEN算法在运行时间、占用内存和收敛性方面的性能,并分析了其MD准确率,结果表明所提方法占用较少内存与运行时间,可以发现不同长度的模体,且具有收敛性和较高的准确率。

Abstract:

To solve the problem of uncertain time series (UTS) motif discovery (MD), a motif discovery algorithm for UTS based on particle swarm optimization (PSO) is proposed. According to the characteristics of UTS, a study framework based on PSO for MD from UTS is designed. Furthermore, through coding and revising the start time of time series segment and the last time for it, the proposed algorithm can be realized to discover the motifs from the UTS. In the experiment, a real-life application is applied to verify the feasibility of the proposed algorithm. Then, it is compared with MK and MOEN in terms of run time and memory usage. Finally, its convergence and accuracy are analyzed. The results show that the proposed algorithm can be used to discover motifs with different lengths by consuming less runtime and memory usage, and it has convergence and high accuracy.