Assoziationsanalyse

Die Assoziationsanalyse bezeichnet die Suche nach starken Regeln. Diese daraus folgenden Assoziationsregeln beschreiben Korrelationen zwischen gemeinsam auftretenden Dingen. Der Zweck einer Assoziationsanalyse besteht also darin, Items (Elemente einer Menge, wie z. B. einzelne Artikel eines Warenkorbs) zu ermitteln, die das Auftreten anderer Items innerhalb einer Transaktion implizieren. Eine solcherart aufgedeckte Beziehung zwischen zwei oder mehr Items kann dann als Regel der Form „Wenn Item(menge) A, dann Item(menge) B“ bzw. A → B dargestellt werden.

Anwendungsfelder

Ein typisches Anwendungsfeld sind die Zusammenhänge beim Einkauf, die sogenannte Warenkorbanalyse, um gezielt Werbemaßnahmen einzuleiten. Ein Beispiel: Bei 80 Prozent der Einkäufe, in denen Bier gekauft wird, werden auch Kartoffelchips gekauft. Beide Produkte kommen in 10 Prozent der Einkäufe vor. Häufig werden diese Erkenntnisse im Crossmarketing genutzt.

Kenngrößen

Kenngrößen von Assoziationsregeln sind:

• Support: relative Häufigkeit der Beispiele, in denen die Regel anwendbar ist.

${\displaystyle \operatorname {supp} (X\cap Y)={\frac {\mathrm {} |X\cap Y|}{N}}}$, mit ${\displaystyle N}$ als Kardinalität der Gesamtdatenmenge. Zu beachten ist hierbei, dass ${\displaystyle {\text{supp}}(X\cap Y)}$ den Support über einer Menge von Items definiert. Dieser entspricht der absoluten Häufigkeit der Itemmenge in den Gesamtdaten. Wir verwenden an dieser Stelle die Schnittmenge der beiden Regelseiten ${\displaystyle X\cap Y}$, um alle Elemente der Gesamtdaten darzustellen, die sowohl die Itemmenge ${\displaystyle X}$ als auch die Itemmenge ${\displaystyle Y}$ beinhalten.

• Konfidenz: relative Häufigkeit der Beispiele, in denen die Regel richtig ist.

${\displaystyle \operatorname {confidence} (X\Rightarrow Y)={\frac {\operatorname {supp} (X\cap Y)}{\operatorname {supp} (X)}}}$

Die Konfidenz einer Regel beschreibt also den relativen Anteil aller Elemente der Gesamtmenge, die sowohl ${\displaystyle X}$ als auch ${\displaystyle Y}$ beinhalten, im Verhältnis zu denjenigen Elemente, die ${\displaystyle X}$ beinhalten.

• Lift: Der Lift gibt an, wie hoch der Konfidenzwert für die Regel den Erwartungswert übertrifft, er zeigt also die generelle Bedeutung einer Regel.

${\displaystyle \operatorname {lift} (X\Rightarrow Y)={\frac {\operatorname {supp} (X\Rightarrow Y)}{\operatorname {supp} (X)\times \operatorname {supp} (Y)}}}$, wobei gilt:

${\displaystyle {\begin{aligned}\operatorname {lift} (X\Rightarrow Y)>1&\rightarrow X{\text{ und }}Y{\text{ sind positiv korreliert}}\\\operatorname {lift} (X\Rightarrow Y)<1&\rightarrow X{\text{ und }}Y{\text{ sind negativ korreliert}}\\\operatorname {lift} (X\Rightarrow Y)=1&\rightarrow X{\text{ und }}Y{\text{ sind unabhängig}}\end{aligned}}}$

Beispiel

Gegeben sei eine Assoziationsregel {Zahnbürste} → {Zahncreme}.

• Support: Mit dem Support wird berechnet, für welchen Anteil aller Transaktionen die Regel {Zahnbürste} → {Zahncreme} gilt. Zur Berechnung wird die Anzahl der Transaktionen, in denen beide interessierenden Itemmengen vorkommen, durch die Anzahl aller Transaktionen geteilt.
• Confidence: Für welchen Anteil der Transaktionen, in denen {Zahnbürste} vorkommt, kommt auch {Zahncreme} vor? Zur Berechnung der Konfidenz wird die Anzahl aller regelerfüllenden Transaktionen durch die Anzahl der Transaktionen, die {Zahnbürste} enthalten, geteilt.

${\displaystyle \operatorname {confidence} (\{{\text{Zahnbürste}}\}\rightarrow \{{\text{Zahncreme}}\})={\frac {\operatorname {supp} (\{{\text{Zahnbürste}},{\text{Zahncreme}}\})}{\operatorname {supp} (\{{\text{Zahnbürste}}\})}}}$

• Lift: Angenommen, 10 Prozent aller Kunden kaufen {Zahnbürste, Zahncreme}, 20 Prozent aller Kunden kaufen {Zahnbürste} und 40 Prozent aller Kunden kaufen {Zahncreme}. Dann hat die Regel einen Lift von 1,25.

Verfahren

Algorithmen sind so zu entwerfen, dass alle Assoziationsregeln mit einer vorab festzulegenden Mindestkonfidenz und Mindestsupport gefunden werden. Die Verfahren sollen keine Annahmen über die zu analysierenden Merkmale benötigen. Dies wäre beispielsweise bei einem Versandhandel mit vielen Tausend Artikeln auch nicht denkbar.

Der erste Algorithmus zur Assoziationsanalyse ist der AIS-Algorithmus (benannt nach seinen Entwicklern Agrawal, Imielinski und Swami)^[1][2] aus dem der Apriori-Algorithmus entwickelt wurde. Dieser wird mehr und mehr vom wesentlich effizienteren FPGrowth-Algorithmus^[3] abgelöst.

Weblinks

• Enrico Lüdecke: Ermittlung von Assoziationsregeln aus großen Datenmengen. Fachhochschule Schmalkalden. Abgerufen am 3. Februar 2021.

Einzelnachweise

1. ↑ R. Agrawal, T. Imieliński, A. swami: Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. In: Mining association rules between sets of items in large databases. 1993, S. 207, doi:10.1145/170035.170072. 
2. ↑ R. Agrawal, T. Imielinski, A. Swami: Database Mining: A Performance Perspective. In: IEEE Transactions on Knowledge and Data Engineering, Special issue on Learning and Discovery in Knowledge-Based Databases. 5(6). Jahrgang, Dezember 1993 (agrawal-family.com [PDF]). 
3. ↑ Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach (Memento vom 31. Oktober 2008 im Internet Archive)