Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (4): 997-1001.DOI: 10.11772/j.issn.1001-9081.2016.04.0997

Previous Articles     Next Articles

Improved frequent itemset mining algorithm based on interval list

XU Yongxiu1, LIU Xumin1, XU Weixiang2   

  1. 1. College of Information Engineering, Capital Normal University, Beijing 100048, China;
    2. College of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China
  • Received:2015-09-25 Revised:2015-11-23 Online:2016-04-10 Published:2016-04-08
  • Supported by:
    This work is supported by the National Natural Science Foundation of China (61272029).

基于间隔链表改进的频繁项集挖掘算法

徐永秀1, 刘旭敏1, 徐维祥2   

  1. 1. 首都师范大学 信息工程学院, 北京 100048;
    2. 北京交通大学 交通运输学院, 北京 100044
  • 通讯作者: 徐永秀
  • 作者简介:徐永秀(1991-),女,山东潍坊人,硕士研究生,主要研究方向:数据挖掘; 刘旭敏(1956-),女,辽宁锦州人,教授,博士,主要研究方向:计算机辅助几何设计、图形图像处理、数据挖掘; 徐维祥(1956-),男,辽宁锦州人,教授,博士,主要研究方向:数据挖掘、交通运输系统分析集成、云计算。
  • 基金资助:
    国家自然科学基金资助项目(61272029)。

Abstract: Focusing on the problem that PrePost algorithm needs to build complex Pre-order and Post-order Code tree (PPC-tree) and Node list (N-list), an improved frequent itemset mining algorithm based on the Interval list (I-list) was proposed. Firstly, data storage structure with more compression compared to Frequent Pattern tree (FP-tree), called Interval FP-tree (IFP-tree), was adopted, which mined frequent itemsets without iteratively establishing conditional tree. Secondly, the more concise method called I-list was used to replace the complex N-list in PrePost so as to improve mining speed. Finally, in the case of single branch path, some frequent itemsets were directly obtained by the method of combination. The experimental results prove the correctness of the proposed algorithm by getting the same results for the same dataset under same minimum supports, the proposed algorithm is superior to PrePost algorithm by about 10 percent in terms of time and space which has a good application in sparse database or intensive database.

Key words: data mining, association rule, frequent itemset, Frequent Pattern tree (FP-tree), Interval list (I-list)

摘要: 针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。

关键词: 数据挖掘, 关联规则, 频繁项集, 频繁模式树, 间隔链表

CLC Number: