一种时序数据间断频繁项挖掘算法

刘 昆 李颖芳 李红林

（1.曲靖师范学院 计算机科学与工程学院，云南 曲靖 655011；2.红河学院 工学院，云南 蒙自 661100）

0 引言

在人类社会和自然界的变迁中，都存在时间的因素。例如，金融证券市场中每天的股票交易中价格波动；零售行业中，某项商品每天的销售额；气象预报研究中，某一地区的每天气温与气压的读数以及在生物医学中，某一症状病人在每个时刻的心跳变化，课堂作业中学生交作业的先后顺序等；这些事件中都有时间的先后顺序，把这些信息称为数据，它们是有时间先后性质的数据，是时间序列数据。所谓时间序列数据就是在一个确定时间区间，以确定的时间量子或者时刻为单位对研究对象进行连续观测得到的一组记录，这组记录是按时间顺序排列的。

不同研究者对时间序列的定义是不一样的。根据所查文献和收据的资料，对时间序列数据给出如下形式化定义：

定义（时间序列数据）时间序列数据 S 是一个有限集{（t1，T1），（t2，T2），…，（tn，Tn）}，满足 ti

本文将时间序列数据的频繁序列挖掘过程分为以下五个步骤：时间序列数据符号化、对符号化后的序列生成互关联后继树、生成互关联线索树、挖掘连续频繁序、挖掘间断频繁序列。

1 针对股票数据应用的时间序列数据符号化表示

针对某股市交易数据中，pi=（第i天收盘价-第i-1天收盘价）/第i天收盘价 *100%，当 pi为 0%～2%时，视为第 i天为“小涨”；pi大于5%时记为第 i天“大涨”，pi在 2%～5%之间，第 i天为“上涨”，同理，当pi为 0%～-2%时，第 i天为“小跌”；pi小于 5%时记为第 i天“大跌”，pi在-2%～-5%之间，记为第i天为“下跌”。把“小涨”用A表示，“上涨”用B表示，“大涨”用C表示，“小跌”用D表示，“下跌”用 E表示，“大跌”用F表示，则此只股票收盘价数据变化规律就可以转化为包含符号{A，B，C，D，E，F}的字符串。

利用该算法就可以把一只股票的变化规律转化成一串字符序列S，S=S1S2…Sn，Si∈String（A，B，C，D，E，F），i=1，2，…，n。

2 连续频繁项和间断频繁项

把某股票交易日收盘价的时间序列数据符号化后得到字符串，子序列相等的定义、连续频繁系列的定义、k元连续频繁序列集的定义参考论文[1]。

间断频繁序列是不连续的、有间断的频繁序列，其定义如下：在S序列中，有子序列 Cm*…*Cn（m=1，2，…，k-2 ； n>=m+2），当 *…* 对应任意某个固定长度子序列时，与序列Ci*…*Cj相等的子序列数小于最小支持阈值（也就是说形如Ci∞固定长度序列∞Cj的序列是连续非频繁序列）；但是，如果把几个这样的不相等的紧密连续非频繁序列计数相加，所得和值大于最小支持阈值，那么就称Ci*…*Cj为间断连续频繁序列。

如例abcdabaabcabddaadd#，如果当某序列个数大于2时，就认为它是频繁序列，那么这个序列中b?d、b?a、a?d就是个间断频繁序列，d（Gfs（b?d））=|Gfs（b?d）|=3。

3 互关联后继树与互关联线索树

复旦大学的胡运发教授和申展、曾海泉等人几年来，对互关联后继树做了深入的研究工作，并获得大量的好的结果[1-6]。互关联后继树模型是一种应用在文本索引中的模型，对连续、有序的字符建立索引，它的任意可进入性给查询序列型数据带来很大的方便[1-6]，本文对互关联后继树就不再论述。

定义 3.1 线索树：以 Cm为树根为 0 层，元模式类型{C1，C2，..，Cm}中的所有元素按顺序构成叶子节点为1层，以后继树生产过程结合，将后继树的分支标记号按后继归类到作为下层的新叶子节点为2层，把此树称为Cm统计线索树，此树共有3层。

定义3.2互关线索数树：把时间序列符号集S的所有线索树组成的森林，叫做S的互关联信息统计线索树。

4 挖掘连续频繁序与挖掘间断频繁序列

使用互关联后继树挖掘多元连续频繁序列在参考文献[1-6]都有所涉猎，本文不过多描述。本文重点主要放在间断频繁项的挖掘上。

挖掘间断频繁序列分3步进行：

（1）构建可能的间断频繁序列。

（2）找出构成可能间断频繁序列的紧密连续非频繁序列。

（3）查询、检验、统计紧密连续非频繁序列，统计非频繁序列出现次数，如果出现次数大于最小支持阈值，则为间断连续频繁序列。

根据间断频繁序列的定义和性质，利用带权有向图找寻间断频繁项的思想。带权有向图建立的步骤如下：

（1）建立以 C={C1，C2，…，Cm}顶点集的有向完全图。

（2）利用互关联统计线索树，将（1）所建图进行加权和修枝；利用线索树的第2层对有向弧进行赋值；例如在序列S中，CmCn子序列出现了w次，则有向弧CmCn的权值为w；删除权值为0的有向弧。

（3）重复（2），直到加上所有的权和删除所有的0弧，构成该序列的带权有向图。

利用带权有向图寻找间断连续频繁序列的步骤如下：

（1）根据间断频繁序列的性质，如果CmCn∈{2元频繁序列}，那么Cm、Cn一定∈{1元频繁项}；根据紧密连续频繁序列与间断连续频繁序列间的关系，删除长度为d（Gfs（Cm*…*Cn））连续频繁序列集中所有的开始字符和结束字符对，并在加权有向图中减去这些紧密频繁序列所经过的路的权值，达到修正加权有向图权值的目的；根据剩下的加权图，找到可能产生间断连续频繁序列Cm、Cn；从带权有向图中提取，以Cm为出度，Cn为入度的有向子图。

（2）根据（1）中提取的子图，找出从 Cm到 Cn所有长度为 d（Gfs（Ci*…*Cj））有向路，放在 V 中。

（3）统计V中路的总和，如果总和>=最小支持阈值，那么Cm*…*Cn可能是间断连续频繁序列，这些路就是构成可能间断连续频繁序列的连续非频繁序列。

（4）利用互关联统计线索树，验证、统计可能连续非频繁序列，得到的总和>=最小支持阈值，则构成了间断频繁序列，否则，没有构成间断频繁序列。

（5）利用上面的步骤找出所有的间断频繁序列。

5 实验分析

本文提出的挖掘算法经过试验能够从时间序列数据中有效的提取一些的时态关联规则。由于实验选取了1000日交易数据为样本，本文算法算出的结果和实验得到的结果完全一致，证明该算法是正确的；经与其他算法挖掘的效率分析比较，本文提出的算法是有效可行的。

［1］刘昆.基于时间序列数据的紧密连续频繁序列挖掘算法[J].曲靖师范学院学报，2008，6：60-68.

［2］张忠平.基于三元互关联后继树的Web日志挖掘[J].计算机应用与软件，2011，10.

［3］霍林.二元互关联后继树精简索引模型研究[J].小型微型计算机系统，2011，2：286-290.

［4］颜文伟，胡运发.一个基于三元互关联后继树的多功能全文检索系统[J].计算机应用与软件，2007，2：124-128.

［5］王政华，胡运发.基于后继区间的互关联后继树搜索算法[J].计算机工程，2007，5：84-86.

［6］杨茹.基于双排序互关联后继树的索引压缩和原文生成算法[J].计算机应用与软件，2010，9：1-4.