手机版
您的当前位置: 好论文网 > 知识百科 > 【时间序列周期检测】时间序列周期模式挖掘算法分析

【时间序列周期检测】时间序列周期模式挖掘算法分析

来源:知识百科 时间:2019-06-14 点击: 推荐访问:时间序列算法模型

【www.ho59.com--知识百科】

[摘 要] 时间序列周期模式的挖掘无论对科研活动还是社会生活都有非常大的实际意义,有利于更好的预测及趋势分析。已有的时间序列周期模式挖掘算法根据周期长度参数是否已知可分为三类:已知周期长度、给定周期长度阈值及周期长度未知的周期模式挖掘。
  [关键词] 周期模式挖掘;周期长度;算法综述
  doi : 10 . 3969 / j . issn . 1673 - 0194 . 2016 . 03. 093
  [中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194(2016)03- 0173- 02
  1 引 言
  已有学者对时间序列周期模式挖掘进行了大量的研究,并针对各种数据特征及应用场景,提出了各种不同周期模式挖掘的算法。根据周期长度是否已知,周期模式挖掘可以分为三类,即周期长度参数已知的周期模式挖掘、给定周期长度参数阈值的周期模式挖掘及周期长度预先未知的周期模式挖掘。各种周期模式的具体分类及前人提出的挖掘算法的总结将在下文进行详细介绍。
  2 时间序列周期模式挖掘的分类
  2.1 已知周期长度的周期模式挖掘
  周期模式挖掘中周期长度是一个重要的参数,大部分算法都是基于周期长度参数已知的前提下提出的,各种不同周期模式挖掘算法的分类如下:
  (1)完全周期模式挖掘与部分周期模式挖掘。完全周期模式(Full Periodic Patterns)挖掘最早由Ozden于1998年提出,他的输入数据是一系列交易数据集,每条交易记录又由一系列项集随机组合而成,另外,每条交易记录被标记了发生时间。算法的目标是挖掘出具有重复性的关联规则。完全周期模式指一个序列经过等间隔划分为等长的子序列,每个子序列为严格相同的周期模式。
  事实上,部分周期模式(Partial Periodic Patterns)在生活中的存在更广泛。部分周期模式[1]最早由Jiawei Han于1999年提出,大部分部分周期模式挖掘算法都是基于Apriori性质。Han 等人通过探索部分周期模式特有的性质,包括 Apriori 启发式性质、最大子模式命中集(Max-subpattern hit set)属性,进一步提出几种新的算法来挖掘部分周期模式。其中最大子模式命中集属性将时间序列模式子集包含在最大命中子模式树中,这样挖掘部分周期模式只需要扫描两次时间序列数据库就能把时间序列中所有的频繁模式分离出来。同时,该算法还可以挖掘多周期的时间序列部分周期模式。Rasheed等提出的增量周期模式[2]挖掘算法大大提高了周期模式的联机分析处理能力,对周期模式的挖掘提出了更高的要求。
  完全周期模式强调序列中每个元素都严格参与构成周期模式,而部分周期模式中未必每个元素都对周期性有贡献,实际上,部分周期模式是比完全周期模式更松散的一种周期模式,在生活中的存在也更加广泛,因此部分周期模式的研究就更富有意义,也是当前的研究热点。
  (2)同步周期模式挖掘与异步周期模式挖掘。同步周期模式(Synchronous Periodic Patters)指周期子序列与原序列严格对齐,如在字符序列{a, f, c, a, d, c, a, g, c, d, c, a}中,子序列{a, *, c},{a,*,*},{*,*, c}都是原序列同步周期模式。如果原序列由于噪声干扰或者元素丢失等,导致子序列与原序列错位性匹配,则构成的周期模式称为异步周期模式(Asynchronous Periodic Patters),上文提到的字符序列中,子序列{a,*},{c,*},{c, a}都是原序列的异步周期模式。
  现实生活中,如果一味的去追求同步周期模式的话很可能就会丢失掉一些规律。只要周期模式客观存在、错位幅度在最大偏差以内、干扰的时间持续长度在可检测范围,那么我们仍旧可以找到该事件的周期模式。Jiong Yang等人提出的异步周期模式挖掘算法LSI[3]就是基于上述思想,他定义了两个参数,“周期模式的最小重复次数”min_rep和两个连续有效的分段间的“最大允许间隔距离”max_dis。基于以上两个参数,他提出一种两阶段的挖掘算法,首先,根据“最大允许间隔距离”参数剪枝生成候选周期模式,然后迭代验证候选周期模式的有效性,并生成最长周期子序列。Kuo-Yu Huang等人在LSI算法的基础上进一步提出SMCA[4]算法,该算法的改进之处在于,除了LSI算法的两个参数外,SMCA算法新增了一个参数――“有效序列的最小重复次数”global_rep,并且SMCA算法允许同一时间点发生多个事件,能处理的数据更复杂。Xiangzhan Yu等人提出的异步周期挖掘算法[5]通过设置多个最小项集支持度阈值,不仅关注模式的频繁性,更关注同一模式中各个元素的周期性挖掘。
  (3)稀有周期模式挖掘。以往的周期模式挖掘算法都是关注频繁周期模式的挖掘,Jiong Yang等人提出一个算法InfoMiner,用于稀少但具有统计意义的周期模式――稀有周期模式(Surprising Periodic Patterns)[6]的挖掘。稀有周期模式挖掘基于信息论中的“信息量”(Information)和“信息增益”(Information Gain)概念,提出一种新的信息增益模型,代替以往的支持度(Support)模型。该模型更关注事件发生概率很小,但一旦出现就具有周期性的序列模式的挖掘。该算法采用“信息增益”指标度量序列中各模式的“奇异度”(Surprise),从而选出奇异度大于用户预定义的阈值的周期模式。由于上述算法没有考虑周期模式的发生位置信息,因此Jiong Yang等人提出一个改进的InfoMiner+算法[7],用广义的信息增益指标度量各模式的奇异度,从而找出所有具有统计意义的部分周期子序列。   2.2 给定周期长度阈值的周期模式挖掘
  实际上,周期模式挖掘算法中提前预知周期长度的情况很少见,但是用户可能会提供一些有用的周期长度信息,比如,雨季来临时每隔三到五天会有一场大雨降临,这说明周期长度阈值为3~5天,这对周期模式的挖掘也有重大意义。
  近似周期模式挖掘不仅允许序列模式中事件的发生位置近似具有周期性,也允许序列模式的结构近似具有周期性。著名的近期周期模式挖掘算法由Dehne等[8]提出,该算法定义一个参数α∈[0,1],使单一事件相邻发生时间间隔绝对差的最大值与最小值之比――周期比最大值为1+α。该算法的缺陷是时间复杂度为O(n3),当输入数据量很大时,算法时间复杂度太高。因此,作者通过定义一个新的参数ε,寻找周期比至多为(1+α)(1+ε)的子序列,从而将时间复杂度降低为O(n1+γ),其中γ为一任意小的正常数。Amir等[9]提出的近似周期模式挖掘算法允许序列模式中事件的发生位置近似具有周期性。该算法预先给定一个参数ε∈[0,1),目标是寻找同一事件的相邻两次发生时间间隔绝对差介于p与p(1+ε)之间的最长周期模式。与之前的近似周期模式挖掘算法相比,该算法的时间复杂度为亚三次方,且大部分情况下为O(n2),算法的时间复杂度有了很大提高。
  2.3 未知周期长度的周期模式挖掘
  所有以上的算法都需要用户主观输入周期长度参数,即用户需要预先知道周期长度或周期长度的阈值范围,这使得这些算法更适用于自然周期长度的数据,比如以小时、日、周、月、年等为周期长度的数据。然而,大部分数据集可能不以自然周期长度重复,因此,需要一种适用性更广的算法来抽取隐含的周期长度及周期模式。
  Ma等[10]于2001年提出一种未知周期长度的周期模式挖掘算法。作者将周期模式关联规则挖掘分为两个子任务:即序列模式周期长度发现和时序关联规则挖掘。文中提出两个算法,前者首先进行序列模式周期长度发现,而后进行周期模式关联规则挖掘,其中,周期长度发现算法采用卡方检验寻找周期长度。后者首先进行事件间关联规则挖掘,然后进行序列模式周期长度发现。经过实验发现,事件间关联规则优先挖掘的算法受噪声影响更小,但周期长度优先挖掘的算法效率更高。孙颂恩和施润身基于蚁群算法的思想[11],通过定义“周期事件发生时间点容忍度rol”提出一种弱限制条件的周期模式挖掘算法,比严格的周期模式挖掘算法实际适用性更强。
  综上所述,将各类时间序列周期模式挖掘的算法从解决的问题、参数个数、算法优缺点等方面对比如表1所示。
  3 结 论
  以上算法都是周期模式挖掘研究的热点方向,其他学者也从不同方面对周期模式挖掘贡献了自己的力量,更多时间序列周期模式类型及挖掘算法有待进一步提出。
  主要参考文献
  [1]Han J,Dong G,Yin, Y. Efficient Mining of Partial Periodic Patterns in Time Series Database[C]//Proceedings of 15th International Conference on Data Engineering,1999, Sydney, NSW:106-115.
  [2]Aref W G,Elfeky M G,Elmagarmid A K. Incremental, Online, and Merge Mining of Partial Periodic Patterns in Time-Series Databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(3): 332-342.
  [3]Yang J,Wang W,Yu P S. Mining Asynchronous Periodic Patterns in Time Series Data[C]//Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York, NY, USA,2000.
  [4]Huang K Y,Chang C H.SMCA:A General Model for Mining Asynchronous Periodic Patterns in Temporal Databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(6): 774-785.
  [5]Xiangzhan Yu, Zhaoxin Zhang, Haining Yu, et al. An Asynchronous Periodic Sequential Patterns Mining Algorithm with Multiple Minimum Item Supports[C]//P2P, 2014 Ninth International Conference on Parallel, Grid, Cloud and Internet Computing (3PGCIC), Guangdong:274-281.
  [6]Yang J,Wang W,Yu,PS. Mining Surprising Periodic Patterns[J]. Data Mining and Knowledge Discovery, 2004, 9(2): 189-216.
  [7]Yang J,Wang W,Yu P S. Infominer+: Mining Partial Periodic Patterns With Gap Penalties[C]//2000 IEEE International Conference on Data Mining, IEEE Computer Society Washington DC, USA,2000:725-728.
  [8]Gfeller, B. Finding Longest Approximate Periodic Patterns[M].Algorithms and Data Structures,Springer Berlin Heidelberg, 2011: 463-474.
  [9]Amir A,Apostolico A,Eisenberg E, et al. Detecting Approximate Periodic Patterns, Design and Analysis of Algorithm[M]. Springer-Verlag Berlin Heidelberg,2012: 1-12.
  [10]Ma S,Hellerstein, J L. Mining Partially Periodic Event Patterns With Unknown Periods[C]//Proceedings of 17th International Conference on Data Engineering, IEEE Computer Society Washington DC,USA, 2001:205-214.
  [11]孙颂恩,施润身. 时序数据中弱限制周期模式的挖掘[J]. 计算机辅助工程,2005,14(4):35-38.

本文来源:http://www.ho59.com/zs/58915/

好论文网 www.ho59.com

Copyright © 2002-2018 . 好论文网 版权所有 京ICP备10015900号

Top