Der Apriori Algorithmus versucht Assoziationsregeln, also logische Zusammenhänge, aus Transaktionen in einer Datenbank zu erlernen. Das Ziel ist es häufig vorkommende Itemsets zu finden, also beispielsweise die Produkte, welche in der Datenbank häufig zusammen vorkommen.

Ein Beispiel zur Suche von Assoziationsregeln

Im Alltag begegnen uns sehr häufig Produktkombinationen, welche man im Bundle meist günstiger kaufen kann. In vielen Schnellrestaurants werden beispielsweise ein Hauptgericht zusammen mit einer Beilage und einem Getränk zu einem vergünstigten Preis verkauft. Das Prinzip dahinter ist immer dasselbe: Produkte, welche oft zusammen gekauft werden, werden zu einem günstigeren Preis angeboten, wenn man sie direkt im Bundle kauft. Das hat sich nicht nur bei Schnellrestaurants durchgesetzt. Es ist mittlerweile auch in Supermärkten oder in Mode Online Shops zu finden, da es zum einen dem Kunden den Einkauf erleichtert und bei den Verkäufern zu höheren Umsätzen führt.

Um solche Bundles finden zu können, wird unter anderem der Apriori Algorithmus genutzt. Dazu werden die Bestelldatenbänke der Anbieter durchsucht und versucht, Assoziationsregeln aufzustellen. Bevor wir mit dem genauen Ablauf des Algorithmus weitermachen können, müssen noch ein paar Begrifflichkeiten geklärt werden, welche in diesem Zusammenhang genutzt werden.

Welche Begrifflichkeiten werden genutzt?

Der Apriori Algorithmus nutzt einige Konzepte und Regeln, welche in unserem Sprachgebrauch nicht wirklich gebräuchlich sind. Deshalb erklären wir die wichtigsten an dieser Stelle kurz, bevor wir uns dem Ablauf des Algorithmus widmen können.

Was ist ein Itemset?

Eine Menge von Elementen wird als Itemset bezeichnet. Eine Menge mit k-Elementen wird auch als k-Itemset bezeichnet. Das Itemset muss mindestens aus zwei Elementen bestehen und kann beispielsweise den Warenkorb bei einem Einkauf repräsentieren. Der Einkauf im Supermarkt hätte zum Beispiel das Itemset bestehend aus Brot, Butter, Milch und Eiern.

Wie hängen Support und Konfidenz zusammen?

Bevor man nach häufig vorkommenden Bundles suchen kann, benötigen wir Kennzahlen, die messen, wie oft gewisse Itemsets zusammen gekauft werden. Dazu nutzt man die Konfidenz und den Support.

Der Support misst, wie oft ein Produkt relativ gekauft wird:

\(\) \[\text{Support (A)} = \frac{\text{Anzahl der Transaktionen in denen A vorkommt}}{\text{Anzahl aller Transaktionen}} \]

Die Konfidenz hingegen misst den Support für alle Transaktionen, die die Elemente A und B enthalten, und teilt sie durch den Support für A:

\(\) \[\text{Konfidenz (A + B)} = \frac{\text{Support (A∪B)}}{\text{Support (A)}} = \frac{\text{Anzahl der Transaktionen mit Element A und B}}{\text{Anzahl der Transaktionen mit Element A}} \]

Für einen Supermarkt würden sich diese Kennzahlen wie folgt berechnen:

Angenommen die Datenbank umfasst 500 Einkäufe insgesamt. In 300 Fällen umfasste der Einkauf auch eine Schokoladentafel. Der Support für Schokolade ist also:

\(\) \[\text{Support (Schokolade)} = \frac{300}{500} = 60 \% \]

In 100 Einkäufen wiederum in denen Schokolade gekauft wurde, wurde auch Milch gekauft. Die Konfidenz für Milch und Schokolade ergibt sich also aus:

\(\) \[\text{Konfidenz (Milch + Schokolade)} = \frac{100}{300} = 33,3 \% \]

Das bedeutet, dass in 60 % aller Transaktionen Schokolade gekauft wird. Wiederum in einem Drittel der “Schokoladen – Transaktionen” wird auch Milch gekauft.

Was ist eine Assoziationsregel?

Eine Assoziationsregel versucht gewisse Regelmäßigkeiten zwischen zwei oder mehr Elementen zu finden, welche ein vorgegebenes Level von Support und Konfidenz erreichen.

Was ist ein Frequent Itemset?

