基于多尺度的时序数据部分周期模式增量挖掘

doi:10.11772/j.issn.1001-9081.2021122190

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 391-397.DOI: 10.11772/j.issn.1001-9081.2021122190

所属专题：数据科学与技术

基于多尺度的时序数据部分周期模式增量挖掘

荀亚玲¹, 王林青¹, 蔡江辉¹^,²(), 杨海峰¹

^1.太原科技大学计算机科学与技术学院，太原 030024
^2.中北大学计算机科学与技术学院，太原 030051

收稿日期:2021-12-29 修回日期:2022-05-30 接受日期:2022-06-10 发布日期:2022-06-30 出版日期:2023-02-10
通讯作者: 蔡江辉
作者简介:荀亚玲（1980—），女，山西霍州人，副教授，博士，CCF会员，主要研究方向：数据挖掘、并行计算
王林青（1997—），男，河北秦皇岛人，硕士研究生，主要研究方向：数据挖掘、并行计算
杨海峰（1980—），男，山西介休人，教授，博士，CCF高级会员，主要研究方向：大数据挖掘与应用。
基金资助:
国家自然科学基金资助项目(62272336);山西省研究生教育创新项目(2022Y699)

Partial periodic pattern incremental mining of time series data based on multi-scale

Yaling XUN¹, Linqing WANG¹, Jianghui CAI¹^,²(), Haifeng YANG¹

^1.College of Computer Science and Technology，Taiyuan University of Science and Technology，Taiyuan Shanxi 030024，China
^2.College of Computer Science and Technology，North University of China，Taiyuan Shanxi 030051，China

Received:2021-12-29 Revised:2022-05-30 Accepted:2022-06-10 Online:2022-06-30 Published:2023-02-10
Contact: Jianghui CAI
About author:XUN Yaling， born in 1980， Ph. D.， associate professor. Her research interests include data mining， parallel computing.
WANG Linqing， born in 1997， M. S. candidate. His research interests include data mining， parallel computing.
YANG Haifeng， born in 1980， Ph. D.， professor. His research interests include big data mining and application.
Supported by:
National Natural Science Foundation of China(62272336);Graduate Education Innovation Project of Shanxi Province(2022Y699)

摘要/Abstract

摘要：

针对动态时序数据部分周期模式挖掘过程存在的计算复杂度过高和扩展性差等问题，提出了一种结合多尺度理论的时间序列部分周期模式挖掘算法（MSI-PPPGrowth），所提算法充分利用了时序数据客观存在的时间多尺度特性，将多尺度理论引入时序数据的部分周期模式挖掘过程。首先，将尺度划分后的原始数据以及增量时序数据作为更细粒度的基准尺度数据集进行独立挖掘；然后，利用不同尺度数据间的相关性实现尺度转换，以间接获取动态更新后的数据集对应的全局频繁模式，从而避免了原始数据集的重复扫描和树结构的不断调整。其中，基于克里金法并考虑时序周期性设计了一个新的频繁缺失计数估计模型（PJK-EstimateCount），以有效估计在尺度转换过程中的缺失项支持度计数。实验结果表明，MSI-PPPGrowth具有良好的可扩展性和实时性，尤其是对于稠密数据集，其性能优势更为突出。

关键词: 频繁项集挖掘, 时序数据, 部分周期模式, 多尺度, 增量挖掘

Abstract:

Aiming at the problems of high computational complexity and poor expansibility in the mining process of partial periodic patterns from dynamic time series data， a partial periodic pattern mining algorithm for dynamic time series data combined with multi-scale theory， named MSI-PPPGrowth （Multi-Scale Incremental Partial Periodic Frequent Pattern） was proposed. In MSI-PPPGrowth， the objective multi-scale characteristics of time series data， were made full use， and the multi-scale theory was introduced in the mining process of partial periodic patterns from time series data. Firstly， both the original data after scale division and incremental time series data were used as a finer-grained benchmark scale dataset for independent mining. Then， the correlation between different scales was used to realize scale transformation， so as to indirectly obtain global frequent patterns corresponding to the dynamically updated dataset. Therefore， the repeated scanning of the original dataset and the constant adjustment of the tree structure were avoided. In which， a new frequent missing count estimation model PJK-EstimateCount was designed based on Kriging method considering the periodicity of time series to effectively estimate the frequent missing item support count in scale transformation. Experimental results show that MSI-PPPGrowth has good scalability and real-time performance. Especially for dense datasets， MSI-PPPGrowth has significant performance advantages.

