Lernen Konstruktion von Frequent Pattern Trees mit dem FP-Growth-Algorithmus | High Performance Rule Mining and Scale Optimization

Swipe um das Menü anzuzeigen

Überblick über FP-Growth

FP-Growth ist ein leistungsstarker Algorithmus zur Erkennung häufiger Itemsets in großen Transaktionsdatensätzen. Im Gegensatz zu Apriori, das Kandidaten-Itemsets generiert und die Datenbank wiederholt durchsucht, erstellt FP-Growth eine kompakte Datenstruktur namens FP-Tree (Frequent Pattern Tree), die das Auffinden häufiger Muster ohne Kandidatengenerierung ermöglicht. Dies führt zu erheblichen Verbesserungen bei Geschwindigkeit und Speicherbedarf, insbesondere bei Datensätzen mit vielen häufigen Mustern.

Baumstruktur

Die FP-Tree-Struktur komprimiert alle Transaktionen in ein Präfixbaum-Format. Jede Transaktion wird verarbeitet, indem ihre Items in absteigender Häufigkeit sortiert und dann in den Baum eingefügt werden, wobei gemeinsame Präfixe mit bestehenden Pfaden geteilt werden. Der Wurzelknoten ist ein Nullknoten, der als Einstiegspunkt dient, und jeder Knoten im Baum repräsentiert ein Item sowie eine Zählung, wie viele Transaktionen dieses Präfix bis zu diesem Punkt teilen.

Knotenverknüpfung

Zur effizienten Mustererkennung sind alle Knoten, die dasselbe Item repräsentieren, über eine verkettete Liste verbunden, die als Header-Tabelle bezeichnet wird. Dies ermöglicht ein schnelles Durchlaufen aller Vorkommen eines bestimmten Items im Baum. Jeder Eintrag in der Header-Tabelle verweist auf den ersten Knoten im Baum für dieses Item, und jeder Knoten enthält einen Link zum nächsten Knoten mit demselben Itemnamen.

Mustererkennung

Das Auffinden häufiger Muster im FP-Tree umfasst zwei Hauptschritte. Zuerst wird der Baum von unten nach oben durchlaufen, indem die Verknüpfungen für jedes Item in der Header-Tabelle verfolgt werden, um alle Präfixpfade zu diesem Item zu sammeln. Anschließend werden für jedes Item bedingte FP-Trees erstellt und rekursiv durchsucht, um alle häufigen Itemsets zu extrahieren. Dieser rekursive Prozess wird fortgesetzt, bis keine weiteren häufigen Muster gefunden werden können.

Beispiel: Schrittweise Konstruktion eines FP-Baums

Im Folgenden wird die genaue schrittweise Konstruktion anhand Ihrer Beispieltransaktionen erläutert, wobei ein Mindestunterstützungswert von 2 angenommen wird (das bedeutet, dass Artikel mindestens zweimal vorkommen müssen, um berücksichtigt zu werden).

Angenommen, Sie haben die folgenden Transaktionen:

- Transaktion 1: A, B, D;
- Transaktion 2: B, C, E;
- Transaktion 3: A, B, C, E;
- Transaktion 4: B, E.

Schritt 1: Datenbank scannen und nach Häufigkeit sortieren

Zunächst liest der Algorithmus den gesamten Datensatz ein, um zu zählen, wie oft jedes einzelne Element vorkommt. Alle Elemente, die unter dem Mindestunterstützungswert liegen, werden verworfen. Anschließend wird eine globale Sortierreihenfolge von der höchsten zur niedrigsten Häufigkeit festgelegt.

Globale Elementhäufigkeit:

B kommt 4-mal vor

E kommt 3-mal vor

A kommt 2-mal vor

C kommt 2-mal vor

D kommt 1-mal vor (Verworfen, da weniger als die Mindestunterstützung von 2)

Die endgültige Sortierreihenfolge: Jede Transaktion wird nun gefiltert und so umgeordnet, dass sie dieser absteigenden Häufigkeitsreihenfolge strikt folgt:

$\mathbf{B} \longrightarrow \mathbf{E} \longrightarrow \mathbf{A} \longrightarrow \mathbf{C}$

Schritt 2: Jede Transaktion umsortieren

Bevor die Elemente in den Baum eingefügt werden, schreibt der Algorithmus jede Transaktion um. Das seltene Element (D) wird entfernt und die verbleibenden Elemente werden entsprechend der neuen globalen Sortierreihenfolge angeordnet.

- Transaktion 1: A, B, D wird zu B, A
- Transaktion 2: B, C, E wird zu B, E, C
- Transaktion 3: A, B, C, E wird zu B, E, A, C
- Transaktion 4: B, E wird zu B, E

Schritt 3: Pfade in den FP-Baum einfügen

Jeder FP-Baum beginnt mit einem leeren Platzhalter, der als Null-Wurzelknoten bezeichnet wird. Nun werden die neu sortierten Transaktionen nacheinander in den Baum eingefügt, wobei Zähler erhöht werden, wenn sich Pfade überschneiden, und neue Zweige entstehen, wenn sie sich trennen.

Transaktion 1 {B, A} einfügen: der Baum erstellt einen neuen Zweig direkt von der Wurzel nach unten.

Transaktion 2 {B, E, C} einfügen: der Algorithmus beginnt an der Wurzel und prüft das erste Element, B. Da B bereits als Kind der Wurzel existiert, überschneiden sich die Pfade! Der Algorithmus geht zu B und erhöht dessen Zähler auf 2. Das nächste Element ist E. Da B noch kein Kind namens E hat, teilt sich der Baum hier und erstellt einen neuen Unterzweig für E, gefolgt von C.

