一种改进的数据流最大频繁项集挖掘算法

摘要/Abstract

摘要：

提出了一种基于DSMMFI算法的改进算法DSMMFIDS算法，它首先将事务数据按一定的全序关系存入DSFIlist列表中；然后按排序后的顺序存储到类似概要数据结构的树中；接着删除树中和DSFIlist列表中的非频繁项，同时删除窗口衰退支持数大的事务项；最后采用自顶向下和自底向上的双向搜索策略来挖掘数据流的最大频繁项集。通过用例分析和实验表明，该算法比DSMMFI算法具有更好的执行效率。

关键词: 数据挖掘, 数据流, 界标窗口, 最大频繁项集, 窗口衰减支持数

Abstract:

Based on the algorithm of DSMMFI, an improved algorithm, named DSMMFIDS (Dictionary Sequence Mining Maximal Frequent Itemsets over Data Streams), is proposed. Firstly, it stores transaction data into DSFIlist in alphabetical order. Secondly, the data are stored sequentially into the tree similar to the summary data structure. Thirdly, nonfrequent items in the tree and DSFIlist are removed, and the transaction items with the maximum count of window attenuation supports are deleted. Finally, the strategy (topdown and bottomup twoway search) is used to mine maximal frequent itemsets over data streams, and case analysis and experiments prove that the algorithm DSMMFIDS has better performance than the algorithm DSMMFI.

Key words: data mining;data stream;landmark windows;maximal frequent itemsets;window attenuation support count

胡健，吴毛毛. 一种改进的数据流最大频繁项集挖掘算法[J]. J4, 2014, 36(05): 963-970.

HU Jian,WU Maomao. An improved algorithm for mining maximal
frequent itemsets over data streams [J]. J4, 2014, 36(05): 963-970.

参考文献

［1］Li H, Lee S, Shan M. Online mining (recently) maximal frequent itemsets over data streams［C］∥Proc of the 15th International Workshops on Research Issues in Data Engineering:Stream Data Mining and Applications, 2005:1118.
［2］Han J,Kamber M.Data mining:Concept and techniques［M］.2nd edition. San Fransisco:Higher Education Press, 2001.
［3］Pan Yunhe,Wang Jinlong,Xu Congfu.State of the art on frequent pattern mining in data streams［J］.Acta Automatica Sinica, 2006,32(4):594602. (in Chinese)
［4］Meng Caixia. Research on mining frequent itemsets in data streams［J］.Computer Engineering and Applications, 2010,46(24):138140. (in Chinese)
［5］Zhuang Bo,Liu Xiyu,Long Kun.TWCTstream:Algorithm for mining frequent patterns in data streams［J］. Computer Engineering and Applications, 2009,45(20):147150. (in Chinese)
［6］Yan Yuejin.Research on mining algorithms of maximal frequent item sets［D］. Changsha:National University of Defense Technology,2005. (in Chinese)
［7］Yan Yuejin, Li Zhoujun, Chen Huowang. A depthfirst search algorithm for mining maximal frequent itemsets［J］.Journal of Computer Research and Development, 2005,42(3):462467. (in Chinese)
［8］Huang Shucheng,Qu Yahui.Survey on data stream classification technologies［J］.Application Research of Computers, 2009,26(10):36043609. (in Chinese)
［9］Ji Genlin,Yang Ming,Song Yuqing, et al.Fast updating maximum frequent itemsets［J］.Chinese Journal of Computer, 2005,28(1):128135. (in Chinese)
［10］Li Hua Fu,Lee Suh Yin.Mining frequent itemsets over data streams using efficient window sliding techniques［J］.Expert Systems with Applications, 2009,36(2,Part 1):14661477.
［11］Giannella C, Han Jiawei, Pei Jian, et al. Mining frequent patterns in data streams at multiple time granularities［M］∥Data Mining:Next Generation Challenges and Future Directions,Cambridge:MIT, 2003.
［12］Ma Da,Wang Jiaqiang.A compressed FPtree based on algorithm for mining maximal frequent itemsets［J］.Journal of Changchun University of Science and Technology(Natural Science Edition), 2009,32(3):457461. (in Chinese)
［13］Ao Fujiang,Yan Yuejin,Liu Baohong, et al.Online mining maximal frequent itemsets in sliding window over data streams［J］.Journal of Sytem Simulation, 2009,21(4):11341139. (in Chinese)
［14］Li Haifeng,Zhang Ning. Maximal frequent itemsets mining method over data stream［J］.Computer Engineering, 2012,38(21):4548. (in Chinese)
［15］Hu Demin, Zhao Ruike. An improved algorithm for mining maximum frequent itemsets［J］.Computer Applications and Software, 2012,29(12):186188. (in Chinese)
［16］Zhang Yueqin, Chen Dong. Mining method of data stream maximum frequent itemsets［J］.Computer Engineering, 2010,36(22):8690. (in Chinese)
［17］Hua Hongjuan, Zhang Jian, Chen Shaohua. Mining algorithm for constrained maximum frequent itemsets based on frequent pattern tree［J］.Computer Engineering, 2011,37(9):7880. (in Chinese)
［18］Li H, Lee S, Shan M. An efficient algorithm for mining frequent itemsets over the entire history of data streams［C］∥Proc of the 1st International Workshop on Knowledge Discovery in Data Streams, held in conjunction with the 15th European Conference on Machine Learning (ECML 2004) and the 8th European Conference on the Principles and Practice of Knowledge Discovery in Databases (PKDD 2004), 2004:1.
［19］Mao Yimin,Yang Luming,Li Hong, et al. An effective algorithm of mining maximal frequent patterns on data stream［J］. Chinese High Technology Letters, 2010,3(3):100107. (in Chinese)
［20］Song Yuqing,Zhu Yuquan,Sun Zhihui, et al.An algorithm and its updating algorithm based on FPtree for mining maximum frequent itemsets［J］.Journal of Software, 2003,14(9):15861592. (in Chinese)
附中文参考文献：
［3］潘云鹤，王金龙，徐从富.数据流频繁模式挖掘研究进展［J］.自动化学报,2006,32(4):594602.
［4］孟彩霞.面向数据流的频繁项集挖掘研究［J］.计算机工程与应用,2010,46(24):138140.
［5］庄波，刘希玉，隆坤.TWCTStream：数据流上的频繁模式挖掘算法［J］.计算机工程与应用,2009,45(20):147150.
［6］颜跃进.最大频繁项集挖掘算法的研究［D］.长沙：国防科学技术大学,2005.
［7］颜跃进，李舟军，陈火旺.一种挖掘最大频繁项集的深度优先算法［J］.计算机研究与发展,2005,42(3):462467.
［8］黄树成，曲亚辉.数据流分类技术研究综述［J］.计算机应用研究,2009,26(10):36043609.
［9］吉根林，杨明，宋余庆,等.最大频繁项目集的快速更新［J］.计算机学报，2005,28(1):128135.
［12］马达，王佳强.一种基于压缩FP树的最大频繁项集挖掘算法［J］.长春理工大学学报（自然科学版）,2009,32(3):457461.
［13］敖富江，颜跃进，刘宝宏，等.在线挖掘数据流滑动窗口中最大频繁项集［J］.系统仿真学报,2009,21(4):11341139.
［14］李海峰，章宁.数据流上的最大频繁项集挖掘方法［J］.计算机工程,2012,38(21):4548.
［15］胡德敏，赵瑞可.一种改进的最大频繁项集挖掘算法［J］.计算机应用与软件,2012,29(12):186188.
［16］张月琴，陈东.数据流最大频繁项集挖掘方法［J］.计算机工程,2010,36(22):8690.
［17］花红娟，张健，陈少华.基于频繁模式树的约束最大频繁项集挖掘算法［J］.计算机工程，2011,37(9):7880.
［19］毛伊敏，杨路明，李宏,等.一种有效的数据流最大频繁模式挖掘算法［J］.高技术通讯,2010,3(3):100107.
［20］宋余庆，朱玉全，孙志挥,等.基于FPTree的最大频繁项目集挖掘及更新算法［J］.软件学报,2003,14(9):15861592.