Ein Frequent Itemset ist eine Menge von Elementen, die häufig zusammen auftreten, und ein vorher definiertes Level an Support und Konfidenz erreichen. Mithilfe von Assoziationsregeln lassen sich Frequent Itemsets finden.

Wie funktioniert der Apriori Algorithmus?

Der Apriori Algorithmus ist eine der Methoden, um Frequent Itemsets in einem Datensatz zu finden. Er funktioniert in zwei Schritten, nämlich “Join” und “Prune”, welche iterativ, also mehrfach hintereinander, ausgeführt werden.

Join: In diesem Schritt werden Itemsets der Menge K gebildet. K steht hierbei für den Wiederholungsschritt.

Prune: In diesem Schritt werden alle Itemsets entfernt, welche die vorher festgelegte Supportschwelle nicht erreichen und deshalb als selten gesehen werden.

Der Apriori Algorithmus macht sich dabei die sogenannte Antimonotone Eigenschaft zunutze. In einfachen Worten besagt sie, dass sobald ein Itemset bestehend aus mehreren Element den Minimum Support nicht erreicht, dann erreichen auch alle Supersets (alle Sets bestehend aus Elementen des Itemsets) den minimalen Support nicht. Anhand unseres Beispiel bedeutet das, dass sobald das Itemset aus Milch und Kekse den Minimum Support nicht erreicht, dann kann das Set bestehend aus Milch, Kekse und Schokolade den minimalen Support auch nicht überschreiten.

In jeder neuen Iteration wird das Itemset um ein Element erweitert und die Schritte “Join” und “Prune” erneut ausgeführt. Der Algorithmus terminiert, wenn in einer Iteration kein neues Itemset mehr gefunden wird, sondern nur Itemsets aus dem vorherigen Schritt bestehen bleiben.

Apriori am Beispiel

Für unser Beispiel kommen wir nochmal auf unseren Supermarkt zu sprechen. In dessen Datenbank befinden sich insgesamt sechs Transaktionen.

Transaktion	Warenkorb
T_1	Milch, Schokolade, Nudeln
T_2	Schokolade, Nudeln, Reis
T_3	Reis, Brot
T_4	Milch, Schokolade, Reis
T_5	Milch, Schokolade, Nudeln, Brot
T_6	Milch, Schokolade, Nudeln, Reis

Für unsere Assoziationsregel wollen wir einen Support von 50 % und eine Konfidenz von 70 % erzielen. Diese Werte sind komplett frei wählbar.

Schritt 1 (K=1): Im ersten Schritt suchen wir Itemsets mit der Menge 1. Das heißt wir zählen wie oft die einzelnen Produkte insgesamt gekauft wurden. Das enstpricht dem Join-Schritt in der ersten Stufe.

Itemset	Anzahl Käufe
Milch	4
Schokolade	5
Nudeln	4
Reis	4
Brot	2

Schritt 2 (K=1): Nach dem Join-Schritt folgt der Prune-Schritt, in dem wir alle Itemsets entfernen, die den minimalen Support nicht erreichen. Wir haben einen Support von 50 % gewählt. Aufgrund der Formal für die Berechnung des Support bedeutet es, dass bei sechs Transaktionen das Itemset mindestens dreimal vorkommen muss, damit der Support erfüllt ist. Alle anderen Itemsets können gestrichen werden:

Itemset	Anzahl Käufe
Milch	4
Schokolade	5
Nudeln	4
Reis	4

Deshalb fällt das Produkt / Itemset “Brot” heraus, da es lediglich zweimal vorkommt.

Schritt 3 (K=2): Nachdem wir den Join- und Prune-Schritt durchgeführt haben, kommen wir in die zweite Stufe. Hier gilt, dass die Größe des Itemsets jetzt 2 ist. Die möglichen Itemsets ergeben sich aus der Kombination aus allen übrigen Produkten der vorherigen Stufen.

Itemset	Anzahl Käufe
Milch, Schokolade	4
Milch, Nudeln	3
Milch, Reis	2
Schokolade, Nudeln	4
Schokolade, Reis	3
Nudeln, Reis	2

Schritt 4 (K=2): Im Prune-Schritt werden wieder die Itemssets entfernt, welche den minimalen Support von drei nicht erreichen. Dadurch fallen die Kombinationen (Milch, Reis) und (Nudeln, Reis) raus:

Itemset	Anzahl Käufe
Milch, Schokolade	4
Milch, Nudeln	3
Schokolade, Nudeln	4
Schokolade, Reis	3

