多元时间序列中-智能科学与人工智能网站

多元时间序列中关联规则的发现史忠植董泽坤中国科学院计算技术研究所2019/9/4多元时间序列的关联规则分析关联规则：设是项的集合。任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，。每个事务有一个标识符，称为TID。设A是一个项集，事务T包含A当且仅当。关联规则是形如的蕴含式，其中,，，。},...,,{21nIIIIITTAITIABAIB关联规则的算法OptimizedApriori优点：只读取一次数据库1.OptimizedApriori是在ArioriTid的基础上，将数据结构由TID,{IID}变换为{IID},{TID}，从而迅速减少了系统的I/O操作。2.在构造候选1-项集时，每一个项（IID）携带了它在数据库中出现的位置记录集合（{TID}），使得以后的操作可以脱离数据库。3.构造k-项集时，新的项目集合（{IID}）由两个k-1项集的项目集合求并集得到，记录号集合（{TID}）由两个k-1项集的记录号集合求交集得到。缺点：消耗大量的内存大型数据库操作时会受到处理器内存容量的限制，数据可能无法一次装入。多元股票时间序列的关联规则（1）数据预处理1.数值离散化s1=3,4,3,2,4,2,0,3,4,4s2=2,3,2,3,3,4,3,1,1,4s3=0,3,4,1,0,1,3,3,3,40(深跌)1(跌)2(平)3(涨)4(大涨)0123456789股票S1股票S2股票S3多元股票时间序列的关联规则（1）TIDITEMS0s1.3,s2.2,s3.01s1.4,s2.3,s3.32s1.3,s2.2,s3.43s1.2,s2.3,s3.14s1.4,s2.3,s3.05s1.2,s2.4,s3.16s1.0,s2.3,s3.37s1.3,s2.1,s3.38s1.4,s2.1,s3.39s1.4,s2.4,s3.42.序列合并多元时间序列合并集：设时间序列的集合S={s1,s2,…,su}，Ti是在时刻i对S的观察值集合，Ti={s1(i),s2(i),…su(i)}(1≤i≤n)，多元时间序列合并集D定义为：D={T1,T2,…,Tn}。D中每组观察值作为一个事务，各分配一个识别号TID。↑↑↑s1s2s3多元股票时间序列的关联规则（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%);测试集中国证券市场1997－2001共五年间近500只股票的收盘价时间序列集（以下同）多元股票时间序列的关联规则（3）测试结果中纺机和二纺机属于典型的纺织机电企业，而陕长岭属于家电企业，他们之间为什么会出现相同的下跌走势呢？而且，用肉眼观察实际走势图，它们之间的形态也有很大差距，这个现象如何解释？在经过仔细分析后，我们发现：陕长岭中很大的一项主营业务是生产纺织机电。这项业务和纺织企业有着密切的联系，这几年间国家对纺织机电的政策也有大的调整。所以，这几只股票的下跌走势比较相同是有内在联系的。这种关系很难从实际走势图中识别，但是关联分析做到了这一点。中纺机↓1，陕长岭↓1二纺机↓1(21.6%,84.1%)多元时间序列的跨事务关联规则分析（1）“跨事务”特性的特点：强调的是出现在不同事务中各项目之间的关联关系，应用到时间序列中就是不同时刻各序列的数据特征之间的关系，如：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(1≤s≤n-w+1)为D的参考时间基准点，如果时刻s+x(0≤x≤w-1)此事件出现，则标记ei(x)属于Ts。每一个ei(x)分配一个识别号IID。多元时间序列的跨事务关联规则是形如XY的蕴涵式，并且满足以下条件：1.X∑,Y∑;2.ei(0)∈X,1≤i≤u;3.ej(q)∈X,1≤j≤u,((i=j)∧(1≤qw-1))∨((i≠j)∧(0≤qw-1));4.ei(p)∈Y,1≤i≤u,max(q)p≤w-1;5.X∩Y=多元时间序列的跨事务关联规则分析（3）和传统关联规则算法比较，跨事务关联规则算法要更复杂：①要处理的数据超过算法能承受的范围后，频繁项集的数目将变得巨大而无法处理；在跨事务分析中，每一个基本项将扩展为w（滑动时间窗口）个。假设有1000个基本项，在传统关联规则分析中，会产生至多（999＋1）*999/2=499500个候选二项集；而在跨事务分析中，会产生(1000*w-1)*(1000*w-1)/2个候选二项集，这个数字以w2的倍数增长。如果w＝3，则会有4498500（增加了9倍）个二项候选集；更严重的是，在构造候选三项集时，会有更多的增长。随着数据的增加，系统的内存将会枯竭，效率明显下降。②候选集数目的增加导致更频繁的数据库扫描动作。为统计每一个候选集的频繁支持度计数值，需要通过搜索数据库中每一条记录来确定候选集的所有项是否出现。很明显，数据库的频繁访问会占用很多运行时间。跨事务关联规则的算法ES-Apriori（1）为提高多元时间序列的跨事务关联规则分析效率，本文提出了一个扩展的分步Apriori算法：ES-Apriori，此算法从两个方面提高了系统的性能。1．仅扫描一次数据库ES-Apriori算法使用了OptimizedApriori算法的优点，将所有一项集的数据库信息读入内存，其后所有k-项集的产生均依靠k-1-项集提供的数据库信息，从而不必多次搜索数据库，降低了系统的I/O代价。2．减少了单次调入内存的数据量ES-Apriori的所有大项集保留了各项的数据库信息，从而减少了数据库扫描次数，但是它的代价是使用大量内存。所以，如何合理分配内存，是ES-Apriori方法的另一重点。通过分析数据的特征，本文利用时间序列的跨事务关联规则性质，提出了“分而治之”的策略，使每一步需要扫描的空间大幅缩减，从而降低内存的开销。跨事务关联规则的算法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,B1-A2,B2。而传统关联规则可能产生的规则有个。625646362616CCCCC跨事务关联规则的算法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步运行：每步只构造包含ei(0)|(1≤i≤u)的频繁项集，挖掘相应的的关联规则。这样，一次调入内存的数据可降低为全部调入的1/u，当有大量数据项参与运算时，此方法也能顺利运行。ES-Apriori算法分割了频繁项集空间，降低了一次调入内存的数据量，从而缓解了因数据爆炸而耗尽内存的问题。为能够快速便捷的读取跨事务关联规则X子集的支持度计数值，我们设计了一颗动态树来保存频繁项集。用每一个节点表示一个项ei(x)，由树的根节点出发所形成的数枝上所有的节点就代表一个频繁k-项集，而树枝的终点记载了这个频繁项集的支持度计数值。跨事务关联规则的算法ES-Apriori（5）:构造动态树以基本项A和B，滑动时间窗口为3的数据库为例，构造一颗6层（最长的关联规则包括6项）共有32个节点的动态树。首先，建立节点1（A0），作为第一层节点；第二项A0A1有两项，需要新建第二层链表，作为子节点直接添加到节点2；因为第三项A0A2与A0A1同属于第二层，作为A0A1的兄弟节点，加入到第二层链表中；同理，A0B0、A0B1、A0B2都属于第二层，都加入到第二层链表中。由于第二层节点的父节点只有节点1，所以第二层只需要一个链表。从第三层开始，每一个新节点可能属于不同的父节点，所以他们会被添加到不同的各自父节点的子节点链表中。例如，节点11（代表频繁项集A0A2B0）的父节点是节点3（代表频繁项集A0A2），所以被加入到节点3的子节点链表中。以此类推，所有的节点都被添加到动态树中。跨事务关联规则的算法ES-Apriori（6）:查询动态树当分解频繁项集为X子集和Y子集时，需要读取X子集的支持度计数值，从而计算XY的支持度。这一搜索过程可以在构造的动态树中快速实现。例如，我们需要得到频繁项A0A2B0B1B2中X子集A0B0B1的支持度计数值，只需要循着节点1（A0）转到第二层链表，由节点2开始顺序搜索节点找到节点4（B0），转入节点4的子节点链表，找到节点14（B1），读出它的支持度计数值。在整个搜索过程中，只需要经过5个节点，这样的速度要比搜索链表高出若干倍，也要比Hash表技术快。在设计中，将已经计算过信任度的频繁项集节点直接销毁，能够减少访问空间，进一步加快搜索速度。ES-Apriori算法流程图项名称映射,交易号映射开始载入数据数据全部载入?N扫描数据库，获得1-项集（L1）L1项的滑动窗口值是否为0？构造2-项集构造k-项集构造动态树输出规则是否还有L1？结束YNNY跨事务关联规则的算法ES-Apriori:算法性能比较ES-Apriori与E-Apriori算法的性能对比由图中可知，当项数小于20k时，E-Apriori和ES-Apriori的执行效率都很高。但是随着数据的增加，E-Apriori的内存使用量将急速增加，导致运算时间骤然变长；而ES-Apriori无论在内存上还是在时间上都呈现平稳增加的态势。在试验中，当总的项数大于30k后，E-Apriori会耗尽计算机内存而无法继续运行；而ES-Apriori却可以顺利运行。试验结论证明，分析较大数据量的多元时间序列的跨事务关联规则时，ES-Apriori算法在时间/空间性能上要优于E-Apriori算法。多元股票序列的跨事务关联规则分析:数据预处理1.离散化：2.序列合并s1=3,4,3,2,4,2,0,3,4,4s2=2,3,2,3,3,4,3,1,1,4s3=0,3,4,1,0,1,3,3,3,43.数据投影合并集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)}0(深跌)1(跌)2(平)3(涨)4(大涨)0123456789股票S1股票S2股票S3TIDITEMS0s1.3,s2.2,s3.01s1.4,s2.3,s3.32s1.3,s2.2,s3.43s1.2,s2.3,s3.14s1.4,s2.3,s3