Apriori-Algorithmus | Online Marketing Basics

Der Apriori-Algorithmus wird im Rahmen einer Assoziationsanalyse durchgeführt. Es wird versucht, logische Zusammenhänge zwischen Objekten, beispielsweise Waren in verschiedenen Warenkörbe, zu entdecken. Die Begriffe Prämisse und Konklusion sind an dieser Stelle wichtig. Es gilt folgender Zusammenhang: Ia -> Ib, wobei Ia als Prämisse bezeichnet wird und Ib als Konklusion.

Ein einfaches Beispiel des Apriori Algorithmus

Für die Durchführung des Algorithmus muss im Schritt 0 ein Mindestsupport und eine Mindestkonfidenz festgelegt werden. Die beiden Begriffe sind essentiell für den Algorithmus. Umgangssprachlich formuliert stellt der Support den prozentualen Anteil dar, wie oft ein Item oder auch Itempaar unter allen beobachteten Transaktionen aufzufinden ist. Für den Algorithmus muss ein Wert festgelegt werden, der eine Assoziation für bedeutungsvoll deklariert. Im Verlauf des Textes wird dies vermutlich klarer mit einem Zahlenbeispiel.

Wir setzen im Rahmen dieses Beispiels den Mindestsupport 40%. Die Mindestkonfidenz beträgt 60%.

Nutzerdaten für ein Apriori-Beispiel

Wir gehen von fünf Nutzern aus, die eine Website besuchen. Jeder Nutzer besucht dabei verschiedene (Unter-)seiten. Wir wollen nun logische Zusammenhänge innerhalb der Verkehrsdaten finden. Für das bessere Verständnis konkretisieren wir das Beispiel noch mehr:

Seite 1 sei die Hauptseite.
Seite 2 sei eine Themenseite über Erkältung und Grippe.
Seite 3 sei eine konversionsorientierte Landingpage für Nasenspray.
Seite 4 sei eine Themenseite zu Behandlungsmethoden für akute Erkältungen.
Seite 5 sei eine Unternehmenspräsentationsseite („Über uns“).

Das Unternehmen stellt die Frage: Wir haben sehr viel Zeit in die Bearbeitung der Seite 4 gesteckt. Wenn jemand unser Nasenspray kaufen will, also eine Kaufintention über den Besuch der Seite 5 äußert, hat er sich dafür vorher Seite 4 angesehen? Ist Seite 4 also ein entscheidender Informationslieferant im Kaufprozess?

Es wurden zur Vereinfachung lediglich fünf Nutzer und ihr Nutzerverhalten aufgezeichnet. In der Praxis sind natürlich mehr Daten hilfreich.

Apriori-Algorithmus
Abbildung 1: Erste Iteration

Nutzer sind in der ersten Spalte notiert. Jede Zeile stellt das Nutzerverhalten dar. Der Support berechnet sich im ersten Schritt einfach. Wie oft wurde die Hauptseite (Seite 1, q1) nutzerübergreifend aufgerufen? Exakt zweimal. Von Nutzer 1 und Nutzer 3. Da wird insgesamt fünf Nutzer haben, ist die Seite 1 also in 40% (2 von 5 Nutzer) aufgerufen wurde. Der Support wird für alle Seiten berechnet. Seite 5 („Über uns“, q5) wurde lediglich von einem Nutzer besucht. Zu wenig! Nur 20% (1 von 5 Nutzer) hat die Seite besucht. Der Mindestsupport liegt bei 40%. Wir betrachten Seite 5 überhaupt nicht mehr in der Analyse.

Seite 1-4 haben den Mindestsupport. Der nächste Schritt ist ebenso trivial. Aus allen Seiten, die den Mindestsupport geschafft haben, werden 2er-Pärchen gebildet.

{q1,q2,q3,q4}

