Skip to content
Voltar aos resultados

FP-Growth (Crescimento de Padrões Frequentes, Frequent Pattern Growth)

Proposto por
Jiawei Han, Jian Pei & Yiwen Yin
Ano
2000
Tipo
Frequent-itemset mining algorithm
Família
Pattern mining

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

O FP-Growth, introduzido por Jiawei Han, Jian Pei e Yiwen Yin em 2000, extrai conjuntos de itens frequentes de dados transacionais sem gerar conjuntos candidatos, o passo custoso que desacelera o algoritmo clássico Apriori.

Ele comprime o banco de dados em uma árvore de padrões frequentes (FP-tree) em duas varreduras, e então gera padrões frequentes recursivamente a partir dessa estrutura, tornando-o dramaticamente mais rápido que o Apriori em conjuntos de dados grandes e densos.

A intuição por trás do método

O Apriori encontra conjuntos de itens frequentes gerando e testando repetidamente combinações candidatas — um processo caro e intensivo em varreduras que explode em dados densos. O FP-Growth toma um caminho diferente: ele comprime todo o banco de dados transacional em uma árvore compacta onde prefixos compartilhados são armazenados uma vez, de modo que padrões comuns se sobrepõem e se comprimem. Então, em vez de gerar candidatos, ele lê padrões frequentes diretamente da árvore seguindo os caminhos que levam a cada item e minerando recursivamente árvores 'condicionais' menores. Duas passagens pelos dados e uma estrutura de dados inteligente substituem as muitas passagens e o estouro combinatório de candidatos do Apriori.

História

Han, Pei e Yin apresentaram o FP-Growth na SIGMOD 2000 como uma alternativa sem geração de candidatos ao Apriori, com um tratamento expandido em seu artigo de 2004 na Data Mining and Knowledge Discovery. A ideia da árvore de padrões frequentes — comprimir transações em uma estrutura de prefixo compartilhado e minerá-la recursivamente — tornou-se uma técnica fundamental na mineração de padrões, ao lado do Apriori (baseado em candidatos) e ECLAT (formato vertical). Permanece um minerador de conjuntos de itens padrão e de alto desempenho em bibliotecas de mineração de dados.

Quando usar

Use o FP-Growth para minerar conjuntos de itens frequentes (e, subsequentemente, regras de associação) de dados transacionais — análise de cesta de compras, mineração de uso da web e clickstream, recomendação e coocorrência em bioinformática — especialmente em conjuntos de dados grandes ou densos onde a geração de candidatos do Apriori é muito lenta. Ele necessita apenas de duas varreduras do banco de dados e tipicamente supera o Apriori. Seus custos: a FP-tree deve caber na memória (uma limitação para dados muito grandes ou extremamente esparsos, onde a árvore comprime mal), a recursão pode ser intrincada de implementar, e como toda mineração baseada em suporte, é sensível ao limiar de suporte mínimo (muito baixo explode a saída, muito alto perde padrões). O ECLAT (interseção vertical de tidsets) é uma alternativa; para as regras em si, combine com a geração de regras de associação.

Limitações e considerações

  • A FP-tree deve caber na memória; conjuntos de dados muito grandes podem não caber.
  • Em dados esparsos, a árvore comprime mal, erodindo a vantagem.
  • A construção recursiva de árvores condicionais é comparativamente complexa de implementar.
  • Sensível ao limiar de suporte mínimo, como toda mineração de conjuntos de itens frequentes.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Sem geração de candidatos — muito mais rápido que o Apriori em dados grandes/densos.
  • Apenas duas varreduras do banco de dados, independentemente do comprimento do padrão.
  • A FP-tree comprime a estrutura compartilhada, economizando memória e tempo em dados densos.
  • Escala para padrões frequentes longos que sobrecarregam métodos baseados em candidatos.

Aplicações

  • Análise de cesta de compras e mineração de regras de associação no varejo.
  • Mineração de padrões de uso da web e clickstream.
  • Recomendação via itens frequentemente coocorrentes.
  • Coocorrência em bioinformática e descoberta de motivos.
  • Qualquer tarefa de conjuntos de itens frequentes em larga escala onde o Apriori é muito lento.

Como funciona

Como funciona

1

Uma primeira varredura do banco de dados conta o suporte de cada item e descarta aqueles abaixo do limiar de suporte mínimo. Os itens frequentes sobreviventes são ordenados por frequência decrescente — essa ordenação permite que transações compartilhem prefixos de árvore e mantém a FP-tree compacta.

Fórmula
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Uma segunda varredura insere cada transação (seus itens frequentes, na ordem ordenada) na FP-tree, incrementando contagens em caminhos de prefixo compartilhados e adicionando novos ramos conforme necessário. Uma tabela de cabeçalho liga todas as ocorrências de cada item, de modo que a árvore representa compactamente a estrutura frequente de todo o conjunto de dados.

Fórmula
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Para cada item frequente (processado do menos frequente para o mais frequente), o algoritmo coleta sua base de padrões condicional — o conjunto de caminhos de prefixo na árvore que coocorrem com esse item, cada um ponderado por sua contagem. Isso captura o contexto em que o item aparece frequentemente.

Fórmula
\text{for each item: collect its conditional pattern base (prefix paths)}
4

A partir de cada base de padrões condicional, uma FP-tree condicional menor é construída e minerada recursivamente, gerando conjuntos de itens mais longos ao anexar o item a padrões encontrados em sua árvore condicional. A recursão termina em árvores de caminho único, cujas combinações de conjuntos de itens são enumeradas diretamente — produzindo todos os conjuntos de itens frequentes sem geração de candidatos.

Fórmula
\text{build conditional FP-trees recursively to grow frequent patterns}

Erros comuns

  • Definir o suporte mínimo muito baixo, produzindo uma explosão de conjuntos de itens.
  • Assumir que ele sempre supera o Apriori — em dados pequenos ou esparsos, o ganho é modesto.
  • Esquecer que conjuntos de itens frequentes não são regras; a geração de regras é um passo separado.
  • Ignorar limites de memória quando a FP-tree não pode ser mantida na RAM.

Perguntas frequentes

Como o FP-Growth é mais rápido que o Apriori?

O Apriori gera e testa repetidamente conjuntos de itens candidatos, varrendo o banco de dados muitas vezes. O FP-Growth evita completamente a geração de candidatos: ele comprime os dados em uma FP-tree em duas varreduras e mina padrões recursivamente a partir dela. Isso remove o estouro combinatório de candidatos, proporcionando grandes acelerações em dados densos.

O que é a FP-tree?

Uma árvore de prefixo comprimida dos itens frequentes do banco de dados. Transações que compartilham um prefixo compartilham um caminho, com contagens de nós registrando o suporte, e uma tabela de cabeçalho liga as ocorrências de cada item. Ela armazena a estrutura frequente do conjunto de dados de forma compacta para que os padrões possam ser lidos sem reexaminar os dados.

Como o FP-Growth se relaciona com o ECLAT e regras de associação?

FP-Growth, ECLAT e Apriori encontram conjuntos de itens frequentes; o ECLAT usa uma abordagem de interseção vertical de tidsets em vez de uma árvore. Encontrar conjuntos de itens frequentes é apenas o primeiro estágio — regras de associação (com confiança/lift) são geradas a partir desses conjuntos de itens em um passo separado.

Métodos relacionados

Fontes

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Abrir referência DOI
    Copiado.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    Abrir referência DOI
    Copiado.