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 :

1. Construction du FP-Tree :
# 🎜🎜#

Pour chaque transaction, supprimez les éléments non fréquents et triez-les selon le support des éléments fréquents pour obtenir un ensemble d'éléments fréquents.

Parcourez chaque transaction et insérez l'ensemble d'éléments fréquents de chaque transaction dans le FP-Tree dans l'ordre d'apparition. Si le nœud existe déjà, augmentez son nombre. S'il n'existe pas, insérez un nouveau. un.

Exploitation d'ensembles d'objets fréquents :

Les méthodes d'extraction d'ensembles d'objets fréquents de FP-Tree incluent :

Démarrage en bas du FP-Tree, recherchez la bibliothèque de modèles conditionnels pour chaque ensemble d'éléments. La bibliothèque de modèles conditionnels contient toutes les transactions qui contiennent cet ensemble d'éléments. Ensuite, un nouveau FP-Tree est construit de manière récursive pour la bibliothèque de modèles conditionnels, et les ensembles d'éléments fréquents dans l'arborescence sont recherchés.

Dans le nouveau FP-Tree, chaque élément fréquent est trié en fonction de son support, un ensemble d'éléments candidats est construit et extrait de manière récursive. Répétez le processus ci-dessus jusqu'à ce que tous les ensembles d'éléments fréquents soient trouvés.

2. Implémentation de l'algorithme FP-Growth

L'implémentation de l'algorithme FP-Growth peut utiliser le langage de programmation Python. Ce qui suit est un exemple simple pour démontrer la mise en œuvre de l'algorithme FP-Growth.

Tout d'abord, définissez un ensemble de données, par exemple :

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_items

où , 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_items

mine_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!