Key words: frequent itemset mining, time series data, partial periodic pattern, multi-scale, incremental mining

中图分类号:

TP301.6

荀亚玲, 王林青, 蔡江辉, 杨海峰. 基于多尺度的时序数据部分周期模式增量挖掘[J]. 计算机应用, 2023, 43(2): 391-397.

Yaling XUN, Linqing WANG, Jianghui CAI, Haifeng YANG. Partial periodic pattern incremental mining of time series data based on multi-scale[J]. Journal of Computer Applications, 2023, 43(2): 391-397.

图/表 15

表1 时序数据库示例表

Tab. 1 Example of time series database

tid	ts	模式	tid	ts	模式
101	1	a，b，e	107	7	c，e，h
102	2	c，g	108	8	a，c，d
103	3	a，b，c	109	9	a，b，g，h
104	4	a，b，h	110	10	c，d，e，f
105	5	a，b，e	111	11	a，b，c
106	6	a，e，f，g	112	12	a，b，c，d

图1 克里金模型

Fig. 1 Model of Kriging

图2 平面场模型

Fig. 2 Model of plane field

图3 构建PPP-Tree

Fig. 3 Construction of PPP-Tree

表2 dseason1尺度数据集

Tab. 2 Scale dataset of dseason1

tid	ts	模式
101	1	a，b，d，e
102	2	b，c
103	3	b，c，d，e

表3 dseason2尺度数据集

Tab. 3 Scale dataset of dseason2

tid	ts	模式
101	1	a，b，c，d
102	2	a，b，d
103	3	b，c

表4 dseason3尺度数据集

Tab. 4 Scale dataset of dseason3

tid	ts	模式
101	1	a，b，d，e
102	2	b，c，e
103	3	a，b，d

表5 dseason4尺度数据集

Tab. 5 Scale dataset of dseason4

tid	ts	模式
101	1	a，b，c
102	2	b，c，d，e
103	3	a，b，e

表6 dIncremental尺度数据表

Tab. 6 Scale dataset of dIncremental

tid	ts	模式
101	1	a，b，c，d
102	2	a，b，d，e
103	3	c，d，e

表7 候选项目集信息

Tab. 7 Candidate itemset information

候选项目集	m	$d s e a s o n 1$	$d s e a s o n 2$	$d s e a s o n 3$	$d s e a s o n 4$
a	3		2	2	2
b	4	3	3	3	3
c	3	2	2		2
d	3	2	2	2
e	2			2	2
ab	3		2	2	2
ad	2		2	2
bc	3	2	2		2
bd	3	2	2	2
be	2			2	2
abd	2		2	2

表7 候选项目集信息

Tab. 7 Candidate itemset information

候选项目集	m	$d s e a s o n 1$	$d s e a s o n 2$	$d s e a s o n 3$	$d s e a s o n 4$
a	3		2	2	2
b	4	3	3	3	3
c	3	2	2		2
d	3	2	2	2
e	2			2	2
ab	3		2	2	2
ad	2		2	2
bc	3	2	2		2
bd	3	2	2	2
be	2			2	2
abd	2		2	2

表8 数据集参数

Tab. 8 Parameters of datasets

数据集	大小/MB	平均长度	数据量
T10I4D100K	4.6	46.0	100 000
T15I1KD300K	48.1	1 681.0	30 000
accidents	7.2	135.2	70 000
Bible	5.4	153.0	36 369

图4 maxPer对运行时间的影响

Fig. 4 Influence of maxPer on running time

图5 minPS对运行时间的影响

Fig. 5 Influence of minPS on running time

表9 数据集尺度划分

Tab. 9 Size division of datasets

尺度大小	值	尺度大小	值
SIZE1	10 000	SIZE3	1 000
SIZE2	5 000	SIZE4	500

图6 不同尺度划分造成的精度影响

Fig. 6 Influence of different scale divisions on accuracy

参考文献 22

