【知识工程】基于同步频繁树的时间序列关联规则分析

第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0L:10.11992/tis.202008012 基于同步频繁树的时间序列关联规则分析 李海林2，龙芳菊 (1.华侨大学信息管理系，福建泉州362021,2.华侨大学现代应用统计与大数据研究中心，福建厦门361021) 摘要：针对经典算法Apriori和频繁模式增长算法(frequent pattern growth,FP-growth)不能直接对时间序列数 据进行关联规则挖掘的问题，提出一种同步频繁树算法(synchronize frequent tree,.SFT)。利用时间序列的时间 属性具有一维性的特点，定义趋势项-位置表示法表示时间序列数据，将首条时间序列构建成一棵基础树，通 过计算树叶子节点与列表项的信息交集，可判断其是否与该树枝中的所有节点构成频繁K项集。在ST算法中， 用趋势项-位置表示的数据内存占用情况要优于原始数据，并且在挖掘过程中不会产生候选频繁项集，使得算 法在整个挖掘过程中表现出较好的时间性能。基于商品数据和股票数据的数值实验表明，SFT算法所得结果 不仅与其他5种对比算法的结果一致，在各量级的数据和不同的支持度计数中，其时间复杂度都要优于对比算法。 关键词：时间序列；线性分段；趋势项-位置：事务集表示：频繁项集；同步频繁树：关联规则：时间效率 中图分类号：TP311.13文献标志码：A文章编号：1673-4785(2021)03-0502-09 中文引用格式：李海林，龙芳菊.基于同步频繁树的时间序列关联规则分析.智能系统学报，2021,16(3)：502-510. 英文引用格式：LI Hailin,,LONGFangju.Association rules analysis of time series based on synchronization frequent treeJ.CAAl transactions on intelligent systems,2021,16(3):502-510. Association rules analysis of time series based on synchronization frequent tree LI Hailin2,LONG Fangju' (1.Department of Information Systems,Huagiao University,Quanzhou 362021,China;2.Research Center of Applied Statistics and Big Data,Huaqiao University,Xiamen 361021,China) Abstract:In this paper,a synchronization frequent tree (SFT)algorithm is proposed to solve the problem that the clas- sic algorithms apriori and FP-growth can not directly mine the association rules of time series data.By making use of the time attribute of time series,which has one-dimensional characteristics,we define the trend item-position representation method to represent the time series data,construct a basic tree for the first time series,and then find the information between the leaf nodes of the tree and the list items by intersection,and then judge whether the item and all the nodes in the branch constitute a frequent K itemsets.In the SFT algorithm,the memory occupancy of the data represented by the trend item-location is better than that of the original data,and candidate frequent itemsets will not be generated during the mining process,which makes the algorithm show better time performance in the entire mining process.Numerical experiments based on commodity data and stock data show that the results of the SFT algorithm are consistent with the results of the comparison algorithm,and what's more,in all levels of data,its time complexity is better than that of the comparison algorithm. Keywords:time series;linear segmentation;trend item-location;transactionset representation;frequent itemsets;syn- chronize frequent trees,association rules,time efficiency 时间序列数据是指一系列时间及其对应属性 息，进而为相关部门或企业的工作提供指导性建 值组成的序列集合，常见于医学、金融、水文等领 议。关联规则是由Agrawal等Io首次提出的，先 域凹。通过分析这些数据，如疾病回、股票和水 找出频繁项集，再通过项集的支持度和置信度等 文数据)等，研究者可以发现相关问题的潜在信 指标，分析被研究对象间的关联关系。例如，购 收稿日期：2020-08-12. 物篮分析案例就是关联规则的一个经典应用。 基金项目：国家自然科学基金项目(71771094.61300139)：福建 Apriori算法是由Agrawal等II提出的，在挖掘频 省自然科学基金项目(2019J01067);福建省社会科 学规划一般项目(FJ2020B088). 繁项集的过程中，该算法不仅要多次扫描数据 通信作者：李海林.E-mail:hailin@hqu.edu.cn 库，还会产生大量的候选频繁项集，因而导致算

DOI: 10.11992/tis.202008012 基于同步频繁树的时间序列关联规则分析 李海林1,2，龙芳菊1 （1. 华侨大学 信息管理系，福建 泉州 362021; 2. 华侨大学 现代应用统计与大数据研究中心，福建 厦门 361021） 摘 要：针对经典算法 Apriori 和频繁模式增长算法 (frequent pattern growth, FP-growth) 不能直接对时间序列数 据进行关联规则挖掘的问题，提出一种同步频繁树算法（synchronize frequent tree, SFT）。利用时间序列的时间 属性具有一维性的特点，定义趋势项−位置表示法表示时间序列数据，将首条时间序列构建成一棵基础树，通 过计算树叶子节点与列表项的信息交集，可判断其是否与该树枝中的所有节点构成频繁 K 项集。在 SFT 算法中， 用趋势项−位置表示的数据内存占用情况要优于原始数据，并且在挖掘过程中不会产生候选频繁项集，使得算 法在整个挖掘过程中表现出较好的时间性能。基于商品数据和股票数据的数值实验表明，SFT 算法所得结果 不仅与其他 5 种对比算法的结果一致，在各量级的数据和不同的支持度计数中，其时间复杂度都要优于对比算法。 关键词：时间序列；线性分段；趋势项−位置；事务集表示；频繁项集；同步频繁树；关联规则；时间效率 中图分类号：TP311.13 文献标志码：A 文章编号：1673−4785(2021)03−0502−09 中文引用格式：李海林, 龙芳菊. 基于同步频繁树的时间序列关联规则分析 [J]. 智能系统学报, 2021, 16(3): 502–510. 英文引用格式：LI Hailin, LONG Fangju. Association rules analysis of time series based on synchronization frequent tree[J]. CAAI transactions on intelligent systems, 2021, 16(3): 502–510. Association rules analysis of time series based on synchronization frequent tree LI Hailin1,2 ，LONG Fangju1 (1. Department of Information Systems, Huaqiao University, Quanzhou 362021, China; 2. Research Center of Applied Statistics and Big Data, Huaqiao University, Xiamen 361021, China) Abstract: In this paper, a synchronization frequent tree (SFT) algorithm is proposed to solve the problem that the clas￾sic algorithms apriori and FP-growth can not directly mine the association rules of time series data. By making use of the time attribute of time series, which has one-dimensional characteristics, we define the trend item-position representation method to represent the time series data, construct a basic tree for the first time series, and then find the information between the leaf nodes of the tree and the list items by intersection, and then judge whether the item and all the nodes in the branch constitute a frequent K itemsets. In the SFT algorithm, the memory occupancy of the data represented by the trend item-location is better than that of the original data, and candidate frequent itemsets will not be generated during the mining process, which makes the algorithm show better time performance in the entire mining process. Numerical experiments based on commodity data and stock data show that the results of the SFT algorithm are consistent with the results of the comparison algorithm, and what’s more, in all levels of data, its time complexity is better than that of the comparison algorithm. Keywords: time series; linear segmentation; trend item-location; transactionset representation; frequent itemsets; syn￾chronize frequent trees; association rules; time efficiency 时间序列数据是指一系列时间及其对应属性 值组成的序列集合，常见于医学、金融、水文等领 域 [1]。通过分析这些数据，如疾病[2] 、股票[3-4] 和水 文数据[5] 等，研究者可以发现相关问题的潜在信 息，进而为相关部门或企业的工作提供指导性建 议。关联规则是由 Agrawal 等 [6] 首次提出的，先 找出频繁项集，再通过项集的支持度和置信度等 指标，分析被研究对象间的关联关系。例如，购 物篮分析案例就是关联规则的一个经典应用。 Apriori 算法是由 Agrawal 等 [7] 提出的，在挖掘频 繁项集的过程中，该算法不仅要多次扫描数据 库，还会产生大量的候选频繁项集，因而导致算 收稿日期：2020−08−12. 基金项目：国家自然科学基金项目 (71771094，61300139)；福建 省自然科学基金项目（2019J01067）；福建省社会科 学规划一般项目（FJ2020B088）. 通信作者：李海林. E-mail：hailin@hqu.edu.cn. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021

第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·

