🧺 Warenkorbanalyse — Apriori-Algorithmus live

Apriori ist ein klassischer Algorithmus (Agrawal & Srikant, 1994) zur Analyse häufiger Itemsets und Assoziationsregeln aus Transaktionsdaten wie Warenkörben. Er baut häufige Itemsets Schritt für Schritt auf: zunächst werden einzelne Artikel gezählt, dann Paare, dann Dreiergruppen und so weiter, wobei alles unterhalb eines Mindest-Support-Schwellenwerts auf jeder Stufe verworfen wird, bevor es jemals zum Aufbau größerer Kandidaten verwendet wird. Genau dieses stufenweise Aussortieren ermöglicht es, auch bei großen Artikelkatalogen zu skalieren, ohne jemals jede mögliche Kombination explizit aufzuzählen.

Support(X) ist schlicht der Anteil aller Transaktionen, die das Itemset X enthalten — ein Maß dafür, wie verbreitet es ist. Konfidenz(A→B) = Support(A∪B) / Support(A) ist die bedingte Wahrscheinlichkeit, dass ein Warenkorb B enthält, gegeben dass er bereits A enthält. Lift(A→B) = Konfidenz(A→B) / Support(B) vergleicht diese bedingte Wahrscheinlichkeit mit der Grundhäufigkeit von B: Ein Lift größer als 1 bedeutet, dass A B wahrscheinlicher macht als der Zufall, ein Lift nahe 1 bedeutet, dass beide im Wesentlichen unabhängig sind, und ein Lift unter 1 bedeutet, dass A B tatsächlich unwahrscheinlicher macht.

Apriori beruht auf der Eigenschaft der abwärtsgerichteten Abgeschlossenheit: Wenn ein Itemset häufig ist, muss auch jede seiner Teilmengen häufig sein, da jede Transaktion, die das vollständige Itemset enthält, auch jede Teilmenge enthält. Die Umkehrung davon ist die Ausschlussregel — wenn auch nur eine (k−1)-Teilmenge eines k-elementigen Kandidaten nicht häufig ist, kann der Kandidat unmöglich häufig sein und wird verworfen, bevor auch nur eine einzige Transaktion durchsucht wird. Ohne dieses Aussortieren würde die Anzahl der Kandidaten-Itemsets mit der Katalogsgröße kombinatorisch wachsen; mit ihm werden nur Kombinationen aus bereits häufigen Bausteinen überhaupt getestet.

Sobald ein häufiges Itemset mit mindestens zwei Elementen gefunden wurde, erzeugt jede Möglichkeit, es in einen nicht-leeren Vordersatz A und den verbleibenden Nachsatz B aufzuteilen, eine Kandidatenregel A→B. Ihr Support ist einfach der Support des Itemsets selbst; ihre Konfidenz und ihr Lift werden aus den Supports von A und B berechnet, die bereits während des Minings gemessen wurden. Die Regeln werden anschließend gefiltert, sodass nur diejenigen erhalten bleiben, die einen Mindest-Konfidenz-Schwellenwert erfüllen, da ein häufiges Itemset nicht garantiert, dass eine bestimmte Aufteilung davon eine starke, vorhersagekräftige Regel ist.

Der Mindest-Support bestimmt, wie weit das stufenweise Wachstum der Itemsets reicht: Erhöht man ihn, überleben auf jeder Stufe nur die stärksten, häufigsten Kombinationen, sodass das Mining nach ein oder zwei Stufen endet; senkt man ihn, überleben auch seltenere Kombinationen, tiefere Stufen werden erkundet, und sowohl die Laufzeit als auch die schiere Anzahl der Kandidaten-Itemsets steigen deutlich an. Die Mindest-Konfidenz wird erst danach angewendet, rein als Filter auf die aus den gefundenen Itemsets abgeleiteten Regeln — erhöht man sie, werden schwache oder zufällige A→B-Aufteilungen verworfen, während nur die einseitigsten, vorhersagekräftigsten Richtungen des Itemsets erhalten bleiben.

Das Mining ist echt. Der Simulator erzeugt eine Menge synthetischer Einkaufstransaktionen mit eingebauter, echter Ko-Okkurrenz-Struktur (bestimmte Artikel werden absichtlich so gestaltet, dass sie wahrscheinlich gemeinsam auftreten), zählt dann Artikel- und Itemset-Vorkommen direkt über diese Transaktionsliste, wendet das übliche Apriori-Verfahren aus Verknüpfen und Aussortieren Schritt für Schritt an und berechnet Konfidenz und Lift aus den tatsächlich gemessenen Supports — nichts ist skriptgesteuert oder vorgetäuscht. Das Verschieben der Regler führt den gesamten Algorithmus von Grund auf über dieselben Transaktionen erneut aus.