一种基于FUP的TD-FP-Tree并行快速更新算法  

A Parallel Fast Update TD-FP-Tree Algorithm Based on FUP

作　　者：周爱武[1] 王琰[1] 陈宝楼[1] 

机构地区：[1]安徽大学计算机科学与技术学院,安徽合肥230039

出　　处：《计算机技术与发展》2013年第4期91-95,共5页Computer Technology and Development

基　　金：安徽省教育科研重点项目(KJ2009A57)

摘　　要：TD-FP-Growth是对经典关联规则挖掘算法FP-Growth算法的改进,它采用新的数据结构TD-FP-Tree。人们已经基于Apriori和FP-Growth算法提出了多种关联规则增量挖掘算法。文中讨论了在基于TD-FP-Tree的结构上如何进行增量挖掘,对批量挖掘算法的瓶颈进行分析,指出加快更新速度的策略。文中基于FUP思想提出了TD-FP-Tree的快速更新算法,重点研究了当有单个项在新增事务加入后由非频繁变为频繁时TD-FP-Tree的处理情况。通过将项分类处理降低更新时间,并部分采用并行处理进一步提高效率。实验表明,文中提出的算法不仅可以快速更新TD-FP-Tree,而且在同基于FP-Tree结构的增量挖掘对比中也有更好的表现。TD-FP-Growth is an improvement to the classical algorithm for mining association rules which called FP-Growth, and it uses a new data structure TD-FP-Tree. Many incremental mining algorithm of association rules have been proposed based on the Apriori and FP-Growth. It discusses how to do incremental mining based on the structure of TD-FP-Tree, analyzes the bottleneck of batch mining and points out the strategy of speeding up update rate. It proposes the fast update algorithm of TD-FP-Tree based on the thought of FUP, and puts the focus on researching how to handle the TD-FP-Tree with the situation that a single item becomes frequent by non-frequent when new transactions are added. It processes items classified to reduce the updated execution time, and adopts parallel processing partially to further improve efficiency. Experiments show that the proposed algorithm not only can quickly update TD-FP-Tree, but also has a better performance on the incremental mining compared with the FP-Tree structure.

关 键 词：关联规则 TD-FP-Growth 增量挖掘 FUP TD-FP-Tree更新 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]