Zum Inhalt springen
Zurück zu den Suchergebnissen

FP-Growth (Frequent Pattern Growth)

Eingeführt von
Jiawei Han, Jian Pei & Yiwen Yin
Jahr
2000
Typ
Frequent-itemset mining algorithm
Familie
Pattern mining

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

FP-Growth, eingeführt von Jiawei Han, Jian Pei und Yiwen Yin im Jahr 2000, extrahiert häufige Itemsets aus Transaktionsdaten, ohne Kandidatenmengen zu generieren – der kostspielige Schritt, der den klassischen Apriori-Algorithmus verlangsamt.

Es komprimiert die Datenbank in zwei Durchläufen in einen Frequent-Pattern Tree (FP-Tree) und extrahiert dann rekursiv häufige Muster aus dieser Struktur, was es auf großen, dichten Datensätzen dramatisch schneller macht als Apriori.

Die Intuition hinter der Methode

Apriori findet häufige Itemsets, indem es wiederholt Kandidatenkombinationen generiert und testet – ein teurer, scanintensiver Prozess, der bei dichten Daten explodiert. FP-Growth geht einen anderen Weg: Es presst die gesamte Transaktionsdatenbank in einen kompakten Baum, in dem gemeinsame Präfixe nur einmal gespeichert werden, sodass sich gemeinsame Muster überlappen und komprimieren. Anstatt dann Kandidaten zu generieren, liest es häufige Muster direkt aus dem Baum aus, indem es den Pfaden folgt, die zu jedem Element führen, und rekursiv in kleineren „bedingten“ Bäumen nach Mustern sucht. Zwei Durchläufe über die Daten und eine clevere Datenstruktur ersetzen die vielen Durchläufe und die kombinatorische Kandidaten-Explosion von Apriori.

Geschichte

Han, Pei und Yin präsentierten FP-Growth auf der SIGMOD 2000 als eine Alternative zu Apriori ohne Kandidatengenerierung, mit einer erweiterten Behandlung in ihrem Artikel Data Mining and Knowledge Discovery aus dem Jahr 2004. Die Idee des Frequent-Pattern Tree – Komprimierung von Transaktionen in eine gemeinsame Präfixstruktur und deren rekursive Analyse – wurde zu einer grundlegenden Technik im Pattern Mining, neben Apriori (kandidatenbasiert) und ECLAT (vertikales Format). Es bleibt ein Standard-Hochleistungs-Itemset-Miner in Data-Mining-Bibliotheken.

Wann wird sie eingesetzt?

Verwenden Sie FP-Growth, um häufige Itemsets (und nachgelagert Assoziationsregeln) aus Transaktionsdaten zu extrahieren – Warenkorbanalyse, Web-Nutzungs- und Klickstrom-Mining, Empfehlungen und Bioinformatik-Ko-Okkurrenzen – insbesondere auf großen oder dichten Datensätzen, bei denen die Kandidatengenerierung von Apriori zu langsam ist. Es benötigt nur zwei Datenbankscans und übertrifft Apriori typischerweise bei weitem. Seine Kosten: Der FP-Tree muss in den Speicher passen (eine Einschränkung für sehr große oder extrem spärliche Daten, bei denen der Baum schlecht komprimiert), die Rekursion kann kompliziert zu implementieren sein, und wie jedes supportbasierte Mining ist es empfindlich gegenüber dem minimalen Support-Schwellenwert (zu niedrig explodiert die Ausgabe, zu hoch verpasst Muster). ECLAT (vertikale Tidset-Schnittmenge) ist eine Alternative; für die Regeln selbst, kombinieren Sie mit der Assoziationsregelgenerierung.

Grenzen und Hinweise

  • Der FP-Tree muss in den Speicher passen; sehr große Datensätze möglicherweise nicht.
  • Bei spärlichen Daten komprimiert der Baum schlecht, was den Vorteil schmälert.
  • Die rekursive Konstruktion bedingter Bäume ist vergleichsweise komplex zu implementieren.
  • Empfindlich gegenüber dem minimalen Support-Schwellenwert, wie bei allen Frequent-Itemset-Mining-Verfahren.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Keine Kandidatengenerierung – viel schneller als Apriori auf großen/dichten Daten.
  • Nur zwei Datenbankscans, unabhängig von der Mustertiefe.
  • Der FP-Tree komprimiert gemeinsame Strukturen und spart Speicher und Zeit bei dichten Daten.
  • Skaliert auf lange häufige Muster, die kandidatenbasierte Methoden überfordern.

