CFMoment:挖掘数据流频繁闭项集算法

doi:10.3969/j.issn.0255-8297.2019.03.009

应用科学学报 ›› 2019, Vol. 37 ›› Issue (3): 389-397.doi: 10.3969/j.issn.0255-8297.2019.03.009

CFMoment:挖掘数据流频繁闭项集算法

王金伟, 吴少华, 瞿治国

南京信息工程大学计算机与软件学院, 南京 210044

收稿日期:2018-05-22 修回日期:2018-10-30 出版日期:2019-05-31 发布日期:2019-05-31
作者简介:王金伟,教授,博导,研究方向:信息安全,E-mail:wjwei_2004@163.com
基金资助:
国家自然科学基金（No.60971006）；国家"863"高技术研究发展计划基金（No.2010AA122202）；澳门特别行政区科学技术发展基金（No.063/2010/A）资助

CFMoment: Closed Frequent Itemsets Mining Based on Data Stream

WANG Jingwei, WU Shaohua, QU Zhiguo

School of Computer and Software, Nanjing University of Information Science and Technology, Nanjing 210044, China

Received:2018-05-22 Revised:2018-10-30 Online:2019-05-31 Published:2019-05-31

摘要/Abstract

摘要： 在数据流上挖掘频繁闭项集是数据挖掘中关联性挖掘的重要研究课题之一.该文提出了一种高效的数据流频繁闭项挖掘算法——CFMoment，通过使用滑动窗口不断维护数据流中的频繁闭项集，可适用于实时性要求较高的多种数据流处理应用环境.该算法利用项目的有效比特序列表示来减少滑动窗口所需的时间和内存，进一步提升了在数据流中挖掘频繁闭项集的效率并有效降低了运行过程中的内存需求.实验表明，该算法不仅获得了高精度的挖掘结果，而且其运算速度明显快于现有的Moment算法，在数据流上挖掘频繁闭项集的内存消耗更少.

关键词: 频繁闭项集, 数据挖掘, 数据流, 滑动窗口

Abstract: Mining closed frequent itemsets over stream data is an important research issue of mining association rules in data mining. In this paper, we propose an efficient closed frequent itemsets mining algorithm in stream data, CFMoment, to maintain the set of closed frequent itemsets in data streams with a sliding window. The new algorithm can be applied to many stream data processing applications with high real-time requirements. It proposes to reduce the time and memory requirements in sliding windows by using the effective bit-sequence representation of items, which further improves the efficiency of closed frequent itemsets in stream data mining and effectively reduces the memory requirements in running process. Experiments show that the proposed algorithm not only attains highly accurate mining results, but also runs significantly faster and consumes less memory than the existing algorithm Moment.

Key words: data streams, data mining, sliding window, closed frequent itemsets

中图分类号:

P751.1

王金伟, 吴少华, 瞿治国. CFMoment:挖掘数据流频繁闭项集算法[J]. 应用科学学报, 2019, 37(3): 389-397.

WANG Jingwei, WU Shaohua, QU Zhiguo. CFMoment: Closed Frequent Itemsets Mining Based on Data Stream[J]. Journal of Applied Sciences, 2019, 37(3): 389-397.

参考文献 24

