第3期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·503· 法的挖掘效率低。为解决这一问题，很多学者从 中。Schluter等u提出利用2种树结构挖掘时间 不同角度提出相应的方法。魏玲等图借鉴文献[9] 序列的关联规则，Rashid等2o基于树结构，采用模 的MapReduce框架，提出了基于MapReduce的 式增长方法挖掘时态模式并给出关联规则，Pankaj Apriori改进算法(MapReduce算法)，算法的基本思 等P也用到了FP-tree结构。另外，马慧等利用 想是将频繁K-1项集的前K-2项作为键，将最后 FP-tree的优势并考虑项间具有不同的有效时间， 一项作为值，并将具有相同键的频繁K-1项集合 提出一种基于FP-tree挖掘时态关联规则算法。 并，以实现快速挖掘出候选频繁K项集。此外， 鉴于上述文献的理论研究及其所存在的问 他们还提出性能更高的基于Bigtable与MapRe- 题，本文针对多条时间序列数据，通过数据降维 duce的Apriori改进算法(BM Apriori算法)，算法 并将符号化后的降维数据用趋势项-位置表示， 以事务集序号记录每个项出现的位置，通过求频 再利用树结构找出频繁K项集，该过程通过求树 繁K-1项集间的序号列表交集，即可快速获取候 的叶子节点与列表项间的信息交集，便可判断该 选频繁K项集。Zhanglo基于概率论知识，通过参 项是否与该树枝中的所有结点构成频繁K项集， 数α和b估算数据项集同时出现的概率，进而确 无需产生大量的候选频繁项集，此外，算法还能 定频繁项集，最终实现对Apriori算法的改进，但 给出频繁项集的支持度和置信度。由于在某些情 是该算法存在频繁项集缺失的可能性。Tran等 况下需要考虑多条时间序列在同时区内的关联关 为了减少Apriori算法扫描数据库的次数，将事 系，例如：在带有时间属性的零售商品销售数据 务集转化成事务矩阵，但是在矩阵运算过程中需 中，顾客常会同时购买A和B等商品，若仅知道 要消耗较长时间。杨秋翔等基于1和0表示数 商品A的需求变化趋势但不知道商品B的变化 据项出现和未出现的数据集表示法创建权值向量 趋势，此时可以通过挖掘商品间的销售量变化趋 矩阵，提出可以在数据挖掘过程中不断缩减矩阵 势的关联规则，进而预测商品B的需求变化趋 的算法(WV_Apriori算法)，以此达到提高挖掘频 势。因此，在同时区内，本文提出一种基于同步 繁K项集速率的目的，但是当数据量越来越大 频繁树的时序数据关联规则算法(synchronize fre- 时，创建的矩阵也会随之扩大，进而降低挖掘速率。an quent tree,SFT). 等I]提出能快速挖掘频繁项集的FP-growth算 法，该算法将原数据存储到FP-tree中，从中挖掘 1时间序列特征表示 频繁项集，从而不会产生候选频繁项集，但是该 挖掘多条时间序列数据间的频繁项集，需要 算法不能给出频繁项集的支持度和置信度。此 先对原数据进行特征表示。本文定义了2种表示 外，上述算法不能直接用于时间序列数据的关联 规则挖掘。Das等于1998年首次提出挖掘时 法，即趋势项-位置表示法和事务集表示法。经 典算法Apriori、FP-growth以及近些年提出的 间序列数据的关联规则，此后该研究成为数据挖 掘领域的热门方向。Velumani等在数据预处 MapReduce、BM_Apriori和WV_Apriori算法都是 基于事务集表示的数据，而SFT算法则是基于趋 理阶段，先将时间序列数据转为多个事务集，再 用Apriori算法挖掘关联规则。赵益1提出了Im- 势项一位置表示的数据。 proved-.Apriori算法，算法通过计算位置列表的方 1.1事务集表示法和趋势项-位置表示法 式可避免多次扫描数据库。然而这2个算法均是 Apriori、FP-growth、MapReduce、BM_Apri- 基于Apriori,,它们都会产生大量的候选频繁项 ori和WV_Apriori等算法只能挖掘事务集数据的 集，会导致其挖掘效率不高。针对时间序列数 频繁项集，对于时间序列数据，需要将其转换为 据，其他学者也做出了相应的努力。Das等1先 事务集才可以使用。本文将时间序列转换为事务 将一条时间序列等分成多条子序列，再挖掘多个 集的方法定义为事务集表示法，其转换规则为： 时间序列的项间关联规则，但是他并没有给出 多条时间序列数据在同时区内的趋势项组合表示 3支及以上股票的实验结果。Chen等)所提的 一个事务。例如：TA=(a1,a2,a3)、TB=(b1,b2,b3)和 CEMiner算法基于区间数据，发现多个项间的闭 Tc=(c1,c2,c)是3条符号化后的时间序列，其转换 合时态模式。Ruan等I提出一种可以在大规模 为事务集的结果为[(a,b1,C1),(a2,b2,c2),(as,b,c】 区间型时态数据上并行和定量挖掘时间序列模式 趋势项-位置表示法是为了提出SFT算法而 的算法。然而，这2种方法不能给出频繁项集的 定义的一种时间序列转换方法，其关键在于考虑 支持度和置信度。由于树形结构分支明确，直观 到时间序列数据的时间属性具有一维性的特点 易懂，因而树形存储结构是一种较为常用的存储 表示规则为趋势项+位置列表，其中趋势项是由 形式，许多学者也将该存储结构应用到数据挖掘 时间序列进行线性分段后的斜率确定，共分上法的挖掘效率低。为解决这一问题，很多学者从 不同角度提出相应的方法。魏玲等[8] 借鉴文献 [9] 的 MapReduce 框架，提出了基于 MapReduce 的 Apriori 改进算法 (MapReduce算法)，算法的基本思 想是将频繁 K−1 项集的前 K−2项作为键，将最后 一项作为值，并将具有相同键的频繁 K−1 项集合 并，以实现快速挖掘出候选频繁 K 项集。此外， 他们还提出性能更高的基于 Bigtable 与 MapRe￾duce 的 Apriori 改进算法 (BM_Apriori 算法)，算法 以事务集序号记录每个项出现的位置，通过求频 繁 K−1 项集间的序号列表交集，即可快速获取候 选频繁 K 项集。Zhang[10]基于概率论知识，通过参 数 a 和 b 估算数据项集同时出现的概率，进而确 定频繁项集，最终实现对 Apriori 算法的改进，但 是该算法存在频繁项集缺失的可能性。Tran 等 [11] 为了减少 Apriori 算法扫描数据库的次数，将事 务集转化成事务矩阵，但是在矩阵运算过程中需 要消耗较长时间。杨秋翔等[12] 基于 1 和 0 表示数 据项出现和未出现的数据集表示法创建权值向量 矩阵，提出可以在数据挖掘过程中不断缩减矩阵 的算法 (WV_Apriori 算法)，以此达到提高挖掘频 繁 K 项集速率的目的，但是当数据量越来越大 时，创建的矩阵也会随之扩大，进而降低挖掘速率。Han 等 [13] 提出能快速挖掘频繁项集的 FP-growth 算 法，该算法将原数据存储到 FP-tree 中，从中挖掘 频繁项集，从而不会产生候选频繁项集，但是该 算法不能给出频繁项集的支持度和置信度。此 外，上述算法不能直接用于时间序列数据的关联 规则挖掘。Das 等 [14] 于 1998 年首次提出挖掘时 间序列数据的关联规则，此后该研究成为数据挖 掘领域的热门方向。Velumani 等 [15] 在数据预处 理阶段，先将时间序列数据转为多个事务集，再 用 Apriori 算法挖掘关联规则。赵益[16] 提出了 Im￾proved-Apriori 算法，算法通过计算位置列表的方 式可避免多次扫描数据库。然而这 2 个算法均是 基于 Apriori，它们都会产生大量的候选频繁项 集，会导致其挖掘效率不高。针对时间序列数 据，其他学者也做出了相应的努力。Das 等 [14] 先 将一条时间序列等分成多条子序列，再挖掘多个 时间序列的项间关联规则，但是他并没有给出 3 支及以上股票的实验结果。Chen 等 [17] 所提的 CEMiner 算法基于区间数据，发现多个项间的闭 合时态模式。Ruan 等 [18] 提出一种可以在大规模 区间型时态数据上并行和定量挖掘时间序列模式 的算法。然而，这 2 种方法不能给出频繁项集的 支持度和置信度。由于树形结构分支明确，直观 易懂，因而树形存储结构是一种较为常用的存储 形式，许多学者也将该存储结构应用到数据挖掘 中。Schlüter等 [19] 提出利用 2 种树结构挖掘时间 序列的关联规则，Rashid 等 [20] 基于树结构，采用模 式增长方法挖掘时态模式并给出关联规则，Pankaj 等 [21] 也用到了 FP-tree结构。另外，马慧等[22] 利用 FP-tree 的优势并考虑项间具有不同的有效时间， 提出一种基于 FP-tree 挖掘时态关联规则算法。 鉴于上述文献的理论研究及其所存在的问 题，本文针对多条时间序列数据，通过数据降维 并将符号化后的降维数据用趋势项−位置表示， 再利用树结构找出频繁 K 项集，该过程通过求树 的叶子节点与列表项间的信息交集，便可判断该 项是否与该树枝中的所有结点构成频繁 K 项集， 无需产生大量的候选频繁项集，此外，算法还能 给出频繁项集的支持度和置信度。由于在某些情 况下需要考虑多条时间序列在同时区内的关联关 系，例如：在带有时间属性的零售商品销售数据 中，顾客常会同时购买 A 和 B 等商品，若仅知道 商品 A 的需求变化趋势但不知道商品 B 的变化 趋势，此时可以通过挖掘商品间的销售量变化趋 势的关联规则，进而预测商品 B 的需求变化趋 势。因此，在同时区内，本文提出一种基于同步 频繁树的时序数据关联规则算法 (synchronize fre￾quent tree, SFT)。 1 时间序列特征表示 挖掘多条时间序列数据间的频繁项集，需要 先对原数据进行特征表示。本文定义了 2 种表示 法，即趋势项−位置表示法和事务集表示法。经 典算法 Apriori、FP-growth 以及近些年提出的 MapReduce、BM_Apriori 和 WV_Apriori 算法都是 基于事务集表示的数据，而 SFT 算法则是基于趋 势项−位置表示的数据。 1.1 事务集表示法和趋势项−位置表示法 Apriori、FP-growth、MapReduce、BM_Apri￾ori 和 WV_Apriori 等算法只能挖掘事务集数据的 频繁项集，对于时间序列数据，需要将其转换为 事务集才可以使用。本文将时间序列转换为事务 集的方法定义为事务集表示法，其转换规则为： 多条时间序列数据在同时区内的趋势项组合表示 一个事务。例如：TA=(a1 ,a2 ,a3 )、TB=(b1 ,b2 ,b3 ) 和 TC=(c1 ,c2 ,c3 ) 是 3 条符号化后的时间序列，其转换 为事务集的结果为 [(a1 ,b1 ,c1 ), (a2 ,b2 ,c2 ), (a3 ,b3 ,c3 )]。 趋势项−位置表示法是为了提出 SFT 算法而 定义的一种时间序列转换方法，其关键在于考虑 到时间序列数据的时间属性具有一维性的特点， 表示规则为趋势项+位置列表，其中趋势项是由 时间序列进行线性分段后的斜率确定，共分上 第 3 期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·503·