{q1, q2} -> Hauptseite und die Themenseite treten gemeinsam auf.
{q1, q3} -> Hauptseite und Landingpage treten gemeinsam auf.
{q1, q4} -> usw.
{q2,q3}
{q2,q4}
{q3,q4}

Erneut legen wir eine Tabelle an. Wir wollen nun überprüfen, ob die Pärchen häufiger zusammen auftreten.

Apriori-Algorithmus

Abbildung 2: Test der Pärchen

Der Mindestsupport bleibt. Die Hauptseite mit der Themenseite, einer anderen Themenseite sowie der Landingpage wurden nur insgesamt in einem von fünf Fällen zusammen aufgerufen. Die Pärchen sind nur jeweils in 20% der Fällen aufgetaucht. Reicht nicht! Keine weitere Betrachtung, kein logischer Zusammenhang. Die Pärchen Seite 2 + 3, Seite 2 + 4 und Seite 3 + 4 schaffen den Mindestsupport. Jetzt können wir schon die ersten Regeln finden. Die Pärchen, die wir nun überprüfen, sind nun die folgenden. Jedes Pärchen beinhaltet zwei Assoziationsregeln, die es zu überprüfen gilt.

{q2,q3}: q2 -> q3? q3 -> q2? (Wenn Seite 2 auftritt, tritt dann Seite 3 auf? Und umgekehrt)
{q2,q4}: q2 -> q4? q4 -> q2? (Wenn Seite 2 auftritt, tritt dann Seite 4 auf? Und umgekehrt)
{q3,q4}: q3 -> q4? q4 -> q3? (Wenn Seite 3 auftritt, tritt dann Seite 4 auf? Und umgekehrt)

Warum werden beide Richtung überprüft? Die Richtung ist wichtig, da die Formell der Konfidenz dies verlangt. Das wird im Folgenden erklärt:

Ich möchte auf Formeln an dieser Stelle verzichten. Denn die Berechnung ist trivial: Die Konfidenz kann stets mit dem gleichen Gedanken entwickelt werden:

Prämisse -> Konklusion

Wie oft treten Prämisse und Konklusion gemeinsam auf? Alle Werte können der Abbildung 2 entnommen werden. {q2,q3} gibt es in zwei von fünf Fällen. {q2,q4} in drei von fünf Fällen. {q3,q4} in drei von fünf Fällen. Das sind unsere Zählerwerte im Bruch, den wir bilden. Für q2 -> q3 und q3 -> q2 ist der Zähler also zwei. Im Nenner steht die Anzahl der Auftreten der Prämisse! Prämisse ist stets das Item vor dem . Die Werte können hier der Abbildung 1 entnommen werden. Das sind unsere Nennerwerte. Liegt der Bruch prozentual über der Mindestkonfidenz von 60%, haben wir Regeln gefunden. Und tatsächlich lassen sich Assoziationen finden. In 100% der Fälle sogar, ruft ein Nutzer der Website Seite 4 auf, wenn er Seite 2 aufgerufen hat. Hier lässt sich nun vielseitig interpretieren. Ist der Inhalte zu schwach von Seite 2, sodass zusätzliche Informationen von Seite 4 benötigt werden?

Apriori-Algorithmus

Abbildung 3: Die ersten Konfidenzen

Gemäß dem Algorithmus müssen nur die Items-Sets aus der vorherigen Iteration berücksichtigt werden, für die die Konfidenz unterschiedlich ist in die jeweiligen Richtungen. Für den Folgeschritt hat das aber keine Bedeutung, da wir lediglich nur noch eine Iteration vor uns haben.

Apriori-Algorithmus

Abbildung 4: Unterschiedliche oder identische Konfidenzen

In Abbildung 4 haben wir bis auf q3 -> q2 fünf neue Regeln gefunden. Nun überprüfen wir 3er-Kombinationen. Es verbleibt lediglich eine zu überprüfende Menge, da Seite 1 und Seite 5 schon längst in der ersten Iteration entfernt wurden.

Apriori-Algorithmus

