FPgrowth - Frequent Item Set Mining

Download

Description

A program to find frequent item sets (also closed and maximal) with the fpgrowth algorithm (frequent pattern growth, Han et al 2000), which represents the transaction database as a prefix tree which is enhanced with pointers that organize the nodes into lists referring to the same item. The search is carried out by projecting the prefix tree, working recursively on the result, and pruning the original tree. Since version 1.2 this implementation also contains the alpha-pruning of the FP-Bonsai techniques.

A paper that describes this implementation:

• An Implementation of the FP-growth Algorithm
  Christian Borgelt
  Workshop Open Source Data Mining Software (OSDM'05, Chicago, IL), 1-5.
  ACM Press, New York, NY, USA 2005.
  fpgrowth.pdf (152 kb) fpgrowth.ps.gz (116 kb) (5 pages)

Some other references:

• Mining Frequent Patterns without Candidate Generation
  J. Han, H. Pei, and Y. Yin
  Proc. Conf. on the Management of Data (SIGMOD'00, Dallas, TX), 1-12
  ACM Press, New York, NY, USA 2000
• Efficiently Using Prefix-trees in Mining Frequent Itemsets
  G. Grahne and J. Zhu
  Proc. Workshop Frequent Item Set Mining Implementations (FIMI 2003, Melbourne, FL)
  CEUR Workshop Proceedings 90, Aachen, Germany 2003
• Reducing the Main Memory Consumptions of fpmax* and fpclose
  G. Grahne and J. Zhu
  Proc. Workshop Frequent Item Set Mining Implementations (FIMI 2004, Brighton, UK)
  CEUR Workshop Proceedings 126, Aachen, Germany 2004
• nonordfp: An FP-growth Variation without Rebuilding the FP-Tree
  B. Rász
  Proc. Workshop Frequent Item Set Mining Implementations (FIMI 2004, Brighton, UK)
  CEUR Workshop Proceedings 126, Aachen, Germany 2004

More information about frequent item set mining, implementations of other algorithms as well as test data sets can be found at the Frequent Itemset Mining Implementations Repository.