Einzelhändler wollten wissen, welche Produkte zusammen gekauft werden, aber die Zahl der möglichen Artikelkombinationen wuchs exponentiell mit der Zahl der SKUs.
Apriori, veröffentlicht 1994, nutzt eine Eigenschaft aus: Jede Obermenge eines seltenen Item-Sets muss selbst selten sein. Es zählt einzelne Artikel, behält die häufigen, erweitert sie zu Paaren und wiederholt dies, sodass es niemals einen Kandidaten zählt, dessen Elternteil bereits gescheitert ist.
Der Trick verwandelt eine Suche, die schnell unüberschaubar wird, in eine, die nur die kleine Front der häufigen Mengen berührt. Er machte die Warenkorbanalyse zu einer praktischen Datenbankabfrage.
Wenn eine Menge selten ist, ist jede Obermenge von ihr ebenfalls selten
Die Abwärtsabgeschlossenheit beschneidet die Suche, bevor sie wächst, sodass die Laufzeit den häufigen Mengen folgt, nicht allen Mengen.
Ein Datenbankscan pro Ebene hält den Speicher auf die Kandidatenmengen beschränkt.
Es liefert exakte häufige Mengen, keine Heuristik und keine stichprobenbasierte Näherung.
Dieselbe Beschneidung lässt sich auf Sequenz- und Muster-Mining über Warenkörbe hinaus verallgemeinern.
Bevor man einen riesigen Raum durchsucht, sollte man nach einer monotonen Eigenschaft suchen, die es erlaubt, ganze Zweige auf einmal zu verwerfen. Eine Regel, die eine Region ausschließt, verkleinert die Suche von exponentiell auf linear.
Apriori wurde zum kanonischen Assoziationsregel-Algorithmus und zu einer Standardlektion im Data Mining. Es begründete das Feld, das Empfehlungs-, Sortiments- und Cross-Sell-Analysen antreibt, sowie später fpgrowth und andere Methoden, die seine Scans reduzieren.
DEN BELEGEN FOLGEN
Die Quellen
- Fast Algorithms for Mining Association Rules in Large Databases VLDB 1994 · vldb.org
- What is the Apriori algorithm? IBM Think · ibm.com