·504· 智能系统学报 第16卷 升、平稳和下降3种，用q1.92、9表示，q表示时 X表示叶子节点所在的列表，x为树的叶子节 间序列名。例如：TA=(a2,a,a1,a3,a1,a3,a1,a1)是一条 点，也是列表的部分项，即X中的项需要满足某 符号化后的时间序列数据，将其用趋势项一位置 些条件后才能成为树的叶子节点。，表示列表 表示为list_A=[{a1(2,4,6,7)},{a2:(0,1)},{as(3,5)], Y的项。loc list表示叶子节点信息表与列表项位 其中，{a2:(0,1)}表示趋势项a2在第0和第1个时 置表的信息交集，其信息量用loc count表示， 区内出现。 data表示仅包含频繁项的数据集，min_supc表示 1.2性能比较与分析 最小支持度计数。 显然事务集表示法并没有减少原数据量，而 算法SFT算法 趋势项-位置表示法只保留每个趋势项，相同趋 输入data,min supc; 势项则用位置索引代替。由于特征表示数据是各 输出频繁K项集。 类算法挖掘工作的基础，其对算法运行效率具有 1)以Root为根，首条时间序列的所有项为 很大影响，因此有必要从转换时效和转换后数据 x,构建一棵基础树； 的内存占用情况对上述2种表示法的性能进行比 2)让所有叶子结点x,与时间序列X后的所有 较和分析。实验采用python程序将后文使用的 Y序列进行匹配计算； 3条股票时间序列数据分别进行事务集表示和趋 3)对x,与y,求loc_Iist,并判断loc_count 势项-位置表示，每条数据量为5343，共16029个 是否不小于min supc: 数据。实验结果如表1所示。 ①是，将loclist作为的节点信息表，y,作 表12种表示法的性能比较 为叶子节点，即x,。x所在的树枝节点构成频繁 Table 1 Performance comparison of two representations 项集，频繁项数即为x所在的树层，项集个数即 性能 事务集表示法 趋势项-位置表示法 为loc count。判断Y是否为最后一条时间序列： 转换时效/s 0.038 0.039 是，输出频繁K项集； 否，输出频繁K项集，重复2)、3)： 内存占用B 16560 96 ②否，不是叶子节点，舍弃。 从转换时效方面，2种表示法处理的数据量 相同，因而差异性不大：从内存占用方面，由趋势 3实例分析 项-位置表示的数据要远低于事务集表示的数 设最小支持度计数min supc为2，用趋势项- 据，因为趋势项-位置表示法以数值型(int)数据 位置表示的时间序列数据集data=[{a:(0,2,3,5, 记录趋势项的变化趋势，而事务集表示法则以字 7,9),a2:(4,6,8),a3:(1)}1,{b1:(2,3),b2:(04,5,6,8 符型(str)数据记录，由于int占用的内存要低于 9),b3:(1,7)}][{c:(3,4,6),c2:(2,7),c3:(0,1,5,8,9) sr占用的内存，因此用前者表示的数据，内存占 }]l,data可视化结果如图1所示，{b:(2,3)}表示 用情况要优于后者。 趋势项b,在第2和第3个时区内出现过。在构建 2同步频繁树 同步频繁树前，需要先去除data中的非频繁项。 鉴于经典算法Apriori和FP-growth不能直接 2 对时间序列数据进行关联规则挖掘，提出了一种 V* 可以解决上述问题的新算法，即SFT算法。新算 :b1 法通过求叶子节点与列表项间的信息交集，便可 a2:a1 判断该项是否与该树枝中的所有节点构成频繁项 集。算法总体思路：先将时间序列用趋势项-位 置表示，并去除非频繁项，再用首条时间序列构 建一棵基础树，通过求叶子节点与列表项间的信 息交集，便可以在树的生长过程中不断挖掘出频 图1实例数据可视化 繁K项集。通过给出频繁K项集所有前缀项的 Fig.1 Visualization of an instance data 信息量，便可以计算出频繁K项集的支持度与置 在data中，由于a的数量仅为l,小于2，因 信度。新方法除了适用于多条数时间序列数据外， 此去掉此非频繁项。根据SFT算法的挖掘步骤， 在小数据和大数据中，其都能取得较优的时间效 利用首条时间序列[{a:(0,2,3,5,7,9),:(4,6,8)] 率，此外还能给出频繁项集的支持度和置信度。 中的a,和a2项构建一棵基础树，如图2所示

升、平稳和下降 3 种，用 q1、q2 、q3 表示，q 表示时 间序列名。例如：TA=(a2 ,a2 ,a1 ,a3 ,a1 ,a3 ,a1 ,a1 ) 是一条 符号化后的时间序列数据，将其用趋势项−位置 表示为 list_A=[{a1 :(2,4,6,7)},{a2 :(0,1)},{a3 :(3,5)}]， 其中，{a2 :(0,1)}表示趋势项 a2 在第 0 和第 1 个时 区内出现。 1.2 性能比较与分析 显然事务集表示法并没有减少原数据量，而 趋势项−位置表示法只保留每个趋势项，相同趋 势项则用位置索引代替。由于特征表示数据是各 类算法挖掘工作的基础，其对算法运行效率具有 很大影响，因此有必要从转换时效和转换后数据 的内存占用情况对上述 2 种表示法的性能进行比 较和分析。实验采用 python 程序将后文使用的 3 条股票时间序列数据分别进行事务集表示和趋 势项−位置表示，每条数据量为 5 343，共 16 029 个 数据。实验结果如表 1 所示。 表 1 2 种表示法的性能比较 Table 1 Performance comparison of two representations 性能 事务集表示法 趋势项−位置表示法 转换时效/s 0.038 0.039 内存占用/B 16 560 96 从转换时效方面，2 种表示法处理的数据量 相同，因而差异性不大；从内存占用方面，由趋势 项−位置表示的数据要远低于事务集表示的数 据，因为趋势项−位置表示法以数值型 (int) 数据 记录趋势项的变化趋势，而事务集表示法则以字 符型 (str) 数据记录，由于 int 占用的内存要低于 str 占用的内存，因此用前者表示的数据，内存占 用情况要优于后者。 2 同步频繁树 鉴于经典算法 Apriori 和 FP-growth 不能直接 对时间序列数据进行关联规则挖掘，提出了一种 可以解决上述问题的新算法，即 SFT 算法。新算 法通过求叶子节点与列表项间的信息交集，便可 判断该项是否与该树枝中的所有节点构成频繁项 集。算法总体思路：先将时间序列用趋势项−位 置表示，并去除非频繁项，再用首条时间序列构 建一棵基础树，通过求叶子节点与列表项间的信 息交集，便可以在树的生长过程中不断挖掘出频 繁 K 项集。通过给出频繁 K 项集所有前缀项的 信息量，便可以计算出频繁 K 项集的支持度与置 信度。新方法除了适用于多条数时间序列数据外， 在小数据和大数据中，其都能取得较优的时间效 率，此外还能给出频繁项集的支持度和置信度。 X 表示叶子节点所在的列表，x 为树的叶子节 点，也是列表的部分项，即 X 中的项需要满足某 些条件后才能成为树的叶子节点。yi 表示列表 Y 的项。loc_list 表示叶子节点信息表与列表项位 置表的信息交集，其信息量用 loc_count 表示， data 表示仅包含频繁项的数据集，min_supc 表示 最小支持度计数。 算法 SFT 算法 输入 data，min_supc； 输出 频繁 K 项集。 1) 以 Root 为根，首条时间序列的所有项为 xt，构建一棵基础树； 2) 让所有叶子结点 xt 与时间序列 X 后的所有 Y 序列进行匹配计算； 3) 对 xt 与 yi 求 loc_list，并判断 loc_count 是否不小于 min_supc： ①是，将 loc_list 作为 yi 的节点信息表，yi 作 为叶子节点，即 xi 。xi 所在的树枝节点构成频繁 项集，频繁项数即为 xi 所在的树层，项集个数即 为 loc_count。判断 Y 是否为最后一条时间序列： 是，输出频繁 K 项集； 否，输出频繁 K 项集，重复 2)、3)； ② 否，yi 不是叶子节点，舍弃。 3 实例分析 设最小支持度计数 min_supc 为 2，用趋势项− 位置表示的时间序列数据集 data=[[{a1 : (0, 2, 3, 5, 7, 9), a2 : (4, 6, 8), a3 : (1)}],[{b1 : (2, 3), b2 : (0, 4, 5, 6, 8, 9), b3 : (1,7)}],[{ c1 : (3, 4, 6), c2 : (2, 7), c3 : (0, 1, 5, 8, 9) }]], data 可视化结果如图 1 所示，{b1 : (2, 3)}表示 趋势项 b1 在第 2 和第 3 个时区内出现过。在构建 同步频繁树前，需要先去除 data 中的非频繁项。 t 0 1 a1 a1 a1 a1 a1 a1 a3 a2 a2 a2 b2 b2 b2 b2 b2 b2 b3 b1 b1 b1 c3 c3 c3 c3 c3 c1 c c1 2 c2 c2 t2 t3 t5 t4 t6 C B 数值 A t/s y4 y3 y2 y1 图 1 实例数据可视化 Fig. 1 Visualization of an instance data 在 data 中，由于 a3 的数量仅为 1，小于 2，因 此去掉此非频繁项。根据 SFT 算法的挖掘步骤， 利用首条时间序列 [{a1 : (0, 2, 3, 5, 7, 9), a2 : (4, 6, 8) }] 中的 a1 和 a2 项构建一棵基础树，如图 2 所示。 ·504· 智 能 系 统 学 报 第 16 卷

