Maison > Article > développement back-end > Explication détaillée de l'algorithme FP-Growth en Python
L'algorithme FP-Growth est un algorithme classique d'exploration de modèles fréquents. C'est un algorithme très efficace pour extraire des collections d'éléments qui apparaissent souvent ensemble à partir d'ensembles de données. Cet article vous présentera en détail le principe et la méthode de mise en œuvre de l'algorithme FP-Growth.
1. Le principe de base de l'algorithme FP-Growth
L'idée de base de l'algorithme FP-Growth est d'établir un FP-Tree (arbre d'ensembles d'éléments fréquents) pour représenter les éléments dans l'ensemble de données Itemsets et exploiter des ensembles d'éléments fréquents à partir de FP-Tree. FP-Tree est une structure de données efficace qui peut exploiter des ensembles d'éléments fréquents sans générer d'ensembles d'éléments fréquents candidats.
FP-Tree contient deux parties : le nœud racine et le nœud d'arbre. Le nœud racine n'a aucune valeur, tandis que les nœuds de l'arborescence incluent le nom d'un élément et le nombre de fois que l'élément apparaît. FP-Tree comprend également des liens pointant vers les mêmes nœuds, ces liens sont appelés « pointeurs de lien ».
Le processus de l'algorithme FP-Growth comprend deux parties : la construction du FP-Tree et l'extraction d'ensembles d'éléments fréquents :
dataset = [['v', 'a', 'p', 'e', 's'], ['b', 'a', 'k', 'e'], ['a', 'p', 'p', 'l', 'e', 's'], ['d', 'i', 'n', 'n', 'e', 'r']]Ensuite, écrivez une fonction pour générer un ensemble d'éléments ordonnés, par exemple :
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_itemsoù , la fonction create_ordered_items est utilisée pour obtenir un ensemble d'éléments ordonné en fonction du nombre d'occurrences de l'élément. Ensuite, écrivez une fonction pour construire le 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)La fonction create_tree est utilisée pour construire le FP-Tree. Enfin, écrivez une fonction pour extraire des ensembles d'éléments fréquents :
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_itemsmine_fp_tree La fonction est utilisée pour extraire des ensembles d'éléments fréquents. 3. RésuméFP-Growth est un algorithme efficace d'exploration de modèles fréquents, en construisant FP-Tree, il peut être utilisé sans générer d'ensembles d'éléments fréquents candidats. ensembles d'éléments fréquents. Python est un langage de programmation très approprié pour implémenter l'algorithme FP-Growth. En utilisant Python, nous pouvons rapidement implémenter cet algorithme et l'utiliser dans la pratique pour exploiter des ensembles d'éléments fréquents. J'espère que cet article pourra vous aider à mieux comprendre les principes et les méthodes de mise en œuvre de l'algorithme FP-Growth.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!