Lernen Verarbeitung von Transaktionsdatenströmen mit dem Apriori-Algorithmus | Grundlagen von Assoziationsregeln und Transaktionsanalyse

Swipe um das Menü anzuzeigen

Der Apriori-Algorithmus ist ein grundlegendes Werkzeug zur Identifizierung häufiger Itemsets in Transaktionsdaten und damit essenziell für die Warenkorbanalyse. Im Zentrum von Apriori steht das Apriori-Prinzip, auch als Abwärtsabschluss-Eigenschaft bekannt.

Definition

Apriori-Prinzip – Wenn ein Itemset häufig ist, müssen auch alle seine Teilmengen häufig sein.

Diese Erkenntnis reduziert die Anzahl der zu bewertenden Itemsets erheblich, da jedes Itemset, das eine seltene Teilmenge enthält, sofort ausgeschlossen werden kann.

Kandidatengenerierung ist die Zuordnungsphase des Algorithmus. In jeder Runde betrachtet der Algorithmus die erfolgreichen, häufigen Itemsets aus der vorherigen Runde und kombiniert sie zu neuen, größeren Gruppen, den sogenannten Kandidaten. Um dies effizient zu gestalten, verbindet der Algorithmus nur Itemsets, die nahezu identisch sind und sich nur im letzten Element unterscheiden.

Funktionsweise: Wenn der Algorithmus feststellt, dass {Bread, Milk} und {Bread, Diapers} jeweils sehr beliebt sind, kombiniert er sie zu einem neuen Kandidaten mit drei Elementen für die nächste Runde: {Bread, Milk, Diapers}.

Unmittelbar nach der Generierung neuer Kandidaten startet der Algorithmus die Pruning-Phase, um unnötige Kandidaten zu entfernen, bevor aufwendige Datenbankberechnungen durchgeführt werden. Dieser Schritt basiert vollständig auf dem Apriori-Prinzip, das besagt, dass ein großes Itemset nur dann häufig sein kann, wenn alle seine kleineren Teilmengen ebenfalls häufig sind. Während des Prunings analysiert der Algorithmus jeden neuen Kandidaten und betrachtet dessen kleinere Teilmengen. Wenn auch nur eine Teilmenge in der vorherigen Runde nicht erfolgreich war, wird der gesamte Kandidat sofort entfernt.

Funktionsweise: Angenommen, der Kandidat {Bread, Milk, Eggs} wird generiert. Der Algorithmus überprüft dessen Teilmengen: {Bread, Milk}, {Bread, Eggs} und {Milk, Eggs}. Wenn Ihre historischen Transaktionsdaten zeigen, dass {Milk, Eggs} eine seltene Kombination ist, die in einer vorherigen Runde ausgeschlossen wurde, entfernt der Algorithmus {Bread, Milk, Eggs} vollständig. So wird Rechenleistung für Kombinationen eingespart, die mathematisch garantiert ausscheiden.

Nachdem die Kandidatenliste auf die vielversprechendsten Gruppen reduziert wurde, folgt die Identifikation häufiger Itemsets. Das System durchsucht die Rohdaten Ihrer Transaktionsdatenbank und zählt exakt, wie oft diese verbleibenden Kandidatengruppen gemeinsam in echten Einkäufen auftreten. Die Gesamtanzahl jedes Kandidaten wird in einen Prozentsatz umgerechnet. Erreicht oder übersteigt dieser Wert den festgelegten Minimalen Support-Schwellenwert, wird der Kandidat offiziell als häufiges Itemset anerkannt.

Definition

Minimale Support-Schwelle ist ein vom Benutzer festgelegter Grenzwert, der bestimmt, wie häufig ein Itemset mindestens auftreten muss, um im Apriori-Algorithmus als signifikant zu gelten. Durch das Setzen dieser Schwelle werden Itemsets herausgefiltert, die zu selten im Datensatz vorkommen. Ein hoher Schwellenwert führt zu weniger, aber häufigeren Itemsets, wodurch interessante, aber seltene Kombinationen möglicherweise übersehen werden. Ist die Schwelle zu niedrig, erhält man zu viele Itemsets, darunter auch solche mit geringem praktischem Nutzen. Die gewählte Schwelle beeinflusst direkt die Tiefe und den Fokus der Analyse und sollte daher den Zielen und dem Umfang der Datenauswertung entsprechen.

Dieser gesamte Drei-Schritte-Zyklus wiederholt sich fortlaufend. Er beginnt mit einzelnen Artikeln, geht zu Paaren über, dann zu Dreiergruppen und erweitert sich weiter, bis eine Runde keine neuen häufigen Itemsets mehr hervorbringt und so das vollständige Netz des Kaufverhaltens der Kunden abbildet.

Um diese Konzepte greifbar zu machen, betrachten Sie ein einfaches Beispiel mit einem kleinen Datensatz. Angenommen, Sie haben folgende Transaktionen:

Transaktion 1: {Milk, Bread};
Transaktion 2: {Milk, Diaper, Beer, Bread};
Transaktion 3: {Milk, Diaper, Beer, Cola};
Transaktion 4: {Diaper, Beer};
Transaktion 5: {Milk, Diaper, Bread, Beer}.