1	KIRAN R U， SHANG H C， TOYODA M， et al. Discovering partial periodic itemsets in temporal databases［C］// Proceedings of the 29th International Conference on Scientific and Statistical Database Management. New York： ACM， 2017： No.30. 10.1145/3085504.3085535
2	LIU Z S， MA Y M， ZHENG H H， et al. Human resource recommendation algorithm based on improved frequent itemset mining［J］. Future Generation Computer Systems， 2022， 126： 284-288. 10.1016/j.future.2021.08.017
3	MIRBAGHERI S M， HAMILTON H J. Mining high utility patterns in interval-based event sequences［J］. Data and Knowledge Engineering， 2021， 135： No.101924. 10.1016/j.datak.2021.101924
4	WU Y X， LEI R， LI Y， et al. HAOP-Miner： self-adaptive high-average utility one-off sequential pattern mining［J］. Expert Systems with Applications， 2021， 184： No.115449. 10.1016/j.eswa.2021.115449
5	TANBEER S K， AHMED C F， JEONG B S， et al. Discovering periodic-frequent patterns in transactional databases［C］// Proceedings of the 2009 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 5476. Berlin： Springer， 2009： 242-253.
6	SHELENKOV A， KOROTKOV E. LEPSCAN — a web server for searching latent periodicity in DNA sequences［J］. Briefings in Bioinformatics， 2012， 13（2）： 143-149. 10.1093/bib/bbr044
7	KIRAN R U， KITSUREGAWA M， REDDY P K. Efficient discovery of periodic-frequent patterns in very large databases［J］. Journal of Systems and Software， 2016， 112： 110-121. 10.1016/j.jss.2015.10.035
8	FOURNIER-VIGER P， LIN C W， DUONG Q H， et al. PFPM： discovering periodic frequent patterns with novel periodicity measures［C］// Proceedings of the 2nd Czech-China Scientific Conference. London： IntechOpen， 2017： 23-35. 10.5772/66780
9	KIRAN R U， KITSUREGAWA M. Discovering quasi-periodic-frequent patterns in transactional databases［C］// Proceedings of the 2013 International Conference on Big Data Analytics， LNCS 8302. Cham： Springer， 2013： 97-115.
10	KIRAN R U， VENKATESH J N， FOURNIER-VIGER P， et al. Discovering periodic patterns in non-uniform temporal databases［C］// Proceedings of the 2017 Pacific-Asia Conference on Knowledge Discovery and Data Mining， LNCS 10235. Cham： Springer， 2017： 604-617.
11	SAIDEEP C， KIRAN R U， ZETTSU K， et al. Parallel mining of partial periodic itemsets in big data［C］// Proceedings of the 2020 International Conference on Industrial， Engineering and Other Applications of Applied Intelligent Systems， LNCS 12144. Cham： Springer， 2020： 807-819.
12	LIKHITHA P， RAVIKUMAR P， KIRAN R U， et al. Discovering closed periodic-frequent patterns in very large temporal databases［C］// Proceedings of the 2020 IEEE International Conference on Big Data. Piscataway： IEEE， 2020： 4700-4709. 10.1109/bigdata50022.2020.9378215
13	ARYABARZAN N， MINAEI-BIDGOLI B. NEclatClosed： a vertical algorithm for mining frequent closed itemsets［J］. Expert Systems with Applications， 2021， 174： No.114738. 10.1016/j.eswa.2021.114738
14	CAI S H， HUANG R B， CHEN J F， et al. An efficient outlier detection method for data streams based on closed frequent patterns by considering anti-monotonic constraints［J］. Information Sciences， 2021， 555： 125-146. 10.1016/j.ins.2020.12.050
15	HACKMAN A， HUANG Y， TSENG V S. Mining trending high utility itemsets from temporal transaction databases［C］// Proceedings of the 2018 International Conference on Database and Expert Systems Applications， LNCS 11030. Cham： Springer， 2018： 461-470.
16	KANG R， WANG C， WANG P， et al. Matching consecutive subpatterns over streaming time series［C］// Proceedings of the 2018 Asia-Pacific Web （APWeb） and Web-Age Information Management （WAIM） Joint International Conference on Web and Big Data， LNCS 10988. Cham： Springer， 2018： 90-105.
17	UPADHYAY P， PANDEY M K， KOHLI N. Periodic pattern mining from spatio-temporal database using novel global pollination artificial fish swarm optimizer-based clustering and modified FP tree［J］. Soft Computing， 2021， 25（6）： 4327-4344. 10.1007/s00500-020-05444-z
18	XUN Y L， CUI X H， ZHANG J F， et al. Incremental frequent itemsets mining based on frequent pattern tree and multi-scale［J］. Expert Systems with Applications， 2021， 163： No.113805. 10.1016/j.eswa.2020.113805
19	JINDAL R， BORAH M D. A novel approach for mining frequent patterns from incremental data［J］. International Journal of Data Mining， Modelling and Management， 2016， 8（3）： 244-264. 10.1504/ijdmmm.2016.079071
20	HUYNH V Q P， KÜNG J， DANG T K. Incremental frequent itemsets mining with IPPC tree［C］// Proceedings of the 2017 International Conference on Database and Expert Systems Applications， LNCS 10438. Cham： Springer， 2017： 463-477.
21	BEAN B， SUN Y， MAGUIRE M. Interval-valued kriging for geostatistical mapping with imprecise inputs［J］. International Journal of Approximate Reasoning， 2022， 140： 31-51. 10.1016/j.ijar.2021.10.003
22	NAKAMURA S， KIRAN R U， LIKHITHA P， et al. Efficient discovery of partial periodic-frequent patterns in temporal databases［C］// Proceedings of the 2021 International Conference on Database and Expert Systems Applications， LNCS 12923. Cham： Springer， 2021： 221-227.

