基于Can树的关联规则增量更新算法改进  

Improved incremental updating algorithm of association rules based on Can-tree

作　　者：胡军[1] 潘皓安 HU Jun;PAN Hao’an(Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065,P.R.China)

机构地区：[1]重庆邮电大学计算智能重庆市重点实验室,重庆400065

出　　处：《重庆邮电大学学报（自然科学版）》2018年第4期558-563,共6页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：国家自然科学基金(61472056;61379114);教育部人文社科规划项目(15XJA630003);重庆市教委科学技术研究项目(KJ1500416);重庆市基础科学与前沿技术研究(cstc2017jcyjAX0406)~~

摘　　要：如何从动态数据中挖掘关联规则是目前知识发现中的一个研究热点。Can树是基于CATS树改进后提出的解决关联规则增量挖掘的一种有效算法,它要求事务中的每个项按照某种特定顺序进行排序后再构建Can树,其顺序一般采用字典序、字母序等。然而,Can树所使用的排序方法有可能使得Can树的规模过大,从而使得算法效率较低。针对该问题,在现有Can树挖掘算法的基础上,使用数据量排序替代现有排序方法,提出了一种基于数据量排序的Can树,并基于新的Can树对原有Can树的建树和挖掘方法进行优化。该方法可以有效减小Can树的规模,实现频繁项集挖掘在空间效率和时间效率上的优化。实验结果表明,该方法在空间效率和时间效率上好于现有的Can树算法,同时具有较好的稳定性。How to mine association rule from dynamic data is one of the hottest topics in knowledge acquisition.Can-tree,which is based on CATS tree,is an effective algorithm for incremental mining association rule.It requires that all items should be in specific order before building Can-tree,like lexicographic order or alphabetical order.However,the current used ordering method may cause the size of Can-tree too large,thus decreasing the efficiency of the algorithm.Aiming at this problem,this paper proposes a new Can-tree,which sorts items by data size instead of the current ordering methods.Meanwhile,the tree building and mining methods are optimized based on the proposed Can-tree.This method can effectively minimize the size of Can-tree,and improve the efficiency of mining frequent itemset in space and time.The experimental results show that this method outperforms the existing Can-tree algorithm in space efficiency,time efficiency,and stability.

关 键 词：关联规则 增量更新 Can树 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]