Machine Learning in Java - Second Edition

FP-Growth algorithm

FP-Growth (where FP is frequent patterns) represents the transaction database as a suffix tree. First, the algorithm counts the occurrence of items in the dataset. In the second pass, it builds a suffix tree, an ordered tree data structure commonly used to store a string. An example of a suffix tree based on the previous example is shown in the following diagram:

If many transactions share the most frequent items, the suffix tree provides high compression close to the tree root. Large itemsets are grown directly, instead of generating candidate items and testing them against the entire database. Growth starts at the bottom ...