imported>Ulanwp: 4 fehlende Sprachparameter eingefügt; 2 leere Parameter entfernt

2026-02-08T16:24:15Z

4 fehlende Sprachparameter eingefügt; 2 leere Parameter entfernt

Neue Seite

Die '''Assoziationsanalyse''' bezeichnet die Suche nach starken [[Geschäftsregel|Regeln]]. Diese daraus folgenden [[Assoziationsregel]]n beschreiben [[Korrelation]]en zwischen gemeinsam auftretenden Dingen. Der Zweck einer Assoziationsanalyse besteht also darin, Items (Elemente einer [[Menge (Mathematik)|Menge]], wie z. B. einzelne Artikel eines Warenkorbs) zu ermitteln, die das Auftreten anderer Items innerhalb einer [[Transaktion (Informatik)|Transaktion]] implizieren. Eine solcherart aufgedeckte [[Relation (Mathematik)|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.

== Definitionen ==
Objekte, deren Beziehungen untersucht werden sollen, heißen im Rahmen der Assoziationsanalyse Items. Gegeben sei die endliche Menge <math>I=\{i_1,i_2,\dots,i_n\}</math> aller <math>n</math> Items eines Betrachtungsraumes. Eine Teilmenge <math>X \subseteq I</math> dieser Grundgesamtheit wird Itemmenge genannt. Enthält die Itemmenge <math>k</math> Elemente, wird sie auch als <math>k</math>-Itemmenge bezeichnet.<ref>{{Literatur |Autor=Christoph Beierle, Gabriele Kern-Isberner |Titel=Methoden wissensbasierter Systeme: Grundlagen, Algorithmen, Anwendungen |Verlag=Springer Fachmedien Wiesbaden |Ort=Wiesbaden |Datum=2014 |ISBN=978-3-8348-1896-6 |DOI=10.1007/978-3-8348-2300-7 |Online=[https://link.springer.com/10.1007/978-3-8348-2300-7 Online] |Abruf=2024-03-03 |Sprache=de}}</ref><ref>{{Literatur |Autor=Pang-Ning Tan, Michael Steinbach, Anuj Karpatne, Vipin Kumar |Titel=Introduction to Data Mining |Auflage=2. |Verlag=Pearson |Datum=2018 |ISBN=978-0-13-312890-1 |Sprache=en}}</ref>

Eine Transaktion <math>t \subseteq I</math> ist eine solche Itemmenge. Die Menge aller Transaktionen bildet die Datenbasis <math>\mathcal D = \{t_1, t_2, \dots,t_d\}</math> mit <math>d=|\mathcal D|</math>.

Eine Assoziationsregel beschreibt eine Implikation der Form <math>X\rightarrow Y</math>. Prämisse <math>X</math> und Konklusion <math>Y</math> sind disjunkte Itemmengen, d. h. <math>X, Y \subseteq I</math> und <math>X \cap Y = \emptyset</math>. Eine Transaktion <math>t</math> erfüllt die Regel <math>X\rightarrow Y</math>, wenn <math>X \cup Y \subseteq t</math>, <math>t</math> also alle in der Regel vorkommenden Items umfasst.

Wichtige Kenngrößen von Assoziationsregeln sind Support und Konfidenz.
* ''Support:'' Der Support einer Itemmenge <math>X</math> gibt die [[relative Häufigkeit]] der Transaktionen aus <math>\mathcal D</math> an, die <math>X</math> enthalten:
:<math>\operatorname{support}(X) = \frac{|\{t \in \mathcal D \mid X \subseteq t\}|}{|\mathcal D|}</math>
:Entsprechend ist der Support einer Regel <math>X\rightarrow Y</math> gegeben durch die relative Häufigkeit der Transaktionen, die sowohl die Elemente der Prämisse <math>X</math> als auch die der Konklusion <math>Y</math> enthalten:
:<math>\operatorname{support}(X\rightarrow Y) = \operatorname{support}(X \cup Y)</math>

* ''Konfidenz:'' Die Konfidenz von <math>X\rightarrow Y</math> gibt den Anteil der <math>X</math> und <math>Y</math> enthaltenden Transaktionen unter den <math>X</math> enthaltenden Transaktionen an:
:<math>\operatorname{confidence}(X\rightarrow Y) = \frac{\operatorname{support}(X \cup Y)}{\operatorname{support}(X)}= \frac{|\{t \in \mathcal D \mid (X \cup Y) \subseteq t\}|}{|\{t \in \mathcal D \mid X \subseteq t\}|}</math>
:Sie beschreibt also die bedingte Wahrscheinlichkeit dafür, dass eine Transaktion die <math>X</math> erfüllt auch <math>Y</math> erfüllt.

* ''Lift:'' Der Lift gibt an, wie hoch der Konfidenzwert für die Regel den [[Erwartungswert]] übertrifft, er zeigt also die generelle Bedeutung einer Regel.
:<math> \operatorname{lift}(X\rightarrow Y) = \frac{ \operatorname{support}(X \cup Y)}{ \operatorname{support}(X) \times \operatorname{support}(Y) } </math>, wobei gilt:
:<math>\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}</math>

== 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.

:<math>\operatorname{confidence}(\{\text{Zahnbürste}\} \rightarrow \{\text{Zahncreme}\}) = \frac{\operatorname{support}(\{ \text{Zahnbürste}, \text{Zahncreme}\})}{\operatorname{support}(\{\text{Zahnbürste}\})}</math>

* ''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.

== Testen der Regeln auf Statistische Signifikanz ==
Generieren von Datensets unter der Nullhypothese ([[Nullhypothese]]: es liegen keine echten Assoziationsregeln vor), kann mithilfe der Swap-Randomisierung erfolgen. Dabei werden relevante Teile des Datensets vollkommen zufällig [[Permutation|permutiert]]. Das Ergebnis der Assoziationsanalyse auf dem originalen Datensatz kann dann mit den Ergebnissen auf den zufällig generierten Datensets verglichen werden um abzuleiten ob das Ergebnis auch unter reinem Zufall hätte auftreten können.<ref>Gionis, A., Mannila, H., Mielikäinen, T., & Tsaparas, P. (2007). Assessing data mining results via swap randomization. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(3), 14-es. [https://www.cs.uoi.gr/~tsap/publications/gionis_2007_swap_randomization.pdf pdf]
</ref>
Der Ansatz erlaubt es die [[Irrtumswahrscheinlichkeit]] zu schätzen.

== Verfahren ==
[[Algorithmus|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)<ref>{{cite journal |first1=R. |last1=Agrawal |first2=T. |last2=Imieliński |first3=A. |last3=swami |year=1993 |title=Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93 |journal=Mining association rules between sets of items in large databases |pages=207 |doi=10.1145/170035.170072 |language=en}}</ref><ref>{{cite journal |author=R. Agrawal, T. Imielinski, A. Swami |title=Database Mining: A Performance Perspective |journal=IEEE Transactions on Knowledge and Data Engineering, Special issue on Learning and Discovery in Knowledge-Based Databases |volume=5(6) |date=1993-12 |url=http://rakesh.agrawal-family.com/papers/tkde93mining.pdf |language=en}}</ref> aus dem der [[Apriori-Algorithmus]] entwickelt wurde. Dieser wird mehr und mehr vom wesentlich effizienteren FPGrowth-Algorithmus<ref>
{{Webarchiv |url=http://www-faculty.cs.uiuc.edu/~hanj/pdf/dami04_fptree.pdf |wayback=20081031212337 |text=Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach}}
</ref> abgelöst.

== Einzelnachweise ==
<references />

[[Kategorie:Data-Mining]]
[[Kategorie:Business Intelligence]]

Assoziationsanalyse - Versionsgeschichte

imported>Ulanwp: 4 fehlende Sprachparameter eingefügt; 2 leere Parameter entfernt