[1]	Garofalakis M N, Gehrke J, Rastogi R. Querying and mining data streams:you only get one look a tutorial[C]//ACM Sigmod International Conference. ACM, 2002, 16(1):635.
[2]	Babcock B, Babu S, Datar M. Models and issues in data stream systems[C]//ACM SigmodSigact-Sigart Symposium on Principles of Database Systems. ACM, 2002:1-16.
[3]	Jiang N, Gruenwald L. Research issues in data stream association rule mining[J]. ACM Sigmod Record, 2006, 35(1):14-19.
[4]	Manku G S, Motwani R. Approximate frequency counts over data streams[M]. VLDB Endowment, 2012, 5(12):346-357.
[5]	Li H F, Lee S Y, Shan M K. An efficient algorithm for mining frequent itemsets over the entire history of data streams[C]//Proceedings of the first International Workshop on Knowledge Discovery in Data Streams, 2004, 1(1):1.
[6]	Li H F, Lee S Y, Shan M K. Online mining (recently) maximal frequent itemsets over data streams[C]//Proceedings of the 15th IEEE International Workshop on Research Issues on Data Engineering, 2005:11-18.
[7]	Yu J X, Chong Z, Lu H. A false negative approach to mining frequent itemsets from high speed transactional data streams[J]. Information Sciences, 2006, 176(14):1986-2015.
[8]	Liu X, Guan J, Hu P. Mining frequent closed itemsets from a landmark window over online data streams[J]. Computers and Mathematics with Applications, 2009, 57(6):927-936.
[9]	Chang J, Lee W. Finding recently frequent itemsets adaptively over online transactional data streams[J]. Information Systems, 2006, 31(8):849-869.
[10]	Woo H J, Lee W S. EstMax:tracing maximal frequent itemsets instantly over online transactional data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(10):1418-1431.
[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]	Chang J, Lee W. A sliding window method for finding recently frequent itemsets over online data streams[J]. Journal of Information Science and Engineering, 2004, 20(4):753-762.
[13]	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.
[14]	Agrawal R, Srikant R. Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference on Very Large Data Bases, 1994:487-499.
[15]	Farzanyar Z, Kangavari M, Cercone N. Max-FISM:mining (recently) maximal frequent itemsets over data streams using the sliding window model[J]. Computers and Mathematics with Applications, 2012, 64:1706-1718.
[16]	Mohit O, Komal T. An enhanced apriori and improved algorithm for association rules[J]. International Research Journal of Engineering and Technology (IRJET), 2016, 3:2395-0072.
[17]	马月坤,刘鹏飞,张振友,孙燕,丁铁凡. 改进的FP-Growth算法及其分布式并行实现[J]. 哈尔滨理工大学学报,2016, 21(2):20-27. Ma Y K, Liu P F, Zhang Z Y, Sun Y, Ding T F. Improved FP-Growth Algorithm and Its Distributed Parallel Implementation[J]. Journal of Harbin University of Science and Technology, 2016, 21(2):20-27.
[18]	Lin J C W, Gan W, Fournier V, Chao H C, Zhan J. Mining of frequent patterns with multiple minimum supports[J]. Engineering Applications of Artifical Intelligence, 2017, 60:83-96.
[19]	Chi Y, Wang H, Yu P, Muntz R. MOMENT:maintaining closed frequent itemsets over a stream sliding window[C]//IEEE International Conference on Data Mining. Brighton, England, IEEE, 2006, 10(3):59-66.
[20]	Jiang N, Gruenwald L. CFI-stream:mining closed frequent itemsets in data streams[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2006:592-597.
[21]	Li H F, Ho C C, Lee S Y. Incremental updates of closed frequent itemsets over continuous data streams[J]. Expert Systems with Applications, 2009, 36(2):2451-2458.
[22]	Dai C, Chen L. An algorithm for mining frequent closed itemsets in data stream[J]. Physics Procedia, 2002, 24:1722-1728.
[23]	Han J, Pei J, Yin Y, Mao R. Mining frequent patterns without candidate generation:a frequentpattern tree approach[J]. Data Mining and Knowledge Discovery, 2004, 8:53-87.
[24]	Nori F, Deypir M, Sadreddini M H. A sliding window-based algorithm for frequent closed itemset mining over data streams[J]. The Journal of Systems and Software, 2013, 86:615-623.

CFMoment:挖掘数据流频繁闭项集算法

CFMoment: Closed Frequent Itemsets Mining Based on Data Stream

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 24

相关文章 15

编辑推荐

Metrics

本文评价

[1]	吕艳霞, 王翠容, 王聪, 苑迎. 一种基于数据不确定性的概念漂移数据流分类算法[J]. 应用科学学报, 2017, 35(5): 559-569.
[2]	刘三民, 刘涛, 王忠群, 修宇, 刘余霞, 孟超. 融合分类器可信度的数据流集成分类[J]. 应用科学学报, 2017, 35(2): 226-232.
[3]	姜静逸1，韩松臣1，汤新民1，倪金霞1，崔国山2. 基于满意度控制的机场应急救援决策规则的数据挖掘[J]. 应用科学学报, 2009, 27(6): 644-650.
[4]	朱小栋;黄志球;陈圣青;黄凤;沈国华. 面向数据流挖掘过程的算法管理框架[J]. 应用科学学报, 2008, 26(1): 61-61 .
[5]	曾红卫;周建云. 基于数据流的组件测试[J]. 应用科学学报, 2007, 25(6): 621-621 .
[6]	王金栋, 周良, 张磊, 丁秋林. 基于分枝路径分析的连续查询降载算法[J]. 应用科学学报, 2007, 25(1): 63-68.
[7]	刘学军, 徐宏炳, 董逸生, 钱江波, 王永利. 基于最大频繁项集信息熵的数据流变化检测[J]. 应用科学学报, 2006, 24(5): 498-502.
[8]	朱玉全, 杨鹤标. 负关联规则挖掘算法研究[J]. 应用科学学报, 2006, 24(4): 382-386.
[9]	王金栋, 张磊, 丁秋林, 黄添强. 一种支持分布式数据流处理的双层重叠网络模型[J]. 应用科学学报, 2006, 24(4): 387-390.
[10]	王永利, 徐宏炳, 董逸生, 钱江波, 刘学军. 数据流上异常数据的在线检测与修正[J]. 应用科学学报, 2006, 24(3): 256-261.
[11]	王金栋, 周良, 张磊, 丁秋林. 面向分布式数据流系统的可扩展负载平衡算法[J]. 应用科学学报, 2006, 24(3): 250-255.
[12]	杨宜东, 孙志挥. 密度相关的数据流偏倚抽样[J]. 应用科学学报, 2006, 24(2): 203-207.
[13]	赵传申, 孙志挥. 多分类-关联规则分类的一种改进算法[J]. 应用科学学报, 2005, 23(6): 615-619.
[14]	钟勇, 秦小麟, 包磊. 基于用户查询模式的挖掘算法及其在入侵检测中的应用[J]. 应用科学学报, 2005, 23(5): 506-512.
[15]	何月顺, 丁秋林. 基于数据挖掘思想的故障模式分析[J]. 应用科学学报, 2005, 23(5): 545-547.