Zum Inhalt springen
Zurück zu den Suchergebnissen

Apriori-Algorithmus

Eingeführt von
Agrawal, R. & Srikant, R.
Jahr
1994
Typ
Frequent itemset and association rule mining algorithm
Familie
Machine learning

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

Schriftgröße

Was leistet sie?

Der Apriori-Algorithmus, der 1994 von Agrawal und Srikant eingeführt wurde, ist die grundlegende Methode zur Entdeckung häufiger Itemsets und Assoziationsregeln in Transaktionsdatenbanken.

Er verwendet eine Breitensuche, die stufenweise vorgeht und durch die anti-monotone Eigenschaft des Supports geleitet wird, um effizient alle Item-Kombinationen zu enumerieren, die über einem vom Benutzer festgelegten Mindestschwellenwert gemeinsam auftreten. Anschließend extrahiert er interpretierbare Wenn-Dann-Regeln aus diesen Mustern.

Die Intuition hinter der Methode

Betrachten Sie eine Supermarkt-Kassenbon-Datenbank. Aprioris Erkenntnis ist die anti-monotone Eigenschaft: Wenn ein Produktpaar selten zusammen gekauft wird, kann keine größere Menge, die dieses Paar enthält, häufig sein. Dies ermöglicht es dem Algorithmus, den exponentiell großen Suchraum möglicher Item-Kombinationen zu beschneiden, indem Kandidaten stufenweise aufgebaut werden – beginnend mit einzelnen Items, dann Paaren, dann Tripeln – und alle Kandidaten verworfen werden, deren Teilmengen bereits als infrequent bekannt sind, noch bevor sie in den Daten gezählt werden.

Geschichte

Rakesh Agrawal und Ramakrishnan Srikant führten den Apriori-Algorithmus 1994 auf der VLDB ein, basierend auf der Formulierung des Assoziationsregel-Mining-Problems von Agrawal et al. aus dem Jahr 1993. Der Name spiegelt seine zentrale Erkenntnis wider: die Nutzung von Vorwissen über häufige (k)-Itemsets zur Beschneidung von Kandidaten auf Stufe k+1. Er wurde zum kanonischen Benchmark, gegen den alle nachfolgenden Algorithmen zur Entdeckung häufiger Itemsets – einschließlich FP-Growth (2000) und Eclat – gemessen werden, und bleibt ein Standardkapitel in Lehrbüchern über Data Mining und maschinelles Lernen.

Wann wird sie eingesetzt?

Verwenden Sie Apriori, wenn das Ziel darin besteht, Kookkurrenz-Muster oder Wenn-Dann-Beziehungen in Transaktions- oder binären Item-Präsenzdaten zu entdecken – Warenkorbanalyse, gemeinsame Bestätigung von Umfrage-Items, Kookkurrenz von medizinischen Diagnosen oder Textterm-Assoziation. Es eignet sich für mittelgroße Datensätze, bei denen Transparenz und Interpretierbarkeit der Ausgaberegeln Priorität haben. Verwenden Sie Apriori nicht, wenn die Transaktionsdatenbank sehr groß ist (Millionen von Zeilen mit breiten Item-Katalogen), da seine wiederholten vollständigen Datenbank-Scans es im Vergleich zu FP-Growth langsam machen; in diesen Fällen wird FP-Growth bevorzugt. Es ist auch für kontinuierliche numerische Daten ohne vorherige Diskretisierung ungeeignet und modelliert keine Richtung oder Kausalität.

Grenzen und Hinweise

  • Wiederholte vollständige Datenbank-Scans machen es auf großen Datensätzen langsam – FP-Growth wird oft in großem Maßstab bevorzugt.
  • Das Senken des Support-Schwellenwerts kann eine exponentielle Anzahl von Kandidaten-Itemsets und Regeln erzeugen, was die Interpretation erschwert.
  • Erfasst keine zeitliche Reihenfolge, Richtung oder kausale Beziehungen zwischen Items.
  • Ergebnisse sind empfindlich gegenüber der Wahl der Support- und Konfidenz-Schwellenwerte, die Domänenwissen oder systematische Abstimmung erfordern.

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

