《[精选]多元时间序列中-智能科学与人工智能网站》由会员分享，可在线阅读，更多相关《[精选]多元时间序列中-智能科学与人工智能网站（29页珍藏版）》请在金锄头文库上搜索。
1、,多元时间序列中 关联规则的发现 史忠植 董泽坤 中国科学院计算技术研究所 2021/5/17,多元时间序列的关联规则分析,关联规则：设 是项的集合。任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合， 。每个事务有一个标识符，称为TID。设A是一个项集，事务T包含A当且仅当 。关联规则是形如 的蕴含式，其中, ， ， 。,关联规则的算法OptimizedApriori,优点：只读取一次数据库 OptimizedApriori是在ArioriTid的基础上，将数据结构由变换为，从而迅速减少了系统的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.序列合并 多元时间序列合并集：设时间序列的集合S=s1, s2, su， Ti
3、是在时刻i对S的观察值集合，Ti=s1(i),s2(i),su(i)(1in)，多元时间序列合并集D定义为：D=T1,T2,Tn。D中每组观察值作为一个事务，各分配一个识别号TID。,多元股票时间序列的关联规则（2）,规则挖掘 设：最小支持度20，最小信任度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）,测试结果,中纺机和
4、二纺机属于典型的纺织机电企业，而陕长岭属于家电企业，他们之间为什么会出现相同的下跌走势呢？而且，用肉眼观察实际走势图，它们之间的形态也有很大差距，这个现象如何解释？在经过仔细分析后，我们发现：陕长岭中很大的一项主营业务是生产纺织机电。这项业务和纺织企业有着密切的联系，这几年间国家对纺织机电的政策也有大的调整。所以，这几只股票的下跌走势比较相同是有内在联系的。这种关系很难从实际走势图中识别，但是关联分析做到了这一点。,中纺机1，陕长岭1 二纺机1 (21.6%,84.1%),多元时间序列的跨事务关联规则分析（1）,“跨事务”特性的特点： 强调的是出现在不同事务中各项目之间的关联关系，应用到时间序
5、列中就是不同时刻各序列的数据特征之间的关系，如： A公司的股票在第一天上涨，B公司的股票在第二天下跌，那么，C公司的股票会在第三天上涨。（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 (0 xw-1)此事件出现
6、，则标记ei(x) 属于Ts。每一个 ei(x)分配一个识别号IID。多元时间序列的跨事务关联规则是形如XY的蕴涵式，并且满足以下条件： X,Y; ei(0)X, 1iu; ej(q)X, 1ju,(i=j)(1qw-1)(ij)(0qw-1); ei(p)Y, 1iu, max(q) pw-1; XY=,多元时间序列的跨事务关联规则分析（3）,和传统关联规则算法比较，跨事务关联规则算法要更复杂： 要处理的数据超过算法能承受的范围后，频繁项集的数目将变得巨大而无法处理； 在跨事务分析中，每一个基本项将扩展为w（滑动时间窗口）个。假设有1000个基本项，在传统关联规则分析中，会产生至多（9991
7、）*999 /2 =499500个候选二项集；而在跨事务分析中，会产生(1000*w-1)*(1000*w-1)/2个候选二项集，这个数字以w2的倍数增长。如果w3，则会有4498500（增加了9倍）个二项候选集；更严重的是，在构造候选三项集时，会有更多的增长。随着数据的增加，系统的内存将会枯竭，效率明显下降。 候选集数目的增加导致更频繁的数据库扫描动作。 为统计每一个候选集的频繁支持度计数值，需要通过搜索数据库中每一条记录来确定候选集的所有项是否出现。很明显，数据库的频繁访问会占用很多运行时间。,跨事务关联规则的算法ES-Apriori（1）,为提高多元时间序列的跨事务关联规则分析效率，本文
8、提出了一个扩展的分步Apriori算法：ES-Apriori，此算法从两个方面提高了系统的性能。 1仅扫描一次数据库 ES-Apriori算法使用了OptimizedApriori算法的优点，将所有一项集的数据库信息读入内存，其后所有k-项集的产生均依靠k-1-项集提供的数据库信息，从而不必多次搜索数据库，降低了系统的I/O代价。 2减少了单次调入内存的数据量 ES-Apriori的所有大项集保留了各项的数据库信息，从而减少了数据库扫描次数，但是它的代价是使用大量内存。所以，如何合理分配内存，是ES-Apriori方法的另一重点。通过分析数据的特征，本文利用时间序列的跨事务关联规则性质，提出了
9、“分而治之”的策略，使每一步需要扫描的空间大幅缩减，从而降低内存的开销。,跨事务关联规则的算法ES-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,
10、 B1-A2, B2。而传统关联规则可能产生的规则有 个。,跨事务关联规则的算法ES-Apriori（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步运行：每步只
11、构造包含ei(0)|( 1iu)的频繁项集，挖掘相应的的关联规则。这样，一次调入内存的数据可降低为全部调入的1/u，当有大量数据项参与运算时，此方法也能顺利运行。 ES-Apriori算法分割了频繁项集空间，降低了一次调入内存的数据量，从而缓解了因数据爆炸而耗尽内存的问题。 为能够快速便捷的读取跨事务关联规则X子集的支持度计数值，我们设计了一颗动态树来保存频繁项集。用每一个节点表示一个项ei(x)，由树的根节点出发所形成的数枝上所有的节点就代表一个频繁k-项集，而树枝的终点记载了这个频繁项集的支持度计数值。,跨事务关联规则的算法ES-Apriori（5）:构造动态树,以基本项A和B，滑动时间窗
12、口为3的数据库为例，构造一颗6层（最长的关联规则包括6项）共有32个节点的动态树。 首先，建立节点1（A0），作为第一层节点；第二项A0A1有两项，需要新建第二层链表，作为子节点直接添加到节点2；因为第三项A0A2与A0A1同属于第二层，作为A0A1的兄弟节点，加入到第二层链表中；同理，A0B0、A0B1、A0B2都属于第二层，都加入到第二层链表中。由于第二层节点的父节点只有节点1，所以第二层只需要一个链表。从第三层开始，每一个新节点可能属于不同的父节点，所以他们会被添加到不同的各自父节点的子节点链表中。例如，节点11（代表频繁项集A0A2B0）的父节点是节点3（代表频繁项集A0A2），所以被
13、加入到节点3的子节点链表中。以此类推，所有的节点都被添加到动态树中。,跨事务关联规则的算法ES-Apriori（6）:查询动态树,当分解频繁项集为X子集和Y子集时，需要读取X子集的支持度计数值，从而计算X Y的支持度。这一搜索过程可以在构造的动态树中快速实现。例如，我们需要得到频繁项A0A2B0B1B2中X子集A0B0B1的支持度计数值，只需要循着节点1（A0）转到第二层链表，由节点2开始顺序搜索节点找到节点4（B0），转入节点4的子节点链表，找到节点14（B1），读出它的支持度计数值。在整个搜索过程中，只需要经过5个节点，这样的速度要比搜索链表高出若干倍，也要比Hash表技术快。在设计中，将
14、已经计算过信任度的频繁项集节点直接销毁，能够减少访问空间，进一步加快搜索速度。,ES-Apriori算法流程图,跨事务关联规则的算法ES-Apriori:算法性能比较,ES-Apriori与E-Apriori算法的性能对比 由图中可知，当项数小于20k时，E-Apriori和ES-Apriori的执行效率都很高。但是随着数据的增加，E-Apriori的内存使用量将急速增加，导致运算时间骤然变长；而ES-Apriori无论在内存上还是在时间上都呈现平稳增加的态势。在试验中，当总的项数大于30k后，E-Apriori会耗尽计算机内存而无法继续运行；而ES-Apriori却可以顺利运行。试验结论证明
15、，分析较大数据量的多元时间序列的跨事务关联规则时，ES-Apriori算法在时间/空间性能上要优于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
16、(2),多元股票序列的跨事务关联规则分析:实验结果,我们定义了两个区间，分别代表不同的事件。其中，涨幅（收盘价昨收盘价）（昨收盘价）大于1%的数值定义为“涨”事件，涨幅小于-1%的数值定义为“跌”事件。 中国凤凰跌(0),仪征化纤跌(1),金杯汽车跌(1)-金杯汽车涨(2)(1.7%,83%),多元时间序列的频繁片断模式关联规则分析,分析多元时间序列中采样值之间的关联规则，必须预先将这些数值映射到一定的区间，以降低数据之间的差异程度。这样才能在一个较小的空间，分析有限的事件之间的关联规则。否则，数据的多值性将导致产生太多的候选项而引发数据爆炸。 另一种克服数据多值性的方法是，将时间序列的片段映射为一个与其相似的片段，将这些数值数据转化为“模式”，并用一个有代表性的片段代替序列中与其相似的片段。这样，数值数据的空间就可以降低到关联规则分析可以接受的范围。 我们将使用聚类的方法搜索时间序列中的频繁“模式”，并用这些模式代替时间序列中与其相似的片段，近而在经过模式匹配的多元时间序列中挖掘关联规则。,时间序列的相似性度量DTW距离,DTW：Dynamic Time Warping 动态时间归整
