多元时间序列中关联规则的发现 史忠植 董泽坤中国科学院计算技术研

1、. 多元时间序列中 关联规则的发现 史忠植 董泽坤 中国科学院计算技术研究所 * 多元时间序列的关联规则分析 关联规则：设 是项的集合。任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合， 。每个事务有一个标识符，称为TID。设A是一个项集，事务T包含A当且仅当 。关联规则是形如 的蕴含式，其中, ， ， 。 关联规则的算法OptimizedApriori 优点：只读取一次数据库 OptimizedApriori是在ArioriTid的基础上，将数据结构由 TID,IID 变换为 IID,TID ，从而迅速减少了系统的I/O操作。 在构造候选1-项集时，每一个项（IID）携带了它在数

2、据库中出现的位置记录集合（TID），使得以后的操作可以脱离数据库。 构造k-项集时，新的项目集合（ IID ）由两个k-1项集的项目集合求并集得到，记录号集合（ TID ）由两个k-1项集的记录号集合求交集得到。 缺点：消耗大量的内存 大型数据库操作时会受到处理器内存容量的限制，数据可能无法一次装入。 多元股票时间序列的关联规则（1） 数据预处理 1.数值离散化 s1=3,4,3,2,4,2,0,3,4,4 s2=2,3,2,3,3,4,3,1,1,4 s3=0,3,4,1,0,1,3,3,3,4 多元股票时间序列的关联规则（1） 多元股票时间序列的关联规则（2） 规则挖掘 设：最小支持度20

3、，最小信任度50% 规则： s1.3 ? s2.2:股票1涨?股票2平(20%,66.7%): s1.4 ? s2.3:股票1大涨? 股票2涨(20%,50%); s2.1 ? s3.3:股票2跌? 股票3涨(20%,100%); 测试集 中国证券市场19972001共五年间近500只股票的收盘价时间序列集（以下同） 多元股票时间序列的关联规则（3） 测试结果 多元时间序列的跨事务关联规则分析（1） “跨事务”特性的特点： 强调的是出现在不同事务中各项目之间的关联关系，应用到时间序列中就是不同时刻各序列的数据特征之间的关系，如： A公司的股票在第一天上涨，B公司的股票在第二天下跌，那么，C公司

4、的股票会在第三天上涨。（s%,c%） 这种规则包含了时间特性，规则的前件可以用来作为后件的预测条件，它们的实际使用价值是很明显的。 多元时间序列的跨事务关联规则分析（2） 多元时间序列的跨事务关联规则： 设= e1(0),e1(w-1),e2(0), e2(w- 1) , ,eu(0), eu(w-1) 是事件的集合，这些事件是多元时间序列合并集D中各序列观察值的属性，w是D的滑动时间窗口。以时刻s (1sn-w+1)为D的参考时间基准点，如果时刻s+x (0xw-1)此事件出现，则标记ei(x) 属于Ts。每一个 ei(x)分配一个识别号IID。多元时间序列的跨事务关联规则是形如X?Y的蕴涵

5、式，并且满足以下条件： X?,Y?; ?ei(0)X, 1iu; ?ej(q)X, 1ju,(i=j)(1q w-1)(ij)(0q w-1); ?ei(p)Y, 1iu, max(q) pw-1; XY=? 多元时间序列的跨事务关联规则分析（3） 和传统关联规则算法比较，跨事务关联规则算法要更复杂： 要处理的数据超过算法能承受的范围后，频繁项集的数目将变得巨大而无法处理； 在跨事务分析中，每一个基本项将扩展为w（滑动时间窗口）个。假设有1000个基本项，在传统关联规则分析中，会产生至多（9991）*999 /2 =499500个候选二项集；而在跨事务分析中，会产生(1000*w-1)*(10

6、00*w-1)/2个候选二项集，这个数字以w2的倍数增长。如果w3，则会有4498500（增加了9倍）个二项候选集；更严重的是，在构造候选三项集时，会有更多的增长。随着数据的增加，系统的内存将会枯竭，效率明显下降。 候选集数目的增加导致更频繁的数据库扫描动作。 为统计每一个候选集的频繁支持度计数值，需要通过搜索数据库中每一条记录来确定候选集的所有项是否出现。很明显，数据库的频繁访问会占用很多运行时间。 跨事务关联规则的算法ES-Apriori（1） 为提高多元时间序列的跨事务关联规则分析效率，本文提出了一个扩展的分步Apriori算法：ES-Apriori，此算法从两个方面提高了系统的性能。

7、1仅扫描一次数据库 ES-Apriori算法使用了OptimizedApriori算法的优点，将所有一项集的数据库信息读入内存，其后所有k-项集的产生均依靠k-1-项集提供的数据库信息，从而不必多次搜索数据库，降低了系统的I/O代价。 ?2减少了单次调入内存的数据量 ES-Apriori的所有大项集保留了各项的数据库信息，从而减少了数据库扫描次数，但是它的代价是使用大量内存。所以，如何合理分配内存，是ES-Apriori方法的另一重点。通过分析数据的特征，本文利用时间序列的跨事务关联规则性质，提出了“分而治之”的策略，使每一步需要扫描的空间大幅缩减，从而降低内存的开销。 跨事务关联规则的算法E

8、S-Apriori（2） 时间序列的跨事务关联规则性质：规则都可以在各序列的参考时间基准点项ei(0)的基础上产生。 此性质可以由时间序列的跨事务关联规则定义中的条件2（频繁项集的X子集必定存在相对地址值为0的项）推出。这一性质为ES-Apriori的分步策略提供了理论依据。 假设有2个基本项A、B，滑动时间窗口3，它的扩展1-项集为A0、A1、A2、B0、B1、B2。考察6-项集A0,A1,A2,B0,B1,B2，它包含的规则有且仅有：A0, B0- A1,A2, B1,B2;A0, A1,B0, B1- A2, B2。而传统关联规则可能产生的规则有 个。 跨事务关联规则的算法ES-Apri

