Survey of frequent pattern mining over data streams

doi:10.11772/j.issn.1001-9081.2018081712

Abstract

Abstract: Advanced applications such as fraud detection and trend learning lead to the development of frequent pattern mining over data streams. Data stream mining has to face more problems than static data mining like spatio-temporal constraint and combinatorial explosion of itemsets. In the paper, the existing frequent pattern mining algorithms over data streams were reviewed, and some classical algorithms and some newest algorithms were analyzed. According to the completeness of pattern set, frequent patterns of data stream could be divided into complete patterns and compressed patterns. Compressed patterns include closed frequent patterns, maximal frequent patterns, top-k frequent patterns and combinations of them. Between them, only closed frequent patterns are losslessly compressed. And constrained frequent pattern mining was used to narrow the result set obtained, satisfying the user's demand more. Algorithms based on sliding window model and time decay model were used to better handle recent transactions which occupy an important position in data stream mining. Moreover, two of the common algorithms, sequential pattern mining and high utility pattern mining algorithms were introduced. At last, further research direction of frequent pattern mining over data streams were discussed.

Key words: data stream, data stream mining, frequent pattern mining, sequential pattern mining, high utility pattern mining

摘要： 一些先进应用如欺诈检测和趋势学习等带来了数据流频繁模式挖掘的发展。不同于静态数据，数据流挖掘面临着时空约束和项集组合爆炸等问题。对已有数据流频繁模式挖掘算法进行综述并对经典和最新算法进行分析。按照模式集合的完整程度进行分类，数据流中频繁模式分为全集模式和压缩模式。压缩模式主要包括闭合模式、最大模式、top-k模式以及三者的组合模式。不同之处是闭合模式是无损压缩的，而其他模式是有损压缩的。为了得到有趣的频繁模式，可以挖掘基于用户约束的模式。为了处理数据流中的新近事务，将算法分为基于窗口模型和基于衰减模型的方法。数据流中模式挖掘常见的还包含序列模式和高效用模式，对经典和最新算法进行介绍。最后给出了数据流模式挖掘的下一步工作。

关键词: 数据流, 数据流挖掘, 频繁模式挖掘, 序列模式挖掘, 高效用模式挖掘

CLC Number:

TP18

HAN Meng, DING Jian. Survey of frequent pattern mining over data streams[J]. Journal of Computer Applications, 2019, 39(3): 719-727.

韩萌, 丁剑. 数据流频繁模式挖掘综述[J]. 计算机应用, 2019, 39(3): 719-727.

References

