Editing Association rule learning (section)

=== FP-growth algorithm ===

FP stands for frequent pattern.<ref>{{cite book|last1=Han|title=Proceedings of the 2000 ACM SIGMOD international conference on Management of data |chapter=Mining frequent patterns without candidate generation |date=2000|volume=SIGMOD '00|pages=1–12|doi=10.1145/342009.335372|isbn=978-1581132175|citeseerx=10.1.1.40.4436|s2cid=6059661}}</ref>

In the first pass, the algorithm counts the occurrences of items (attribute-value pairs) in the dataset of transactions, and stores these counts in a 'header table'. In the second pass, it builds the FP-tree structure by inserting transactions into a [[trie]].

Items in each transaction have to be sorted by descending order of their frequency in the dataset before being inserted so that the tree can be processed quickly.
Items in each transaction that do not meet the minimum support requirement are discarded.
If many transactions share most frequent items, the FP-tree provides high compression close to tree root.

Recursive processing of this compressed version of the main dataset grows frequent item sets directly, instead of generating candidate items and testing them against the entire database (as in the apriori algorithm).

Growth begins from the bottom of the header table i.e. the item with the smallest support by finding all sorted transactions that end in that item. Call this item <math>I</math>.

A new conditional tree is created which is the original FP-tree projected onto <math>I</math>. The supports of all nodes in the projected tree are re-counted with each node getting the sum of its children counts. Nodes (and hence subtrees) that do not meet the minimum support are pruned. Recursive growth ends when no individual items conditional on <math>I</math> meet the minimum support threshold. The resulting paths from root to <math>I</math> will be frequent itemsets. After this step, processing continues with the next least-supported header item of the original FP-tree.

Once the recursive process has completed, all frequent item sets will have been found, and association rule creation begins.<ref>Witten, Frank, Hall: Data mining practical machine learning tools and techniques, 3rd edition{{page needed|date=January 2019}}</ref>