Die Assoziationsanalyse gehört zum Standardwerkzeug eines jeden Datenanalysten. Sie wird typischerweise in der Warenkorbanalyse eingesetzt, denn mit ihr lassen sich Aussagen über das wahrscheinliche Kaufverhalten von Kunden treffen. Eine Assoziationsregel folgt dabei immer dem Schema: „Wenn A, dann B“ und gibt dazu eine Wahrscheinlichkeit an. Im folgenden Artikel erkläre ich dir alle wichtigen Begriffe in den Zusammenhang und gebe dir außerdem ein Beispiel für eine Assoziationsanalyse nach dem Apriori-Algorithmus.
Einführung in die Assoziationsanalyse
Assoziationsanalysen werden häufig in der Warenkorbanalyse eingesetzt. Du kannst dir den Sinn ganz einfach vom Begriff herleiten: „Wenn ich an A denke, denke ich auch an B“, so funktioniert eine Assoziation klassischerweise. In der Assoziationsanalyse geht es deshalb darum, Verbindungen zwischen verschiedenen „Items“, zum Beispiel verschiedenen Produkten zu finden, um dadurch Zusammenhänge zwischen diesen Produkten aufzudecken. Eine Assoziationsregel folgt dabei immer dem Schema: Prämisse (body) –> Schlußfolgerung (head).
Nehmen wir zu Beginn ein einfaches Beispiel für eine Assoziationsregel:
- 94 Prozent aller Kunden, die Spaghetti kaufen, kaufen auch Pesto
- oder anders ausgedrückt {Spaghetti} –> {Pesto} [Konfindenz: 94%]
- 89 Prozent aller Kunden, die Blumenerde und Dünger kaufen, kaufen auch einen Topf
- oder anders ausgedrückt {Blumenerde, Dünger} –> {Blumentopf} [Konfindenz: 89%]
Aus diesen Regeln lassen sich dann Handlungsempfehlungen ableiten, etwa zum Aufbau eines Supermarkts (Welche Produkte sollten in räumlicher Nähe zueinander stehen?) oder weitere Kaufempfehlungen aussprechen (Kunden kauften auch).
JEDOCH: Die oben genannten, beispielhaften Regeln sind nicht sehr überraschend. Wen wundert es, dass jemand, der Blumenerde und Dünger kauft auch einen Topf benötigt? Oder das Spaghetti oft mit Pesto gegessen werden? Wahrscheinlich niemanden. Anders sieht es bei dem folgenden Beispiel für eine Assoziationsregel aus:
- 78 Prozent aller Kunden, die sich für einen Tanzkurs anmelden, sind auch auf Partnersuche
Dieses Wissen ist schon viel weniger trivial, das heißt, weniger erwartet und deswegen interessant für uns. Denn beim Data Mining geht es immer auch darum, unerwartetes Wissen sichtbar zu machen. Und: Beim Data Mining arbeiten wir in der Regel mit riesigen Datensätzen, die einiges an Rechenleistung benötigen. Deswegen habe kluge Mathematiker sich Gedanken darüber gemacht, wie man eine Assoziationsregel weiter beschreiben kann und vor allem, wie man bei der Berechnung der Regeln am besten vorgeht, um solche Regeln, die keinen Mehrwert bieten, von vorneherein auszuschließen und keine Rechenleistung an sie zu verschwenden.
Man unterscheidet daher zwei Ansätze in der Warenkorbanalye: Den Brute Force Ansatz, sozusagen den „Erststandard,“ und die Warenkorbanalyse nach dem Apriori Algorithmus. Der Apriori Algorithmus ist sozusagen ein Aufsatz, wie ein Kitchentool, dass einem die Arbeit erleichtert.
Grundannahmen der Assoziationsanalyse nach dem Apriori Algorithmus
Bei der Assoziationsanalyse nach dem Apriori Algorithmus macht man sich folgendes Wissen zunutze:
Wenn ein Item A nicht häufig ist, dann ist auch ein Itemset A,B nicht häufig.
Wie ist das zu verstehen? Nehmen wir an, wir haben die folgenden 4 Transaktionen:
Um unsere Assoziationsregeln aufzustellen, können wir jetzt einfach alle Kombinationen von Produkten (also Itmes) miteinander durchgehen und aus allen Kombinationen Regeln ableiten und alle diese Regeln würden auch zutreffen, denn sie kommen ja in unseren Transaktionen so vor.
Also zum Beispiel: Aus Cola, Bier und Wasser folgt Saft. Oder in schlau aufgeschrieben: { Cola, Bier, Wasser } -> { Saft }
Diese Regel sehen wir in unserer ersten Transaktion (T1). Wer Cola, Bier und Wasser kauft, hat in dem Fall auch Saft gekauft.
Schon auf den ersten Blick ist aber ersichtlich, dass das Item „Saft“ in allen Transaktionen T1 bis T4 nur einmal vorkommt. Beim Vorgehen nach dem Apriori Algorithmus würde man dieses Item daher ausschließen, und auf dessen Basis keine Regeln erzeugen. Denn am Ende wollen wir ja nur die Regeln, die eine gewisse aussagekraft für uns haben. (Eine Regel, die mit 1% Wahrscheinlichkeit zutifft, ist genau so unnütz, wie eine Regel, die mit 99% Wahrscheinlichkeit zu trifft). Stattdessen ermitteln wir beim Apriori Algorithmus zunächst die frequent itemsets in einer Menge von Transaktionen und arbeiten nur mit diesen weiter.
Nach dem Brute Force Ansatz ist das anders, hier werden erst alle möglichen Regeln erzeugt und dann in einem zweiten Schritt solche aussortiert, die keinen wirklichen Mehrwert haben. Das bedeutet mehr Aufwand und mehr Rechenleistung, besonders bei extrem großen Datensätzen.
Der Unterschied zwischen der Warenkorbanalyse nach dem Apriori-Algorithmus und dem Brute-Force-Ansatz liegt daher hauptsächlich in der Effizienz und Vorgehensweise bei der Ermittlung häufiger Itemsets (Artikelkombinationen) aus einer großen Menge von Transaktionen (z. B. Einkäufe in einem Supermarkt).
Merke:
Damit wir nicht sämtliche, völlig trivialen Regeln zwischen Produkten berechnen oder auch solche, die so gut wie nie vorkommen, gibt es ein paar Mechanismen in der Assoziationsanalyse, die dem Vorbeugen, wie die Ermittlung der frequent item sets und die Kennzahlen (Mindest-)Support, Konfidenz und Lift.
Der Mindestsupport ist eine Art Auschlußkriterium für nicht interessante Regeln.
Die Konfidenz sagt aus, wie verlässlich eine Regel ist, also wie wahrscheinlich sie ein tritt. Der Lift gibt Auskunft über die Stärke einer Assoziationsregel. Er hilft uns zu verstehen, ob das gemeinsame Auftreten von zwei Produkten (oder Ereignissen) zufällig ist oder ob tatsächlich eine statistische Beziehung besteht.
Achtung, jetzt wird’s nerdy. Ich werde anfangen mit Fachbegriffen und Formeln um mich zu schmeißen. Ich hoffe, du bleibst trotzdem am Ball.
Für unsere Schritt für Schritt Anleitung einer Assoziationsanalyse müssen wir zunächst ein paar Begriffe klären.
Was ist ein Item?
Ein Item ist in unserem Beispiel ein einzelnes Produkt.
Was ist ein Itemset?
Ein Itemset ist eine Kombination von Produkten, aber auch das einzelne Produkt (Einerkombination).
Was ist eine Transaktion?
Eine Transkation ist der Kauf von einem Itemset.
Los geht’s: Gegeben sei eine Menge M von Transaktionen. Ein Kunde hat zum Beispiel Mehl, Saft und Kuchen gekauft (T1). Ein anderer Bananen, Brot und Saft (T2) usw. In unserem Fall sind das 10 Transaktionen, also M = 10.
Diese 10 Transaktionen bringen wir zunächst in eine Form, mit der wir arbeiten können. In etwa so:
Neben M, der Menge an Transaktionen, gibt es noch I, die Menge an unterschiedlichen Items, die in M vorkommen. In unserem Fall bedeutet das:
I = { Mehl, Saft, Kuchen, Bananen, Brot, Eier, Limo}
Alle in I vorhandenen Items können Itemsets miteinander bilden und sind auch für sich gesehen bereits ein Itemset.
Eine Regel ist eine Implikation zwischen zwei Itemsets X und Y in der Form: Aus X folgt Y
Also zum Beispiel: Aus Mehl und Saft folgt Kuchen. Oder in schlau aufgeschrieben: { Mehl, Saft } -> { Kuchen }
Diese Regel sehen wir in unserer ersten Transaktion (T1). Wer Mehl und Saft kauft, hat in dem Fall auch Kuchen gekauft. Aus X (Mehl und Saft) folgt daher Y (Kuchen). Soweit, so gut.
Um unsere Assoziationsregeln aufzustellen, können wir also einfach alle Kombinationen miteinander durchgehen und aus allen Kombinationen Regeln ableiten und alle diese Regeln würden auch zutreffen, denn sie kommen ja in unseren Transaktionen so vor. Am Ende haben wir dabei aber nichts gewonnen, denn wir wollen ja, wie bereits oben erläutert, nur bestimmte Regeln, eben die, die nicht völlig trivial sind oder völlig absurd sind. (Eine Regel, die mit 1% Wahrscheinlichkeit zutifft, ist genau so unnütz, wie eine Regel, die mit 99% Wahrscheinlichkeit zu trifft).
Wir brauchen deswegen weitere Kennzahlen, die unsere Regeln näher beschreiben. Hier kommen die Begriffe Support bzw. Mindestsupport, Frequent Itemset und Konfidenz ins Spiel.
Support, Mindestsupport, Frequent Itemset und Konfidenz
Der Support gibt an, wie häufig ein Itemset in allen Transaktionen T1 bis T10 vorkommt.
Betrachtet man eine Grundgesamtheit von Transaktionen oder Warenkörben, die jeweils aus Itemsets bestehen, kann man zählen wie oft diese Itemsets vorkommen (absolute Häufigkeit). Aussagekräftiger als die absolute Häufigkeit der Itemsets ist jedoch die relative Häufigkeit eines Itemsets bezogen auf alle Transaktionen. Daher berechnen wir für den Support: Häufigkeit des Itemsets / Alle Transaktionen
Der Mindestsupport ist ein vorgegebener Grenzwert in Prozent, zum Beispiel: 40 Prozent.
Ein frequent Itemset ist ein Itemset, dass den Grenzwert erfüllt (genauer gesagt: dessen Support den Grenzwert erfüllt).
Eine Beschränkung auf die Betrachtung häufiger Itemsets ist aus praktischen Gründen notwendig, da die Anzahl an verschiedenen möglichen Itemsets in realen Beispielen sehr groß werden kann.
Die Konfidenz oder auch Confidence (C) beschreibt die Verlässlichkeit oder auch die „Treffsicherheit“ einer Regel. Sie sagt aus, wie wahrscheinlich es ist, dass, wenn die Prämisse (Mehl und Saft) gegeben ist, auch die Schlußfolgerung (Kuchen) eintritt.
Schauen wir uns das am Beispiel an:
Nehmen wir das Itemset Mehl und Saft. Das Itemset Mehl und Saft kommt genau 5 mal vor in unseren Transaktionen T1 bis T10.
Das bedeutet: Das Itemset Mehl und Saft hat eine Support von 5.
Der Support wird dabei immer als relativer Anteil zur Menge, also in Prozent angeben.
Heißt in unserem Fall:
sup {Mehl, Saft } = 5/10 = 0,5 (50 Prozent)
Oder nehmen wir das Itemset Saft und Kuchen. Das Itemset Saft und Kuchen kommt genau 4 Mal vor und hat somit einen Support von 4, bzw. 4/10 = 40 Prozent. Auf diese Weise lässt sich der Support für alle Itemsets bestimmen. Was sagt nun aber der Support aus bzw. wofür ist er wichtig?
Den Support verstehen
Mit der Berechnung des Supports macht man sich folgendes Wissen zunutze:
Wenn ein Item A nicht häufig ist, dann ist auch ein Itemset A,B nicht häufig.
Die Kenntnis über den Support eines Itemsets dient uns also dazu, zu erkennen, wie sinnvoll bzw. aussagekräftig eine Assoziationsregel ist, bzw. wie viel Sinn es macht, auf Basis dieses Itemsets weitere Regeln zu formulieren. In unserer Liste haben wir zum Beispiel das Item Limo. Limo kommt in allen Transaktionen genau einmal vor und hat damit einen Support von 10 Prozent. Dieser niedrige Support sagt aus, dass die Wahrscheinlichkeit gering ist, dass diese Regel (also dieses Itemset) noch öfter in unserer Gesamtmenge von Transaktionen vorkommt. Und genau so ist: Limo kommt in genau einer Transaktion vor und in keiner weiteren.
Deswegen berechnet man bei der Assoziationsanalyse nach dem Apriroi-Ansatz zunächst den Support für alle Itemsets und sortiert dann solche aus, die den Mindestsupport nicht erfüllen, bevor man weitere Kombinationen bildet. Alle Regeln bzw. Itemkombinationen, die den Mindestsupport nicht erfüllen, werden nicht weiter verfolgt. So können bereits über den Support Kombinationen ausgeschlossen werden: Wenn Itemset AB nicht häufig ist, dann kam man den Rest der Kombinationen, in denen AB vorkommt, schon aussortieren.
Die Konfidenz verstehen
Die Konfidenz oder auch Confidence (C) beschreibt die Verlässlichkeit oder auch die „Treffsicherheit“ einer Regel. Sie gibt an, wie wahrscheinlich es ist, dass, wenn die Prämisse (Mehl und Saft) gegeben ist, auch die Schlußfolgerung (Kuchen) eintritt.
Wenn unsere Regel lautet: (gesprochen: Wenn X, dann berechnen wir die Konfidenz C, in dem wir messen, wie oft das Itemset X und gemeinsam vorkommt, verglichen mit der Häufigkeit von dem Item alleine. Diese Messung erfolgt über den Support, der ja bereits die Häufigkeiten angibt. Daraus ergibt sich folgende Formel:
Gesprochen: Die Konfidenz von X zu Y ist gleich der Support von X vereinigt mit Y, geteilt durch den Support von X.
Erklärung der Begriffe:
- C (X -> Y): Die Konfidenz der Regel wenn X, dann Y
- Support (X ∪ Y): Der Support von X vereinigt mit Y ist die Häufigkeit, mit der X und Y zusammen in den Transaktionen vorkommen.
- Support(X): Der Support von X ist die Häufigkeit, mit der X alleine in den Transaktionen vorkommt.
Es wird also einfach die Häufigkeit der Itemmenge ( mit verglichen mit der Häufigkeit von alleine.
Zum Beispiel: .
Gesprochen: Die Konfidenz von aus Äpfeln folgt Milch ist gleich der Support von Äpfel und Milch geteilt durch den Support von Äpfel.
Dabei muss immer gelten:
Die Konfidenz kann daher maximal 1 sein. Eine Konfidenz von 1 würde in dem obigen Beispiel bedeuten, dass immer, wenn Äpfel in einem Warenkorb sind, auch Milch gekauft wird.
Assoziationsanalyse – Vorgehen nach dem Apriori-Ansatz
Vorgehen:
- Bestimmen aller Items und Kombinationen von Items mit vorgegebenen Mindestsupport.
- Der Support lässt sich für jedes einzelne Item und jede Kombination von Items berechnen. Aufgrund der Tatsache, dass, wenn ein Item A nicht häufig ist, auch die Kombination AB nicht häufig ist, beginnt man bei der Berechnung des Supports bei den Einerkombinationen.
- Items und Itemkombinationen, die den Mindestsupport nicht erfüllen, werden nicht weiter berücksichtigt.
- Als nächstes bildet man aus den nicht aussortierten Kombinationen die Assoziationsregel und berechnet deren Konfidenz.
Assoziationsanalyse-Beispiel nach dem Apriori-Ansatz
Hier nochmal unsere Transaktionen mit den Itemkombinationen:
Support berechnen
Einerkombinationen
Wie oft kommen die Items in der Gesamtmenge der Transatkionen vor?
sup (Kuchen) = 7/10 (in 7 von 10 Transaktionen)
sup (Saft) = 6/10 (in 6 von 10 Transaktionen)
sup (Mehl) = 5/10 (in 5 von 10 Transaktionen)
sup (Brot) = 4/10 (in 4 von 10 Transaktionen)
sup (Eier) = 4/10 (in 4 von 10 Transaktionen)
sup (Bananen) = 2/10 (in 2 von 10 Transaktionen)
sup (Limo) = 1/10 (in 1 von 10 Transaktionen)
Gewünschter Mindestsupport: 40%. Heißt: Alle Items und deren Kombinationen, die diesen Mindestsupport nicht erfüllen, werden nicht weiter berücksichtigt. Bananen und Limo werden nicht weiter berücksichtigt, da ihr Mindestsupport unter 40% liegt.
Es verbleiben die Items: Kuchen, Saft, Mehl, Brot, Eier.
Zweierkombinationen
Aus den verbliebenen Items bilden wir alle Zweierkombinationen und berechnen wieder deren Support:
sup (Kuchen, Saft) = 4/10 = 40 Prozent
sup (Kuchen, Mehl) = 4/10 = 40 Prozent
sup (Kuchen, Eier) = 3/10 = 30 Prozent
sup (Kuchen, Brot) = 2/10 = 20 Prozent
sup (Saft, Mehl) = 5/10 = 50 Prozent
sup (Saft, Brot) = 2/10 = 20 Prozent
sup (Saft, Eier)= 1/10 = 10 Prozent
sup (Mehl, Brot) = 1/10 = 10 Prozent
sup (Mehl, Eier) = 1/10 = 10 Prozent
sup (Brot, Eier) = 2/10 = 20 Prozent
Auch hier werden wieder alle Kombinationen mit einem Support unter 40 % aussortiert und nicht weiter berücksichtigt.
Dreierkombinationen
Aus den übriggebliebenen Itemsets (Kuchen, Saft, Mehl) bilden wir die Dreierkombinationen:
sup (Kuchen, Saft, Mehl) = 4/10 = 40 Prozent
Das heißt: Kuchen, Saft und Mehl sind unsere frequent Itemsets, die wir nun miteinander kombinieren können, um daraus Regeln zu erzeugen.
Regeln erzeugen
Zum Erzeugen der Regeln kombinieren wir unsere frequent Itemsets Kuchen, Saft und Mehl miteinander.
Aus (Kuchen, Saft) erhalten wir 2 Regeln:
Kuchen -> Saft (Aus Kuchen folgt Saft, ein Kunde, der Kuchen kauft, kauft auch Saft)
Saft -> Kuchen (Aus Saft folgt Kuchen)
Aus (Kuchen, Mehl) erhalten wir 2 Regeln:
Kuchen -> Mehl
Mehl -> Kuchen
Aus (Saft, Mehl) erhalten wir 2 Regeln:
Saft -> Mehl
Mehl -> Saft
Aus Kuchen, Saft, Mehl erhalten wir 3 Regeln:
Kuchen + Saft -> Mehl
Kuchen + Mehl-> Saft
Saft + Mehl -> Kuchen
Konfidenz berechnen
Die Konfidenz einer Regel X -> Y wird berechnet:
- durch die Anzahl der Transaktionen in M, die X und Y enthalten,
- im Verhältnis zur Anzahl der Transaktionen in M, die X enthalten.
Anders gesagt: Die Konfidenz ist der Support der gesamten Regel geteilt durch den Support der Prämisse.
X -> Y
{ Mehl, Saft } -> { Kuchen }
In unserem Beispiel ist das die Anzahl der Transaktionen in M, die Mehl, Saft und Kuchen enthalten, geteilt durch die Anzahl der Transaktionen, die Mehl und Saft enthalten.
sup (Mehl; Saft) = 5/10 = 50 %
sup (Mehl; Saft; Kuchen) = 4/10 = 40 %
50 % / 40 % =
konf (Kuchen à Saft) =
sup (Kuchen, Saft) / sup(Saft) = 4/10 / 6/10 = gerundet 0,67
konf (Saft à Kuchen) =
sup (Saft, Kuchen) / sup(Kuchen) = 4/10 / 7/10 = gerundet 0,57
konf (Kuchen à Mehl) =
sup (Kuchen, Mehl) / sup(Mehl) = 4/10 / 5/10 = 0,8
konf (Mehl à Kuchen) =
sup (Mehl, Kuchen) / sup (Kuchen) = 4/10 / 7 /10 = gerundet 0,57
konf (Saft à Mehl) =
sup ( Saft, Mehl) / sup (Mehl) = 5/10 / 5/10 = 1
konf (Mehl à Saft) =
sup( Mehl, Saft) / sup (Saft) = 5/10 / 6/10 = gerundet 0,83
konf (Kuchen + Saft à Mehl) =
sup ( Kuchen, Saft, Mehl) / (sup (Kuchen, Saft) = 4/10 / 4/10 = 1
konf (Saft + Mehl à Kuchen) =
sup (Saft, Mehl, Kuchen) / sup ( Saft, Mehl) = 4/10 / 5/10 = 0,8
Alle berechneten Regeln haben eine Konfidenz von mindestens 0,5, was bedeutet, dass sie alle eine gewisse Stärke haben. Einige Regeln haben sogar eine Konfidenz von 1, was darauf hinweist, dass sie in allen relevanten Fällen zutreffen. Um jedoch die tatsächliche Nützlichkeit dieser Regeln zu bewerten, müsste man zusätzlich den Lift berechnen, der das Verhältnis der tatsächlichen Konfidenz zur erwarteten Konfidenz angibt.