Abbildung 5: 3er-Kombination überprüfen

Die 3er-Kombination schafft den Mindestsupport! In zwei von fünf Fällen sind die Seiten 2, 3 und 4 gemeinsam in einer einzelnen Nutzer-Session aufgerufen worden.

Wir überprüfen die Mindestkonfidenz für sechs Regeln:
{q2,q3,q4}: q2 -> q3,q4, q4,q3 -> q2?
{q2,q3,q4}: q3 -> q2,q4? q2,q4 -> q3?
{q2,q3,q4}: q4 -> q2,q3? q2,q3 -> q4?

Apriori-Algorithmus

Abbildung 6: Logiken überprüfen in der 3er-Kombination

Hier muss man genau hinsehen. q3,q4 -> q2 z.B. q3,q4 ist die Prämisse, d.h. hier muss der absolute Wert für das Pärchen aus Abbildung 2 genommen werden! Im Nenner steht also drei. Für alle 3er-Pärchen ist der Nenner gleich: zwei. Den die dreier Kombination taucht dreimal auf. Zwei Regeln schaffen den Konfidenzwert nicht.

Alle Assoziationsregeln in der Übersicht

q2 -> q3: Wenn die Themenunterseite zu Erkältungen und Grippe aufgerufen wird, dann wird mit einer Konfidenz von ca. 66,67% auch die Landingpage aufgeruft.

q2 -> q4: Wenn die Themenunterseite zu Erkältungen und Grippe aufgeruft wird, dann wird auch die Themenseite zu Behandlungsmethoden aufgerufen (100% Konfidenz!)

q4 -> q2: Mit einer Konfidenz von 75% passiert ein Nutzer die Themenseite von Behandlungsmethoden und im Anschluss die Themenunterseite zu Erkältung und Grippe.

q3 -> q4: Mit einer Konfidenz von 75% wird die Themenseite zu Behandlungsmethoden aufgerufen, wenn zuvor die Landingpage besucht wurde.

q4 -> q3: Mit einer Konfidenz von 75% wird die Landingpage besucht, wenn vorher die Themenseite zu Behandlungsmethoden aufgerufen wurde.

q2 -> q3,q4: Mit einer Konfidenz von 66,67% werden Landing-Page und Themenseite zu Behandlungsmethoden aufgerufen, wenn zuvor die Themenseite zu Erkältung und Grippe aufgerufen wurde.

q3,q4 -> q2: Mit einer Konfidenz von 66,67% wird die Themenseite zu Erkältung und Grippe jedes Mal aufgerufen, wenn die Landingpage und die Themenseite zu Behandlungsmethoden aufgerufen wurde.

q2,q4 -> q3: Mit einer Konfidenz von 66,67% wird die Landingpage jedes Mal aufgerufen, wenn die Themenseite zu Erkältung und Grippe sowie die Themenseite zu Behandlungsmethoden aufgerufen wurde.

q2,q3 -> q4: In 100% der Fälle: Wird die Landing-Page und die Themenseite zu Erkältung aufgerufen, wird auch die Themenseite zu Behandlungsmethoden aufgerufen.

Anwendung des Apriori-Algorithmus in der Praxis

skyscraper verwendet den Apriori-Algorithmus, um eine Assoziationsanalyse von Webtraffic durchzuführen. Bei geschickter Konfiguration können beispielsweise Google Analytics Daten verwendet werden

Marvin Jörs

Marvin Jörs ist Gründer und geschäftsführender Gesellschafter der Skyscraper Marketing UG. Bereits mit 14 Jahren absolvierte Jörs sein erstes Schulpraktikum bei der Deutschen Telekom mit Aspekten aus der Suchmaschinenoptimierung. Seitdem erfolgten mehrere berufliche Stationen sowie Aktivitäten als freiberuflicher Webdesigner. Er hat an der Technischen Universität in Darmstadt einen B.Sc. in Wirtschaftsinformatik abgeschlossen.