Schritt 5 (K=3): In diesem Schritt bilden wir die Itemsets mit der Menge 3. Das sind die Mengen, welche sich aus den übrigen Produkten bilden lassen:

Itemset	Anzahl Käufe
Milch, Schokolade, Nudeln	–
Milch, Schokolade, Reis	–
Milch, Nudeln, Reis	–
Nudeln, Schokolade, Reis	–

Für diese Itemsets haben wir keinen einzigen Kauf, jedoch kann man trotzdem prüfen, ob die Itemsets den Support erreichen würden. Dazu machen wir uns die Antimonotone Eigenschaft zunutze. Hierbei fällt auf, dass das Itemset (Milch, Schokolade, Reis) aus den Subsets (Milch, Schokolade), (Schokolade, Reis) und (Milch, Reis) besteht. Das Itemset (Milch, Reis) konnte aber den Support nicht erreichen, sodass auch das größere Itemset (Milch, Schokolade, Reis) nicht häufig vorkommen kann, auch wenn es dafür keine Zahlen gibt.

Mit derselben Begründung fallen auch die Itemsets (Milch, Nudeln, Reis) und (Nudeln, Schokolade, Reis) heraus, da das Itemset (Nudeln, Reis) nicht oft genug vorkommt. Das letzte übrig gebliebene Itemset kann jetzt genutzt werden, um mithilfe der Konfidenz Assoziationsregeln abzuleiten.

Schritt 6: Folgende Assoziationsregeln können wir prüfen:

• (Milch, Schokolade) -> Nudeln:

\(\) \[\text{Konfidenz (Milch, Schokolade)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Milch, Schokolade)}} = \frac{3}{4} = 75 \%\]

(Milch, Nudeln) -> Schokolade:

\(\) \[\text{Konfidenz (Milch, Nudeln)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Milch, Nudeln)}} = \frac{3}{3} = 100 \%\]

(Schokolade, Nudeln) -> Milch:

\(\) \[\text{Konfidenz (Schokolade, Nudeln)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Schokolade, Nudeln)}} = \frac{3}{4} = 75 \%\]

(Milch) -> (Schokolade, Nudeln):

\(\) \[\text{Konfidenz (Milch)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Milch)}} = \frac{3}{4} = 75 \%\]

(Schokolade) -> (Milch, Nudeln):

\(\) \[\text{Konfidenz (Schokolade)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Schokolade)}} = \frac{3}{5} = 60 \%\]

Nudeln -> (Milch, Schokolade):

\(\) \[\text{Konfidenz (Nudeln)} = \frac{\text{Support (Milch, Schokolade, Nudeln)}}{\text{Support(Nudeln)}} = \frac{3}{4} = 75 \%\]

Nach der Durchführung des Apriori Algorithmus ergeben sich insgesamt fünf Assoziationsregeln, die unserem Konfidenzlevel von 70 % standhalten. Dazu gehört unter anderem die Regel “(Milch, Schokolade) -> (Nudeln)”. Diese bedeutet, dass wenn bereits Milch und Schokolade gekauft wurden, dann ist auch der Kauf von Nudeln sehr wahrscheinlich.

Welche Vor- und Nachteile hat die Nutzung des Apriori Algorithmus?

Der Apriori Algorithmus ist eine gute Möglichkeit, um Assoziationsregeln in großen Datenbanken mit vielen Transaktionen zu finden. Darüber hinaus sind die Schritte “Join” und “Prune” relativ einfach in Programmiersprachen, wie Python, zu entwickeln. Zusätzlich gibt es auch Module, welche den Import des Apriori Algorithmus noch weiter vereinfachen.

Jedoch wird der Algorithmus bei großen Datenbanken sehr rechenintensiv. Wie bei unserem Beispiel bereits klar wurde, müssen viele Kombinationen und Schritte berechnet werden, die bereits bei unserem einfachen Beispiel viel Zeit und Ressourcen in Anspruch nehmen. Vor der Umsetzung muss also sichergestellt werden, dass sich der Aufwand lohnt.

Welche Anwendungen nutzen diesen Algorithmus?

Es gibt verschiedene Anwendungen in denen Assoziationsregeln gesucht werden und somit auch der Apriori Algorithmus genutzt wird. Hier sind gewisse Themenfelder in denen Assoziationen gesucht werden:

