7.2 Grundbegriffe

Die Assoziationsanalyse arbeitet mit einigen Grundbegriffen, die zunächst definiert und erläutert werden sollen.

Items bilden die Grundgesamtheit $G$ von Bezeichnern (z.B. alle Artikel eines Supermarkts {Äpfel, Milch, Käse, …} ). Die Anzahl der betrachteten Items kann groß sein: So umfasst das Sortiment eines Drogeriemarkts über 10000 verschiedene Artikel (vgl. dm - Über uns), der Online-Händler Amazon hat 229 Mio. Artikel gelistet (vgl. Statista 2017).

Item-Menge ( item sets ):

Eine Item-Menge $X$ ist aus Items zusammengesetzt. Eine k-Item-Menge enthält $k$ Items. Zum Beispiel die 3 Item-Menge {Äpfel, Brot, Milch}. Bei einer Grundgesamtheit von $N$ verschiedenen Items ergeben sich theoretisch $2^N$ möglicher Kombinationen an Item-Mengen (Abschnitt 7.3 ).

Support (“Reichweite”):

Betrachtet man eine Grundgesamtheit von Transaktionen oder Warenkörben, die jeweils aus Item-Mengen bestehen, kann man zählen wie oft diese Item-Menge vorkommt (absolute Häufigkeit). Wichtiger als die absolute Häufigkeit der Item-Menge ist die relative Häufigkeit einer Item-Menge bezogen auf alle Transaktionen

