第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