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

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

2、以后的操作可以脱离数据库。构造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,4 s3=0,3,4,1,0,1,3,3,3,40(深跌)1(跌)2(平)3(涨)4(大涨)0 1 2 3 4 5 6 7 8 9股票S1 股票S2 股票S3多元股票时间序列的关联规那么1TIDITEMS0s1

3、.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)(1in)，多元时间序列合并集D定义为：D=T1,T2,Tn。D中每组察看值作为一个事务，各分配一个识别号TID。s1s2s3多元股票时间序列的关联规那么2

4、规那么发掘 设：最小支持度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测试结果 中纺机和二纺机属于典型的纺织机电企业，而陕长岭属于家电企业，他们之间为什么会出现一样的下跌走势呢？而且，用肉眼察看实践走势图，它们之间的形状也有很大差距，这个景象如何解释？在经过仔细分析后，我们发现：陕长岭中很大的一项主营业务是消费纺织机电。

5、这项业务和纺织企业有着亲密的联络，这几年间国家对纺织机电的政策也有大的调整。所以，这几只股票的下跌走势比较一样是有内在联络的。这种关系很难从实践走势图中识别，但是关联分析做到了这一点。 中纺机1，陕长岭1 二纺机1 (21.6%,84.1%)多元时间序列的跨事务关联规那么分析1“跨事务特性的特点： 强调的是出如今不同事务中各工程之间的关联关系，运用到时间序列中就是不同时辰各序列的数据特征之间的关系，如： A公司的股票在第一天上涨，B公司的股票在第二天下跌，那么，C公司的股票会在第三天上涨。s%,c% 这种规那么包含了时间特性，规那么的前件可以用来作为后件的预测条件，它们的实践运用价值是很明显的

6、。多元时间序列的跨事务关联规那么分析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)此事件出现，那么标志ei(x) 属于Ts。每一个 ei(x)分配一个识别号IID。多元时间序列的跨事务关联规那么是形如XY的蕴涵式，并且满足以下条件：X,Y;ei(0)X, 1iu;ej(q)X, 1ju,(i=j)(1qw-1)(ij)(0qw-1);e

7、i(p)Y, 1iu, max(q) A1,A2, B1,B2;A0, A1,B0, B1-A2, B2。而传统关联规那么能够产生的规那么有 个。跨事务关联规那么的算法ES-Apriori3在计算这2条规那么的置信度时，只需求搜索由A0构造的频繁项集空间，并不需求搜索由B0构造的频繁项集空间不思索衔接时产生的反复项集。由于这个6-项集的符合时间序列的跨事务关联规那么条件的一切X子集只需A0, B0、A0, A1,B0, B1，这两项都是在A0的根底上构造产生的。同理，5项集B0, A1,A2,B1, B2的X子集B0、B0, A1, B1只须搜索由B0构造的频繁项集空间。跨事务关联规那么的算法

8、ES-Apriori4从上面的分析得出，发掘一切规那么可以分成u步运转：每步只构造包含ei(0)|( 1iu)的频繁项集，发掘相应的的关联规那么。这样，一次调入内存的数据可降低为全部调入的1/u，当有大量数据项参与运算时，此方法也能顺利运转。ES-Apriori算法分割了频繁项集空间，降低了一次调入内存的数据量，从而缓解了因数据爆炸而耗尽内存的问题。为可以快速便利的读取跨事务关联规那么X子集的支持度计数值，我们设计了一颗动态树来保管频繁项集。用每一个节点表示一个项ei(x)，由树的根节点出发所构成的数枝上一切的节点就代表一个频繁k-项集，而树枝的终点记载了这个频繁项集的支持度计数值。 跨事务关

9、联规那么的算法ES-Apriori5:构造动态树以根本项A和B，滑动时间窗口为3的数据库为例，构造一颗6层最长的关联规那么包括6项共有32个节点的动态树。 首先，建立节点1A0，作为第一层节点；第二项A0A1有两项，需求新建第二层链表，作为子节点直接添加到节点2；由于第三项A0A2与A0A1同属于第二层，作为A0A1的兄弟节点，参与到第二层链表中；同理，A0B0、A0B1、A0B2都属于第二层，都参与到第二层链表中。由于第二层节点的父节点只需节点1，所以第二层只需求一个链表。从第三层开场，每一个新节点能够属于不同的父节点，所以他们会被添加到不同的各自父节点的子节点链表中。例如，节点11代表频繁

10、项集A0A2B0的父节点是节点3代表频繁项集A0A2，所以被参与到节点3的子节点链表中。以此类推，一切的节点都被添加到动态树中。 跨事务关联规那么的算法ES-Apriori6:查询动态树 当分解频繁项集为X子集和Y子集时，需求读取X子集的支持度计数值，从而计算X Y的支持度。这一搜索过程可以在构造的动态树中快速实现。例如，我们需求得到频繁项A0A2B0B1B2中X子集A0B0B1的支持度计数值，只需求循着节点1A0转到第二层链表，由节点2开场顺序搜索节点找到节点4B0，转入节点4的子节点链表，找到节点14B1，读出它的支持度计数值。在整个搜索过程中，只需求经过5个节点，这样的速度要比搜索链表高

