Home > Article > Backend Development > Detailed explanation of FP-Growth algorithm in Python
FP-Growth algorithm is a classic frequent pattern mining algorithm. It is a very efficient algorithm for mining collections of items that often appear together from data sets. This article will introduce you to the principle and implementation method of FP-Growth algorithm in detail.
1. Basic Principle of FP-Growth Algorithm
The basic idea of FP-Growth algorithm is to establish an FP-Tree (frequent itemset tree) to represent the frequent itemsets in the data set, and Mining frequent itemsets from FP-Tree. FP-Tree is an efficient data structure that can mine frequent itemsets without generating candidate frequent itemsets.
FP-Tree contains two parts: root node and tree node. The root node has no value, whereas the tree nodes include the name of an item and the number of times the item occurs. FP-Tree also includes links pointing to the same nodes, these links are called "link pointers".
The process of FP-Growth algorithm includes two parts: building FP-Tree and mining frequent itemsets:
For For each transaction, non-frequent items are deleted and sorted according to the support of frequent items to obtain a frequent itemset.
Traverse each transaction, and insert the frequent itemset of each transaction into the FP-Tree in the order of appearance. If the node already exists, increase its count. If it does not exist, insert a new node. .
The methods of mining frequent itemsets from FP-Tree include:
Start from the bottom of FP-Tree , find the conditional pattern library of each item set, and the conditional pattern library contains all transactions that contain the item set. Then, a new FP-Tree is recursively constructed for the conditional pattern library, and frequent itemsets in the tree are searched.
In the new FP-Tree, each frequent item is sorted according to its support, a set of candidates is constructed, and mined recursively. Repeat the above process until all frequent itemsets are found.
2. Implementation of FP-Growth algorithm
The FP-Growth algorithm can be implemented using the Python programming language. The following is a simple example to demonstrate the implementation of the FP-Growth algorithm.
First, define a data set, for example:
dataset = [['v', 'a', 'p', 'e', 's'], ['b', 'a', 'k', 'e'], ['a', 'p', 'p', 'l', 'e', 's'], ['d', 'i', 'n', 'n', 'e', 'r']]
Then, write a function to generate an ordered item set, for example:
def create_ordered_items(dataset): # 遍历数据集,统计每个项出现的次数 item_dict = {} for trans in dataset: for item in trans: if item not in item_dict: item_dict[item] = 1 else: item_dict[item] += 1 # 生成有序项集 ordered_items = [v[0] for v in sorted(item_dict.items(), key=lambda x: x[1], reverse=True)] return ordered_items
Among them, the create_ordered_items function is used to follow Get the ordered itemset by the number of occurrences of the item.
Next, write a function to build FP-Tree:
class TreeNode: def __init__(self, name, count, parent): self.name = name self.count = count self.parent = parent self.children = {} self.node_link = None def increase_count(self, count): self.count += count def create_tree(dataset, min_support): # 生成有序项集 ordered_items = create_ordered_items(dataset) # 建立根节点 root_node = TreeNode('Null Set', 0, None) # 建立FP-Tree head_table = {} for trans in dataset: # 过滤非频繁项 filtered_items = [item for item in trans if item in ordered_items] # 对每个事务中的项集按频繁项的支持度从大到小排序 filtered_items.sort(key=lambda x: ordered_items.index(x)) # 插入到FP-Tree中 insert_tree(filtered_items, root_node, head_table) return root_node, head_table def insert_tree(items, node, head_table): if items[0] in node.children: # 如果节点已存在,则增加其计数 node.children[items[0]].increase_count(1) else: # 如果节点不存在,则插入新的节点 new_node = TreeNode(items[0], 1, node) node.children[items[0]] = new_node # 更新链表中的指针 if head_table.get(items[0], None) is None: head_table[items[0]] = new_node else: current_node = head_table[items[0]] while current_node.node_link is not None: current_node = current_node.node_link current_node.node_link = new_node if len(items) > 1: # 对剩余的项进行插入 insert_tree(items[1:], node.children[items[0]], head_table)
The create_tree function is used to build FP-Tree.
Finally, write a function to mine frequent itemsets:
def find_freq_items(head_table, prefix, freq_items, min_support): # 对头指针表中的每个项按照出现的次数从小到大排序 sorted_items = [v[0] for v in sorted(head_table.items(), key=lambda x: x[1].count)] for item in sorted_items: # 将前缀加上该项,得到新的频繁项 freq_set = prefix + [item] freq_count = head_table[item].count freq_items.append((freq_set, freq_count)) # 构建该项的条件模式库 cond_pat_base = get_cond_pat_base(head_table[item]) # 递归地构建新的FP-Tree,并寻找频繁项集 sub_head_table, sub_freq_items = create_tree(cond_pat_base, min_support) if sub_head_table is not None: find_freq_items(sub_head_table, freq_set, freq_items, min_support) def get_cond_pat_base(tree_node): cond_pat_base = [] while tree_node is not None: trans = [] curr = tree_node.parent while curr.parent is not None: trans.append(curr.name) curr = curr.parent cond_pat_base.append(trans) tree_node = tree_node.node_link return cond_pat_base def mine_fp_tree(dataset, min_support): freq_items = [] # 构建FP-Tree root_node, head_table = create_tree(dataset, min_support) # 挖掘频繁项集 find_freq_items(head_table, [], freq_items, min_support) return freq_items
The mine_fp_tree function is used to mine frequent itemsets.
3. Summary
FP-Growth algorithm is an efficient frequent pattern mining algorithm. By constructing FP-Tree, frequent items can be mined without generating candidate frequent item sets. Collection excavation. Python is a programming language that is very suitable for implementing the FP-Growth algorithm. By using Python, we can quickly implement this algorithm and use it in practice to mine frequent itemsets. I hope this article can help you better understand the principles and implementation methods of the FP-Growth algorithm.
The above is the detailed content of Detailed explanation of FP-Growth algorithm in Python. For more information, please follow other related articles on the PHP Chinese website!