Aprenda Comparando o Desempenho Algorítmico | Mineração de Regras de Alto Desempenho e Otimização de Escala

Deslize para mostrar o menu

Compreender as diferenças computacionais entre Apriori e FP-Growth é fundamental ao minerar regras de associação em larga escala. Abaixo está uma análise estruturada para ajudar na comparação eficaz desses dois algoritmos:

Uso de Memória

Apriori

Gera todos os conjuntos de itens possíveis e os armazena na memória, o que pode fazer o uso de memória crescer exponencialmente à medida que o número de itens únicos aumenta;

FP-Growth

Constrói uma estrutura compacta de FP-tree que armazena as transações de forma mais eficiente ao colapsar prefixos comuns, reduzindo significativamente o consumo de memória em conjuntos de dados densos.

Velocidade

Apriori

Escaneia repetidamente o conjunto de dados para contar as frequências dos conjuntos de itens, resultando em tempo de execução elevado, especialmente à medida que o tamanho do conjunto de itens aumenta;

FP-Growth

Requer apenas duas passagens completas sobre os dados—uma para determinar os itens frequentes e outra para construir a FP-tree—tornando-o significativamente mais rápido para conjuntos de dados grandes.

Escalabilidade

Apriori

Apresenta dificuldades de escalabilidade devido à explosão combinatória dos conjuntos de itens candidatos, tornando-o impraticável para conjuntos de dados muito grandes ou densos;

FP-Growth

Apresenta melhor escalabilidade ao evitar a geração de candidatos e utilizar compressão em árvore, permitindo mineração eficiente mesmo com o aumento do tamanho dos dados e da complexidade dos conjuntos de itens.

Cenários Práticos

Usar Apriori

Quando os conjuntos de dados são pequenos ou esparsos, a interpretabilidade e simplicidade são importantes, ou quando se deseja ajustar facilmente os limiares mínimos de suporte;

Usar FP-Growth

Quando os conjuntos de dados são grandes, densos, ou quando eficiência de memória e velocidade são prioridades.

O exemplo de código a seguir demonstra como criar um conjunto de dados sintético de transações de mercado e comparar o desempenho em tempo de execução dos algoritmos Apriori e FP-Growth utilizando a biblioteca mlxtend do Python. Você verá como cada algoritmo lida com os mesmos dados e como seus tempos de execução diferem, destacando sua eficiência em cenários práticos.


              123456789101112131415161718192021222324252627
            
import pandas as pd
from mlxtend.frequent_patterns import apriori, fpgrowth
import numpy as np
import time

# Create a medium-sized synthetic dataset
np.random.seed(42)
items = ['apple', 'banana', 'milk', 'bread', 'butter', 'cheese', 'eggs', 'juice']
n_transactions = 3000
data = []
for _ in range(n_transactions):
    basket = np.random.choice(items, size=np.random.randint(2, 6), replace=False)
    data.append({item: (item in basket) for item in items})
df = pd.DataFrame(data)

# Timing Apriori
start_apriori = time.time()
apriori(df, min_support=0.05, use_colnames=True)
end_apriori = time.time()

# Timing FP-Growth
start_fpgrowth = time.time()
fpgrowth(df, min_support=0.05, use_colnames=True)
end_fpgrowth = time.time()

print(f"Apriori runtime: {end_apriori - start_apriori:.3f} seconds")
print(f"FP-Growth runtime: {end_fpgrowth - start_fpgrowth:.3f} seconds")

1. Quando você deve preferir FP-Growth ao invés de Apriori para mineração de regras de associação?

2. Qual afirmação melhor descreve a diferença de complexidade computacional entre Apriori e FP-Growth?

Tudo estava claro?

Obrigado pelo seu feedback!

Seção 2. Capítulo 2

Pergunte à IA

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

Seção 2. Capítulo 2