A Novel Algorithm for Mining Frequent Patterns Directly in Trans-Tree
一种直接在Trans-树中挖掘频繁模式的新算法

Frequent pattern mining plays an essential role in many important data mining tasks. FP-growth is a very efficient algorithm for frequent pattern mining. However, it still suffers from creating conditional FP-tree separately and recursively during the mining process. In this paper, we propose a new algorithm, called Least-Item-First Pattern Growth (LIFPG), for mining frequent patterns. LIFPG mines frequent patterns directly in Trans-tree without using any additional data structures. The key idea is that least items are always considered first when the current pattern growth. By this way, conditional sub-tree can be created directly in Trans-tree by adjusting node-links and recounting counts of some nodes. Experiments show that, in comparison with FP-Growth, our algorithm is about four times faster and saves half of memory; it also has good time and space scalability with the number of transactions, and has an excellent performance in dense dataset mining as well.