[1]	戎妍, 刘嘉雯, 李馨蕾. 面向学生课堂情感计算的自适应混合网络[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2919-2930.
[2]	陈彤, 杨丰玉, 熊宇, 严荭, 邱福星. 基于多尺度频率通道注意力融合的声纹库构建方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2407-2413.
[3]	李晨倩, 刘俊. 基于半监督和多尺度级联注意力的超声颈动脉斑块分割方法[J]. 《计算机应用》唯一官方网站, 2024, 44(8): 2604-2610.
[4]	刘丽, 侯海金, 王安红, 张涛. 基于多尺度注意力的生成式信息隐藏算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2102-2109.
[5]	熊武, 曹从军, 宋雪芳, 邵云龙, 王旭升. 基于多尺度混合域注意力机制的笔迹鉴别方法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2225-2232.
[6]	唐媛, 陈艳平, 扈应, 黄瑞章, 秦永彬. 基于多尺度混合注意力卷积神经网络的关系抽取模型[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2011-2017.
[7]	施赛龙, 方智文. 基于多尺度聚合和共享注意力的注视估计模型[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2047-2054.
[8]	李伟, 张晓蓉, 陈鹏, 李清, 张长青. 基于正态逆伽马分布的多尺度融合人群计数算法[J]. 《计算机应用》唯一官方网站, 2024, 44(7): 2243-2249.
[9]	王美, 苏雪松, 刘佳, 殷若南, 黄珊. 时频域多尺度交叉注意力融合的时间序列分类方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1842-1847.
[10]	程小辉, 黄云天, 张瑞芳. 基于多尺度和加权坐标注意力的轻量化红外道路场景检测模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1927-1934.
[11]	宋洪涛, 于江生, 韩启龙. 工业多元时序数据质量评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1743-1750.
[12]	李鸿天, 史鑫昊, 潘卫国, 徐成, 徐冰心, 袁家政. 融合多尺度和注意力机制的小样本目标检测[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1437-1444.
[13]	付顺旺, 陈茜, 李智, 王国美, 卢妤. 用于篡改图像检测和定位的双通道渐进式特征过滤网络[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1303-1309.
[14]	吴宁, 罗杨洋, 许华杰. 基于多尺度特征融合的遥感图像语义分割方法[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 737-744.
[15]	蒋占军, 吴佰靖, 马龙, 廉敬. 多尺度特征和极化自注意力的Faster-RCNN水漂垃圾识别[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 938-944.

基于多尺度的时序数据部分周期模式增量挖掘

Partial periodic pattern incremental mining of time series data based on multi-scale

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 22

相关文章 15

编辑推荐

Metrics