machine-learningrecursiondata-miningfpgrowth

Recursion in FP-Growth Algorithm


I am trying to implement FP-Growth (frequent pattern mining) algorithm in Java. I have built the tree, but have difficulties with conditional FP tree construction; I do not understand what recursive function should do. Given a list of frequent items (in increasing order of frequency counts) - a header, and a tree (list of Node class instances) what steps should the function take?

image retrieved from https://www.google.com/url?sa=i&source=images&cd=&cad=rja&uact=8&ved=2ahUKEwiT4Oeeg53lAhWPhOAKHUdSAmkQjRx6BAgBEAQ&url=https%3A%2F%2Fwww.researchgate.net%2Ffigure%2FPseudocode-FP-tree-Purba-30_fig2_330783065&psig=AOvVaw3fyRRKroFZwnASsE-vuMZy&ust=1571186297476542

I have hard time understanding this pseudocode above. Are alpha and Betha nodes in the Tree, and what do generate and construct functions do?

I can do FP-Growth by hand, but find the implementation extremely confusing. If that could help, I can share my code for FP-Tree generation.


Solution

    1. alpha is the prefix that lead to this specific prefix tree
    2. beta is the new prefix (of the tree to be constructed)
    3. the generate line means something like: add to result set the pattern beta with support anItem.support
    4. the construct function creates the new patterns from which the new tree is created

    An example of the construct function (bottom up way) would be something like:

    function construct(Tree, anItem)   
        conditional_pattern_base = empty list
        in Tree find all nodes with tag = anItem
        for each node found:
           support = node.support
           conditional_pattern = empty list
           while node.parent != root_node
                conditional_pattern.append(node.parent)
                node = node.parent
           conditional_pattern_base.append( (conditional_pattern, support))
        return conditional_pattern_base