Zum Inhalt springen
Zurück zu den Suchergebnissen

Assoziationsregel-Mining (Apriori)

Eingeführt von
Rakesh Agrawal & Ramakrishnan Srikant
Jahr
1994
Typ
Unsupervised pattern discovery 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?

Assoziationsregel-Mining ist eine unüberwachte Data-Mining-Technik, die Muster des gemeinsamen Auftretens (Co-Occurrence) zwischen Elementen in Transaktionsdatensätzen aufdeckt.

Formell 1993 von Agrawal, Imieliński und Swami eingeführt und 1994 mit dem wegweisenden Apriori-Algorithmus von Agrawal und Srikant verfeinert, identifiziert sie Regeln der Form X ⇒ Y – was bedeutet, dass Transaktionen, die das Itemset X enthalten, tendenziell auch das Itemset Y enthalten – quantifiziert durch Support, Konfidenz und Lift.

Die Intuition hinter der Methode

Stellen Sie sich ein Protokoll von Supermarktbelegen vor: Wenn Tausende von Kunden, die Brot und Butter kaufen, auch Milch kaufen, verdient dieses Muster Aufmerksamkeit. Assoziationsregel-Mining arbeitet wie ein akribischer Bibliothekar, der jeden Beleg durchforstet, zählt, wie oft Elementkombinationen zusammen auftreten, und die Kombinationen aufdeckt, die eine Mindesthäufigkeit überschreiten. Sobald häufige Gruppen gefunden wurden, fragt der Algorithmus: Wenn Sie diese Elemente bereits haben, wie zuverlässig sagt dies das nächste Element voraus? Diese Zwei-Pass-Logik von Häufigkeit-dann-Konfidenz ist das Herzstück von Apriori.

Geschichte

Die grundlegende Arbeit von Agrawal, Imieliński und Swami (1993) definierte das Assoziationsregelproblem im Kontext von Supermarkt-Transaktionsdaten. Agrawal und Srikants VLDB-Paper von 1994 stellte den Apriori-Algorithmus und seine effiziente Pruning-Strategie vor, wodurch groß angelegtes Mining praktikabel wurde. Spätere Arbeiten führten FP-Growth (Han et al., 2000) ein, das die Kandidatengenerierung vollständig vermeidet, und ECLAT, das im vertikalen Datenformat miniert – wodurch eine reiche algorithmische Familie etabliert wurde, die heute zentral für Data-Mining-Lehrpläne ist.

Wann wird sie eingesetzt?

Assoziationsregel-Mining eignet sich für große Transaktionsdatensätze, bei denen das Ziel darin besteht, Co-Occurrence-Muster ohne eine vordefinierte Zielvariable zu entdecken. Es wird davon ausgegangen, dass Elemente pro Transaktion binär sind (vorhanden/nicht vorhanden). Es ist geeignet für die Warenkorbanalyse, Empfehlungssysteme, Web-Clickstream-Analyse und die Entdeckung medizinischer Koinzidenzdiagnosen. Es ist ungeeignet für kontinuierliche oder ordinale Daten, es sei denn, diese werden vordiskretisiert, für Datensätze mit sehr hoher Dimensionalität (exponentieller Kandidatenraum) oder wenn kausale statt assoziativer Inferenz erforderlich ist. Alternativen umfassen FP-Growth für eine schnellere Aufzählung häufiger Itemsets und Sequenz-Mining, wenn die zeitliche Reihenfolge wichtig ist.

Grenzen und Hinweise

  • Exponentieller Kandidatenraum: Die Anzahl der Regeln wächst kombinatorisch mit der Anzahl der unterschiedlichen Elemente.
  • Das Support-Konfidenz-Framework kann zu irreführenden Regeln führen, wenn die Basisraten der Elemente stark variieren (Lift-Anpassung erforderlich).
  • Das binäre Transaktionsmodell erfordert die Diskretisierung kontinuierlicher Variablen, was zu Informationsverlust führt.
  • Hohe Mindest-Support-Schwellenwerte übersehen seltene, aber wertvolle Regeln; niedrige Schwellenwerte erzeugen Tausende von trivialen Regeln.

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

Stärken

  • Vollständig unüberwacht: keine gelabelten Daten oder vordefiniertes Ziel erforderlich.
  • Interpretierbare Ausgabe: Regeln sind menschenlesbare Wenn-Dann-Anweisungen mit quantifiziertem Support und Konfidenz.
  • Skalierbar durch Apriori-Pruning; die FP-Growth-Variante eliminiert wiederholte Datenbankscans vollständig.
  • Domänenunabhängig: angewendet in Einzelhandel, Gesundheitswesen, Webanalyse und Bioinformatik.

Anwendungen

  • Einzelhandel: Produktplatzierung und Cross-Selling-Empfehlungen aus Point-of-Sale-Transaktionsprotokollen.
  • Gesundheitswesen: Co-Occurrence-Analyse von Diagnosen, Prozeduren oder Medikamenten in elektronischen Gesundheitsakten.
  • Webanalyse: Entdeckung von Clickstream-Mustern für Seitenempfehlungen und Navigationsoptimierung.
  • Bioinformatik: Identifizierung von koexprimierten Gensätzen und Proteininteraktionsmotiven.
  • Cybersicherheit: Erkennung korrelierter Netzwerkereignisse, die auf Intrusion-Muster hindeuten.

