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
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
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}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}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)}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
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
Abrir referência DOICopiado.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 DOICopiado.