Stärken

  • Generiert vollständig interpretierbare Wenn-Dann-Regeln mit quantifiziertem Support, Konfidenz und Lift.
  • Die anti-monotone Beschneidungseigenschaft macht eine ansonsten exponentielle Suche handhabbar.
  • Erfordert keine vorherige Kennzeichnung der Daten; es ist vollständig unüberwacht.
  • Schwellenwertparameter (Support, Konfidenz) geben dem Analysten direkte Kontrolle über die Granularität der Regeln.
  • Ausgaberegeln sind handlungsorientiert und können ohne algorithmischen Hintergrund an nicht-technische Stakeholder kommuniziert werden.
  • Wegweisend, stark zitiert und in praktisch jeder wichtigen Data-Mining-Bibliothek implementiert.

Anwendungen

  • Warenkorbanalyse: Entdeckung, welche Produkte häufig zusammen gekauft werden, um Regalplatzierung und Werbeaktionen zu steuern.
  • Medizinische Informatik: Identifizierung von gemeinsam auftretenden Symptomen, Diagnosen oder Medikamentenverschreibungen in Patientenakten.
  • Web-Nutzungs-Mining: Ermittlung, welche Seiten oder Funktionen Benutzer tendenziell gemeinsam besuchen oder aktivieren.
  • Analyse von Umfragen und Fragebögen: Erkennung, welche Items oder Skalenantworten systematisch gemeinsam bestätigt werden.
  • Bootstrapping von Empfehlungssystemen: Generierung von Kandidaten-Item-Assoziationen vor dem Einsatz von kollaborativem Filtern.
  • Betrugserkennung: Aufdeckung ungewöhnlicher Kookkurrenz-Muster in Transaktionsprotokollen, die von normalen Warenkörben abweichen.

So funktioniert es

So funktioniert es

1

Der Analyst wählt vor der Ausführung des Algorithmus zwei Schwellenwerte: Mindest-Support (der Anteil der Transaktionen, die ein gegebenes Itemset enthalten müssen, damit es als häufig gilt) und Mindest-Konfidenz (die bedingte Wahrscheinlichkeit, die für eine Wenn-Dann-Regel erforderlich ist, um beibehalten zu werden). Diese beiden Werte steuern das Volumen und die Spezifität der Ausgabe und sollten durch Domänenwissen oder explorative Läufe kalibriert werden.

2

Der Algorithmus führt einen vollständigen Scan der Transaktionsdatenbank durch, um zu zählen, wie oft jedes einzelne Item vorkommt. Nur Items, deren Support den Mindest-Support-Schwellenwert erreicht oder überschreitet, werden beibehalten; die übrigen werden verworfen. Diese Menge häufiger einzelner Items bildet die erste Stufe der Kandidaten.

Formel
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

Die auf Stufe k gefundenen häufigen Itemsets werden paarweise verknüpft, um Kandidaten-Itemsets der Größe k+1 zu bilden. Nur Paare, die dieselben ersten k-1 Items teilen, werden verknüpft, eine Regel, die die Kandidatenmenge kompakt hält. Eine neue Datenbank-Scan zählt den Support jedes Kandidaten.

4

Vor dem Zählen wird jeder Kandidat der Größe k+1 gegen alle seine (k)-Teilmengen geprüft. Wenn eine Teilmenge auf der vorherigen Stufe nicht häufig war, wird der Kandidat sofort ohne Lesen der Daten verworfen, wodurch die anti-monotone Eigenschaft zur Reduzierung der Berechnung genutzt wird. Die Überlebenden dieses Beschneidungsschritts bilden die nächste Stufe der häufigen Itemsets.

5

Aus jedem häufigen Itemset der Größe zwei oder mehr werden alle möglichen Wenn-Dann-Regeln generiert, indem die Items in einen Antezedens und ein Konsequens aufgeteilt werden. Jede Regel wird auf Konfidenz ausgewertet – der Anteil der Antezedens-Transaktionen, die auch das Konsequens enthalten. Regeln unterhalb der Mindest-Konfidenz werden verworfen.

Formel
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

