多元时间序列中关联规则的发现(PPT-28)

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

2、时，每一个项（IID）携带了它在数据库中出现的位置记录集合（TID），使得以后的操作可以脱离数据库。3.构造k-项集时，新的项目集合（ IID ）由两个k-1项集的项目集合求并集得到，记录号集合（ TID ）由两个k-1项集的记录号集合求交集得到。n缺点：消耗大量的内存大型数据库操作时会受到处理器内存容量的限制，数据可能无法一次装入。多元股票时间序列的关联规则（1）n数据预处理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

3、 7 8 9股票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)(1in)，多元时间序列合并集D定义为

4、：D=T1,T2,Tn。D中每组观察值作为一个事务，各分配一个识别号TID。s1s2s3多元股票时间序列的关联规则（2）n规则挖掘 设：最小支持度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%);n测试集中国证券市场19972001共五年间近500只股票的收盘价时间序列集（以下同）多元股票时间序列的关联规则（3）n测试结果 中纺机和二纺机属于典型的纺织机电企业，而陕长岭属于家电企业，他们之间为什么会出现相同的下跌走势呢？而且，用肉眼观察

5、实际走势图，它们之间的形态也有很大差距，这个现象如何解释？在经过仔细分析后，我们发现：陕长岭中很大的一项主营业务是生产纺织机电。这项业务和纺织企业有着密切的联系，这几年间国家对纺织机电的政策也有大的调整。所以，这几只股票的下跌走势比较相同是有内在联系的。这种关系很难从实际走势图中识别，但是关联分析做到了这一点。 中纺机1，陕长岭1 二纺机1 (21.6%,84.1%)多元时间序列的跨事务关联规则分析（1）n“跨事务”特性的特点： 强调的是出现在不同事务中各项目之间的关联关系，应用到时间序列中就是不同时刻各序列的数据特征之间的关系，如： A公司的股票在第一天上涨，B公司的股票在第二天下跌，那么，

6、C公司的股票会在第三天上涨。（s%,c%） 这种规则包含了时间特性，规则的前件可以用来作为后件的预测条件，它们的实际使用价值是很明显的。多元时间序列的跨事务关联规则分析（2）n多元时间序列的跨事务关联规则多元时间序列的跨事务关联规则： 设= 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。

7、多元时间序列的跨事务关联规则是形如XY的蕴涵式，并且满足以下条件：1.X,Y;2.ei(0)X, 1iu;3.ej(q)X, 1ju,(i=j)(1qw-1)(ij)(0qw-1);4.ei(p)Y, 1iu, max(q) A1,A2, B1,B2;A0, A1,B0, B1-A2, B2。而传统关联规则可能产生的规则有 个。625646362616CCCCC跨事务关联规则的算法ES-Apriori（3）在计算这2条规则的置信度时，只需要搜索由A0构造的频繁项集空间，并不需要搜索由B0构造的频繁项集空间（不考虑连接时产生的重复项集）。因为这个6-项集的符合时间序列的跨事务关联规则条件的所有X

8、子集只有A0, B0、A0, A1,B0, B1，这两项都是在A0的基础上构造产生的。同理 ， 5 项 集 B 0 , A1,A2,B1, B2的X子集B0、B0, A1, B1只须搜索由B0构造的频繁项集空间。跨事务关联规则的算法ES-Apriori（4）n从上面的分析得出，挖掘所有规则可以分成u步运行：每步只构造包含ei(0)|( 1iu)的频繁项集，挖掘相应的的关联规则。这样，一次调入内存的数据可降低为全部调入的1/u，当有大量数据项参与运算时，此方法也能顺利运行。nES-Apriori算法分割了频繁项集空间，降低了一次调入内存的数据量，从而缓解了因数据爆炸而耗尽内存的问题。n为能够快速

9、便捷的读取跨事务关联规则X子集的支持度计数值，我们设计了一颗动态树来保存频繁项集。用每一个节点表示一个项ei(x)，由树的根节点出发所形成的数枝上所有的节点就代表一个频繁k-项集，而树枝的终点记载了这个频繁项集的支持度计数值。 跨事务关联规则的算法ES-Apriori（5）:构造动态树以基本项A和B，滑动时间窗口为3的数据库为例，构造一颗6层（最长的关联规则包括6项）共有32个节点的动态树。 首先，建立节点1（A0），作为第一层节点；第二项A0A1有两项，需要新建第二层链表，作为子节点直接添加到节点2；因为第三项A0A2与A0A1同属于第二层，作为A0A1的兄弟节点，加入到第二层链表中；同理，

10、A0B0、A0B1、A0B2都属于第二层，都加入到第二层链表中。由于第二层节点的父节点只有节点1，所以第二层只需要一个链表。从第三层开始，每一个新节点可能属于不同的父节点，所以他们会被添加到不同的各自父节点的子节点链表中。例如，节点11（代表频繁项集A0A2B0）的父节点是节点3（代表频繁项集A0A2），所以被加入到节点3的子节点链表中。以此类推，所有的节点都被添加到动态树中。 跨事务关联规则的算法ES-Apriori（6）:查询动态树 当分解频繁项集为X子集和Y子集时，需要读取X子集的支持度计数值，从而计算X Y的支持度。这一搜索过程可以在构造的动态树中快速实现。例如，我们需要得到频繁项A0

