基于AO算法的数据流频繁项集挖掘

计算机工程与科学 ›› 2020, Vol. 42 ›› Issue (12): 2259-2264.

基于AO算法的数据流频繁项集挖掘

文凯1,2,3,耿小海1,2,3，朱璐伟1,2,3，许萌萌1,2,3

（1.重庆邮电大学通信与信息工程学院，重庆 400065；2.重庆邮电大学通信新技术应用研究中心，重庆 400065；
3.重庆信科设计有限公司，重庆 401121）

收稿日期:2019-11-21 修回日期:2020-03-20 接受日期:2020-12-25 出版日期:2020-12-25 发布日期:2021-01-05

Frequent itemsets mining for data stream based on AO algorithm

WEN Kai1,2,3,GENG Xiao-hai1,2,3,ZHU Lu-wei1,2,3,XU Meng-meng1,2,3

(1.School of Communication and Information Engineering,
Chongqing University of Posts and Telecommunications,Chongqing 400065;

2.Research Center of New Telecommunication Technology,
Chongqing University of Posts and Telecommunications,Chongqing 400065;

3.Chongqing Information Technology Designing Co.,Ltd.,Chongqing 401121,China)

Received:2019-11-21 Revised:2020-03-20 Accepted:2020-12-25 Online:2020-12-25 Published:2021-01-05

摘要/Abstract

摘要： 针对传统数据流频繁项集挖掘算法在支持度更新、窗口更新方式、频繁k-项集挖掘等方面存在的一系列问题，造成空间和时间效率不高，改进研究了一种高效挖掘数据流频繁项集的AO算法。采用滑动窗口思想，对数据流分块挖掘；在满窗口有新数据流入时，采用取余插入完成数据更新；挖掘频繁k-项集采用And Operation求解支持度，并在挖掘过程结合超集检测，极大地提高了挖掘效率。实验结果表明，该算法在时间和空间效率上均有一定的优越性。

关键词: 数据流, 超集检测, 频繁项集, 与运算

Abstract: In view of a series of problems existing in support update, window update mode and frequent k-itemset mining of traditional frequent itemset mining algorithm in data flow, which results in low efficiency of space and time, an efficient AO algorithm for mining frequent itemsets in data streams is improved. The algorithm uses the idea of sliding window to mine the data stream in blocks; when there is new data flowing in the full window, the residual insertion is used to update the data; and operation is used to solve the support degree of frequent k-itemsets, and the superset detection is combined in the mining process, which greatly improves the mining efficiency. The experimental results show that the algorithm has good superiority in both time and space efficiency.

Key words: data stream, superset checking, frequent itemsets, And Operation

文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.

WEN Kai, GENG Xiao-hai, ZHU Lu-wei, XU Meng-meng, . Frequent itemsets mining for data stream based on AO algorithm[J]. Computer Engineering & Science, 2020, 42(12): 2259-2264.

[1]	李金熹, 尹首一, 魏少军, 胡杨. 基于MLIR的数据流模型[J]. 计算机工程与科学, 2024, 46(07): 1151-1157.
[2]	张家豪, 邓金易, 尹首一, 魏少军, 胡杨. 基于Actor模型的众核数据流硬件架构探索[J]. 计算机工程与科学, 2024, 46(06): 959-967.
[3]	丁滟, 王闯, 冯了了, 王锋, 常俊胜. 基于区块链监管的联盟数据可信流通[J]. 计算机工程与科学, 2022, 44(10): 1771-1780.
[4]	张喜龙, 韩萌, 陈志强, 武红鑫, 李慕航. 基于Hellinger距离的不平衡漂移数据流Boosting分类算法[J]. 计算机工程与科学, 2022, 44(05): 788-799.
[5]	乔冠杰, 吕高锋, 谭靖, 莫露莎. 大规模数据流统计中冷热流替换策略优化[J]. 计算机工程与科学, 2021, 43(09): 1567-1573.
[6]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[7]	熊菊霞1,2,3,吴尽昭1,2,3. 异构复杂信息网络敏感数据流动态挖掘[J]. 计算机工程与科学, 2020, 42(04): 628-633.
[8]	张馨予, 安建成, 曹锐. 基于自适应随机森林的数据流分类算法[J]. 计算机工程与科学, 2020, 42(03): 543-549.
[9]	杨杰，张东月，周丽华，黄皓，丁海燕. 基于网格耦合的数据流异常检测[J]. 计算机工程与科学, 2020, 42(01): 25-35.
[10]	廖纪勇，吴晟，刘爱莲. 基于布尔矩阵约简的Apriori算法改进研究[J]. 计算机工程与科学, 2019, 41(12): 2231-2238.
[11]	袁泉1,2,郭江帆1,赵学华1. 一种基于集成的不均衡数据流分类算法[J]. 计算机工程与科学, 2019, 41(08): 1519-1524.
[12]	李艺煌，马胜，郭阳，陈桂林，徐睿. 基于平铺数据流的可配置神经网络加速器[J]. 计算机工程与科学, 2019, 41(06): 963-972.
[13]	肖文，胡娟. 稀疏数据频繁项集挖掘算法研究综述[J]. 计算机工程与科学, 2019, 41(05): 780-787.
[14]	李易1，常成娟1，卢圣健1，江道忠2，范东睿1，叶笑春1. 面向数据流结构的指令映射优化方法[J]. 计算机工程与科学, 2019, 41(01): 9-13.
[15]	杨胜哲，于俊清,唐九飞. 数据流程序动态调度与优化[J]. 计算机工程与科学, 2017, 39(07): 1201-1210.