[1]	雷轩, 程光, 张玉健, 郭靓, 张付存. 基于电力网络态势感知平台的告警信息关联分析[J]. 计算机工程与科学, 2023, 45(07): 1197-1208.
[2]	王晨宇, 温浩珉, 郭晟楠, 林友芳, 万怀宇, . 面向快递员揽收到达时间预测的多任务深度时空网络[J]. 计算机工程与科学, 2023, 45(01): 136-144.
[3]	丁滟, 王闯, 冯了了, 王锋, 常俊胜. 基于区块链监管的联盟数据可信流通[J]. 计算机工程与科学, 2022, 44(10): 1771-1780.
[4]	程小刚, 郭韧, 周长利, . 基于理性密码学的分布式隐私保护数据挖掘框架[J]. 计算机工程与科学, 2022, 44(10): 1781-1787.
[5]	王文涛, 马慧芳, 舒跃育, 贺相春. 基于上下文表示的知识追踪方法[J]. 计算机工程与科学, 2022, 44(09): 1693-1701.
[6]	张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 基于Hellinger距离的不平衡漂移数据流Boosting分类算法[J]. 计算机工程与科学, 2022, 44(05): 788-799.
[7]	乔冠杰, 吕高锋, 谭靖, 莫露莎. 大规模数据流统计中冷热流替换策略优化[J]. 计算机工程与科学, 2021, 43(09): 1567-1573.
[8]	刘云, 肖添. 网络日志数据中条件因果挖掘算法的优化研究[J]. 计算机工程与科学, 2021, 43(09): 1584-1590.
[9]	文凯, 许萌萌, 张许红, . 基于列表结构的加权可擦除项集挖掘算法[J]. 计算机工程与科学, 2021, 43(09): 1676-1683.
[10]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[11]	熊中敏, 汪博, 陶然, 郑宗生, 陈明, . 一种基于主属性判定的关联规则挖掘约简算法[J]. 计算机工程与科学, 2021, 43(04): 738-745.
[12]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[13]	藏润强, 左美云, 郭鑫鑫. 基于Doc2Vec和BiLSTM的老年患者疾病预测研究[J]. 计算机工程与科学, 2020, 42(12): 2273-2279.
[14]	何望1,2，林果园1,2. 基于FP-Growth改进算法的云服务器故障数据分析[J]. 计算机工程与科学, 2020, 42(05): 770-775.
[15]	熊菊霞1,2,3,吴尽昭1,2,3. 异构复杂信息网络敏感数据流动态挖掘[J]. 计算机工程与科学, 2020, 42(04): 628-633.