Transaktion 3 {B, E, A, C} einfügen: von der Wurzel ausgehend trifft der Pfad auf B (Zähler erhöht sich auf 3), dann weiter zum bestehenden E-Knoten (Zähler erhöht sich auf 2). Das nächste Element ist A. Da E noch kein Kind namens A hat, erstellt der Baum eine neue Verzweigung unter E für (A:1) -> (C:1).

Transaktion 4 {B, E} einfügen: der Algorithmus folgt dem beliebtesten Präfixpfad, B erhöht sich auf 4, E erhöht sich auf 3. Die Transaktion endet hier, es werden keine neuen Knoten hinzugefügt.

(Null Root) | (B: 4) / \ (A: 1) (E: 3) / \ (C: 1) (A: 1) | (C: 1)


              12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
            
transactions = [
    ['A', 'B', 'D'],
    ['B', 'C', 'E'],
    ['A', 'B', 'C', 'E'],
    ['B', 'E']
]

# Step 1: Counting item frequency
from collections import defaultdict, Counter

item_counts = Counter()
for transaction in transactions:
    item_counts.update(transaction)

# Step 2: Removing infrequent items
min_support = 2
freq_items = {item for item, count in item_counts.items() if count >= min_support}

# Step 3: Sorting items in each transaction by frequency
def sort_transaction(transaction):
    return sorted([item for item in transaction if item in freq_items],
                  key=lambda item: (-item_counts[item], item))

sorted_transactions = [sort_transaction(t) for t in transactions]

# Step 4: Defining FP-Tree node class
class FPTreeNode:
    def __init__(self, item, count, parent):
        self.item = item
        self.count = count
        self.parent = parent
        self.children = {}
        self.link = None  # Node link for header table

# Step 5: Building the FP-Tree and header table
def build_fp_tree(transactions):
    root = FPTreeNode(None, 1, None)
    header_table = defaultdict(list)

    for transaction in transactions:
        current = root
        for item in transaction:
            if item not in current.children:
                current.children[item] = FPTreeNode(item, 1, current)
                header_table[item].append(current.children[item])
            else:
                current.children[item].count += 1
            current = current.children[item]
    # Linking nodes in header table
    for item, nodes in header_table.items():
        for i in range(len(nodes) - 1):
            nodes[i].link = nodes[i + 1]
    return root, header_table

fp_root, header_table = build_fp_tree(sorted_transactions)

# Step 6: Printing the FP-Tree
def print_tree(node, indent=0):
    if node.item is not None:
        print('  ' * indent + f"{node.item}:{node.count}")
    for child in node.children.values():
        print_tree(child, indent + 1)

print_tree(fp_root)

Dieses Codebeispiel zeigt, wie ein FP-Baum aus einer Liste von Transaktionen mit Python konstruiert wird. Nachfolgend eine detaillierte Erläuterung der einzelnen Schritte:

Zählen der Elementhäufigkeiten:
- Der Code verwendet die Counter-Klasse aus dem Modul collections, um zu zählen, wie oft jedes Element in allen Transaktionen vorkommt;
- Dies hilft dabei, festzustellen, welche Elemente häufig genug sind, um in den Baum aufgenommen zu werden.
Entfernen seltener Elemente:
- Elemente, die den Mindestunterstützungswert nicht erreichen, werden herausgefiltert;
- Die Menge freq_items enthält nur Elemente, die mindestens so oft vorkommen, wie durch min_support festgelegt.
Sortieren der Transaktionen nach Häufigkeit:
- Jede Transaktion wird gefiltert, sodass nur häufige Elemente übrig bleiben;
- Die Elemente werden dann in absteigender Reihenfolge ihrer globalen Häufigkeit sortiert (und alphabetisch, um Gleichstände aufzulösen);
- Das Sortieren maximiert die Präfixteilung im FP-Baum und macht den Baum dadurch kompakter.
Definition der FP-Baum-Knotenklasse:
- Die Klasse FPTreeNode repräsentiert jeden Knoten im Baum;
- Jeder Knoten speichert den Elementnamen, den Zähler, einen Zeiger auf das Elternelement, ein Wörterbuch seiner Kinder und einen Link zum nächsten Knoten mit demselben Elementnamen (für die Traversierung der Header-Tabelle).
Erstellen des FP-Baums und der Header-Tabelle:
- Die Funktion build_fp_tree erstellt den Baum, indem sie jede sortierte Transaktion einfügt;
- Ausgehend von der Wurzel prüft die Funktion für jedes Element einer Transaktion, ob ein Kindknoten existiert – falls nicht, wird einer erstellt und zur Header-Tabelle hinzugefügt;
- Existiert bereits ein Knoten, wird dessen Zähler erhöht;
- Nach dem Aufbau des Baums verknüpft der Code alle Knoten mit demselben Elementnamen über das Attribut link, was eine schnelle Traversierung über die Header-Tabelle ermöglicht.
Ausgabe der FP-Baum-Struktur:
- Die Funktion print_tree gibt den Baum aus, indem sie jeden Knoten und dessen Zähler rekursiv mit Einrückung zur Darstellung der Baumstruktur ausgibt;
- Diese Ausgabe hilft dabei, zu visualisieren, wie Transaktionen in gemeinsamen Pfaden im FP-Baum komprimiert werden.

1. Welcher der folgenden Punkte ist ein wesentlicher Vorteil von FP-Growth gegenüber dem Apriori-Algorithmus?

2. Wie ist die Struktur eines FP-Tree-Knotens aufgebaut?

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 1

Fragen Sie AI

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

Abschnitt 2. Kapitel 1