fp-skeleton-partB.py

fp-skeleton-partB.py

def fp_growth(transaction_db, min_sup, fp_list, prefix = []):
    
    ####### STEP A: CONCATENATE #######
    # Get one itemsets which meet minimum support
    one_itemset_dict = get_one_itemsets(transaction_db, min_sup)
    
    # Concanenate frequent patterns with prefix
    freq_patterns = []
    for key,val in one_itemset_dict.items():
        pattern = prefix + [key]
        freq_patterns.append((pattern,val))
    
    for pat in freq_patterns:
        if pat not in fp_list:
            fp_list.append(pat[0])
    
    
    ####### STEP B: GENERATE FP-TREE #######
    # Initialize node link dictionary
    node_link_dict = {item:[] for item in one_itemset_dict.keys()}

    # Create tree data structure as a list of dictionary nodes
    # Insert root node as {name:None, count:None, parent: None}
    fp_tree = [{'name':"Root", 'count':None, 'parent': None}]
    
    root_node = fp_tree[0]
    for t_tup in transaction_db.list_items:
        # Sort t according to 1-itemset support counts
        # This is required only at the root node
        if prefix == []:
            t = sort_transaction(t_tup[0], one_itemset_dict)
        else:
            t = [i for i in t_tup[0] if i in one_itemset_dict.keys()]
        
        if len(t) > 1:
            insert_tree(t[0], t[1:], root_node, fp_tree, node_link_dict, t_tup[1])
    
    
    # Step C code to be filled here
    
    
    if cpb_db.shape[0] > 0:
        fp_growth(cpb_db, min_sup, fp_list, prefix + [item])