$$S\left(X\right)=\frac{\#AuftretenvonX}{\#Transaktionen}$$

Eine Item-Menge nennt man häufig (engl. frequent itemset), wenn $S\ge S_{min}$, wobei $S_{min}$ eine für das Problem entsprechend gewählte untere Grenze für die Häufigkeit ist. Eine Beschränkung auf die Betrachtung häufiger Item-Mengen ist aus praktischen Gründen notwendig, da die Anzahl an verschiedenen möglichen Item-Mengen in realen Beispielen sehr groß werden kann (vgl.7.3).

Bis jetzt haben wir nur Item-Mengen betrachtet, aber noch keine Beziehungen oder Regeln zwischen Item-Mengen.

Konfidenz (“Treffsicherheit”) einer Regel:

Die Konfidenz $C(X\Rightarrow Y)$ misst, wie oft eine Item-Menge $Y$ zusammen mit einer Item-Menge $X$ auftritt

$$C(X\Rightarrow Y)=\frac{S(X,Y)}{S\left(X\right)}$$

Es wird also einfach die Häufigkeit der gemeinsamen Item-Menge ($X$ mit $Y$) verglichen mit der Häufigkeit von $X$ alleine. Zum Beispiel: $C(Äpfel\Rightarrow Milch)=\frac{S(Äpfel,Milch)}{S\left(Äpfel\right)}$. Da immer gelten muss $S(X,Y)\le S\left(X\right)$, kann die Konfidenz maximal 1 sein. Eine Konfidenz von 1 würde im obigen Beispiel bedeuten, dass immer, wenn Äpfel in einem Warenkorb sind, auch Milch gekauft wird.

Abbildung 7.1: Schematische Darstellung einiger Warenkörbe

In Abbildung 7.1 sind schematisch einige Warenkörbe dargestellt sowie diejenigen mit Windeln bzw. Bier farblich markiert. Nehmen wir an, dass es sich um insgesamt 100 Transaktionen/Warenkörbe handelt, davon seien in 30 Transaktionen Windeln enthalten, in 40 Bier sowie in 20 Transaktionen Windeln und Bier (Schnittmenge). Daraus ergeben sich folgende Werte für den Support: $$S\left(Bier\right)=\frac{40}{100}=40\%$$ $$S\left(Windeln\right)=\frac{30}{100}=30\%$$ $$S\left(Windeln,Bier\right)=\frac{20}{100}=20\%$$ Die Konfidenz der Regel $Windeln Bier $ ergibt sich zu

$$C(Windeln\Rightarrow Bier)=\frac{S(Windeln,Bier)}{S\left(Windeln\right)}=\frac{2}{3}\approx 67\%$$ oder in Worten: In 67% aller Transaktionen, in denen Windeln verkauft werden, wird auch Bier mit verkauft. Beachte, dass die Konfidenz abhängig von der Richtung der Regel ist. Es wird also einfach die Häufigkeit der gemeinsamen Item-Menge ($X$ mit $Y$) verglichen mit der Häufigkeit von $X$ alleine. Da immer gelten muss $S(X,Y)\le S\left(X\right)$, kann die Konfidenz maximal 1 sein. Eine Konfidenz von 1 würde im obigen Beispiel bedeuten, dass immer wenn Windeln in einem Warenkorb sind, auch Bier gekauft wird.

Assoziationsregel

Eine Assoziationsregel gibt man dann allgemein in der Form $$X\Rightarrow Y[S\%,C\%]$$ an. Zum Beispiel: $Windeln\Rightarrow Bier[20\%,67\%]$. Man nennt den linken Teil der Regel (“wenn”-Teil) auch Prämisse oder Antezedens, den rechten Teil der Regel (“dann”-Teil) auch Konklusion oder Konsequenz.

In einem zweiten Beispiel betrachten wir 5 einzelne Warenkörbe:

Tabelle 7.1: Beispiel Warenkörbe

Id	Items
1	{Windeln, Bier}
2	{Windeln, Milch, Brot, Käse}
3	{Bier, Milch, Brot, Butter}
4	{Windeln, Bier, Milch, Brot}
5	{Windeln, Milch, Bier, Butter}

Versuchen Sie, die folgende Tabelle zu vervollständigen, indem Sie Support und Konfidenz für die angegebenen Regeln ausrechnen!

Tabelle 7.2: Regeln

Regeln	Support	Konfidenz
{Windeln} $\to$ {Bier}	3/5	3/4
{Brot} $\to$ {Milch}	?	?
{Brot, Windeln} $\to$ {Käse}	?	?

Lift

In der Praxis hat man oft das Problem, dass man zu viele Regeln findet, und es stellt sich die Frage, welche Regeln interessant sind. Support und Konfidenz liefern Aussagen über die Häufigkeit einer Item-Menge bzw. einer Assoziationsregel. Setzt man die beobachtete Konfidenz einer Regel $X\Rightarrow Y$ in Beziehung zur statistisch erwarteten Konfidenz, misst man den Informationsgewinn durch die Regel $X\Rightarrow Y$. Diese Größe nennt man Lift $L$. Der Lift gibt also an, wie viel die beobachtete Konfidenz einer Regel die erwartete Konfidenz übertrifft:

$$L(X\Rightarrow Y)=\frac{C(X\Rightarrow Y)}{C_{expected}(X\Rightarrow Y)}$$

$Lift=1$ bedeutet kein Informationsgewinn. Die Regel ist zufällig und entspricht der statistischen Erwartung.

$Lift>1$ bedeutet, dass $Y$ wahrscheinlicher ist, falls $X$ beobachtet wird. Je größer der Lift, desto potenziell interessanter oder überraschender ist die Regel.

Als Erwartungswert für die Konfidenz kann man die unbedingte Wahrscheinlichkeit für den rechten Teil der Regel nehmen, dies entspricht aber genau dem Support $S\left(Y\right)$, so dass gilt

$$Lift(X\Rightarrow Y)=\frac{S(X,Y)}{S\left(X\right)\ast S\left(Y\right)}=\frac{P\left(Y|X\right)}{P\left(Y\right)}=\frac{bedingteWahrsch.}{unbedingteWahrsch.}$$ Der Lift vergleicht also die bedingte Wahrscheinlichkeit $P\left(Y|X\right)$ mit der unbedingten Wahrscheinlichkeit $P\left(Y\right)$.

Wie schon bei der Korrelation (vgl. Abschnitt 2.2.4 ) gilt: Eine bestehende Assoziation bedeutet, dass Objekte assoziiert sind, aber nicht unbedingt in einem kausalen Zusammenhang zueinander stehen!