Überlebende Regeln werden nach Lift geordnet, der die beobachtete Konfidenz mit der Basis-Häufigkeit des Konsequens vergleicht. Ein Lift über 1 signalisiert, dass Antezedens und Konsequens häufiger als zufällig gemeinsam auftreten; ein Lift nahe 1 zeigt Unabhängigkeit an; ein Lift unter 1 zeigt eine negative Assoziation an. Regeln mit dem höchsten Lift sind die handlungsorientiertesten Entdeckungen.

Formel
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

Häufige Fallstricke

  • Festlegen des Mindest-Supports zu niedrig und Ertrinken in Tausenden von minderwertigen Regeln ohne Filterung nach Lift.
  • Interpretation hoher Konfidenz als Kausalität statt Kookkurrenz – eine Regel mit hoher Konfidenz, aber Lift nahe 1 ist trivial.
  • Anwendung von Apriori auf kontinuierliche Merkmale, ohne sie vorher zu diskretisieren, was den Item-Raum aufbläht und die Ergebnisse verschlechtert.
  • Berichterstattung über Regeln, ohne zu prüfen, ob die Stichprobengrößen der Itemsets groß genug sind, um die Support-Schätzungen zu vertrauen.
  • Versäumnis, informative Regeln zu entfernen (z. B. Regeln, die universell gekaufte Artikel wie eine Kundenkarte betreffen).

Häufig gestellte Fragen

Was ist der Unterschied zwischen Support, Konfidenz und Lift?

Support ist der Anteil aller Transaktionen, die das Itemset enthalten – er misst die Prävalenz. Konfidenz ist die bedingte Wahrscheinlichkeit, dass das Konsequens bei gegebenem Antezedens auftritt – sie misst die Zuverlässigkeit der Regel. Lift ist das Verhältnis der beobachteten Konfidenz zur Basis-Häufigkeit des Konsequens; ein Lift über 1 zeigt eine echte positive Assoziation und keine zufällige Übereinstimmung aufgrund der Popularität des Items an.

Wann sollte ich FP-Growth gegenüber Apriori wählen?

FP-Growth komprimiert die Datenbank in eine Baumstruktur und minet sie ohne wiederholte vollständige Scans, was sie auf großen Datensätzen oder bei niedrigem Mindest-Support erheblich schneller macht. Apriori ist leichter zu verstehen und zu implementieren und funktioniert gut auf kleinen bis mittelgroßen Datensätzen, bei denen die Laufzeit keine Engstelle darstellt.

Wie wähle ich Mindest-Support und Konfidenz?

Es gibt keine allgemeingültige Regel. Üblich ist es, den Algorithmus mit mehreren Support-Stufen auszuführen, die Anzahl der häufigen Itemsets gegen den Support aufzutragen und einen Wert im Knick der Kurve zu wählen. Die Konfidenz wird dann basierend auf der Geschäfts- oder Forschungsfrage festgelegt – höhere Konfidenz für geschäftskritische Regeln, niedrigere für explorative Entdeckungen. Validieren Sie immer die Top-Regeln anhand von Domänenexpertise.

Kann Apriori numerische oder kontinuierliche Daten verarbeiten?

Apriori erfordert binäre Item-Präsenzdaten. Kontinuierliche Variablen müssen vor der Kodierung als Items in Bins diskretisiert werden (z. B. Alter in niedrig/mittel/hoch). Eine schlechte Diskretisierung kann die entdeckten Regeln stark verzerren, daher verdient die Binning-Strategie sorgfältige Überlegung.

Impliziert Apriori Kausalität zwischen Items?

Nein. Assoziationsregeln erfassen Kookkurrenz, nicht Kausalität oder Richtung. Eine Regel 'Brot → Butter' bedeutet, dass sie oft im selben Warenkorb vorkommen; sie bedeutet nicht, dass der Kauf von Brot jemanden zum Kauf von Butter veranlasst, noch dass die Beziehung in irgendeinem kausalen Sinne asymmetrisch ist.

Verwandte Methoden

Quellen

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Publikationsreferenz öffnen
    Kopiert.
  2. Apriori algorithm. Wikipedia.

    Publikationsreferenz öffnen
    Kopiert.