11、A2B0B1B2中X子集A0B0B1的支持度计数值，只需要循着节点1（A0）转到第二层链表，由节点2开始顺序搜索节点找到节点4（B0B0），转入节点4的子节点链表，找到节点14（B1），读出它的支持度计数值。在整个搜索过程中，只需要经过5个节点，这样的速度要比搜索链表高出若干倍，也要比Hash表技术快。在设计中，将已经计算过信任度的频繁项集节点直接销毁，能够减少访问空间，进一步加快搜索速度。 ES-Apriori算法流程图项名称映射,交易号映射开始载入数据数据全部载入?N扫描数据库，获得1-项集（L1）L1项的滑动窗口值是否为0？构造2-项集构造k-项集构造动态树输出规则是否还有L1？结束YN

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

13、iori算法。多元股票序列的跨事务关联规则分析:数据预处理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将沿着时间方向，把在同一时间窗口内的数据投影到同一事务内。假设时间窗口值为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 股票S3T

14、IDITEMS0s1.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.4s1s2s3多元股票序列的跨事务关联规则分析:实验结果n我们定义了两个区间，分别代表不同的事件。其中，涨幅（收盘价昨收盘价）（昨收盘价）大于1%的数值定义为“涨”事件，涨幅小于-1%的数值定义为“跌”事件。 中国凤凰跌(0),仪征化纤跌(1),金杯汽车跌(1)-金杯汽车涨(2)(1.7

15、%,83%)多元时间序列的频繁片断模式关联规则分析n分析多元时间序列中采样值之间的关联规则，必须预先将这些数值映射到一定的区间，以降低数据之间的差异程度。这样才能在一个较小的空间，分析有限的事件之间的关联规则。否则，数据的多值性将导致产生太多的候选项而引发数据爆炸。n另一种克服数据多值性的方法是，将时间序列的片段映射为一个与其相似的片段，将这些数值数据转化为“模式”，并用一个有代表性的片段代替序列中与其相似的片段。这样，数值数据的空间就可以降低到关联规则分析可以接受的范围。n我们将使用聚类的方法搜索时间序列中的频繁“模式”，并用这些模式代替时间序列中与其相似的片段，近而在经过模式匹配的多元时间

16、序列中挖掘关联规则。时间序列的相似性度量DTW距离nDTW：Dynamic Time Warping 动态时间归整（或动态时间弯折），这项技术已经在语音识别上使用了很多年，在1994年，由Berndt和Clifford首先应用到数据挖掘中。n不同序列的相似性可以通过计算它们之间的欧几里得距离来衡量，但是这种方法对序列在时间轴上相近数值的提前或推后出现会产生较大的误差。在用欧几里得距离和DTW距离分别计算四个序列的相似度，然后再对它们聚类，结果如下： 四个时间序列的聚类：欧几里得距离 DTW距离动态时间规整DTW (1)n假设我们有两个时间序列Q和C,长度分别是n和m，n为了用DTW排列这两个序

17、列，我们构造一个（n,m）的矩阵，第(i,j)单元记录两个点qi和ci之间的欧几里得距离。一条弯折的路径W，是由若干个彼此相连的矩阵单元构成，这条路经描述了Q和C之间的一种映射。设第k个单元定义为wk=(i,j)k, 则n这条弯折的路径服从许多限制：1. 边界条件 且这条路径必须由第一个单元经过矩阵到达最后一个单元。2. 连续性 设 ，那么， 。这个条件限制了允许的每一个弯折步必须彼此相邻。（包括对角线单元）3. 单调性 设 ，那么， 。 这个条件限制了W中的点在时间上的不能回退。 Kkwwwww,.,.,21nmKnm),max() 1 , 1 (1w),(mnwK),(),(1bawbaw

18、kk1, 1bbaa),(),(1bawbawkk0, 0bbaa动态时间规整DTW (2)n满足上述条件的路径数的是指数级的，然而，我们只关心整个路径中最短的、消费最少的一条路经KwCQDTWkkk1min),(图中的两个序列之间的DTW距离，可以通过动态规划的方法找到一条最短的路经。这里，每个序列采12个点，点点距离构成（12,12）的矩阵。首先初始化矩阵的每一个单元的局部距离 ，通过下面的循环，累计距离 就等于当前单元的局部距离 和相邻单元中的最短累计距离相加。这样，计算到最后一个点的时侯，一条最短路径就得了出来。 jicqjid),(),(ji),(jid)1,(), 1(),1, 1(min),(),(jijijijidji频繁片段模式关联规则分析：挖掘频繁片段模式n为了能够对时间序列中不同片段的模式进行关联规则分析，需要对时间序列中相近的片段序列（子序列）分类。在这里我们不采用由相关领域专家提供的序列模板作为分类标准，而是直接从序列中“提炼”。这一过程需要用到有关聚类（clustering）的方法。n在时间序列中，定义一个滑动时间窗口，窗口的大小w等于模式的长度pattern_length。将滑动时间窗口应用到序列s中，沿着时间的方向，每个窗口内的子序列定义一个标识，然后对于所有的n-w+1个子序列聚类。在这里，我们只需要搜集频繁出现的子序列（或片段），而