• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

J4 ›› 2016, Vol. 38 ›› Issue (05): 1039-1045.

• 论文 • 上一篇    下一篇

一种基于倒排索引树的增量更新关联挖掘算法

徐春,李广原,王玄,田换   

  1. (广西师范学院计算机与信息工程学院,广西 南宁 530001)
  • 收稿日期:2015-12-13 修回日期:2016-02-14 出版日期:2016-05-25 发布日期:2016-05-25
  • 基金资助:

    广西自然科学基金(2014GXNSFAA118388);广西高校科研项目(YB2014237);广西混杂计算与集成电路设计重点实验室开放课题(2012HCIC03)

An  incremental updating association rule mining
algorithm based on inverted index tree     

XU Chun,LI Guangyuan,WANG Xuan,TIAN Huan   

  1. (School of Computer and Information Engineering,Guangxi Normal University,Nanning  530001,China)
  • Received:2015-12-13 Revised:2016-02-14 Online:2016-05-25 Published:2016-05-25

摘要:

增量更新关联规则挖掘主要解决事务数据库中交易记录不断更新和最小支持度发生变化时关联规则的维护问题。针对目前诸多增量更新关联规则挖掘算法存在效率低、计算成本高、规则难以维护等问题,提出一种基于倒排索引树的增量更新关联挖掘算法。该算法有效地将倒排索引技术与树型结构相结合,使得交易数据库中的数据不断更新和最小支持度随应用环境不同而不断改变时,以实现无需扫描原始交易数据库和不产生候选项集的情况下生成频繁项集。实验结果表明,该算法只需占用较小的存储空间、且检索项集的效率较高,能高效地解决增量更新关联规则难以维护的问题。

关键词: 增量更新挖掘, 倒排索引, 倒排索引树, 频繁项集, 关联规则

Abstract:

The primary mission of incremental updating association rule mining is to solve the problem of the maintenance of the association rules, when transaction records are updated constantly and minimum support is changed in the online database. Given that many incremental update association rule mining algorithms have many problems, such as low efficiency and high computation cost, as well as difficult maintenance of the association rules, we propose an efficient algorithm for incremental updating association mining based on inverted index tree. The algorithm effectively combines the inverted index and the tree structure, so that the data in the transaction database is updated constantly with time and the minimum support degree is changed continuously with the application environment. Frequent item sets are generated without scanning the original transaction database and without generating candidate item sets. Experimental results show that the proposed algorithm can effectively solve the problem of incremental updating association rules with less memory space and higher efficiency.

Key words: incremental updating mining;inverted index;inverted index tree;frequent item sets;association rules