Lære Sammenligning af Algoritmisk Ydeevne | High Performance Rule Mining and Scale Optimization

Stryg for at vise menuen

Forståelse af de beregningsmæssige forskelle mellem Apriori og FP-Growth er afgørende ved minedrift af associationsregler i stor skala. Her er en struktureret oversigt, der hjælper med at sammenligne disse to algoritmer effektivt:

Hukommelsesforbrug

Apriori

Genererer alle mulige itemsets og gemmer dem i hukommelsen, hvilket kan få hukommelsesforbruget til at vokse eksponentielt, efterhånden som antallet af unikke elementer stiger;

FP-Growth

Opbygger en kompakt FP-træ-struktur, der lagrer transaktioner mere effektivt ved at sammenflette fælles præfikser, hvilket markant reducerer hukommelsesforbruget for tætte datasæt.

Hastighed

Apriori

Gentagne scanninger af datasættet for at tælle hyppigheden af itemsets, hvilket fører til lang køretid, især når størrelsen på itemsets øges;

FP-Growth

Kræver kun to fulde gennemløb af dataene—et for at bestemme hyppige elementer og et andet for at opbygge FP-træet—hvilket gør det markant hurtigere for store datasæt.

Skalerbarhed

Apriori

Har udfordringer med skalerbarhed på grund af den kombinatoriske eksplosion af kandidat-itemsets, hvilket gør det upraktisk for meget store eller tætte datasæt;

FP-Growth

Skalerer bedre ved at undgå generering af kandidater og udnytte trækomprimering, hvilket muliggør effektiv minedrift, selv når datamængden og kompleksiteten af itemsets vokser.

Praktiske scenarier

Brug Apriori

Når datasæt er små eller sparsomme, hvor fortolkelighed og enkelhed er vigtige, eller når du ønsker nem justering af minimum support-grænser;

Brug FP-Growth

Når datasæt er store, tætte, eller hvor hukommelseseffektivitet og hastighed er prioriteret.

Følgende kodeeksempel demonstrerer, hvordan man opretter et syntetisk datasæt af market basket-transaktioner og sammenligner køretidens ydeevne for Apriori- og FP-Growth-algoritmerne ved hjælp af Pythons mlxtend-bibliotek. Du vil se, hvordan hver algoritme håndterer de samme data, og hvordan deres eksekveringstider adskiller sig, hvilket fremhæver deres effektivitet i praktiske scenarier.


              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. Hvornår bør du foretrække FP-Growth frem for Apriori til at finde associationsregler?

2. Hvilken påstand beskriver bedst forskellen i beregningskompleksitet mellem Apriori og FP-Growth?

Var alt klart?

Tak for dine kommentarer!

Sektion 2. Kapitel 2

Spørg AI

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Sektion 2. Kapitel 2