FPGrowth

FPGrowth is a data mining algorithm for frequent pattern mining. It finds frequent itemsets in a transaction database without generating candidate itemsets, addressing the scalability limitations of Apriori on large datasets.

FPGrowth builds a compact data structure called the FP-tree (Frequent Pattern tree). The database is scanned to identify frequent items and their supports. Each transaction is sorted by decreasing frequency of items and inserted into the FP-tree, so common prefixes are shared. A header table links to the first node of each item, and each node stores the item, count, and links to other nodes of the same item.

Mining uses conditional pattern bases and conditional FP-trees. For a frequent item, a conditional base is formed from paths ending with that item, from which a conditional FP-tree is built. The algorithm recursively mines these trees to generate frequent itemsets that include the item. This avoids enumerating non-minimal candidates.

Advantages and limitations: FP-growth is typically faster and more scalable than Apriori on large, repetitive datasets because it avoids candidate generation and uses tree-based compression. Its performance depends on the data's compressibility. Memory usage can be high for very large databases.

History and implementations: FP-growth was introduced by Han, Pei, and Yin in 2000 as an alternative to Apriori. It has been implemented in several data mining libraries and tools, including SPMF and Weka.