第3期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·505· Root 挖掘结果进行比较和分析，以检验SFT算法的有 效性和性能。 41数据介绍 a:0,2,3,5,7,9y a2(4,6,8) 零售商品数据是从UCI网站下载的 Online RetailⅡ，取其中代号为20725、20727和20728 图2基础树 Fig.2 Base tree 的销售量。每条数据的时间在2010年12月2日- 2011年12月9日，共225天，675个数据量。股 叶子节点a、a2分别与时间序列B和C中的 票数据是从预测者网中获取，冠城大通股票 项进行匹配计算，即[{b:(2,3),b2:0,4,5,6,8,9), (600067)、中船科技股票(600072)和上汽集团股 b:(1,7)}]和[{c:(3,4,6),c2:(2,7),c3:(0,1,5,8, 票(600104)的日收盘价，每支股票的时间在 9)】,结果如图3所示。例如a1与b2的loc_Iist 1997年12月25日-2021年3月4日，共5343个 为(0,5,9)，即1 oc count为3，因而b2成为叶子节 工作日，16029个数据量。为了获取多条时间序 点，其信息表为(0,5,9)，信息量为3，由于b2位于 列间的变化趋势规则，需要先将每条时间序列分 第2层树，则a1b2是频繁2项集，项集个数为3。 割成多个趋势项，然后再借鉴文献[23]的对齐思 而a,与b3的loc list为(7)，即loc_count小于2，因 想将多条时间序列的趋势项对齐。例如，在时区 此b3不是叶子节点。 [0,3】内，时间序列A的趋势项是a1,而时间序列 Root B在[0,1]和[1,3]区间内的趋势项为b1和b2,为 了与B对齐，序列A的[0,3]时区被分成[0,1]和 a1(0,2,3,5,7,9の a:(4,6,8 [1,3引，对应的趋势项是a、a。本文使用的分割策 略为基于滑动窗口的线性回归，分割所得线段可 G:(2,7:0,5,の0：(2,36：0,5,9G年(4,66e:(4,6,8 以保留原数据的局部变化趋势。以上汽集团股票 图3同步频繁树的生长 数据为例，图5是它的原始变化趋势，图6展示的 Fig.3 Growth process of synchronize frequent tree 是时间在2020年8月14日-2020年9月24日该 由于C是最后一条时间序列，因此输出图3 支股票的数据分割过程，蓝色表示原始时间序 中的所有频繁2项集：a1C2、a1c3、a2c1,其项集个数 列，红色表示分割后的局部拟合线段，表2则给出 分别为2、3、2，但B并非最后一条时间序列，先 部分具体的原始数据。 输出频繁2项集ab1、ab2、a2c1、ab2,再以同样的 思路将叶子节点b、b2、b,与时间序列C中的项进 行匹配计算，结果如图4所示，由于叶子结点是最 25 后一条时间序列中的项，因此一棵完整的同步频 繁树构建完成，并输出所有的频繁3项集，即 15 ab2c3、a2b2C1o 10 Root 100020003000400050006000 数据量 @:0,2,3,5,7,9の a2:(4,6,8 图5上汽集团历年的股票数据 G2,70,5,96:(2,3)6:0,5.G4664,68 Fig.5 Stock data of Shangqi group over the years 20.5 G3(0,5,9の C:(4,6) 20.0 图4完整的同步频繁树 19.5 Fig.4 Complete synchronized frequent tree 藏190 4数值实验 8.0 为了验证SFT算法具有普适性，使用零售商 20 304050.60 品数据和股票数据分别进行实验。分别与基于时 数据量 间序列事务集的Apriori、FP-growth、MapRe- 图6时间序列线性分段（上汽集团股票） duce、BM_Apriori9以及WV_Aprior算法的 Fig.6 Linear segmentation of time series(Shangqi group)

Root a1 : (0, 2, 3, 5, 7, 9) a2 : (4, 6, 8) 图 2 基础树 Fig. 2 Base tree 叶子节点 a1、a2 分别与时间序列 B 和 C 中的 项进行匹配计算，即 [{b1 : (2, 3), b2 : (0, 4, 5, 6, 8, 9), b3 : (1,7) }] 和 [{ c1 : (3, 4, 6), c2 : (2, 7), c3 : (0, 1, 5, 8, 9) }]，结果如图 3 所示。例如 a1 与 b2 的 loc_list 为 (0,5,9)，即 loc_count 为 3，因而 b2 成为叶子节 点，其信息表为 (0,5,9)，信息量为 3，由于 b2 位于 第 2 层树，则 a1b2 是频繁 2 项集，项集个数为 3。 而 a1 与 b3 的 loc_list 为 (7)，即 loc_count 小于 2，因 此 b3 不是叶子节点。 Root a2 : (4, 6, 8) b1 : (2, 3) b2 c2 : (2, 7) c : (0, 5, 9) 3 : (0, 5, 9) a1 : (0, 2, 3, 5, 7, 9) b2 c1 : (4, 6, 8) : (4, 6) 图 3 同步频繁树的生长 Fig. 3 Growth process of synchronize frequent tree 由于 C 是最后一条时间序列，因此输出图 3 中的所有频繁 2 项集：a1c2、a1c3、a2c1，其项集个数 分别为 2、3、2，但 B 并非最后一条时间序列，先 输出频繁 2 项集 a1b1、a1b2、a2 c1、a2b2，再以同样的 思路将叶子节点 b1、b2、b1 与时间序列 C 中的项进 行匹配计算，结果如图 4 所示，由于叶子结点是最 后一条时间序列中的项，因此一棵完整的同步频 繁树构建完成，并输出所有的频繁 3 项集，即 a1b2 c3、a2b2 c1。 Root a2 : (4, 6, 8) b1 : (2, 3) b2 c2 : (2, 7) c3 : (0, 5, 9) : (0, 5, 9) a1 : (0, 2, 3, 5, 7, 9) b2 c : (4, 6, 8) 1 : (4, 6) c3 : (0, 5, 9) c1 : (4, 6) 图 4 完整的同步频繁树 Fig. 4 Complete synchronized frequent tree 4 数值实验 为了验证 SFT 算法具有普适性，使用零售商 品数据和股票数据分别进行实验。分别与基于时 间序列事务集的 Apriori[7] 、FP-growth[14] 、MapRe￾duce[9-10] 、BM_Apriori[9] 以及 WV_Apriori[13] 算法的 挖掘结果进行比较和分析，以检验 SFT 算法的有 效性和性能。 4.1 数据介绍 零售商品数据是 从 UCI 网站下载 的 Online_Retail_II，取其中代号为 20 725、20 727 和 20 728 的销售量。每条数据的时间在 2010 年 12 月 2 日− 2011 年 12 月 9 日，共 225 天，675 个数据量。股 票数据是从预测者网中获取，冠城大通股 票 (600067)、中船科技股票 (600072) 和上汽集团股 票 (600104) 的日收盘价，每支股票的时间在 1997 年 12 月 25 日−2021 年 3 月 4 日，共 5 343 个 工作日，16 029 个数据量。为了获取多条时间序 列间的变化趋势规则，需要先将每条时间序列分 割成多个趋势项，然后再借鉴文献 [23] 的对齐思 想将多条时间序列的趋势项对齐。例如，在时区 [0, 3] 内，时间序列 A 的趋势项是 a1，而时间序列 B 在 [0,1] 和 [1, 3] 区间内的趋势项为 b1 和 b2，为 了与 B 对齐，序列 A 的 [0, 3] 时区被分成 [0,1] 和 [1, 3]，对应的趋势项是 a1、a1。本文使用的分割策 略为基于滑动窗口的线性回归，分割所得线段可 以保留原数据的局部变化趋势。以上汽集团股票 数据为例，图 5 是它的原始变化趋势，图 6 展示的 是时间在 2020 年 8 月 14 日−2020 年 9 月 24 日该 支股票的数据分割过程，蓝色表示原始时间序 列，红色表示分割后的局部拟合线段，表 2 则给出 部分具体的原始数据。 35 40 30 25 20 15 10 5 0 1 000 2 000 3 000 4 000 5 000 6 000 数据量 数值 图 5 上汽集团历年的股票数据 Fig. 5 Stock data of Shangqi group over the years 20.0 20.5 19.5 19.0 18.5 18.0 0 10 20 30 40 50 60 数据量 数值 图 6 时间序列线性分段 (上汽集团股票) Fig. 6 Linear segmentation of time series(Shangqi group) 第 3 期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·505·

·506· 智能系统学报 第16卷 表2原始数据（上汽集团股票） 为说明实验结果的真实可靠性，图8给出了 Table 2 Raw data(Shangqi group) 当min supc=12时，频繁2项集的详细数据。其 日期 收盘价元 日期 收盘价/元 中，阴影部分的数字表示满足min supc的频繁项 2020-09-01 19.02 2020-09-14 19.43 集个数，例如频繁项集ab1共有38个，非阴影部 2020-09-02 18.91 2020-09-15 19.67 分的数字表示不满足min supc的项集个数，‘一 2020-09-03 19.21 2020-09-16 19.89 则表示该频繁项集不存在，因为本文挖掘的是不 2020-09-04 19.26 2020-09-17 20.32 同时间序列间的关联关系，所以aa2等不是要找 2020-09-07 19.40 2020-09-18 20.25 2020-09-08 20.04 2020-09-21 20.13 的频繁2项集。 2020-09-09 19.20 2020-09-22 19.74 a a 42 2020-09-10 19.14 2020-09-23 19.83 42- 2020-09-11 18.99 2020-09-24 19.30 43 一 b138 35 b b: 4.2时序数据关联分析 25 9 0 34 本次实验共分为2组，第1组使用商品销售 9 46 10 32 4522 21 数据集，第2组使用股票数据集。实验采用SFT 24 7 11161016 c3301349232541 C 算法，除了与经典算法Apriori和FP-growth进行 比较外，实验还给出了近年来提出并且具有较好 图8频繁2项集及其个数 性能的MapReduce、BM_Apriori和WV_Apriori算 Fig.8 Frequent 2 itemsets and their number 法的挖掘结果进行比较。由于近年来从时间序列 鉴于FP-growth算法不能给出频繁项集的支 角度研究商品销售关联性成为热门方向2421 持度和置信度，而MapReduce、BM Apriori和 因此本文将给出详细的商品销售数据挖掘结果， WV_Apriori是为挖掘频繁项集而提出的算法，故 并用股票数据的部分结果说明新方法具有普适 本文仅给出SFT和Apriori算法所挖掘频繁项集 性。第1组实验结果如图7所示，图7中展示了 的支持度和置信度。当min_supc=l2时，2个算法 基于不同的min supc,.实验算法和对比算法的频 均给出如表3所示的结果，其中Rule表示规则， 繁2、3项集的个数。实验表明，无论min_supc Sup表示支持度，Conf表示置信度。以ab→c 取什么值，这些算法的挖掘结果都是相同的，进 为例，其表明增加购买20725商品、20727商品和 而说明SFT方法能够取得同样精度的效果。 20728商品的规则数占总规则数的0.09：当都增 加购买20725和20727时，20728的购买量会增 30 Apriori EM Apriori 加的概率为0.57。 FP-growth WV Apriori MapReduce SFT 表3SFT与Apriori算法挖掘关联规则 20 Table 3 Association rules mined by SFT and Apriori 项集 Rule Sup Conf Rule Sup Conf a1=b10.170.38 a1→b20.110.25 a1→b30.160.37 a1→c1 0.200.46 a1→c20.100.24 a1→c3 0.130.3 2 16 20 a2=c30.050.43 a3→b1 0.150.38 最小支持度计数 (a)频繁2项集 a3→b20.100.25 a3→b3 0.150.36 频繁2项集 a3→c10.140.34 a3→c3 0.220.53 0.200.53 0.070.19 0 Apriori b3→C1 b1→c2 FP-growth MapReduce b1=c3 0.100.27 b2→c1 0.090.37 EM Apriori b2=c3 0.110.44 b3=→c1 0.090.25 WV Apriori SFT b3→c20.070.19 b3→c3 0.190.54 a1b1→c10.090.57a1→b1c10.090.22 2 4b2→c10.060.6a1→b2c910.06 0.15 a1b3→c30.070.45a1b3=c30.070.17 12 16 20 2 最小支持度计数 频繁3项集ab1→c10.080.54a3→b1910.080.20 (b)频繁3项集 4b1→c30.050.34a3=b1c0.050.13 ab2→c30.060.60a3→b2c30.060.15 图7频繁项集个数对比（商品数据） ab3=→c30.100.67a3→b3930.100.25 Fig.7 Comparison of frequent itemsets(commodity data)

表 2 原始数据 (上汽集团股票) Table 2 Raw data(Shangqi group) 日期 收盘价/元 日期 收盘价/元 2020-09-01 19.02 2020-09-14 19.43 2020-09-02 18.91 2020-09-15 19.67 2020-09-03 19.21 2020-09-16 19.89 2020-09-04 19.26 2020-09-17 20.32 2020-09-07 19.40 2020-09-18 20.25 2020-09-08 20.04 2020-09-21 20.13 2020-09-09 19.20 2020-09-22 19.74 2020-09-10 19.14 2020-09-23 19.83 2020-09-11 18.99 2020-09-24 19.30 4.2 时序数据关联分析 本次实验共分为 2 组，第 1 组使用商品销售 数据集，第 2 组使用股票数据集。实验采用 SFT 算法，除了与经典算法 Apriori 和 FP-growth 进行 比较外，实验还给出了近年来提出并且具有较好 性能的 MapReduce、BM_Apriori 和 WV_Apriori 算 法的挖掘结果进行比较。由于近年来从时间序列 角度研究商品销售关联性成为热门方向[ 2 4 - 2 5 ] ， 因此本文将给出详细的商品销售数据挖掘结果， 并用股票数据的部分结果说明新方法具有普适 性。第 1 组实验结果如图 7 所示，图 7 中展示了 基于不同的 min_supc，实验算法和对比算法的频 繁 2、3 项集的个数。实验表明，无论 min_supc 取什么值，这些算法的挖掘结果都是相同的，进 而说明 SFT 方法能够取得同样精度的效果。 25 30 20 15 10 5 0 4 8 12 16 20 最小支持度计数 频繁项集/个 27 26 20 19 17 20 25 15 10 5 0 4 8 12 16 20 24 24 最小支持度计数 频繁项集/个 22 11 7 4 2 Apriori FP-growth MapReduce EM_Apriori WV_Apriori SFT (a) 频繁 2 项集 (b) 频繁 3 项集 Apriori FP-growth MapReduce EM_Apriori WV_Apriori SFT 图 7 频繁项集个数对比 (商品数据) Fig. 7 Comparison of frequent itemsets(commodity data) 为说明实验结果的真实可靠性，图 8 给出了 当 min_supc =12 时，频繁 2 项集的详细数据。其 中，阴影部分的数字表示满足 min_supc 的频繁项 集个数，例如频繁项集 a1b1 共有 38 个，非阴影部 分的数字表示不满足 min_supc 的项集个数，‘—’ 则表示该频繁项集不存在，因为本文挖掘的是不 同时间序列间的关联关系，所以 a1a2 等不是要找 的频繁 2 项集。 a1 a2 a3 b1 b2 b3 c1 c2 c3 a1 a2 a3 b1 b2 b3 c1 c2 c3 图 8 频繁 2 项集及其个数 Fig. 8 Frequent 2 itemsets and their number a1b1 ⇒ c1 鉴于 FP-growth 算法不能给出频繁项集的支 持度和置信度，而 MapReduce、BM_Apriori 和 WV_Apriori 是为挖掘频繁项集而提出的算法，故 本文仅给出 SFT 和 Apriori 算法所挖掘频繁项集 的支持度和置信度。当 min_supc=12 时，2 个算法 均给出如表 3 所示的结果，其中 Rule 表示规则， Sup 表示支持度，Conf 表示置信度。以 为例，其表明增加购买 20 725 商品、20 727 商品和 20 728 商品的规则数占总规则数的 0.09；当都增 加购买 20 725 和 20 727 时，20 728 的购买量会增 加的概率为 0.57。 表 3 SFT 与 Apriori 算法挖掘关联规则 Table 3 Association rules mined by SFT and Apriori 项集 Rule Sup Conf Rule Sup Conf 频繁2项集 a1⇒ b1 0.17 0.38 a1⇒ b2 0.11 0.25 a1⇒ b3 0.16 0.37 a1⇒c1 0.20 0.46 a1⇒c2 0.10 0.24 a1⇒c3 0.13 0.3 a2⇒c3 0.05 0.43 a3⇒ b1 0.15 0.38 a3⇒ b2 0.10 0.25 a3⇒ b3 0.15 0.36 a3⇒c1 0.14 0.34 a3⇒c3 0.22 0.53 b3⇒c1 0.20 0.53 b1⇒c2 0.07 0.19 b1⇒c3 0.10 0.27 b2⇒c1 0.09 0.37 b2⇒c3 0.11 0.44 b3⇒c1 0.09 0.25 b3⇒c2 0.07 0.19 b3⇒c3 0.19 0.54 频繁3项集 a1 b1⇒c1 0.09 0.57 a1⇒ b1 c1 0.09 0.22 a1 b2⇒c1 0.06 0.6 a1⇒ b2 c1 0.06 0.15 a1 b3⇒c3 0.07 0.45 a1 b3⇒ c3 0.07 0.17 a3 b1⇒c1 0.08 0.54 a3⇒ b1c1 0.08 0.20 a3 b1⇒c3 0.05 0.34 a3⇒ b1 c3 0.05 0.13 a3 b2⇒c3 0.06 0.60 a3⇒ b2 c3 0.06 0.15 a3 b3⇒c3 0.10 0.67 a3 ⇒ b3 c3 0.10 0.25 ·506· 智 能 系 统 学 报 第 16 卷

第3期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·507· 为了说明SFT算法具有普适性，第2组实验 由于挖掘频繁项集所耗时间占整个挖掘过程的多 使用股票数据。由于挖掘步骤与第1组实验相 数时间，因此图10给出6种算法在挖掘商品数据 同，因此图9直接给出挖掘结果，其表明6种算法 和股票数据频繁项集时所消耗的时间可视化图， 的挖掘结果相同，因而说明SFT算法具有较强的 表4是具体的数值结果。实验表明，无论在数据 普适性。 量为675的商品数据，还是在数据量为16029的 30 7 股票数据，SFT算法的时间效率在不同最小支持 Apriori FP-growth 计数的取值下都要优于其他算法，因而说明 MapReduce EM Apriori SFT算法具有较强的稳健性。 WV Apriori 15 SFT 0.016 ◆Apriori 。FP-growth 10 0.014 M apReduce *-BM Apriori 0.012 0.010 0.008 50 75 100 125 150 0.006 最小支持度计数 0.004 30 (a)频繁2项集 0.002 Apriori 12 16 FP-growth 最小支持度计数 20 MapReduce (a)商品数据 16 EM Apriori WV Apriori 0.14 SFT 0.12 0.10 ◆-ADr10r1 -FP-growth 0.08 MapReduce BM Apriori WV Apriori ◆SFT 0.06 25 0 75 100 125 ◆ 150 0.04 最小支持度计数 0.02 (b)频繁3项集 25 50 100 125 图9频繁项集个数对比（股票数据） 最小支持度计数 Fig.9 Comparison of frequent itemsets(stock data) (b)股票数据 4.3时间效率分析 图10时间复杂度对比 时间效率是衡量算法好坏的重要指标之一。 Fig.10 Comparison of time complexity-commodity data 表46种算法挖掘频繁项集的时耗 Table 4 Time consumption of six algorithms for mining frequent itemsets 数据集 Min sup Apriori FP-growth MapReduce BM_Apriori WV_Apriori SFT 0.014386 0.003870 0.008764 0.002653 0.002778 0.001897 8 0.011101 0.003590 0.008223 0.002444 0.002693 0.001069 商品数据 12 0.009170 0.003321 0.007040 0.002141 0.002609 0.001000 16 0.008713 0.003251 0.006831 0.002012 0.002598 0.000982 20 0.007933 0.003049 0.006371 0.001961 0.002505 0.000933 25 0.057053 0.007691 0.024362 0.009790 0.115257 0.004307 50 0.056445 0.007544 0.023703 0.009662 0.113917 0.004247 股票数据 75 0.055805 0.007434 0.023542 0.009632 0.113889 0.004138 100 0.048232 0.007375 0.023023 0.009398 0.113221 0.004035 125 0.043928 0.007243 0.022827 0.009105 0.112937 0.003988 由图10和表4的定量结果分析可知，SFT算 角度进一步分析实验结果。本文认为影响SFT 法要优于其他5种对比算法，因而有必要从定性 算法取得较好性能的主要因素有：1)在生成频繁

为了说明 SFT 算法具有普适性，第 2 组实验 使用股票数据。由于挖掘步骤与第 1 组实验相 同，因此图 9 直接给出挖掘结果，其表明 6 种算法 的挖掘结果相同，因而说明 SFT 算法具有较强的 普适性。 25 30 20 15 10 5 0 25 50 75 100 125 最小支持度计数 频繁项集/个 27 27 27 24 22 (a) 频繁 2 项集 25 30 20 15 10 5 0 25 50 75 100 125 150 150 最小支持度计数 频繁项集/个 25 16 11 11 5 (b) 频繁 3 项集 Apriori FP-growth MapReduce EM_Apriori WV_Apriori SFT Apriori FP-growth MapReduce EM_Apriori WV_Apriori SFT 图 9 频繁项集个数对比（股票数据） Fig. 9 Comparison of frequent itemsets (stock data) 4.3 时间效率分析 时间效率是衡量算法好坏的重要指标之一。 由于挖掘频繁项集所耗时间占整个挖掘过程的多 数时间，因此图 10 给出 6 种算法在挖掘商品数据 和股票数据频繁项集时所消耗的时间可视化图， 表 4 是具体的数值结果。实验表明，无论在数据 量为 675 的商品数据，还是在数据量为 16 029 的 股票数据，SFT 算法的时间效率在不同最小支持 计数的取值下都要优于其他算法，因而说 明 SFT 算法具有较强的稳健性。 0.014 0.016 0.012 0.010 0.008 0.006 0.004 0.002 0 4 8 12 16 20 最小支持度计数 时间代价/s (a) 商品数据 0.14 0.12 0.10 0.08 0.06 0.04 0.02 0 25 50 75 100 125 最小支持度计数 时间代价/s (b) 股票数据 Apriori FP-growth MapReduce BM_Apriori WV_Apriori SFT Apriori FP-growth MapReduce BM_Apriori WV_Apriori SFT 图 10 时间复杂度对比 Fig. 10 Comparison of time complexity-commodity data 表 4 6 种算法挖掘频繁项集的时耗 Table 4 Time consumption of six algorithms for mining frequent itemsets s 数据集 Min_sup Apriori FP-growth MapReduce BM_Apriori WV_Apriori SFT 商品数据 4 0.014 386 0.003 870 0.008 764 0.002 653 0.002778 0.001 897 8 0.011 101 0.003 590 0.008 223 0.002 444 0.002 693 0.001 069 12 0.009 170 0.003 321 0.007 040 0.002 141 0.002 609 0.001 000 16 0.008 713 0.003 251 0.006 831 0.002 012 0.002 598 0.000 982 20 0.007 933 0.003 049 0.006 371 0.001 961 0.002 505 0.000 933 股票数据 25 0.057 053 0.007 691 0.024 362 0.009 790 0.115 257 0.004 307 50 0.056 445 0.007 544 0.023 703 0.009 662 0.113 917 0.004 247 75 0.055 805 0.007 434 0.023 542 0.009 632 0.113 889 0.004 138 100 0.048 232 0.007 375 0.023 023 0.009 398 0.113 221 0.004 035 125 0.043 928 0.007 243 0.022 827 0.009 105 0.112 937 0.003 988 由图 10 和表 4 的定量结果分析可知，SFT 算 法要优于其他 5 种对比算法，因而有必要从定性 角度进一步分析实验结果。本文认为影响 SFT 算法取得较好性能的主要因素有：1) 在生成频繁 第 3 期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·507·

·508· 智能系统学报 第16卷 K项集的过程中，SFT算法不会产生候选频繁项 法，然而在数据量较大的股票数据中，该算法会 集；2)SFT算法只需要对叶子节点和列表趋势项 产生候选频繁K项集，因而其时间效率略低于 求一次信息交集，即可快速判断出频繁K项集； FP-growth算法。3)MapReduce算法通过合并具 3)由1.2节分析得出，由趋势项-位置表示的数 有相同键的频繁K-1项集，即可快速产生候选频 据，其所占内存要远低于事务集表示的数据，因 繁K项集，因而其挖掘速率要快于Apriori算法， 而导致在程序运行过程中，SFT算法的处理速度 但是正因它还会产生较多的候选项集，因此导致 要快于其他算法。 其运行效率不及余下的其他算法。4)FP- 限于篇幅有限并且考虑到各类因素对不同算 growth算法只需要扫描2次数据库，并通过头指 法的影响程度不同，因而对于每个对比算法，仅 针可以快速找到其他树枝上的相同项，因而在数 给出必要的分析和解释：1)WV Apriori算法在数 据量较大的股票数据中，其挖掘速率要优于除了 据量较少的商品数据中，具有较好的时间效率， SFT以外的其他算法，但是由于其挖掘的基础数 而在数据量较大的股票数据中，其时间效率明显 据用事务集表示，此外，在重新对事务集进行排 降低，表现出很差的稳健性。导致这种结果的原 序、构建FP-tree、提取条件模式基以及构建条件 因：①在创建0-1矩阵的过程中，每项表示一列， FP-tree过程中，消耗了较多时间，因此导致其运 每个事务表示一行，当数据量越来越大时，其创 行速率不及SFT算法。5)当最大频繁项集是 建的矩阵会越来越大，因而将会消耗更多的时 K时，Apriori算法需要扫描K次数据库，并从大 间；②由于频繁项集的挖掘是基于0-1矩阵，当矩 量候选频繁项集中挖掘出频繁K项集，因而导致 阵很大时，除了遍历矩阵需要较多的时间外，矩 其具有较低的挖掘速率。 阵占用较多内存也会影响程序的运行速率；③由 表5分别从6个层面，概括总结6种算法的 于WV Apriori算法只需要遍历一次数据库，并且 区别与联系：除了SFT算法外，其他算法都是基 在挖掘更高的频繁项集时，不断缩小矩阵，因此 于用事务集表示的数据；SFT和BM Apriori算法 当数据量较小时，其效率要高于Apriori、FP- 分别用项的位置和事务的序号代替原数据，而其 growth和MapReduce算法，正因为该算法需要遍 他算法仅仅是通过不同的方法表示保留原数据： 历完整个矩阵后才能判断项间是否构成频繁项 SFT算法与FP-growth和WV Apriori算法一样不 集，因此其运行速率不及BM_Apriori和SFT算 会产生候选频繁项集；仅有SFT算法和BM_Apri- 法。2)由于BM_Apriori算法直接求2个频繁 o算法可以直接判断频繁K项集，而其他算法则 K-1项之间的序号列表交集，即可快速找出它们 需要遍历完整个数据库才能判断；SFT和Apri 之间的所有项集个数，但是该算法的基础数据用 oi算法能给出频繁项集的支持度与置信度，而其 事务集表示，因而在数据量较少的商品数据中， 他算法不能；SFT算法与FP-growth、Mapre 其时间效率要优于除了SFT算法以外的其他算 duce和BM Apriori算法都能应用于大数据中。 表56种算法对比 Table 5 Comparison of six algorithms 对比项 Apriori FP-growth Mapreduce BM Apriori WV_Apriori SFT 基础数据表示 事务集 事务集 事务集 事务集 事务集 趋势项-位置 挖掘基础 Cu-1) 条件模式基 Co-1) 事务的序号 布尔矩阵 项的位置 候选频繁项集 有 无 有 有 无 无 直接判断频繁K项 否 否 否 是 否 是 有无sup,conf 有 无 无 无 无 有 适用大数据 否 是 是 是 否 是 显然，无论在定量分析还是定性分析中， 联规则的新方法，即SFT算法，并给出了近些年 SFT算法都要优于其他算法。 来提出的，且具有较好性能的MapReduce、 5结束语 BM_Apriori和WV_Apriori算法挖掘结果作对 比。SFT算法的总体思路是先将时间序列数据用 针对经典算法Apriori和FP-growth不适用于 趋势项-位置表示，再通过求叶子节点与列表项间 时间序列数据，提出了一种挖掘时间序列数据关 的信息交集，进而可以快速挖掘出频繁K项集

K 项集的过程中，SFT 算法不会产生候选频繁项 集；2) SFT 算法只需要对叶子节点和列表趋势项 求一次信息交集，即可快速判断出频繁 K 项集； 3) 由 1.2 节分析得出，由趋势项−位置表示的数 据，其所占内存要远低于事务集表示的数据，因 而导致在程序运行过程中，SFT 算法的处理速度 要快于其他算法。 限于篇幅有限并且考虑到各类因素对不同算 法的影响程度不同，因而对于每个对比算法，仅 给出必要的分析和解释：1) WV_Apriori 算法在数 据量较少的商品数据中，具有较好的时间效率， 而在数据量较大的股票数据中，其时间效率明显 降低，表现出很差的稳健性。导致这种结果的原 因：①在创建 0-1 矩阵的过程中，每项表示一列， 每个事务表示一行，当数据量越来越大时，其创 建的矩阵会越来越大，因而将会消耗更多的时 间；②由于频繁项集的挖掘是基于 0-1 矩阵，当矩 阵很大时，除了遍历矩阵需要较多的时间外，矩 阵占用较多内存也会影响程序的运行速率；③ 由 于 WV_Apriori 算法只需要遍历一次数据库，并且 在挖掘更高的频繁项集时，不断缩小矩阵，因此 当数据量较小时，其效率要高于 Apriori、FP￾growth 和 MapReduce 算法，正因为该算法需要遍 历完整个矩阵后才能判断项间是否构成频繁项 集，因此其运行速率不及 BM_Apriori 和 SFT 算 法。2) 由于 BM_Apriori 算法直接求 2 个频繁 K−1 项之间的序号列表交集，即可快速找出它们 之间的所有项集个数，但是该算法的基础数据用 事务集表示，因而在数据量较少的商品数据中， 其时间效率要优于除了 SFT 算法以外的其他算 法，然而在数据量较大的股票数据中，该算法会 产生候选频繁 K 项集，因而其时间效率略低于 FP-growth 算法。3) MapReduce 算法通过合并具 有相同键的频繁 K−1 项集，即可快速产生候选频 繁 K 项集，因而其挖掘速率要快于 Apriori 算法， 但是正因它还会产生较多的候选项集，因此导致 其运行效率不及余下的其他算法。 4) FP￾growth 算法只需要扫描 2 次数据库，并通过头指 针可以快速找到其他树枝上的相同项，因而在数 据量较大的股票数据中，其挖掘速率要优于除了 SFT 以外的其他算法，但是由于其挖掘的基础数 据用事务集表示，此外，在重新对事务集进行排 序、构建 FP-tree、提取条件模式基以及构建条件 FP-tree 过程中，消耗了较多时间，因此导致其运 行速率不及 SFT 算法。5) 当最大频繁项集是 K 时，Apriori 算法需要扫描 K 次数据库，并从大 量候选频繁项集中挖掘出频繁 K 项集，因而导致 其具有较低的挖掘速率。 表 5 分别从 6 个层面，概括总结 6 种算法的 区别与联系：除了 SFT 算法外，其他算法都是基 于用事务集表示的数据；SFT 和 BM_Apriori 算法 分别用项的位置和事务的序号代替原数据，而其 他算法仅仅是通过不同的方法表示保留原数据； SFT 算法与 FP-growth 和 WV_Apriori 算法一样不 会产生候选频繁项集；仅有 SFT 算法和 BM_Apri￾ori 算法可以直接判断频繁 K 项集，而其他算法则 需要遍历完整个数据库才能判断；SFT 和 Apri￾ori 算法能给出频繁项集的支持度与置信度，而其 他算法不能； SFT 算法与 FP-growth、 Mapre￾duce 和 BM_Apriori 算法都能应用于大数据中。 表 5 6 种算法对比 Table 5 Comparison of six algorithms 对比项 Apriori FP-growth Mapreduce BM_Apriori WV_Apriori SFT 基础数据表示 事务集 事务集 事务集 事务集 事务集 趋势项-位置 挖掘基础 C(k-1) 条件模式基 C(k-1) 事务的序号 布尔矩阵 项的位置 候选频繁项集 有 无 有 有 无 无 直接判断频繁K项 否 否 否 是 否 是 有无sup,conf 有 无 无 无 无 有 适用大数据 否 是 是 是 否 是 显然，无论在定量分析还是定性分析中， SFT 算法都要优于其他算法。 5 结束语 针对经典算法 Apriori 和 FP-growth 不适用于 时间序列数据，提出了一种挖掘时间序列数据关 联规则的新方法，即 SFT 算法，并给出了近些年 来提出的，且具有较好性能 的 MapReduce、 BM_Apriori 和 WV_Apriori 算法挖掘结果作对 比。SFT 算法的总体思路是先将时间序列数据用 趋势项−位置表示，再通过求叶子节点与列表项间 的信息交集，进而可以快速挖掘出频繁 K 项集。 ·508· 智 能 系 统 学 报 第 16 卷