• Bildung: Im Bildungsbereich werden Assoziationen gesucht, wenn man beispielsweise herausfinden will, warum manche Schüler oder Studenten in Fächern besser abschneiden als andere.
• Medizin: Bei der Entwicklung von neuen Medikamenten werden Assoziationsregeln untersucht, um festzustellen, wie ein neues Medikament im Zusammenspiel mit körperlichen Merkmalen wirkt. Dazu wird das Sample, welches das Medikament getestet hat, genauer untersucht.
• Biologie: Auf der ganzen Welt werden Waldbrände immer häufiger. Deshalb wird aktuell untersucht, welche Frühwarnfaktoren, wie extreme Trockenheit oder hohe Temperaturen, in Zusammenhang mit Waldbränden stehen, um diese möglichst frühzeitig erkennen und vorbeugen zu können.
• E-Commerce & Recommendation: Das klassische Beispiel für den Apriori Algorithmus haben wir in diesem Beitrag kennengelernt: die Warenkorbanalyse. Anhand des Kaufverhaltens von früheren Kunden wird versucht, Assoziationen zwischen Produkten zu erkennen und diese dann für Produktempfehlungen zu nutzen.

Wie kann der Apriori Algorithmus verbessert werden?

Bei einer großen Datenbank kann der Apriori Algorithmus sehr ineffizient sein und viel Zeit in Anspruch nehmen. Deshalb gibt es aktuell einige Methoden, die helfen sollen, den Algorithmus effizienter und schneller zu machen. Dazu gehören:

1. Hash-based Itemset Counting: Bei dieser Methode wird versucht die Erstellung der Itemsets zu beschleunigen. Dazu nutzt man eine sogenannte Hash Tabelle, die jedem Produkt oder Transaktion eine eindeutige Nummer gibt. Dadurch müssen nicht speicherintensive Strings mitgezogen und verarbeitet werden, sondern die effizienteren Hashes.
2. Transaction Reduction: Vor der Durchführung des Apriori Algorithmus, wird die Datenbank nach wiederholten Transaktionen durchsucht, welche dann ausgeschlossen werden. Genauso werden bereits frühzeitig seltene Transaktionen herausgefiltert, da diese für die Berechnung des Algorithmus keine Rolle spielen.
3. Partitioning: Für diese Methode wird die Anzahl der Datenbankscans deutlich reduziert. Der Grundgedanke hierbei ist, dass ein Itemset nur dann häufig sein kann, wenn es in mindestens einer von zwei Datenbankpartitionen vorkommt. Somit muss die komplette Datenbank lediglich zweimal durchlaufen werden, was deutlich effizienter sein kann.
4. Sampling: Statt häufige Itemsets in der gesamten Datenbank zu suchen, wird bei diesem Ansatz lediglich eine Untersuchungseinheit der Datenbank genommen und untersucht. Dabei besteht jedoch die Gefahr, dass Itemsets verloren gehen, welche eigentlich häufig vorkommen. Um dieses Risiko zu umgehen, sollte man einen vergleichsweise niedrigen Support nutzen.
5. Dynamic Itemset Counting: Bei dieser Methode können bereits beim Scannen der Datenbank neue potenzielle Itemsets gefunden werden.

Das solltest Du mitnehmen

• Der Apriori Algorithmus versucht Assoziationsregeln, also logische Zusammenhänge, aus Transaktionen in einer Datenbank zu erlernen. Das Ziel ist es häufig vorkommende Itemsets zu finden, also beispielsweise die Produkte, welche in der Datenbank häufig zusammen vorkommen.
• Der Apriori Algorithmus funktioniert in zwei Schritten (“Join” und “Prune”), welche iterativ hintereinander ausgeführt werden.
• In jedem Schritt wird ein Itemset erstellt, welches um ein Produkt größer ist, als im vorherigen Schritt (“Join”). Dann wird untersucht welches dieser Itemsets den vorher definierten Support erfüllt und somit bestehen bleibt.
• Obwohl der Apriori Algorithmus relativ einfach zu verstehen und implementieren ist, kann er bei großen Datenbanken sehr ineffizient sein und viel Rechenleistung benötigen. Deshalb gibt es bereits einige Ansätze, um die Performance des Algorithmus zu verbessern.
• In der Praxis wird der Apriori Algorithmus immer dann genutzt, wenn Assoziationsregeln gesucht werden. Dazu zählen beispielsweise die Medizin, Biologie oder der E-Commerce.

Andere Beiträge zum Thema Apriori

• Ein interessantes Paper zur Verbesserung des Apriori Algorithmus findest Du hier.