[1] BIFET A. Adaptive stream mining:pattern learning and mining from evolving data stream[C]//Proceedings of the 2010 Conference on Adaptive Stream Mining:Pattern Learning and Mining from Evolving Data Streams. Amsterdam, Netherlands:IOS Press, 2010:1-212.
[2] MANKU G S, MOTWANI R. Approximate frequency counts over data streams[C]//Proceedings of the 28th International Conference on Very Large DataBases. San Francisco, CA:Morgan Kaufmann, 2002:346-375.
[3] CHARIKAR M, CHEN K, FARACH-COLTON M. Finding frequent items in data streams[C]//Proceedings of the 2002 International Colloquium on Automata, Languages and Programming, LNCS 2380. 2002:693-703.
[4] YANG T, ZHOU Y, JIN H, et al. Pyramid sketch:a sketch framework for frequency estimation of data streams[J]. Proceedings of the VLDB Endowment, 2017, 10(11):1442-1453.
[5] LI H-F, SHAN M-K, LEE S-Y. DSM-FI:an efficient algorithm for mining frequent itemsets in data streams[J]. Knowledge Information Systems, 2008, 17(1):79-97.
[6] 李国徽,陈辉.挖掘数据流任意滑动时间窗口内频繁模式[J].软件学报,2008,19(19):2585-2596.(LI G H, CHEN H. Mining the frequent patterns in an arbitrary sliding window over online data streams[J]. Journal of Software, 2008, 19(10):2585-2596.)
[7] MEMAR M, SADREDDINI M H, DEYPIR M, et al. A block-based approach for frequent itemset mining over data streams[C]//Proceedings of the 20118th International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, NJ:IEEE, 2011:1647-1651.
[8] LI H-F, LEE S-Y. Mining frequent itemsets over data streams using efficient window sliding techniques[J]. Expert Systems with Applications, 2009, 36(2):1466-1477.
[9] FAN G, YIN S. A frequent itemset mining algorithm based on matrix in sliding window over data steam[C]//ISDEA'13:Proceedings of the 20133rd International Conference on Intelligent System Design and Engineering Applications. Washington, DC:IEEE Computer Society, 2013:66-69.
[10] CHANG J H, LEE W S. Finding recent frequent itemsets adaptively over online data streams[C]//KDD'03:Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2003:487-492.
[11] SHIN S J, LEE D S, LEE W S. CP-tree:an adaptive synopsis structure for compressing frequent itemsets over online data streams[J]. Information Sciences, 2014, 278:559-576.
[12] SILVA A, ANTUNES C. Pushing constraints into data streams[C]//BigMine'13:Proceedings of the 2nd International Workshop on Big Data, Streams and Heterogeneous Source Mining:Algorithms, Systems, Programming Models and Applications. New York:ACM, 2013:79-86.
[13] FARHAT A, GOUIDER M S, SAID L B. New algorithm for frequent itemsets mining from evidential data streams[J]. Procedia Computer Science, 2016, 96:645-653.
[14] KUSUMAKUMARI V, SHERIGAR D, CHANDRAN R, et al. Frequent pattern mining on stream data using Hadoop CanTreeGTree[J]. Procedia Computer Science, 2017, 115:266-273.
[15] BUSTIO-MARTÍNEZ L, CUMPLIDO R, HERNÁNDEZ-LEÍN R, et al. On the design of hardware-software architectures for frequent itemsets mining on data streams[J]. Journal of Intelligent Information Systems, 2018, 50(3):415-440.
[16] LI H, ZHANG N, ZHU J, et al. Probabilistic frequent itemset mining over uncertain data streams[J]. Expert Systems with Applications, 2018, 112:274-287.
[17] CHI Y, WANG H, YU P S, et al. Catch the moment:maintaining closed frequent itemsets over a data stream sliding window[J]. Knowledge and Information Systems, 2006, 10(3):265-294.
[18] YEN S-J, WU C-W, LEE Y-S, et al. A fast algorithm for mining frequent closed itemsets over stream sliding window[C]//Proceedings of the 2011 IEEE International Conference on Fuzzy Systems. Piscataway, NJ:IEEE, 2011:996-1002.
[19] NORI F, DEYPIR M, SADREDDINI M H. A sliding window based algorithm for frequent closed itemset mining over data streams[J]. Journal of Systems and Software, 2013, 86(3):615-623.
[20] DAI C, CHEN L. An algorithm for mining frequent closed itemsets in data stream[J]. Physics Procedia, 2012, 24(C):1722-1728.
[21] HAN M, DING J, Li J. TDMCS:an efficient method for mining closed frequent patterns over data streams based on time decay model[J]. International Arab Journal of Information Technology, 2017, 14(6):851-860.
[22] REDDY V S, RAO T V, GOVARDHAN A. Fast and Lossless Mining of Closed Frequent Itemsets (FLMCFI) over data streams[J]. Journal of Advanced Research in Dynamical and Control Systrems, 2018, 10:256-263.
[23] LEE G, YUN U, RYU K H. Sliding window based weighted maximal frequent pattern mining over data streams[J]. Expert Systems with Applications, 2014, 41(2):694-708.
[24] KARIM M R, COCHEZ M, BEYAN O D, et al. Mining maximal frequent patterns in transactional databases and dynamic data streams:a Spark-based approach[J]. Information Sciences, 2018, 432:278-300.
[25] CHANG Y I, LI C E, CHOU T J, et al. A weight-order-based lattice algorithm for mining maximal weighted frequent patterns over a data stream sliding window[C]//Proceedings of the 2018 IEEE International Conference on Applied System Innovation. Piscataway, NJ:IEEE, 2018:961-964.
[26] HOMEM N, CARVALHO J P. Finding top-k elements in data streams[J]. Information Sciences, 2010, 180(24):4958-4974.
[27] AMPHAWAN K, SOULAS J, LENCA P. Mining top-k regular episodes from sensor streams[J]. Procedia Computer Science, 2015, 69:76-85.
[28] LI J, GONG S. Top-k-FCI:mining top-k frequent closed itemsets in data streams[J]. Journal of Computational Information Systems, 2011, 7(13):4819-4826.
[29] TSAI P S M. Mining top-k frequent closed itemsets over data streams using the sliding window model[J]. Expert Systems with Applications, 2010, 37(10):6968-6973.
[30] AMPHAWAN K, LENCA P. Mining top-k frequent-regular closed patterns[J]. Expert Systems with Applications, 2015, 42(21):7882-7894.
[31] LIM Y, KANG U. Time-weighted counting for recently frequent pattern mining in data streams[J]. Knowledge and Information Systems, 2017,53(2):391-422.
[32] SONG C, LIU X, GE T. Top-k frequent items and item frequency tracking over sliding windows of any sizes[C]//Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2017:199-202.
[33] LEUNG C K-S, HAO B, JIANG F. Constrained frequent itemset mining from uncertain data streams[C]//Proceedings of the 2010 IEEE 26th International Conference on Data Engineering Workshops. Washington, DC:IEEE Computer Society, 2010:120-127.
[34] HU W-C, WANG B-N, CHENG Z-L. Mining frequent closed patterns with item constraints in data streams[C]//Proceedings of the 2008 International Conference on Machine Learning and Cybernetics. Piscataway, NJ:IEEE, 2008:274-280.
[35] CUZZOCREA A, LEUNG C K S, MacKINNON R K. Mining constrained frequent itemsets from distributed uncertain data[J]. Future Generation Computer Systems, 2014, 37:117-126.
[36] 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.
[37] CAGLIERO L, CERQUITELLI T, CHIUSANO S, et al. Characterizing unpredictable patterns in wireless sensor network data[J]. Information Sciences, 2018,467:149-162.
[38] LI C-W, JEA K-F. An adaptive approximation method to discover frequent itemsets over sliding-window-based data streams[J]. Expert Systems with Applications, 2011, 38(10):13386-13404.
[39] DEYPIR M, SADREDDINI M H. EclatDS:an efficient sliding window based frequent pattern mining method for data streams[J]. Intelligent Data Analysis, 2011, 15(4):571-587.
[40] CHEN H, SHU L, XIA J, et al. Mining frequent patterns in a varying-size sliding window of online transactional data streams[J]. Information Sciences, 2012, 215:15-36.
[41] LI C-W, JEA K-F. An approach of support approximation to discover frequent patterns from concept-drifting data streams based on concept learning[J]. Knowledge and Information Systems, 2014, 40(3):639-671.
[42] 李海峰,章宁,朱建明,等.时间敏感数据流上的频繁项集挖掘算法[J].计算机学报,2012,35(11):2283-2293.(LI H F, ZHANG N, ZHU J M, et al. Frequent itemset mining over time sensitive streams[J]. Chinese Journal of Computers, 2012, 35(11):2283-2293.)
[43] DEYPIR M, SADREDDINI M H, HASHEMI S. Towards a variable size sliding window model for frequent itemset mining over data streams[J]. Computers and Industrial Engineering, 2012, 63(1):161-172.
[44] 韩萌,王志海,丁剑.一种频繁模式决策树处理可变数据流[J].计算机学报,2016,39(8):1541-1554.(HAN M, WANG Z H, DING J. Efficient decision tree for evolving data streams based on frequent patterns[J]. Chinese Journal of Computers, 2016, 39(8):1541-1554.)
[45] 吴枫,仲妍,吴泉源.基于时间衰减模型的数据流频繁模式挖掘[J].自动化学报,2010,36(5):674-684.(WU F, ZHONG Y, WU Q Y. Ming frequent patterns over data stream under the time decaying model[J]. Acta Automatica Sinica, 2010, 36(5):674-684.)
[46] 廖国琼,吴凌琴,万常选.基于概率衰减窗口模型的不确定数据流频繁模式挖掘[J].计算机研究与发展,2012,49(5):1105-1115.(LIAO G Q, WU L Q, WANG C X. Frequent patterns mining over uncertain data streams based on probability decay window model[J]. Journal of Computer Research and Development, 2012, 49(5):1105-1115.)
[47] LI H, HO C, et al. A single-scan algorithm for mining sequential patterns from data streams[J]. International Journal of Innovative Computing, 2012, 8(3):1799-1820.
[48] CHEN L, MEI Q. Mining frequent items in data stream using time fading model[J]. Information Sciences, 2014, 257:54-69.
[49] 韩萌,王志海,原继东.一种基于时间衰减模型的数据流闭合模式挖掘方法[J].计算机学报,2015,38(7):1473-1482.(HAN M, WANG Z H, YUAN J D. Efficient method for mining closed frequent patterns from data streams based on time decay model[J]. Chinese Journal of Computers, 2015, 38(7):1473-1482.)
[50] CHEN J, CHEN P. Sequential pattern mining for uncertain data streams using sequential sketch[J]. Journal of Networks, 2014, 9(2):252-258.
[51] CHENG X, SU S, XU S, et al. Differentially private maximal frequent sequence mining[J]. Computers and Security, 2015, 55(C):175-192.
[52] AHMED C F, TANBEER S K, JEONG B-S, et al. Single-pass incremental and interactive mining for weighted frequent patterns[J]. Expert Systems with Applications, 2012, 39(9):7976-7994.
[53] AHMED C F, TANBEER S K, JEONG B-S, et al. Interactive mining of high utility patterns over data streams[J]. Expert Systems with Applications, 2012, 39(15):11979-11991.
[54] BRAUN P, CAMERON J J, CUZZOCREA A, et al. Effectively and efficiently mining frequent patterns from dense graph streams on disk[J]. Procedia Computer Science, 2014, 35:338-347.
[55] CUZZOCREA A, HAN Z, JIANG F, et al. Edge-based mining of frequent subgraphs from graph streams[J]. Procedia Computer Science, 2015, 60:573-582.
[56] FOURNIER-VIGER P, LIN J C W, KIRAN R U, et al. A survey of sequential pattern mining[J]. Data Science and Pattern Recognition, 2017,1(1):54-77.
[57] PEI J, HAN J, MORTAZAVI-ASL B, et al. Mining sequential patterns by pattern-growth:the PrefixSpan approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11):1424-1440.
[58] TÖWS D, HASSANI M, BEECKS C, et al. Optimizing sequential pattern mining within multiple streams[EB/OL].[2018-07-07]. http://cs.emis.de/LNI/Proceedings/Proceedings242/223.pdf.
[59] HASSANI M, TÖWS D, SEIDL T. Understanding the bigger picture:batch-free exploration of streaming sequential patterns with accurate prediction[C]//Proceedings of the 32nd Annual ACM Symposium on Applied Computing. New York:ACM, 2017:866-869.
[60] ZIHAYAT M, CHEN Y, AN A. Memory-adaptive high utility sequential pattern mining over data streams[J]. Machine Learning, 2017, 106(6):799-836.
[61] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of the 2005 Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 3518. Berlin:Springer, 2005:689-695.
[62] YUN U, KIM D, RYANG H, et al. Mining recent high average utility patterns based on sliding window from stream data[J]. Journal of Intelligent and Fuzzy Systems, 2016, 30(6):3605-3617.
[63] YUN U, RYANG H, LEE G, et al. An efficient algorithm for mining high utility patterns from incremental databases with one database scan[J]. Knowledge-Based Systems, 2017, 124:188-206.
[64] DAWAR S, SHARMA V, GOYAL V. Mining top-k high-utility itemsets from a data stream under sliding window model[J]. Applied Intelligence, 2017, 47(4):1240-1255.
[65] YUN U, KIM D, YOON E, et al. Damped window based high average utility pattern mining over data streams[J]. Knowledge-Based Systems, 2018,144:188-205.
[66] CHOI H-J, PARK C H. Emerging topic detection in twitter stream based on high utility pattern mining[J]. Expert Systems with Applications, 2019, 115:27-36.
[67] CUZZOCREA A, LEUNG C K. Computing theoretically-sound upper bounds to expected support for frequent pattern mining problems over uncertain big data[C]//Proceedings of the 2016 International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, CCIS 611. Berlin:Springer, 2016:379-392.
[68] HEMALATHA C S, VAIDEHI V, LAKSHMI R. Minimal infrequent pattern based approach for mining outliers in data streams[J]. Expert Systems with Applications, 2015, 42(4):1998-2012.
[69] DUONG Q-H, RAMAMPIARO H, NØRVÅG K, et al. High utility drift detection in quantitative data streams[J]. Knowledge-Based Systems, 2018, 157:34-51.
[70] de ASSUNÇÃO M D, da SILVA VEITH A, BUYYA R. Distributed data stream processing and edge computing:a survey on resource elasticity and future directions[J]. Journal of Network and Computer Applications, 2018, 103:1-17.
[71] ur REHMAN M H, LIEW C S, WAH T Y, et al. Towards next-generation heterogeneous mobile data stream mining applications:opportunities, challenges, future research directions[J]. Journal of Network and Computer Applications, 2017, 79:1-24.