Die Assoziationsanalyse gehört zum Repertiore der explorativen Datenanalyse und wird verwendet, um versteckte Muster und Beziehungen zwischen verschiedenen Elementen in großen Datensätzen aufzudecken. Ihr Hauptverwendungszweck besteht darin, Zusammenhänge zwischen verschiedenen Produkten oder Ereignissen aufzudecken, die nicht sofort offensichtlich sind. In diesem Artikel klären wir die wichtigsten Begriffe rund um die Assoziationsanalyse und klären, was der Unterschied zwischen dem Brute Force und dem Apriori Ansatz ist.
Was ist das Ziel einer Assoziationsanalyse?
Assoziationsanalysen werden häufig in der Warenkorbanalyse eingesetzt, zum Teil werden die Begriffe Assoziationsanalyse und Warenkorbanalyse auch synonym verwendet, was jedoch nicht ganz korrekt ist. Die Warenkorbanalyse ist lediglich ein klassisches Beispiel.
Was ist das Ziel? Das Ziel ist, Assoziationen, also Verbindungen und Wahrscheinlichkeiten zwischen zwei oder mehr Produkten aufzudecken. Eine Assoziationsregel folgt dabei immer dem Schema: aus A folgt B. In der Fachsprache werden diese beiden Teile einer Assoziationsregel auch Prämisse (body) und Schlußfolgerung (head) genannt. Um diese Assoziationen aufzudecken, werden alle Items (z.B. die Produkte aus allen Einkäufen) miteinander kombiniert und dann berechnet, wie wahrscheinlich diese sind. Dabei werden 2 Ansätze unterschieden – der Brute Force Ansatz und der apriori mode.
Brute Force Ansatz und Apriori Algorithmus – das ist der Unterschied
Der Unterschied zwischen der Warenkorbanalyse nach dem Apriori-Algorithmus und dem Brute-Force-Ansatz liegt 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).
1. Brute-Force-Ansatz
Beim Brute-Force-Ansatz werden zunächst alle möglichen Kombinationen von Artikeln gebildet und danach analysiert, welche Kombinationen davon häufig gemeinsam vorkommen.
Du gehst dabei so vor: Nimm alle möglichen Kombinationen von Artikeln (bei Artikeln sind das 2 hoch n−1 Kombinationen) und prüfe, wie oft jede Kombination in den Transaktionsdaten vorkommt.
Problem: Das dauert extrem lange, weil die Anzahl der Kombinationen sehr schnell explodiert, vor allem bei vielen Artikeln. Das frisst unglaublich viel Rechenleistung.
2. Apriori-Algorithmus
Der Apriori-Algorithmus geht das schlauer an, indem er von Anfang an unwahrscheinliche Kombinationen rauswirft.
Hier beginnst du damit, zu prüfen, wie oft die einzelnen Artikel überhaupt in den Kombinationen vorkommen. Diese Häufigkeit nennt man „Support“. Nur wenn ein Artikel oder eine Kombination einen gewissen Mindestsupport erfüllt, wird diese weiterhin berücksichtigt. Ansonsten wird der Artikel und alle mit ihm vorkommenden Kombinationen aussortiert. Dieses Vorgehen ist deshalb zweckmäßig, weil es sich folgende Überlegung zu nutze macht: Wenn ein Item A nicht häufig ist, dann ist auch ein Itemset A,B nicht häufig.
Danach bildest du nur aus diesen häufigen Artikeln Kombinationen, z. B. 2er-Paare, und prüfst wieder, welche davon oft zusammen gekauft werden. Artikel, die schon allein selten sind, brauchst du in den Kombinationen gar nicht weiter betrachten. So gehst du Schritt für Schritt zu größeren Kombinationen über, aber immer nur mit den häufigen Artikeln. Das spart jede Menge Rechenzeit.
Kurz gesagt:
- Der Brute Force probiert stumpf alles durch, was bei vielen Artikeln ziemlich aufwändig ist.
- Apriori filtert frühzeitig unwichtige Kombinationen raus, wodurch du viel schneller Ergebnisse bekommst und den Rechenaufand deutlich senken kannst.
Die wichtigsten Begriffe der Assoziationsanalyse einfach erklärt
Items und Itemsets
Ein Item ist ein einzelnes Element oder Objekt in einem Datensatz. Im Kontext der Assoziationsanalyse könnte ein Item beispielsweise ein einzelnes Produkt in einem Supermarkt sein, wie z.B. „Mehl“, „Butter“ oder „Saft“. Ein Item steht für sich alleine und ist die kleinste betrachtete Einheit in der Analyse.
Ein Itemset kann sowohl aus einem einzelnen Item (Einerkombination) bestehen, als auch aus einer Gruppe von Items, die in einer Transaktion gemeinsam vorkommen. In der Notation wird dies typischerweise durch geschweifte Klammern dargestellt.
Schauen wir uns das an einem Beispiel an:
In der Abbildung oben siehst du 10 Transaktionen (T1 bis T10). Es lassen sich außerdem 6 einzelne Items identifizieren, nämlich Mehl, Saft, Kuchen, Bananen, Brot, Eier, Limo. Alle vorhandenen Items können Itemsets miteinander bilden und sind auch für sich gesehen bereits ein Itemset (Einerkombination).
Allein die erste Transaktion T1 enthält damit bereits folgende Itemsets:
{Mehl}
{Saft}
{Kuchen}
{Mehl, Saft}
{Mehl, Kuchen}
und {Saft, Kuchen}
Itemsets sind die Objekte, auf denen Assoziationsregeln basieren. In der Analyse wird untersucht, wie oft bestimmte Itemsets in den Daten vorkommen und wie sie miteinander in Beziehung stehen.
Support und Mindestsupport: Kennzahlen zur Relevanz von Itemsets in Transaktionen
Der Support gibt an, wie häufig ein bestimmtes Itemset (also eine Kombination von Items oder ein einzelnes Item als Einerkombination) in den Transaktionsdaten vorkommt. Er ist eine zentrale Kennzahl, die die Häufigkeit und somit die Relevanz eines Itemsets misst.
Der Support gibt an, wie häufig ein Itemset in allen Transaktionen vorkommt und zwar als relativer Anteil der Gesamt-Transaktionen.
Schauen wir uns das an einem Beispiel an:
In der Abbildung oben siehst du 10 Transaktionen (T1 bis T10). Wie oft kommt das Itemset {Eier, Kuchen} darin vor?
Wir finden die Kombination von Eier und Kuchen in den Transaktionen T6, T8 und T9, also in 3 von insgesamt 10 Transaktionen.
Der Support für dieses Itemset ist daher:
Support({Eier, Kuchen}) = 3/10 = 0,3 oder 30%
Abstrakt ausgedrückt ist der Support somit:
Was können wir daraus ableiten und warum ist das wichtig?
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 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. Im Beispiel hat das Itemset {Eier, Kuchen} eine relative Häufigkeit von 30 Prozent, es kommt in 30 Prozent aller Transaktionen vor. Als weiteres Itemset haben wir das Item Limo in unserer Liste. 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.
Hoher Support: Ein hoher Support zeigt an, dass das Itemset in vielen Transaktionen vorkommt, was auf eine hohe Relevanz hinweist.
Niedriger Support: Ein niedriger Support bedeutet, dass das Itemset selten vorkommt, was darauf hinweisen kann, dass es weniger relevant oder weniger häufig beobachtet wird.
Der Mindestsupport ist ein Schwellenwert in der Assoziationsanalyse, der festlegt, wie häufig ein Itemset in den Transaktionsdaten mindestens vorkommen muss, damit es als relevant betrachtet wird.
