Lära Jämförelse av algoritmisk prestanda | Högpresterande regelutvinning och skaloptimering

Svep för att visa menyn

Att förstå de beräkningsmässiga skillnaderna mellan Apriori och FP-Growth är avgörande vid association rule mining i stor skala. Här är en strukturerad översikt för att effektivt jämföra dessa två algoritmer:

Minnesanvändning

Apriori

Genererar alla möjliga itemsets och lagrar dem i minnet, vilket kan leda till exponentiell ökning av minnesanvändningen när antalet unika objekt ökar;

FP-Growth

Bygger en kompakt FP-trädstruktur som lagrar transaktioner mer effektivt genom att slå samman gemensamma prefix, vilket kraftigt minskar minnesåtgången för täta datamängder.

Hastighet

Apriori

Skannar upprepade gånger datasetet för att räkna förekomster av itemset, vilket leder till lång körtid, särskilt när storleken på itemset ökar;

FP-Growth

Kräver endast två fullständiga genomgångar av data—en för att identifiera frekventa objekt och en annan för att bygga FP-trädet—vilket gör den avsevärt snabbare för stora dataset.

Skalbarhet

Apriori

Har svårt med skalbarhet på grund av den kombinatoriska explosionen av kandidat-itemset, vilket gör den opraktisk för mycket stora eller täta dataset;

FP-Growth

Skalar bättre genom att undvika generering av kandidater och utnyttja träkomprimering, vilket möjliggör effektiv utvinning även när datamängd och itemset-komplexitet ökar.

Praktiska scenarier

Använd Apriori

När datamängder är små eller glesa, tolkbarhet och enkelhet är viktiga, eller när du vill kunna justera minimigränser för stöd enkelt;

Använd FP-Growth

När datamängder är stora, täta, eller när minneshantering och hastighet är prioriterade.

Följande kodexempel visar hur man skapar en syntetisk datamängd av marknadskorgstransaktioner och jämför körtidsprestandan för Apriori- och FP-Growth-algoritmerna med hjälp av Pythons mlxtend-bibliotek. Du får se hur varje algoritm hanterar samma data och hur deras exekveringstider skiljer sig åt, vilket belyser deras effektivitet i praktiska 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. När bör du föredra FP-Growth framför Apriori för att hitta associationsregler?

2. Vilket påstående beskriver bäst skillnaden i beräkningskomplexitet mellan Apriori och FP-Growth?

Var allt tydligt?

Tack för dina kommentarer!

Avsnitt 2. Kapitel 2

Fråga AI

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

Avsnitt 2. Kapitel 2