Der Algorithmus identifiziert zunächst alle einzelnen Artikel, die häufig vorkommen, generiert dann Kandidatenpaare daraus, entfernt diejenigen, die seltene Artikel enthalten, und setzt diesen Prozess fort, um größere häufige Gruppen wie {Milk, Diaper, Beer} zu entdecken.


              1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
            
import pandas as pd
from itertools import combinations

# Example transaction dataset
transactions = [
    ['Milk', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Bread'],
    ['Milk', 'Diaper', 'Beer', 'Cola'],
    ['Diaper', 'Beer'],
    ['Milk', 'Diaper', 'Bread', 'Beer']
]

# Convert transactions to a DataFrame of one-hot encoded items
all_items = sorted(set(item for transaction in transactions for item in transaction))
df = pd.DataFrame([{item: (item in transaction) for item in all_items} for transaction in transactions])

def apriori(df, min_support=0.6):

    def get_support(itemset):
        return (df[list(itemset)].all(axis=1).sum()) / len(df)

    # Step 1: Finding frequent 1-itemsets
    frequent_itemsets = []
    current_level = []
    for item in all_items:
        support = get_support([item])
        if support >= min_support:
            current_level.append(frozenset([item]))
            frequent_itemsets.append((frozenset([item]), support))

    k = 2
    while current_level:
        # Step 2: Candidate generation
        candidates = []
        level_list = list(current_level)
        for i in range(len(level_list)):
            for j in range(i+1, len(level_list)):
                union = level_list[i] | level_list[j]
                if len(union) == k and union not in candidates:
                    # Step 3: Pruning
                    subsets = list(combinations(union, k-1))
                    if all(frozenset(subset) in current_level for subset in subsets):
                        candidates.append(union)

        # Step 4: Support counting
        next_level = []
        for candidate in candidates:
            support = get_support(candidate)
            if support >= min_support:
                next_level.append(candidate)
                frequent_itemsets.append((candidate, support))

        current_level = next_level
        k += 1

    # Format output
    return [(set(itemset), round(support, 2)) for itemset, support in frequent_itemsets]

# Running Apriori and displaying frequent itemsets
frequent_itemsets = apriori(df, min_support=0.6)
for itemset, support in frequent_itemsets:
    print(f"Frequent Itemset: {itemset}, Support: {support}")

Dieser Python-Code demonstriert eine einfache Implementierung des Apriori-Algorithmus zur Identifikation häufiger Itemsets in Transaktionsdaten. Die einzelnen Schritte werden wie folgt durchgeführt:

Datenvorbereitung

Die Transaktionen werden als Liste von Listen dargestellt, wobei jede Unterliste die gemeinsam gekauften Artikel enthält.
Alle eindeutigen Artikel werden identifiziert und sortiert.
Ein One-Hot-encodiertes DataFrame wird erstellt: Jede Zeile repräsentiert eine Transaktion, jede Spalte entspricht einem Artikel, wobei True oder False das Vorhandensein oder Fehlen anzeigt.

Schritte des Apriori-Algorithmus

1. Identifikation häufiger 1-Itemsets

Der Algorithmus berechnet den Support für jeden einzelnen Artikel (den Anteil der Transaktionen, die den Artikel enthalten).
Wenn der Support eines Artikels den min_support-Schwellenwert (hier 0,6) erreicht oder überschreitet, gilt er als häufig und wird in die erste Liste der häufigen Itemsets aufgenommen.

2. Kandidatengenerierung

Für Itemsets der Länge k (beginnend mit 2) generiert der Algorithmus neue Kandidaten-Itemsets, indem er häufige Itemsets aus der vorherigen Runde kombiniert, die bis auf ein Element identisch sind.
Es werden nur eindeutige Kombinationen berücksichtigt, um Duplikate zu vermeiden.

3. Pruning (Beschneidung)

Jede neue Kandidatenmenge wird auf Teilmengen der Länge k-1 überprüft.
Wenn eine Teilmenge nicht in der Liste der häufigen Itemsets aus der vorherigen Iteration enthalten ist, wird der Kandidat gemäß dem Apriori-Prinzip ausgeschlossen (gepruned).

4. Supportzählung

Für jeden verbleibenden Kandidaten zählt der Algorithmus, wie viele Transaktionen alle Artikel des Kandidaten enthalten.
Der Support wird berechnet und mit dem Schwellenwert verglichen. Nur Kandidaten, die den Schwellenwert erreichen, werden als häufige Itemsets für die nächste Runde beibehalten.

5. Iteration

Die Schritte 2–4 werden wiederholt, wobei die Größe der Itemsets jeweils erhöht wird, bis keine neuen häufigen Itemsets mehr gefunden werden.

Ausgabe

Die endgültige Liste enthält alle häufigen Itemsets und deren Supportwerte.
Der Code gibt jedes häufige Itemset und dessen Support aus und zeigt, welche Kombinationen von Artikeln häufig gemeinsam in den Transaktionen auftreten.

1. Welche der folgenden Aussagen beschreibt den Schritt der Kandidatengenerierung im Apriori-Algorithmus am besten?

2. Was ist der Hauptgrund für das Pruning von Kandidaten-Itemsets während des Apriori-Algorithmus?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 1. Kapitel 4

Fragen Sie AI

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

Abschnitt 1. Kapitel 4