Lernen Vergleich der Algorithmischen Leistung | High Performance Rule Mining and Scale Optimization

Swipe um das Menü anzuzeigen

Das Verständnis der rechnerischen Unterschiede zwischen Apriori und FP-Growth ist entscheidend beim Mining von Assoziationsregeln im großen Maßstab. Nachfolgend eine strukturierte Übersicht, um diese beiden Algorithmen effektiv zu vergleichen:

Speicherverbrauch

Apriori

Erzeugt alle möglichen Itemsets und speichert sie im Speicher, was dazu führen kann, dass der Speicherverbrauch exponentiell ansteigt, wenn die Anzahl der eindeutigen Items zunimmt;

FP-Growth

Erstellt eine kompakte FP-Tree-Struktur, die Transaktionen effizienter speichert, indem gemeinsame Präfixe zusammengefasst werden, wodurch der Speicherbedarf bei dichten Datensätzen erheblich reduziert wird.

Geschwindigkeit

Apriori

Durch wiederholtes Durchsuchen des Datensatzes zur Zählung der Häufigkeiten von Itemsets entsteht eine hohe Laufzeit, insbesondere mit zunehmender Größe der Itemsets;

FP-Growth

Benötigt nur zwei vollständige Durchläufe über die Daten – einen zur Bestimmung häufiger Items und einen weiteren zum Aufbau des FP-Baums – und ist dadurch bei großen Datensätzen deutlich schneller.

Skalierbarkeit

Apriori

Hat Schwierigkeiten mit der Skalierbarkeit aufgrund der kombinatorischen Explosion von Kandidaten-Itemsets, was es für sehr große oder dichte Datensätze unpraktisch macht;

FP-Growth

Skaliert besser, indem die Generierung von Kandidaten vermieden und die Baumkompression genutzt wird, was effizientes Mining auch bei wachsender Datenmenge und Komplexität der Itemsets ermöglicht.

Praktische Szenarien

Apriori verwenden

Bei kleinen oder spärlichen Datensätzen, wenn Interpretierbarkeit und Einfachheit wichtig sind oder wenn die Mindestunterstützungsschwellen einfach angepasst werden sollen;

FP-Growth verwenden

Bei großen, dichten Datensätzen oder wenn Speichereffizienz und Geschwindigkeit Priorität haben.

Das folgende Codebeispiel zeigt, wie ein synthetischer Datensatz von Warenkorbetransaktionen erstellt und die Laufzeitleistung der Algorithmen Apriori und FP-Growth mit der Python-Bibliothek mlxtend verglichen wird. Es wird veranschaulicht, wie jeder Algorithmus mit denselben Daten umgeht und wie sich ihre Ausführungszeiten unterscheiden, wodurch ihre Effizienz in praktischen Szenarien hervorgehoben wird.


              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. Wann sollte FP-Growth gegenüber Apriori für das Auffinden von Assoziationsregeln bevorzugt werden?

2. Welche Aussage beschreibt am besten den Unterschied in der Rechenkomplexität zwischen Apriori und FP-Growth?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 2

Fragen Sie AI

Fragen Sie alles oder probieren Sie eine der vorgeschlagenen Fragen, um unser Gespräch zu beginnen

Abschnitt 2. Kapitel 2