时间序列中频繁序列模式挖掘方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN106469171A(43)申请公布日2017.03.01(21)申请号201510511829.2(22)申请日2015.08.20(71)申请人武汉泰乐奇信息科技有限公司地址430073湖北省武汉市东湖新技术区关东工业园7-5栋4118室(72)发明人曾承李志浩隗佳(51)Int.Cl.G06F17/30(2006.01)权利要求书1页说明书4页附图2页(54)发明名称时间序列中频繁序列模式挖掘方法(57)摘要本发明涉及时间序列挖掘技术领域，适用于金融、营销、生物医疗等领域，用于挖掘海量时间序列中连续出现的频繁序列模式。本发明提供一种快速、可并行的频繁时序序列挖掘方法，在此过程中，提出一种“区段频次索引”的结构用来辅助快速定位关键元素的“下一个元素”，以一种主动的方式由较短的频繁序列逐步增长为更长的频繁序列。更进一步地，考虑到频繁序列可能存在重复或包含，提出一种新的搜索策略：将所有频繁序列连接为一个较长的序列，通过查询各个序列的次数决定是否是包含或重复的。此方法较好地保持了频繁序列的最简性。CN106469171ACN106469171A权利要求书1/1页1.一种在海量时间序列中挖掘频繁序列模式的方法，其特征在于如下步骤：a.将长度为n的时间序列循环左移n次，每次移动1位，在每次移位后生成一个新的长度为n的序列，最终得到n个序列，将每个序列当做矩阵的一行，按照先后顺序构成一个n阶矩阵，记为M1；b.将步骤a得到的n个序列按首字符字典顺序排序，首字符相同的按第二个字符字典顺序排列，以此类推，再将每个序列当做矩阵的一行，按照先后顺序构成一个n阶输出矩阵记为M2，将M2第一列标识为F列，最后一列标识为L列；c.针对M2矩阵的L列，构建区段频次索引；d.对F列中的元素依次进行FN操作，将得到的元素集合C按照元素值进行分组，相同值的元素被分到同一组；e.若某个组内的元素个数大于或等于频繁支持度（人为规定的频繁序列必须达到的次数），则对该组元素递归地进行步骤d操作，直到组内元素个数小于频繁支持度为止；f.对步骤e得到的频繁序列进行去重操作，即若某个频繁序列A包含频繁序列B，则认为B是重复序列，将B删除，最终得到无包含、无重复的频繁序列集合。2.如权利要求1所述的区段频次索引，其特征在于如下步骤：a.对待操作序列进行等长分段，其中每段被称为一个BLOCK；b.假设待操作序列被分成s个BLOCK，从待操作序列首部开始，统计第1个到第i（1<i<s）个BLOCK组成的子序列中各元素出现的次数，以此类推，直到序列结束，最后得到i-1个元素频次的统计结果，并保存到区段索引文件中；c.由步骤b得到的区段索引文件，可判断出要索引的元素对应在哪一个BLOCK中，进而在对应的BLOCK中进行查找，省去了从头开始查找的时间，最终快速得到该元素在该序列中的位置。3.如权利要求1所述的FN操作，其特征在于如下步骤：a.将待操作的元素记为m，由L中的区段频次索引可以得出m在L中的位置集合；b.针对L列中的每个元素m，找到其同行中F列对应的元素m’，由于每行序列都是由原序列逐个左移形成的，故m’即为m在时间序列上的下一个元素，这些元素构成了一个集合，记为C。2CN106469171A说明书1/4页时间序列中频繁序列模式挖掘方法技术领域[0001]本发明涉及时间序列挖掘技术领域，适用于金融、营销、生物医疗等领域，用于挖掘海量时间序列中连续出现的频繁序列模式。背景技术[0002]时间序列（TimeSeries）泛指那些随时间或空间有序变化的数据集合，这些数据集合往往采用等时间或空间间隔的方法进行度量，如金融股票价格、商品销售数据、气象数据以及生物医疗的电图过程监控数据等，时间序列挖掘在这些领域有着巨大的应用和研究价值。以金融领域举例来说，金融市场的海量时间序列挖掘，在客户分析、欺诈检测、金融投资组合研究、股票趋势预测以及证券投资公司分析导向等方向有着指导性的意义。[0003]时间序列数据挖掘的目的就是从时间序列中检测出用户感兴趣或者具有潜在知识的模式，这些模式可以帮我们更好的发现到其中蕴含的规律，进而为创造更大价值提供支持。[0004]近年来，随着存储技术和互联网的发展，各个行业的时间序列数据有着海量、密集的发展趋势，目前经典的频繁模式挖掘方法有Apriori算法和FP-Growth算法、以及基于它们的一些变种算法，都存在运行时间长、内存使用量大的问题，无法满足日益增长的数据处理要求。[0005]针对以上传统方法的不足，实现对海量时间序列中频繁序列地高效挖掘，包括较少的运行时间和内存占用，而且方法必须支持弹性的扩展，如分布式扩展等，本发明提出一种新型的时间序列挖掘方法。发明内容[0006]