第3期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·509· 本文具的创新点：1)新定义的事务集表示法 预测方法研究[J.四川大学学报，2018.55(1)少：61-66 可以将多条时间序列数据转换成事务集，该转换 CHENG Xiaolin,ZHENG Xing,LI Xuwei.Research of 法让仅适用于挖掘无序数据的关联规则算法也可 stock time based on probabilistic suffix tree[J].Journal of 以挖掘时间序列数据，此外还定义了趋势项- Sichuan University,2018.55(1):61-66. 位置表示法，用该方法表示的数据，其内存占用 [5]王玲，徐培培，彭开香.基于因子模型和动态规划的多元 要低于原数据所占的内存，而内存占用情况会影 时间序列分段方法J.控制与决策，2020,35(1)：35-44 响算法运行速率；2)SFT算法可以挖掘多条时间 WANG Ling,XU Peipei,PENG Kaixiang.Segmentation 序列数据间的关联规则，弥补了Apriori、FP- of multivariate time series with factor model and dynamic programming[J].Control and decision,2020,35(1):35-44. growth等算法不适用于时间序列数据的缺点；3) [6]AGRAWAL R.IMIELINSKI T.SWAMI A.Mining asso- 通过计算树叶子节点与列表项间的信息交集，便 ciation rules between sets of items in large databases[C1// 可快速判断频繁K项集，并且不会产生候选频繁 Proceedings of the 1993 ACM SIGMOD International 项集，因而提高了算法的挖掘速率；4)SFT算法充 Conference on Management of Data.Washington,USA, 分利用时间序列具有一维性特点，并采用了直观 1993:207-216. 易懂的树型结构，这为时间序列数据关联分析的 [7]AGRAWAL R,SRIKANT R.Mining sequential 研究提供了一种新的研究思路和视角。实验表 patterns[C]//Proceedings of the 11th International Confer- 明：1)基于趋势项-位置表示法表示的时间序列 ence on Data Engineering.Taipei,China,1995:3-14. 数据，其内存占用要远低于用事务集表示的时间 [8]魏玲，魏永江，高长元.基于Bigtable与MapReduce的 序列数据；2)利用SFT算法挖掘出的频繁项集与 Apriori算法改进[J].计算机科学，2015,42(10)： 经典算法Apriori、FP-growth以及近些年来所提 208-210,243 的，并且具有较好性能的MapReduce、BM Apri- WEI Lin,WEI Yongjiang,GAO Changyuan.Improved ori和WV Apriori算法的挖掘结果相同；3)无论 Apriori algorithm based on bigtable and MapReduce[J] 在大数据还是小数据中，SFT算法的时间效率都 Computer science,.2015,42(10y:208-210,243. [9]KARIM R.HOSSAIN A.RASHID M.et al.A MapRe- 要优于对比算法；4)对于关联规则，SFT算法给出 duce framework for mining maximal contiguous frequent 的结果与Apriori的结果相同。 patterns in large DNA sequence datasets[J].IETE technic- SFT算法具有较高较优的时间性能，使其有 al review,2012,292):162-168. 较强的普适性。然而，SFT算法只考虑到同时区 [10]ZHANG Xiaolu.Pythagorean fuzzy clustering analysis:a 内不同时间序列间的关联关系，挖掘在不同时区 hierarchical clustering algorithm with the ratio index- 内不同时间序列间的关联关系，将是进一步需要 based ranking methods[J.International journal of intelli- 研究的工作。 gent systems,2018,33(9):1798-1822 参考文献： [11]TRAN T N.DRAB K,DASZYKOWSKI M.Revised DBSCAN algorithm to cluster data with dense adjacent [1]陈海燕，刘晨晖，孙博.时间序列数据挖掘的相似性度量 clusters[J].Chemometrics and intelligent laboratory sys- 综述.控制与决策，2017,32(1)：1-11 tems.2013,120(15):92-96. CHEN Haiyan,LIU Chenhui,SUN Bo.Survey on similar- [12]杨秋翔，孙涵.基于权值向量矩阵约简的Apriori算法 ity measurement of time series data mining[J].Control and [J.计算机工程与设计，2018.39(3)：690-693,762 decision,2017,32(1)y1-11 YANG Qiuxiang,SUN Han.Apriori algorithm based on [2]ACHEBAK H,DEVOLDER D,BALLESTER J.Trends in weight vector matrix reduction[J].Computer engineering temperature-related age-specific and sex-specific mortality and design,2018.39(3):690-693,762 from cardiovascular diseases in Spain:a national time- [13]HAN Jiawei,PEI Jian,YIN Yiwen.Mining frequent pat- series analysis[J].The lancet planetary health,2019,3(7): terns without candidate generation[J.ACM sigmod re- e297-e306. cord.2000,29(2):1-12 [3]李海林，梁叶.基于关键形态特征的多元时间序列降维 [14]DAS G.LIN K I,MANNILA H,et al.Rule discovery 方法[)控制与决策，2020,35(3)：629-636. from time series[C]//Proceedings of the 4th International LI Hailin,LIANG Ye.Dimension reduction for multivari- Conference on Knowledge Discovery and Data Mining. ate time series based on crucial shape features[J].Control New York,USA,1998:16-22. and decision.2020,35(3629-636. [15]VELUMANI B.UMAJOTHY P.Mining temporal associ- [4]程小林，郑兴，李旭伟.基于概率后缀树的股票时间序列 ation rules from time series microarray using apriori al-

本文具的创新点：1) 新定义的事务集表示法 可以将多条时间序列数据转换成事务集，该转换 法让仅适用于挖掘无序数据的关联规则算法也可 以挖掘时间序列数据，此外还定义了趋势项− 位置表示法，用该方法表示的数据，其内存占用 要低于原数据所占的内存，而内存占用情况会影 响算法运行速率；2) SFT 算法可以挖掘多条时间 序列数据间的关联规则，弥补了 Apriori、FP￾growth 等算法不适用于时间序列数据的缺点；3) 通过计算树叶子节点与列表项间的信息交集，便 可快速判断频繁 K 项集，并且不会产生候选频繁 项集，因而提高了算法的挖掘速率；4) SFT 算法充 分利用时间序列具有一维性特点，并采用了直观 易懂的树型结构，这为时间序列数据关联分析的 研究提供了一种新的研究思路和视角。实验表 明：1) 基于趋势项−位置表示法表示的时间序列 数据，其内存占用要远低于用事务集表示的时间 序列数据；2) 利用 SFT 算法挖掘出的频繁项集与 经典算法 Apriori、FP-growth 以及近些年来所提 的，并且具有较好性能的 MapReduce、BM_Apri￾ori 和 WV_Apriori 算法的挖掘结果相同；3) 无论 在大数据还是小数据中，SFT 算法的时间效率都 要优于对比算法；4) 对于关联规则，SFT 算法给出 的结果与 Apriori 的结果相同。 SFT 算法具有较高较优的时间性能，使其有 较强的普适性。然而，SFT 算法只考虑到同时区 内不同时间序列间的关联关系，挖掘在不同时区 内不同时间序列间的关联关系，将是进一步需要 研究的工作。 参考文献： 陈海燕, 刘晨晖, 孙博. 时间序列数据挖掘的相似性度量 综述 [J]. 控制与决策, 2017, 32(1): 1–11. CHEN Haiyan, LIU Chenhui, SUN Bo. Survey on similar￾ity measurement of time series data mining[J]. Control and decision, 2017, 32(1): 1–11. [1] ACHEBAK H, DEVOLDER D, BALLESTER J. Trends in temperature-related age-specific and sex-specific mortality from cardiovascular diseases in Spain: a national time￾series analysis[J]. The lancet planetary health, 2019, 3(7): e297–e306. [2] 李海林, 梁叶. 基于关键形态特征的多元时间序列降维 方法 [J]. 控制与决策, 2020, 35(3): 629–636. LI Hailin, LIANG Ye. Dimension reduction for multivari￾ate time series based on crucial shape features[J]. Control and decision, 2020, 35(3): 629–636. [3] [4] 程小林, 郑兴, 李旭伟. 基于概率后缀树的股票时间序列 预测方法研究 [J]. 四川大学学报, 2018, 55(1): 61–66. CHENG Xiaolin, ZHENG Xing, LI Xuwei. Research of stock time based on probabilistic suffix tree[J]. Journal of Sichuan University, 2018, 55(1): 61–66. 王 玲, 徐培培, 彭开香. 基于因子模型和动态规划的多元 时间序列分段方法 [J]. 控制与决策, 2020, 35(1): 35–44. WANG Ling, XU Peipei, PENG Kaixiang. Segmentation of multivariate time series with factor model and dynamic programming[J]. Control and decision, 2020, 35(1): 35–44. [5] AGRAWAL R, IMIELIŃSKI T, SWAMI A. Mining asso￾ciation rules between sets of items in large databases[C]// Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. Washington, USA, 1993: 207–216. [6] AGRAWAL R, SRIKANT R. Mining sequential patterns[C]//Proceedings of the 11th International Confer￾ence on Data Engineering. Taipei, China, 1995: 3–14. [7] 魏玲, 魏永江, 高长元. 基于 Bigtable 与 MapReduce 的 Apriori 算法改进 [J]. 计算机科学, 2015, 42(10): 208–210, 243. WEI Lin, WEI Yongjiang, GAO Changyuan. Improved Apriori algorithm based on bigtable and MapReduce[J]. Computer science, 2015, 42(10): 208–210, 243. [8] KARIM R, HOSSAIN A, RASHID M, et al. A MapRe￾duce framework for mining maximal contiguous frequent patterns in large DNA sequence datasets[J]. IETE technic￾al review, 2012, 29(2): 162–168. [9] ZHANG Xiaolu. Pythagorean fuzzy clustering analysis: a hierarchical clustering algorithm with the ratio index￾based ranking methods[J]. International journal of intelli￾gent systems, 2018,33(9): 1798–1822. [10] TRAN T N, DRAB K, DASZYKOWSKI M. Revised DBSCAN algorithm to cluster data with dense adjacent clusters[J]. Chemometrics and intelligent laboratory sys￾tems. 2013,120(15): 92−96. [11] 杨秋翔, 孙涵. 基于权值向量矩阵约简的 Apriori 算法 [J]. 计算机工程与设计, 2018, 39(3): 690–693,762. YANG Qiuxiang, SUN Han. Apriori algorithm based on weight vector matrix reduction[J]. Computer engineering and design, 2018, 39(3): 690–693,762. [12] HAN Jiawei, PEI Jian, YIN Yiwen. Mining frequent pat￾terns without candidate generation[J]. ACM sigmod re￾cord, 2000, 29(2): 1–12. [13] DAS G, LIN K I, MANNILA H, et al. Rule discovery from time series[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. New York, USA, 1998: 16−22. [14] VELUMANI B, UMAJOTHY P. Mining temporal associ￾ation rules from time series microarray using apriori al- [15] 第 3 期 李海林，等：基于同步频繁树的时间序列关联规则分析 ·509·

