高级搜索

一种基于邻接表的最大频繁项集挖掘算法

殷茗 王文杰 张煊宇 姜继娇

引用本文: 殷茗, 王文杰, 张煊宇, 姜继娇. 一种基于邻接表的最大频繁项集挖掘算法[J]. 电子与信息学报, doi: 10.11999/JEIT180692 shu
Citation:  Ming YIN, Wenjie WANG, Xuanyu ZHANG, Jijiao JIANG. An Maximal Frequent Itemsets Mining Algorithm Based on Adjacency Table[J]. Journal of Electronics and Information Technology, doi: 10.11999/JEIT180692 shu

一种基于邻接表的最大频繁项集挖掘算法

    作者简介: 殷茗: 女,1978年生,博士,副教授,主要方向为企业信息化、信息管理与信息系统、电子服务;
    王文杰: 男,1992年生,硕士,主要研究方向为数据挖掘,机器学习;
    张煊宇: 男,1995年生,硕士,主要研究方向为信息管理与信息系统。E-mail:;
    姜继娇: 男,1979年生,博士,副教授,主要方向为行为金融与风险管理;
    通讯作者: 王文杰, wenjie@mail.nwpu.edu.cn
  • 基金项目: 教育部人文与社会科学基金(16YJA630068, 18YJA630043),航空科学基金(2016ZG53071),陕西省自然科学基础研究计划项目(2018JM7008),陕西省社会科学基金(2018S28),西北工业大学研究生种子基金(ZZ2018222)

摘要: 针对Apriori算法与FP-Growth算法在最大频繁项集挖掘过程中存在的运行低效、内存消耗大、难以适应稠密数据集的处理、影响大数据价值挖掘时效等问题,该文提出一种基于邻接表的最大频繁项集挖掘算法。该算法只需遍历数据库一次,同时用哈希表对邻接表进行辅助存储,减小了遍历的空间规模。理论分析与实验结果表明,该算法时间与空间复杂度较低,提高了最大频繁项集挖掘速率,尤其在处理稠密数据集时具有较好的优越性。

