一种基于前缀树的频繁模式挖掘算法

挖掘频繁模式是许多数据挖掘任务的关键步骤。基于FP-Tree的挖掘算法由于无须生成候进项集效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、而且在挖掘过程中需要递归地创建大量的条件FP-Tree,时空效率不高。因此,本文提出一种基于前缀树的新算法。该算法通过引入一种新结构—前缀树(Prefix Tree)用来压缩存放数据所相关信息,并通过调整前缀树中节点信息和节点键直接在Prefix Tree上采用深度优先的策略挖掘频繁模式,而不需要任何附加的数据结构,从而大大提高了挖掘效率。

A Mining Algorithm for Frequent Patterns Based on Prefix Tree

Mining frequent patterns is a key problem in data mining research. Although mining based on FP-Tre achieves better performance and efficiency than Apriori-like algorithms because of avoiding costly candidate genera tion, it still suffers from creating conditional FP-Tree separately and recursively during the mining process. In this pa per, we propose a new method PTM that designs a new structure called Prefix Tree, which stores all of the informa tion in a highly compact form. PTM mines frequent patterns in depth-first order and directly in Prefix Tree by adjust ing node information and node links without using any additional data structures. Thus, it can improve performanc greatly.