·510· 智能系统学报 第16卷 gorithm[J].Review of bioinformatics and biometrics, MA Hui,TANG Yong,PAN Yan.A FP-tree based parti- 2013,2(2):29-36 tion mining approach to discovering temporal association [16]赵益.多时间序列上时序关联规则的挖掘D].上海：东 rules[J].Computer engineering,2006,32(17):132-134. 华大学，2018. [23]张建业，潘泉，张鹏等.基于斜率表示的时间序列相似 ZHAO Yi.Discovery of tempopal assocition rules in mul- 性度量方法[J].模式识别与人工智能，2007,20(2)： tivariate time series[D],Shang Hai:Donghua University, 271-274. 2018. ZHANG Jianye,PAN Quan,ZHANG Peng,et al.Simil- [17]CHEN Yicheng,PENG W C,LEE S Y.CEMiner-An arity measuring method in time series based on slope[J]. efficient algorithm for mining closed patterns from time Pattern recognition and artificial intelligence,2007,20(2) interval-based data[C]//Proceedings of the IEEE 11th In- 271-274. ternational Conference on Data Mining.Vancouver, [24]SALEM M Z.Effects of perfume packaging on Basque Canada,2011:121-130 female consumers purchase decision in Spain[J].Manage- [18]RUAN Guangchen,ZHANG Hui,PLALE B.Parallel and ment decision,.2018,56(8):1748-1768. quantitative sequential pattern mining for large-scale in- [25]LI Hailin,WU Y J,CHEN Yewang.Time is money:dy- terval-based temporal data[Cl//Proceedings of 2014 IEEE namic-model-based time series data-mining for correla- International Conference on Big Data (Big Data).Wash- tion analysis of commodity sales[J].Journal of computa- ington,USA,2014:32-39. tional and applied mathematics,2020,370:112659 [19]SCHLUTER T,CONRAD S.Mining several kinds of 作者简介： temporal association rules enhanced by tree structures[C/ 李海林，教授，博士生导师，主要 Proceedings of the 2nd International Conference on In- 研究方向为数据挖掘与决策支持。主 formation,Process,and Knowledge Management.Saint 持国家自然科学基金项目2项、省部 级基金项目4项。发表学术论文 Maarten.Netherland Antilles.2010:86-93. 60余篇。 [20]RASHID MM.GONDAL I.KAMRUZZAMAN J.Min- ing associated patterns from wireless sensor networks[J]. IEEE transactions on computers,2015,64(7):1998-2011. [21]PANKAJ G,SAGAR BB.Discovering weighted calen- 龙芳菊，硕士研究生，主要研究方 向为数据挖掘与企业管理。 dar-based temporal relationship rules using frequent pat- tern tree[J].Indian journal of science and technology, 2016,9(28:1-6. [22]马慧，汤痛，潘炎.一种基于P-树的时态关联规则的分 区挖掘方法[J.计算机工程，2006,32(17)：132-134 [责任编辑：李雪莲]

