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