高级搜索

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

殷茗 王文杰 张煊宇 姜继娇

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

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

    作者简介: 殷茗: 女,1978年生,博士,副教授,主要研究方向为企业信息化、信息管理与信息系统、电子服务;
    王文杰: 男,1992年生,硕士,主要研究方向为数据挖掘、机器学习;
    张煊宇: 男,1995年生,硕士,主要研究方向为信息管理与信息系统;
    姜继娇: 男,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]. 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]. 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]. 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]

      王守华陆明炽孙希延纪元法胡丁梅. 基于无迹卡尔曼滤波的iBeacon/INS数据融合定位算法. 电子与信息学报, 2019, 41(0): 1-8. doi: 10.11999/JEIT180748

    2. [2]

      周艺华吉文杨宇光. 基于f-mOPE的数据库密文检索方案. 电子与信息学报, 2019, 41(8): 1793-1799. doi: 10.11999/JEIT180805

    3. [3]

      吕增威魏振春韩江洪孙仁浩夏成凯. 基于多目标优化的无线传感器网络移动充电及数据收集算法. 电子与信息学报, 2019, 41(8): 1877-1884. doi: 10.11999/JEIT180897

    4. [4]

      陈莹许潇月. 基于双向参考集矩阵度量学习的行人再识别. 电子与信息学报, 2019, 41(0): 1-9. doi: 10.11999/JEIT190159

    5. [5]

      雒江涛何宸王俊霞. 命名数据网络中可追溯且轻量级的细粒度访问控制机制. 电子与信息学报, 2019, 0(0): 1-7. doi: 10.11999/JEIT181160

    6. [6]

      田子建贺方圆. 一种基于分布式压缩感知的矿井目标指纹数据库建立方法. 电子与信息学报, 2019, 41(0): 1-7. doi: 10.11999/JEIT180857

  • 图 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下载量:  27
  • 文章访问数:  298
  • HTML全文浏览量:  221
  • 引证文献数: 0
文章相关
  • 通讯作者:  王文杰, wenjie@mail.nwpu.edu.cn
  • 收稿日期:  2018-07-08
  • 录用日期:  2019-05-17
  • 网络出版日期:  2019-05-29
  • 刊出日期:  2019-08-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章