gorithm[J]. Review of bioinformatics and biometrics, 2013, 2(2): 29−36. 赵益. 多时间序列上时序关联规则的挖掘 [D]. 上海: 东 华大学, 2018. ZHAO Yi. Discovery of tempopal assocition rules in mul￾tivariate time series[D], Shang Hai: Donghua University, 2018. [16] CHEN Yicheng, PENG W C, LEE S Y. CEMiner—An efficient algorithm for mining closed patterns from time interval-based data[C]//Proceedings of the IEEE 11th In￾ternational Conference on Data Mining. Vancouver, Canada, 2011: 121−130. [17] RUAN Guangchen, ZHANG Hui, PLALE B. Parallel and quantitative sequential pattern mining for large-scale in￾terval-based temporal data[C]//Proceedings of 2014 IEEE International Conference on Big Data (Big Data). Wash￾ington, USA, 2014: 32−39. [18] SCHLÜTER T, CONRAD S. Mining several kinds of temporal association rules enhanced by tree structures[C]// Proceedings of the 2nd International Conference on In￾formation, Process, and Knowledge Management. Saint Maarten, Netherland Antilles, 2010: 86−93. [19] RASHID M M, GONDAL I, KAMRUZZAMAN J. Min￾ing associated patterns from wireless sensor networks[J]. IEEE transactions on computers, 2015, 64(7): 1998−2011. [20] PANKAJ G, SAGAR B B. Discovering weighted calen￾dar-based temporal relationship rules using frequent pat￾tern tree[J]. Indian journal of science and technology, 2016, 9(28): 1–6. [21] 马慧, 汤庸, 潘炎. 一种基于 FP-树的时态关联规则的分 区挖掘方法 [J]. 计算机工程, 2006, 32(17): 132−134. [22] MA Hui, TANG Yong, PAN Yan. A FP-tree based parti￾tion mining approach to discovering temporal association rules[J]. Computer engineering, 2006, 32(17): 132−134. 张建业, 潘泉, 张鹏等. 基于斜率表示的时间序列相似 性度量方法 [J]. 模式识别与人工智能, 2007, 20(2): 271−274. ZHANG Jianye, PAN Quan, ZHANG Peng, et al. Simil￾arity measuring method in time series based on slope[J]. Pattern recognition and artificial intelligence, 2007, 20(2): 271−274. [23] SALEM M Z. Effects of perfume packaging on Basque female consumers purchase decision in Spain[J]. Manage￾ment decision, 2018, 56(8): 1748−1768. [24] LI Hailin, WU Y J, CHEN Yewang. Time is money: dy￾namic-model-based time series data-mining for correla￾tion analysis of commodity sales[J]. Journal of computa￾tional and applied mathematics, 2020, 370: 112659. [25] 作者简介： 李海林，教授，博士生导师，主要 研究方向为数据挖掘与决策支持。主 持国家自然科学基金项目 2 项、省部 级基金项目 4 项。发表学术论文 60 余篇。 龙芳菊，硕士研究生，主要研究方 向为数据挖掘与企业管理。 [ 责任编辑：李雪莲 ] ·510· 智 能 系 统 学 报 第 16 卷