9、ori（3） 在计算这2条规则的置信度时，只需要搜索由A0构造的频繁项集空间，并不需要搜索由B0构造的频繁项集空间（不考虑连接时产生的重复项集）。因为这个6-项集的符合时间序列的跨事务关联规则条件的所有X子集只有A0, B0、A0, A1,B0, B1，这两项都是在A0的基础上构造产生的。同理，5项集B0, A1,A2,B1, B2的X子集B0、B0, A1, B1只须搜索由B0构造的频繁项集空间。 跨事务关联规则的算法ES-Apriori（4） 从上面的分析得出，挖掘所有规则可以分成u步运行：每步只构造包含ei(0)|( 1iu)的频繁项集，挖掘相应的的关联规则。这样，一次调入内存的数据可降

10、低为全部调入的1/u，当有大量数据项参与运算时，此方法也能顺利运行。 ES-Apriori算法分割了频繁项集空间，降低了一次调入内存的数据量，从而缓解了因数据爆炸而耗尽内存的问题。 为能够快速便捷的读取跨事务关联规则X子集的支持度计数值，我们设计了一颗动态树来保存频繁项集。用每一个节点表示一个项ei(x)，由树的根节点出发所形成的数枝上所有的节点就代表一个频繁k-项集，而树枝的终点记载了这个频繁项集的支持度计数值。 跨事务关联规则的算法ES-Apriori（5）:构造动态树 以基本项A和B，滑动时间窗口为3的数据库为例，构造一颗6层（最长的关联规则包括6项）共有32个节点的动态树。 首先，建立

11、节点1（A0），作为第一层节点；第二项A0A1有两项，需要新建第二层链表，作为子节点直接添加到节点2；因为第三项A0A2与A0A1同属于第二层，作为A0A1的兄弟节点，加入到第二层链表中；同理，A0B0、A0B1、A0B2都属于第二层，都加入到第二层链表中。由于第二层节点的父节点只有节点1，所以第二层只需要一个链表。从第三层开始，每一个新节点可能属于不同的父节点，所以他们会被添加到不同的各自父节点的子节点链表中。例如，节点11（代表频繁项集A0A2B0）的父节点是节点3（代表频繁项集A0A2），所以被加入到节点3的子节点链表中。以此类推，所有的节点都被添加到动态树中。 跨事务关联规则的算法ES

12、-Apriori（6）:查询动态树 当分解频繁项集为X子集和Y子集时，需要读取X子集的支持度计数值，从而计算X ? Y的支持度。这一搜索过程可以在构造的动态树中快速实现。例如，我们需要得到频繁项A0A2B0B1B2中X子集A0B0B1的支持度计数值，只需要循着节点1（A0）转到第二层链表，由节点2开始顺序搜索节点找到节点4（B0），转入节点4的子节点链表，找到节点14（B1），读出它的支持度计数值。在整个搜索过程中，只需要经过5个节点，这样的速度要比搜索链表高出若干倍，也要比Hash表技术快。在设计中，将已经计算过信任度的频繁项集节点直接销毁，能够减少访问空间，进一步加快搜索速度。 ES-Ap

13、riori算法流程图 跨事务关联规则的算法ES-Apriori:算法性能比较 ES-Apriori与E-Apriori算法的性能对比 由图中可知，当项数小于20k时，E-Apriori和ES-Apriori的执行效率都很高。但是随着数据的增加，E-Apriori的内存使用量将急速增加，导致运算时间骤然变长；而ES-Apriori无论在内存上还是在时间上都呈现平稳增加的态势。在试验中，当总的项数大于30k后，E-Apriori会耗尽计算机内存而无法继续运行；而ES-Apriori却可以顺利运行。试验结论证明，分析较大数据量的多元时间序列的跨事务关联规则时，ES-Apriori算法在时间/空间性能

14、上要优于E-Apriori算法。 多元股票序列的跨事务关联规则分析:数据预处理 1.离散化： 2.序列合并 s1=3,4,3,2,4,2,0,3,4,4 s2=2,3,2,3,3,4,3,1,1,4 s3=0,3,4,1,0,1,3,3,3,4 3.数据投影 合并集D将沿着时间方向，把在同一时间窗口内的数据投影到同一事务内。假设时间窗口值为3，则TID=0的事务为： T=s1.3(0),s2.2(0),s3.0(0),s1.4(1),s2.3(1),s3.3(1),s1.3(2),s2.2(2),s3.4(2) 多元股票序列的跨事务关联规则分析:实验结果 我们定义了两个区间，分别代表不同的事件。其中，涨幅（收盘价昨收盘价）（昨收盘价）大于1%的数值定义为“涨”事件，涨幅小于-1%的数值定义为“跌”事件。 中国凤凰跌(0),仪征化纤跌(1),金杯汽车跌(1)-金杯汽车涨(2)(1.7%,83%) 多元时间序列的频繁片断模式关联规则分析 分析多元时间序列中采样值之间的关联规则，必须预先将这些数值映射到一定的区间，以降低数据之间的差异程度。这样才能在一个较小的空间，分析有限的事件之间的关联规则。否则，数据的多值性将导致产生太多的候选项而引发数据爆炸。 另一种克服数据多值性的方法是，将时间序列的片段映射为一个与其相似的片