the frequent pattern growth algorithm fpgrowth is a widely used data mining technique for discovering frequent itemsets in large transaction databases it overcomes some of the limitations of traditional methods such as apriori by efficiently constructing the fptree wiki https athena ecs csus edumeiassociationcwfpgrowth html examples https www javatpoint comfpgrowthalgorithmindatamining a node in a frequent pattern tree args name the name of this node numoccur the number of occurrences of the node parentnode the parent node example parent treenodeparent 1 none child treenodechild 2 parent child name child child count 2 create frequent pattern tree args dataset a list of transactions where each transaction is a list of items minsup the minimum support threshold items with support less than this will be pruned default is 1 returns the root of the fptree headertable the header table dictionary with item information example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup fptree treenode null set 1 none lenheadertable 4 headertablea 4 none treenode a 4 treenode null set 1 none headertablee1 doctest normalizewhitespace treenode e 1 treenode b 3 treenode a 4 treenode null set 1 none sortedheadertable a b c e fptree name null set sortedfptree children a b fptree children a name a sortedfptree children a children b c update the fptree with a transaction args items list of items in the transaction intree the current node in the fptree headertable the header table dictionary with item information count the count of the transaction example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup fptree treenode null set 1 none transaction a b e updatetreetransaction fptree headertable 1 fptree treenode null set 1 none fptree children a children b children e children fptree children a children b children e count 2 headertable e 1 name e update the header table with a node link args nodetotest the node to be updated in the header table targetnode the node to link to example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup fptree treenode null set 1 none node1 treenodea 3 none node2 treenodeb 4 none node1 treenode a 3 none node1 updateheadernode1 node2 node1 treenode a 3 none node1 nodelink treenode b 4 none node2 nodelink is none true return the updated node ascend the fptree from a leaf node to its root adding item names to the prefix path args leafnode the leaf node to start ascending from prefixpath a list to store the item as they are ascended example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup path ascendtreefptree children a path path ascending from a leaf node a a find the conditional pattern base for a given base pattern args basepat the base pattern for which to find the conditional pattern base treenode the node in the fptree example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup fptree treenode null set 1 none lenheadertable 4 basepattern frozenset a sortedfindprefixpathbasepattern fptree children a mine the fptree recursively to discover frequent itemsets args intree the fptree to mine headertable the header table dictionary with item information minsup the minimum support threshold prefix a set of items as a prefix for the itemsets being mined freqitemlist a list to store the frequent itemsets example dataset a b c a c a b e a b c e b e minsup 2 fptree headertable createtreedataset minsup fptree treenode null set 1 none frequentitemsets minetreefptree headertable minsup set frequentitemsets expeitm c c a e a e e b a b allexpected in frequentitemsets for expected in expeitm true pass headertablebasepat1 as nodetotest to updateheader a node in a frequent pattern tree args name the name of this node num_occur the number of occurrences of the node parent_node the parent node example parent treenode parent 1 none child treenode child 2 parent child name child child count 2 create frequent pattern tree args data_set a list of transactions where each transaction is a list of items min_sup the minimum support threshold items with support less than this will be pruned default is 1 returns the root of the fp tree header_table the header table dictionary with item information example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup fp_tree treenode null set 1 none len header_table 4 header_table a 4 none treenode a 4 treenode null set 1 none header_table e 1 doctest normalize_whitespace treenode e 1 treenode b 3 treenode a 4 treenode null set 1 none sorted header_table a b c e fp_tree name null set sorted fp_tree children a b fp_tree children a name a sorted fp_tree children a children b c parent is none for the root node update the fp tree with a transaction args items list of items in the transaction in_tree the current node in the fp tree header_table the header table dictionary with item information count the count of the transaction example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup fp_tree treenode null set 1 none transaction a b e update_tree transaction fp_tree header_table 1 fp_tree treenode null set 1 none fp_tree children a children b children e children fp_tree children a children b children e count 2 header_table e 1 name e update the header table with a node link args node_to_test the node to be updated in the header table target_node the node to link to example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup fp_tree treenode null set 1 none node1 treenode a 3 none node2 treenode b 4 none node1 treenode a 3 none node1 update_header node1 node2 node1 treenode a 3 none node1 node_link treenode b 4 none node2 node_link is none true return the updated node ascend the fp tree from a leaf node to its root adding item names to the prefix path args leaf_node the leaf node to start ascending from prefix_path a list to store the item as they are ascended example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup path ascend_tree fp_tree children a path path ascending from a leaf node a a find the conditional pattern base for a given base pattern args base_pat the base pattern for which to find the conditional pattern base tree_node the node in the fp tree example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup fp_tree treenode null set 1 none len header_table 4 base_pattern frozenset a sorted find_prefix_path base_pattern fp_tree children a mine the fp tree recursively to discover frequent itemsets args in_tree the fp tree to mine header_table the header table dictionary with item information min_sup the minimum support threshold pre_fix a set of items as a prefix for the itemsets being mined freq_item_list a list to store the frequent itemsets example data_set a b c a c a b e a b c e b e min_sup 2 fp_tree header_table create_tree data_set min_sup fp_tree treenode null set 1 none frequent_itemsets mine_tree fp_tree header_table min_sup set frequent_itemsets expe_itm c c a e a e e b a b all expected in frequent_itemsets for expected in expe_itm true pass header_table base_pat 1 as node_to_test to update_header
from __future__ import annotations

