Please use this identifier to cite or link to this item:
標題: An improved frequent pattern growth method for mining association rules
作者: Lin, Ke-Chung
Liao, I-En
Chen, Zhi-Sheng
關鍵字: FP-tree;Frequent itemset mining;Association rules
Project: Expert Systems with Applications, Volume 38, Issue 5, Page(s) 5154-5161.
Many algorithms have been proposed to efficiently mine association rules. One of the most important approaches is FP-growth. Without candidate generation, FP-growth proposes an algorithm to compress information needed for mining frequent itemsets in FP-tree and recursively constructs FP-trees to find all frequent itemsets. Performance results have demonstrated that the FP-growth method performs extremely well. In this paper, we propose the IFP-growth (improved FP-growth) algorithm to improve the performance of FP-growth. There are three major features of IFP-growth. First, it employs an address-table structure to lower the complexity of forming the entire FP-tree. Second, it uses a new structure called FP-tree(+) to reduce the need for building conditional FP-trees recursively. Third, by using address-table and FP-tree the proposed algorithm has less memory requirement and better performance in comparison with FP-tree based algorithms. The experimental results show that the IFP-growth requires relatively little memory space during the mining process. Even when the minimum support is low, the space needed by IFP-growth is about one half of that of FP-growth and about one fourth of that of nonordfp algorithm. As to the execution time, our method outperforms FP-growth by one to 300 times under different minimum supports. The proposed algorithm also outperforms nonordfp algorithm in most cases. As a result, IFP-growth is very suitable for high performance applications. (C) 2010 Elsevier Ltd. All rights reserved.
ISSN: 0957-4174
DOI: 10.1016/j.eswa.2010.10.047
Appears in Collections:資訊科學與工程學系所

Show full item record

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.