Aprenda Construção de Árvores de Padrões Frequentes com o Algoritmo FP-Growth | Mineração de Regras de Alto Desempenho e Otimização de Escala

Deslize para mostrar o menu

Visão Geral do FP-Growth

FP-Growth é um algoritmo de alto desempenho projetado para mineração de conjuntos frequentes de itens em grandes conjuntos de dados transacionais. Diferente do Apriori, que gera conjuntos candidatos de itens e realiza múltiplas varreduras no banco de dados, o FP-Growth constrói uma estrutura de dados compacta chamada FP-Tree (Árvore de Padrões Frequentes), permitindo minerar padrões frequentes sem a geração de candidatos. Isso resulta em melhorias significativas de velocidade e uso de memória, especialmente para conjuntos de dados com muitos padrões frequentes.

Estrutura da Árvore

A estrutura da FP-Tree comprime todo o conjunto de transações em um formato de árvore de prefixos. Cada transação é processada ordenando seus itens em ordem decrescente de frequência e, em seguida, inserindo-os na árvore, compartilhando prefixos comuns com caminhos já existentes. O nó raiz é um nó nulo que serve como ponto de entrada, e cada nó na árvore representa um item juntamente com uma contagem de quantas transações compartilham aquele prefixo até aquele ponto.

Encadeamento de Nós

Para facilitar a mineração eficiente, todos os nós que representam o mesmo item são conectados por meio de uma lista encadeada, formando o chamado header table. Isso permite percorrer rapidamente todas as ocorrências de um determinado item na árvore. Cada entrada na header table aponta para o primeiro nó na árvore para aquele item, e cada nó contém um link para o próximo nó com o mesmo nome de item.

Mineração de Padrões

A mineração de padrões frequentes a partir da FP-Tree envolve dois passos principais. Primeiro, percorre-se a árvore de baixo para cima, seguindo os links para cada item na header table para coletar todos os caminhos de prefixo que levam a esse item. Em seguida, constroem-se FP-Trees condicionais para cada item e realiza-se a mineração recursiva dessas árvores para extrair todos os conjuntos frequentes de itens. Esse processo recursivo continua até que não haja mais padrões frequentes a serem encontrados.

Exemplo: Construção passo a passo da FP-Tree

Vamos acompanhar a construção exata passo a passo usando os exemplos de transações, assumindo um Limite Mínimo de Suporte de 2 (ou seja, os itens devem aparecer pelo menos duas vezes para serem considerados).

Suponha que você tenha as seguintes transações:

- Transaction 1: A, B, D;
- Transaction 2: B, C, E;
- Transaction 3: A, B, C, E;
- Transaction 4: B, E.

Passo 1: Escanear o Banco de Dados e Ordenar por Frequência

Primeiro, o algoritmo lê todo o conjunto de dados para contar quantas vezes cada item individual aparece. Qualquer item que fique abaixo do limite mínimo de suporte é descartado. Em seguida, uma ordem global de classificação é estabelecida do item mais frequente para o menos frequente.

Contagem Global de Itens:

B aparece 4 vezes

E aparece 3 vezes

A aparece 2 vezes

C aparece 2 vezes

D aparece 1 vez (Descartado porque está abaixo do Suporte Mínimo de 2)

Regra Final de Ordenação: Agora, toda transação será filtrada e reorganizada para seguir estritamente esta ordem decrescente de frequência:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Passo 2: Reordenar Cada Transação

Antes de inserir os itens na árvore, o algoritmo reescreve cada transação. Ele remove o item infrequente (D) e reorganiza os itens restantes para corresponder à nova regra global de ordenação.

- Transaction 1: A, B, D torna-se B, A
- Transaction 2: B, C, E torna-se B, E, C
- Transaction 3: A, B, C, E torna-se B, E, A, C
- Transaction 4: B, E torna-se B, E

Passo 3: Inserir Caminhos na FP-Tree

Toda FP-Tree começa com um nó raiz vazio chamado de Null Root Node. Agora inserimos as transações reordenadas na árvore uma a uma, incrementando os contadores quando os caminhos se sobrepõem e ramificando quando divergem.

Inserir Transação 1 {B, A}: a árvore cria um novo ramo diretamente a partir da raiz.

Inserir Transação 2 {B, E, C}: o algoritmo começa na raiz e verifica o primeiro item, B. Como B já existe como filho da raiz, o caminho se sobrepõe! O algoritmo move-se para B e incrementa seu contador para 2. O próximo item é E. Como B ainda não possui um filho chamado E, a árvore se divide aqui e cria um novo sub-ramo para E, seguido de C.

Inserir Transação 3 {B, E, A, C}: começando pela raiz, o caminho passa por B (contador incrementa para 3), depois desce para o nó E existente (contador incrementa para 2). O próximo item é A. Como E não possui um filho chamado A, a árvore cria uma nova divisão sob E para (A:1) -> (C:1).

Inserir Transação 4 {B, E}: o algoritmo segue pelo caminho de prefixo mais popular e B incrementa para 4, E incrementa para 3. A transação termina aqui, então nenhum novo nó é adicionado.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Este exemplo de código mostra como construir uma FP-Tree a partir de uma lista de transações usando Python. Veja uma explicação detalhada de cada etapa:

Contagem das frequências dos itens:
- O código utiliza a classe Counter do módulo collections para contar quantas vezes cada item aparece em todas as transações;
- Isso ajuda a identificar quais itens são frequentes o suficiente para serem incluídos na árvore.
Remoção de itens infrequentes:
- Os itens que não atingem o limite mínimo de suporte são filtrados;
- O conjunto freq_items contém apenas os itens que aparecem pelo menos o número de vezes especificado por min_support.
Ordenação das transações por frequência:
- Cada transação é filtrada para manter apenas os itens frequentes;
- Os itens são então ordenados em ordem decrescente de frequência global (e alfabeticamente para desempate);
- A ordenação maximiza o compartilhamento de prefixos na FP-Tree, tornando a árvore mais compacta.
Definição da classe de nó da FP-Tree:
- A classe FPTreeNode representa cada nó da árvore;
- Cada nó armazena o nome do item, o contador, um ponteiro para o nó pai, um dicionário de filhos e um link para o próximo nó com o mesmo nome de item (para percorrer a tabela de cabeçalho).
Construção da FP-Tree e da tabela de cabeçalho:
- A função build_fp_tree cria a árvore inserindo cada transação ordenada;
- A partir da raiz, para cada item em uma transação, a função verifica se já existe um nó filho—se não, cria um e adiciona à tabela de cabeçalho;
- Se o nó já existe, seu contador é incrementado;
- Após construir a árvore, o código conecta todos os nós com o mesmo nome de item usando o atributo link, permitindo uma navegação rápida pela tabela de cabeçalho.
Impressão da estrutura da FP-Tree:
- A função print_tree exibe a árvore imprimindo recursivamente cada nó e seu contador, com indentação para mostrar a estrutura da árvore;
- Essa saída ajuda a visualizar como as transações são comprimidas em caminhos compartilhados dentro da FP-Tree.

1. Qual das alternativas a seguir é uma vantagem chave do FP-Growth em relação ao algoritmo Apriori?

2. Qual é a estrutura de um nó da FP-Tree?

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 1

Pergunte à IA

Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo

Seção 2. Capítulo 1