一种改进的时间序列特征模式提取方法研究

史震

摘 要：传统的时间序列特征模式提取算法，在基于前缀检索的基础上引入了项集间隔约束的思想，优化了特征模式提取的质量。本文在此基础上引入了跨度阈值，对模式候选集进行了深度的剪纸及优化，有效提高了特征模式的挖掘质量。通过实验结果证明，特征模式质量改善明显。

关键词：时间序列；特征模式；跨度阈值

中图分类号：TP311 文献标识码：A 文章编号：1671-2064（2017）08-0254-01

随着大数据时代的到来，时间序列方面的研究也逐步被重视并占据着重要的的地位。贾艳芳等人提出的基于改进的PrefixSpan算法[1]对序列化数据进行特征模式提取，其融入了MPP算法的思想，使其可以对单序列数据进行模式挖掘。该方法充分利用了序列的原始特性，但提取的模式候选集中序列之间的部分属性存在较大的偏差，因此可信度较低，模式的特征性不强。

在单序列特征模式提取问题中，为了提高模式的可信度，谢飞等人提出了MAIL算法，该算法引入了项集间隔约束思想，从而避免了候选集中序列项集间隔的较大差异，在模式质量方面有所改善和提高。但在满足序列自身项集间隔约束的同时并未对序列之间跨度差异进行限定，因此在部分特征模式候选集中序列与序列之间的跨度差异较大，抗干扰性较弱，影响特征模式质量。

本文在前人算法的基础上引入了跨度阈值约束机制，通过模式候选集的模式过滤，优化了特征模式的提取。经验证，提取的特征模式质量得以显著改善。

1 序列特征模式提取

1.1 跨度阈值

定义：跨度阈值。目标序列S中，模式P匹配到的所有序列位置组成模式候选集M。在候选集M中，每一个序列都对应一个跨度值L，在候选集总的跨度值中选取该集合中位数，记为MI，与MI差值的绝对值满足自给定约束范围的序列记为可用序列。其中，自给定约束范围即为跨度阈值。

不同的跨度阈值对特征模式提取的影响不同，因此可以灵活的按需提取不同精度的特征模式，从而发现模式的潜在特性，细粒度化的提高特征模式质量。

1.2 特征性判定

序列中满足设定支持度的模式即为特征模式，由于序列本身周期性特点以及其中较多孤立干扰点的存在，其挖掘出的特征模式候选集中的序列之间存在互相重叠的特性，若重叠率较高，在一定程度上会影响特征模式的质量，致使特征模式的特征性不明显。

为了定性的表征特征模式的该特性，可以通过如下公式来计算得出，计算公式为：

其中，分母为特征模式候选集中所有序列的总跨度之和，分子为候选集中所有子序列段的跨度乘以其权重之和，其中权重为该重叠子序列个数的倒数，η的取值范围在[0，1]之间。该值作为特征模式质量参考值可以在一定程度上有效的判定出特征模式独特性的强弱。

2 模式候选集结构的改进

模式候选集用以模式的扩展，记录匹配序列在目标序列中出现的位置信息，并以首字符位置作为该模式匹配序列的索引标记。为了保证模式的完备性和一致性，模式候选集采用如下数据结构（模式候选集结构（部分）见表1）。

由以前基于前缀式的检索方式改为基于首字符位置的内外混合式搜索方式。外部搜索加快了对模式位置的定位，内部搜索实现了对特征模式的跨度阈值检测。

3 实验结果分析

3.1 实验环境

所有算法运行在Pentium Dual CPU 3.0GHz，内存为2GB的计算机上，使用JDK1.7开发环境实现。

3.2 數据来源及预处理

数据源采用提供的来自不同领域的3条时间序列的实际数据集：Ocean、Burstin和Advertisement，序列长度均为12000。

3.3 实验对比分析

跨度阈值的引入对特征模式的提取质量产生很大的影响，从提取的特征模式数量、特征η值这两个方面进行对比。实验参数：跨度阈值约束等级分为5和10，项集间隔约束采用g=[0，4]，支持度support=20。

经实验验证，随着跨度阈值约束逐渐增强，序列中提取出的特征模式数量较以往算法有明显减少，但特征模式的特征η值均值有显著提高，这表明特征模式候选集中序列之间的重叠率下降，特征模式的特征性和可信度得到明显加强和提高。例如Ocean序列数据集，以往算法所提取的特征模式的特征η值均值仅为18.4%和42.1%，可见其中特征模式候选集中序列之间的重叠率较高，而改进算法的特征性均值提升至77.1%，在一定程度上剪去了重叠率较高的特征模式，突出了特征模式的特征性。

4 结语

跨度阈值的引入，一方面限定特征模式候选集中序列间跨度的差异，降低了特征模式候选集中序列之间的重叠率，提高了特征模式质量；另一方面提供了一种将特征模式的特征性进行细粒度划分的方式，为更深入的理解序列特征模式提供了依据。

参考文献

[1]Pei J， Han J， Mortazavi-Asl B， et al. Prefixspan： Mining sequential patterns efficiently by prefix-projected pattern growth[C]//icccn. IEEE，2001：0215.