Anwendungen

  • Warenkorbanalyse und Retail-Assoziations-Mining.
  • Web-Nutzungs- und Klickstrom-Muster-Mining.
  • Empfehlungen durch häufig gemeinsam auftretende Elemente.
  • Bioinformatik-Ko-Okkurrenzen und Motivfindung.
  • Jede groß angelegte Frequent-Itemset-Aufgabe, bei der Apriori zu langsam ist.

So funktioniert es

So funktioniert es

1

Ein erster Datenbankdurchlauf zählt den Support jedes Elements und verwirft diejenigen unterhalb des minimalen Support-Schwellenwerts. Die verbleibenden häufigen Elemente werden nach absteigender Häufigkeit sortiert – diese Reihenfolge ermöglicht es Transaktionen, Baumpräfixe zu teilen, und hält den FP-Tree kompakt.

Formel
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

Ein zweiter Durchlauf fügt jede Transaktion (ihre häufigen Elemente in sortierter Reihenfolge) in den FP-Tree ein, erhöht die Zählungen entlang gemeinsamer Präfixpfade und fügt bei Bedarf neue Zweige hinzu. Eine Header-Tabelle verknüpft alle Vorkommen jedes Elements, sodass der Baum die häufige Struktur des gesamten Datensatzes kompakt darstellt.

Formel
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

Für jedes häufige Element (verarbeitet vom am wenigsten häufigen zuerst) sammelt der Algorithmus seine bedingte Musterbasis – die Menge der Präfixpfade im Baum, die mit diesem Element zusammen auftreten, jeweils gewichtet nach seiner Zählung. Dies erfasst den Kontext, in dem das Element häufig vorkommt.

Formel
\text{for each item: collect its conditional pattern base (prefix paths)}
4

Aus jeder bedingten Musterbasis wird ein kleinerer bedingter FP-Tree aufgebaut und rekursiv durchsucht, wobei längere häufige Itemsets durch Anhängen des Elements an Muster, die in seinem bedingten Baum gefunden wurden, erweitert werden. Die Rekursion endet bei Einzelpfad-Bäumen, deren Itemset-Kombinationen direkt aufgezählt werden – wodurch alle häufigen Itemsets ohne Kandidatengenerierung erzielt werden.

Formel
\text{build conditional FP-trees recursively to grow frequent patterns}

Häufige Fallstricke

  • Einstellung des minimalen Supports zu niedrig, was zu einer Explosion von Itemsets führt.
  • Annahme, dass es Apriori immer schlägt – bei kleinen oder spärlichen Daten ist der Gewinn gering.
  • Vergessen, dass häufige Itemsets keine Regeln sind; die Regelgenerierung ist ein separater Schritt.
  • Übersehen von Speicherbeschränkungen, wenn der FP-Tree nicht im RAM gehalten werden kann.

Häufig gestellte Fragen

Wie ist FP-Growth schneller als Apriori?

Apriori generiert und testet wiederholt Kandidaten-Itemsets und scannt die Datenbank viele Male. FP-Growth vermeidet die Kandidatengenerierung vollständig: Es komprimiert die Daten in zwei Scans in einen FP-Tree und extrahiert Muster rekursiv daraus. Dies eliminiert die kombinatorische Kandidaten-Explosion und führt zu großen Geschwindigkeitssteigerungen bei dichten Daten.

Was ist der FP-Tree?

Ein komprimierter Präfixbaum der häufigen Elemente der Datenbank. Transaktionen, die ein Präfix teilen, teilen einen Pfad, wobei Knotenzählungen den Support aufzeichnen und eine Header-Tabelle die Vorkommen jedes Elements verknüpft. Er speichert die häufige Struktur des Datensatzes kompakt, sodass Muster abgerufen werden können, ohne die Daten erneut zu scannen.

Wie verhält sich FP-Growth zu ECLAT und Assoziationsregeln?

FP-Growth, ECLAT und Apriori finden alle häufige Itemsets; ECLAT verwendet einen vertikalen Tidset-Schnittmengen-Ansatz anstelle eines Baumes. Das Finden häufiger Itemsets ist nur die erste Stufe – Assoziationsregeln (mit Konfidenz/Lift) werden in einem separaten Schritt aus diesen Itemsets generiert.

Verwandte Methoden

Quellen

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    DOI-Referenz öffnen
    Kopiert.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    DOI-Referenz öffnen
    Kopiert.