11、出假设干倍，也要比Hash表技术快。在设计中，将曾经计算过信任度的频繁项集节点直接销毁，可以减少访问空间，进一步加快搜索速度。 ES-Apriori算法流程图项称号映射,买卖号映射开场载入数据数据全部载入?N扫描数据库，获得1-项集L1L1项的滑动窗口值能否为0？构造2-项集构造k-项集构造动态树输出规那么能否还有L1？终了YNNY跨事务关联规那么的算法ES-Apriori:算法性能比较ES-Apriori与E-Apriori算法的性能对比 由图中可知，当项数小于20k时，E-Apriori和ES-Apriori的执行效率都很高。但是随着数据的添加，E-Apriori的内存运用量将急速添加，导

12、致运算时间骤然变长；而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,4 s3=0,3,4,1,0,1,3,3,3,43.数据投影 合并集D将沿着时间方向，把在同一时

13、间窗口内的数据投影到同一事务内。假设时间窗口值为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(大涨)0 1 2 3 4 5 6 7 8 9股票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.05s1.2,s2.4,s3.16s1.0,s2.3,s3.37s1.3,s2.1,s3.38s1.4

14、,s2.1,s3.39s1.4,s2.4,s3.4s1s2s3多元股票序列的跨事务关联规那么分析:实验结果我们定义了两个区间，分别代表不同的事件。其中，涨幅收盘价昨收盘价昨收盘价大于1%的数值定义为“涨事件，涨幅小于-1%的数值定义为“跌事件。 中国凤凰跌(0),仪征化纤跌(1),金杯汽车跌(1)-金杯汽车涨(2)(1.7%,83%)多元时间序列的频繁片断方式关联规那么分析分析多元时间序列中采样值之间的关联规那么，必需预先将这些数值映射到一定的区间，以降低数据之间的差别程度。这样才干在一个较小的空间，分析有限的事件之间的关联规那么。否那么，数据的多值性将导致产生太多的候选项而引发数据爆炸。另一

15、种抑制数据多值性的方法是，将时间序列的片段映射为一个与其类似的片段，将这些数值数据转化为“方式，并用一个有代表性的片段替代序列中与其类似的片段。这样，数值数据的空间就可以降低到关联规那么分析可以接受的范围。我们将运用聚类的方法搜索时间序列中的频繁“方式，并用这些方式替代时间序列中与其类似的片段，近而在经过方式匹配的多元时间序列中发掘关联规那么。时间序列的类似性度量DTW间隔DTW：Dynamic Time Warping 动态时间归整或动态时间弯折，这项技术曾经在语音识别上运用了很多年，在1994年，由Berndt和Clifford首先运用到数据发掘中。不同序列的类似性可以经过计算它们之间的欧

16、几里得间隔来衡量，但是这种方法对序列在时间轴上相近数值的提早或推后出现会产生较大的误差。在用欧几里得间隔和DTW间隔分别计算四个序列的类似度，然后再对它们聚类，结果如下： 四个时间序列的聚类：欧几里得间隔 DTW间隔动态时间规整DTW (1)假设我们有两个时间序列Q和C,长度分别是n和m，为了用DTW陈列这两个序列，我们构造一个n,m的矩阵，第(i,j)单元记录两个点qi和ci之间的欧几里得间隔。一条弯折的途径W，是由假设干个彼此相连的矩阵单元构成，这条路经描画了Q和C之间的一种映射。设第k个单元定义为wk=(i,j)k, 那么这条弯折的途径服从许多限制：1. 边境条件 且这条途径必需由第一个

17、单元经过矩阵到达最后一个单元。2. 延续性 设 ，那么， 。这个条件限制了允许的每一个弯折步必需彼此相邻。包括对角线单元3. 单调性 设 ，那么， 。 这个条件限制了W中的点在时间上的不能回退。 动态时间规整DTW (2)满足上述条件的途径数的是指数级的，然而，我们只关怀整个途径中最短的、消费最少的一条路经图中的两个序列之间的DTW间隔，可以经过动态规划的方法找到一条最短的路经。这里，每个序列采12个点，点点间隔构成12,12的矩阵。首先初始化矩阵的每一个单元的部分间隔 ，经过下面的循环，累计间隔 就等于当前单元的部分间隔 和相邻单元中的最短累计间隔相加。这样，计算到最后一个点的时侯，一条最短

18、途径就得了出来。 频繁片段方式关联规那么分析：发掘频繁片段方式为了可以对时间序列中不同片段的方式进展关联规那么分析，需求对时间序列中相近的片段序列子序列分类。在这里我们不采用由相关领域专家提供的序列模板作为分类规范，而是直接从序列中“提炼。这一过程需求用到有关聚类clustering的方法。在时间序列中，定义一个滑动时间窗口，窗口的大小w等于方式的长度pattern_length。将滑动时间窗口运用到序列s中，沿着时间的方向，每个窗口内的子序列定义一个标识，然后对于一切的n-w+1个子序列聚类。在这里，我们只需求搜集频繁出现的子序列或片段，而个别景象将不再讨论关联分析只关怀频繁项之间的规那么，这样可以降低