from dataclasses import dataclass, field


@dataclass
class TreeNode:
    

    name: str
    count: int
    parent: TreeNode | None = None
    children: dict[str, TreeNode] = field(default_factory=dict)
    node_link: TreeNode | None = None

    def __repr__(self) -> str:
        return f"TreeNode({self.name!r}, {self.count!r}, {self.parent!r})"

    def inc(self, num_occur: int) -> None:
        self.count += num_occur

    def disp(self, ind: int = 1) -> None:
        print(f"{'  ' * ind} {self.name}  {self.count}")
        for child in self.children.values():
            child.disp(ind + 1)


def create_tree(data_set: list, min_sup: int = 1) -> tuple[TreeNode, dict]:
    
    header_table: dict = {}
    for trans in data_set:
        for item in trans:
            header_table[item] = header_table.get(item, [0, None])
            header_table[item][0] += 1

    for k in list(header_table):
        if header_table[k][0] < min_sup:
            del header_table[k]

    if not (freq_item_set := set(header_table)):
        return TreeNode("Null Set", 1, None), {}

    for k in header_table:
        header_table[k] = [header_table[k], None]

    fp_tree = TreeNode("Null Set", 1, None)  
    for tran_set in data_set:
        local_d = {
            item: header_table[item][0] for item in tran_set if item in freq_item_set
        }
        if local_d:
            sorted_items = sorted(
                local_d.items(), key=lambda item_info: item_info[1], reverse=True
            )
            ordered_items = [item[0] for item in sorted_items]
            update_tree(ordered_items, fp_tree, header_table, 1)

    return fp_tree, header_table


def update_tree(items: list, in_tree: TreeNode, header_table: dict, count: int) -> None:
    
    if items[0] in in_tree.children:
        in_tree.children[items[0]].inc(count)
    else:
        in_tree.children[items[0]] = TreeNode(items[0], count, in_tree)
        if header_table[items[0]][1] is None:
            header_table[items[0]][1] = in_tree.children[items[0]]
        else:
            update_header(header_table[items[0]][1], in_tree.children[items[0]])
    if len(items) > 1:
        update_tree(items[1:], in_tree.children[items[0]], header_table, count)


def update_header(node_to_test: TreeNode, target_node: TreeNode) -> TreeNode:
    
    while node_to_test.node_link is not None:
        node_to_test = node_to_test.node_link
    if node_to_test.node_link is None:
        node_to_test.node_link = target_node
    
    return node_to_test


def ascend_tree(leaf_node: TreeNode, prefix_path: list[str]) -> None:
    
    if leaf_node.parent is not None:
        prefix_path.append(leaf_node.name)
        ascend_tree(leaf_node.parent, prefix_path)


def find_prefix_path(base_pat: frozenset, tree_node: TreeNode | None) -> dict:
    
    cond_pats: dict = {}
    while tree_node is not None:
        prefix_path: list = []
        ascend_tree(tree_node, prefix_path)
        if len(prefix_path) > 1:
            cond_pats[frozenset(prefix_path[1:])] = tree_node.count
        tree_node = tree_node.node_link
    return cond_pats


def mine_tree(
    in_tree: TreeNode,
    header_table: dict,
    min_sup: int,
    pre_fix: set,
    freq_item_list: list,
) -> None:
    
    sorted_items = sorted(header_table.items(), key=lambda item_info: item_info[1][0])
    big_l = [item[0] for item in sorted_items]
    for base_pat in big_l:
        new_freq_set = pre_fix.copy()
        new_freq_set.add(base_pat)
        freq_item_list.append(new_freq_set)
        cond_patt_bases = find_prefix_path(base_pat, header_table[base_pat][1])
        my_cond_tree, my_head = create_tree(list(cond_patt_bases), min_sup)
        if my_head is not None:
            
            header_table[base_pat][1] = update_header(
                header_table[base_pat][1], my_cond_tree
            )
            mine_tree(my_cond_tree, my_head, min_sup, new_freq_set, freq_item_list)


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    data_set: list[frozenset] = [
        frozenset(["bread", "milk", "cheese"]),
        frozenset(["bread", "milk"]),
        frozenset(["bread", "diapers"]),
        frozenset(["bread", "milk", "diapers"]),
        frozenset(["milk", "diapers"]),
        frozenset(["milk", "cheese"]),
        frozenset(["diapers", "cheese"]),
        frozenset(["bread", "milk", "cheese", "diapers"]),
    ]
    print(f"{len(data_set) = }")
    fp_tree, header_table = create_tree(data_set, min_sup=3)
    print(f"{fp_tree = }")
    print(f"{len(header_table) = }")
    freq_items: list = []
    mine_tree(fp_tree, header_table, 3, set(), freq_items)
    print(f"{freq_items = }")