https stackoverflow com questions 58385765 recursion-in-fp-growth-algorithm

Question

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? 

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. Thanks in advance.

Answer 1

The create line indicates something like: alpha is the prefix that leads to this specific prefix tree
 beta is the new prefix (of the tree to be constructed) 
add to result is what the generate line means. support anItem by setting the pattern beta.
The construct function generates new patterns from which a new tree can be generated.

An example of the construct function (from the bottom up) might be:

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