machine_learning.frequent_pattern_growth
========================================

.. py:module:: machine_learning.frequent_pattern_growth

.. autoapi-nested-parse::

   The Frequent Pattern Growth algorithm (FP-Growth) 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 FP-Tree

   WIKI: https://athena.ecs.csus.edu/~mei/associationcw/FpGrowth.html

   Examples: https://www.javatpoint.com/fp-growth-algorithm-in-data-mining



Attributes
----------

.. autoapisummary::

   machine_learning.frequent_pattern_growth.data_set


Classes
-------

.. autoapisummary::

   machine_learning.frequent_pattern_growth.TreeNode


Functions
---------

.. autoapisummary::

   machine_learning.frequent_pattern_growth.ascend_tree
   machine_learning.frequent_pattern_growth.create_tree
   machine_learning.frequent_pattern_growth.find_prefix_path
   machine_learning.frequent_pattern_growth.mine_tree
   machine_learning.frequent_pattern_growth.update_header
   machine_learning.frequent_pattern_growth.update_tree


Module Contents
---------------

.. py:class:: TreeNode

   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


   .. py:method:: __repr__() -> str


   .. py:method:: disp(ind: int = 1) -> None


   .. py:method:: inc(num_occur: int) -> None


   .. py:attribute:: children
      :type:  dict[str, TreeNode]


   .. py:attribute:: count
      :type:  int


   .. py:attribute:: name
      :type:  str


   .. py:attribute:: node_link
      :type:  TreeNode | None
      :value: None



   .. py:attribute:: parent
      :type:  TreeNode | None
      :value: None



.. py:function:: ascend_tree(leaf_node: TreeNode, prefix_path: list[str]) -> None

   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']


.. py:function:: create_tree(data_set: list, min_sup: int = 1) -> tuple[TreeNode, dict]

   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']


.. py:function:: find_prefix_path(base_pat: frozenset, tree_node: TreeNode | None) -> dict

   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']))
   []


.. py:function:: mine_tree(in_tree: TreeNode, header_table: dict, min_sup: int, pre_fix: set, freq_item_list: list) -> None

   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


.. py:function:: update_header(node_to_test: TreeNode, target_node: TreeNode) -> TreeNode

   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


.. py:function:: update_tree(items: list, in_tree: TreeNode, header_table: dict, count: int) -> None

   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'


.. py:data:: data_set
   :type:  list[frozenset]