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

摘要

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 partial-ly 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.