English

    1. [1]

      WU Xindong, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1–37. doi: 10.1007/s10115-007-0114-2

    2. [2]

      FASIH H and SHAHRAKI M H N. Incremental mining maximal frequent patterns from univariate uncertain data[J]. Knowledge-Based Systems, 2018, 152: 40–50. doi: 10.1016/j.knosys.2018.04.001

    3. [3]

      易彤, 徐宝文, 吴方君. 一种基于FP树的挖掘关联规则的增量更新算法[J]. 计算机学报, 2004, 27(5): 703–710. doi: 10.3321/j.issn:0254-4164.2004.05.017
      YI Tong, XU Baowen, and WU Fangjun. A FP-tree based incremental updating algorithm for mining association rules[J]. Chinese Journal of Computers, 2004, 27(5): 703–710. doi: 10.3321/j.issn:0254-4164.2004.05.017

    4. [4]

      陈安龙, 唐常杰, 陶宏才, 等. 基于极大团和FP-Tree的挖掘关联规则的改进算法[J]. 软件学报, 2004, 15(8): 1198–1207. doi: 10.13328/j.cnki.jos.2004.08.012
      CHEN Anlong, TANG Changjie, TAO Hongcai, et al. An improved algorithm based on maximum clique and FP-Tree for mining association rules[J]. Journal of Software, 2004, 15(8): 1198–1207. doi: 10.13328/j.cnki.jos.2004.08.012

    5. [5]

      BUI H, VO B, NGUYEN H, et al. A weighted N-list-based method for mining frequent weighted itemsets[J]. Expert Systems with Applications, 2018, 96: 388–405. doi: 10.1016/j.eswa.2017.10.039

    6. [6]

      AGRAWAL R and SRIKANT R. Fast algorithms for mining association rules in large databases[C]. Proceedings of the 20th International Conference on Very Large Data Bases, San Francisco, 1994: 487–499.

    7. [7]

      APILETTI D, BARALIS E, CERQUITELLI T, et al. Frequent itemsets mining for big data: A comparative analysis[J]. Big Data Research, 2017, 9: 67–83. doi: 10.1016/j.bdr.2017.06.006

    8. [8]

      肖波, 徐前方, 蔺志青, 等. 可信关联规则及其基于极大团的挖掘算法[J]. 软件学报, 2008, 19(10): 2597–2610.
      XIAO Bo, XU Qianfang, LIN Zhiqing, et al. Credible association rule and its mining algorithm based on maximum clique[J]. Journal of Software, 2008, 19(10): 2597–2610.

    9. [9]

      HAN Jiawei, PEI Jian, and YIN Yiwen. Mining frequent patterns without candidate generation[C]. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, 2000: 1–12. doi: 10.1145/342009.335372.

    10. [10]

      KARIM 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. doi: 10.1016/j.ins.2017.11.064

    11. [11]

      吉根林, 杨明, 宋余庆, 等. 最大频繁项目集的快速更新[J]. 计算机学报, 2005, 28(1): 128–135. doi: 10.3321/j.issn:0254-4164.2005.01.016
      JI Genlin, YANG Ming, SONG Yuqing, et al. Fast updating maximum frequent itemsets[J]. Chinese Journal of Computers, 2005, 28(1): 128–135. doi: 10.3321/j.issn:0254-4164.2005.01.016

    12. [12]

      宋余庆, 朱玉全, 孙志挥, 等. 基于FP-Tree的最大频繁项目集挖掘及更新算法[J]. 软件学报, 2003, 14(9): 1586–1592. doi: 10.13328/j.cnki.jos.2003.09.012
      SONG Yuqing, ZHU Yuquan, SUN Zhihui, 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. doi: 10.13328/j.cnki.jos.2003.09.012

    13. [13]

      VIJAYARANI S and SHARMILA S. Comparative analysis of association rule mining algorithms[C]. Proceedings of 2016 International Conference on Inventive Computation Technologies, Coimbatore, 2016: 1–6. doi: 10.1109/INVENTIVE.2016.7830203.

    14. [14]

      LIU Li, YU Shuo, WEI Xiang, et al. An improved Apriori-based algorithm for friends recommendation in microblog[J]. International Journal of Communication Systems, 2018, 31(2): e3453. doi: 10.1002/dac.3453

    15. [15]

      连志春, 伊凤新. 一种改进的频繁模式树生长算法[J]. 应用科技, 2008, 35(6): 47–51. doi: 10.3969/j.issn.1009-671X.2008.06.012
      LIAM Zhichun and YI Fengxin. An improved frequent pattern tree growth algorithm[J]. Applied Science and Technology, 2008, 35(6): 47–51. doi: 10.3969/j.issn.1009-671X.2008.06.012

    1. [1]

      赵学健孙知信袁源. 基于预判筛选的高效关联规则挖掘算法. 电子与信息学报, doi: 10.11999/JEIT151107

    2. [2]

      王力吴成东陈东岳. 基于密度权期望最大与分裂合并策略的线状模式挖掘. 电子与信息学报, doi: 10.3724/SP.J.1146.2011.01014

    3. [3]

      孙力娟陈小东韩崇郭剑. 一种新的数据流模糊聚类方法. 电子与信息学报, doi: 10.11999/JEIT141415

    4. [4]

      王菊刘付显. 一种面向多属性不确定数据流的模体发现算法. 电子与信息学报, doi: 10.11999/JEIT160247

    5. [5]

      张清华幸禹可周玉兰. 基于粒计算的增量式知识获取方法. 电子与信息学报, doi: 10.3724/SP.J.1146.2010.00217

    6. [6]

      徐小龙李永萍. 一种基于MapReduce的知识聚类与统计机制. 电子与信息学报, doi: 10.11999/JEIT150247

    7. [7]

      江逸茗兰巨龙郭通田铭. 一种面向可重构网络的业务聚类方法. 电子与信息学报, doi: 10.3724/SP.J.1146.2012.00973

    8. [8]

      张亚红李玉鑑张婷. 检测多元相关关系的最大信息熵方法. 电子与信息学报, doi: 10.11999/JEIT140053

    9. [9]

      职为梅张婷范明. 基于影响函数的k-近邻分类. 电子与信息学报, doi: 10.11999/JEIT141433

    10. [10]

      王晓晔王正欧. 正则化训练的神经网络与粗集理论相结合的股票时间序列数据挖掘技术. 电子与信息学报,

    11. [11]

      朱凤翔戚文峰. Fp上pn-周期序列的1-错线性复杂度. 电子与信息学报, doi: 10.3724/SP.J.1146.2006.01568

    12. [12]

      姜园张朝阳仇佩亮周东方. 用于数据挖掘的聚类算法. 电子与信息学报,

    13. [13]

      李锦玲汪斌强. 基于最大频繁序列模式挖掘的App-DDoS攻击的异常检测. 电子与信息学报, doi: 10.3724/SP.J.1146.2012.01372

    14. [14]

      万里廖建新朱晓民. 一种时间序列频繁模式挖掘算法及其在WSAN行为预测中的应用. 电子与信息学报, doi: 10.3724/SP.J.1146.2009.00300

    15. [15]

      高毫林彭天强李弼程郭志刚. 基于多表频繁项投票和桶映射链的快速检索方法. 电子与信息学报, doi: 10.3724/SP.J.1146.2012.00548

    16. [16]

      曹广真金亚秋. 基于水平集方法的多源遥感数据融合及城区道路提取. 电子与信息学报, doi: 10.3724/SP.J.1146.2005.01682

    17. [17]

      龚晓峰毛蕾林秋华徐友根刘志文. 基于四阶累积量张量联合对角化的多数据集联合盲源分离. 电子与信息学报, doi: 10.11999/JEIT180414

    18. [18]

      徐涛孟野卢敏. 基于RankClus算法的机场流程日志活动挖掘. 电子与信息学报, doi: 10.11999/JEIT151137

    19. [19]

      方滨兴. 在线社交网络的挖掘与分析专题序言. 电子与信息学报,

    20. [20]

      龚卫华郭伟鹏杨良怀. 信任网络中多维信任序列模式挖掘方法研究. 电子与信息学报, doi: 10.3724/SP.J.1146.2013.01362

  • 图 1  顶头表与FP-Tree

    图 2  基于邻接表的最大频繁项集挖掘过程

    图 3  由数据集生成邻接表

    图 4  处理稀疏与稠密数据集不同事务数量的效率对比图

    图 5  处理稀疏与稠密数据集不同支持度计数的效率对比图

    表 1  事务数据库

    TID
    T100B, C, E
    T200F, B
    T300C, A, D
    T400D, B, C, A, E
    T500C, E, D
    T600E, F
    下载: 导出CSV

    表 2  3种算法的最大频繁项集挖掘结果

    AprioriFP-Growth基于邻接表的算法支持度
    (A,C:2)(A,C:2)(C,A:2)0.3
    (D,A:2)(A,D:2)(A,D:2)0.3
    (B,C:2)(B,C:2)(B,C:2)0.3
    (E,B:2)(B,E:2)(B,E:2)0.3
    (D,C:3)(D,C:3)(C,D:3)0.5
    (C,E:3)(E,C:3)(C,E:3)0.5
    (D,E:2)(D,E:2)(E,D:2)0.3
    (D,A,C:2)(A,C,D:2)(C,A,D:2)0.3
    (E,C,B:2)(B,C,E:2)(B,C,E:2)0.3
    (D,C,E:2)(D,C,E:2)(C,D,E:2)0.3
    下载: 导出CSV
  • 加载中
图(5)表(2)
计量
  • PDF下载量:  11
  • 文章访问数:  89
  • HTML全文浏览量:  71
  • 引证文献数: 0
文章相关
  • 通讯作者:  王文杰, wenjie@mail.nwpu.edu.cn
  • 收稿日期:  2018-07-08
  • 录用日期:  2019-05-17
  • 网络出版日期:  2019-05-29
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章