So funktioniert es

So funktioniert es

1

Der Algorithmus durchsucht die Transaktionsdatenbank D, um zu zählen, wie oft jedes Itemset X vorkommt. Ein Itemset wird nur dann als häufig deklariert – und in L_k platziert –, wenn sein Support (der Anteil der Transaktionen, die es enthalten) den benutzerdefinierten Mindest-Support-Schwellenwert σ_min erreicht oder überschreitet. Der Prozess beginnt mit einzelnen Elementen (k=1) und baut iterativ größere Kandidatensätze auf.

Formel
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

Die Anti-Monotonie-Eigenschaft des Supports besagt, dass jede Teilmenge eines häufigen Itemsets selbst häufig sein muss. Apriori nutzt dies aus, indem es jedes Kandidaten-k-Itemset verwirft, dessen (k-1)-Teilmengen nicht alle im verifizierten häufigen Satz L_{k-1} enthalten sind. Dies reduziert den Suchraum drastisch und vermeidet teure Datenbankscans für Itemsets, die unmöglich häufig sein können.

Formel
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

Aus jedem häufigen Itemset X ∪ Y generiert der Algorithmus Regeln X ⇒ Y, wobei X und Y disjunkte Teilmengen sind. Eine Regel wird nur beibehalten, wenn ihre Konfidenz – die bedingte Wahrscheinlichkeit von Y gegeben X, berechnet als support(X ∪ Y) / support(X) – den Mindest-Konfidenz-Schwellenwert γ_min erreicht oder überschreitet. Dieser Schritt wandelt rohes gemeinsames Auftreten in gerichtete prädiktive Aussagen um.

Formel
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

Beibehaltene Regeln werden nach Lift geordnet und gefiltert, welcher misst, wie viel wahrscheinlicher Y mit X auftritt, als es zufällig der Fall wäre. Lift > 1 deutet auf eine positive Korrelation jenseits der Unabhängigkeit hin; Lift = 1 deutet auf Unabhängigkeit hin; Lift < 1 deutet auf eine negative Korrelation hin. Zusätzliche Interessantheitsmaße wie Conviction und Leverage können den Regelsatz für den praktischen Einsatz weiter verfeinern.

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

Häufige Fallstricke

  • Ein zu niedrig eingestellter Mindest-Support überflutet den Analysten mit scheinbaren Regeln; die Schwellenwertauswahl erfordert Domänenwissen oder Kreuzvalidierung.
  • Verwechslung von statistischer Assoziation mit Kausalität: Ein hoher Lift impliziert nicht, dass X Y verursacht.
  • Ignorieren der Elementhäufigkeitsverteilung: Häufige Elemente dominieren Regeln und verdrängen bedeutungsvolle Assoziationen seltener Elemente.
  • Behandlung von Konfidenz allein als Qualitätsmetrik; eine Regel mit hoher Konfidenz, aber geringem Lift kann nicht besser abschneiden als der Zufall.

Häufig gestellte Fragen

Was ist der Unterschied zwischen Support, Konfidenz und Lift?

Support misst, wie häufig ein Itemset im gesamten Datensatz vorkommt. Konfidenz misst die bedingte Wahrscheinlichkeit des Konsequens gegeben das Antezedens. Lift normalisiert die Konfidenz durch die marginale Häufigkeit des Konsequens und zeigt, ob das gemeinsame Auftreten das übersteigt, was unter Unabhängigkeit zu erwarten wäre. Alle drei Metriken werden zusammen für eine robuste Regelauswertung benötigt.

Wie reduziert der Apriori-Algorithmus den Rechenaufwand?

Apriori nutzt die Anti-Monotonie-Eigenschaft aus: Wenn ein Itemset selten ist, müssen auch alle seine Obermengen selten sein. Indem der Algorithmus jeden Kandidaten verwirft, dessen Teilmengen nicht alle als häufig verifiziert sind, beschneidet er große Teile des Suchraums vor dem Zählen, wodurch die Anzahl der erforderlichen Datenbankdurchläufe im Vergleich zur Brute-Force-Aufzählung drastisch reduziert wird.

Wann sollte ich FP-Growth anstelle von Apriori verwenden?

FP-Growth wird bevorzugt, wenn der Datensatz groß und der Mindest-Support-Schwellenwert niedrig ist, da er die Transaktionsdatenbank in eine kompakte FP-Baumstruktur komprimiert und Muster direkt ohne explizite Kandidatengenerierung miniert. Dies eliminiert wiederholte vollständige Datenbankscans, wodurch es auf dichten Datensätzen mit vielen häufigen Itemsets wesentlich schneller ist als Apriori.

Verwandte Methoden

Quellen

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    DOI-Referenz öffnen
    Kopiert.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

    Publikationsreferenz öffnen
    Kopiert.