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.

Definitionen

Objekte, deren Beziehungen untersucht werden sollen, heißen im Rahmen der Assoziationsanalyse Items. Gegeben sei die endliche Menge I={i1,i2,…,in} aller n Items eines Betrachtungsraumes. Eine Teilmenge X⊆I dieser Grundgesamtheit wird Itemmenge genannt. Enthält die Itemmenge k Elemente, wird sie auch als k-Itemmenge bezeichnet.

Eine Transaktion t⊆I ist eine solche Itemmenge. Die Menge aller Transaktionen bildet die Datenbasis 𝒟={t1,t2,…,td} mit d=|𝒟|.

Eine Assoziationsregel beschreibt eine Implikation der Form X→Y. Prämisse X und Konklusion Y sind disjunkte Itemmengen, d. h. X,Y⊆I und X∩Y=∅︀. Eine Transaktion t erfüllt die Regel X→Y, wenn X∪Y⊆t, t also alle in der Regel vorkommenden Items umfasst.

Wichtige Kenngrößen von Assoziationsregeln sind Support und Konfidenz.

support⁡(X)=|{t∈𝒟∣X⊆t}||𝒟|
Entsprechend ist der Support einer Regel X→Y gegeben durch die relative Häufigkeit der Transaktionen, die sowohl die Elemente der Prämisse X als auch die der Konklusion Y enthalten:
support⁡(X→Y)=support⁡(X∪Y)
confidence⁡(X→Y)=support⁡(X∪Y)support⁡(X)=|{t∈𝒟∣(X∪Y)⊆t}||{t∈𝒟∣X⊆t}|
Sie beschreibt also die bedingte Wahrscheinlichkeit dafür, dass eine Transaktion die X erfüllt auch Y erfüllt.
lift⁡(X→Y)=support⁡(X∪Y)support⁡(X)×support⁡(Y), wobei gilt:
lift⁡(X→Y)>1⇒X und Y sind positiv korreliertlift⁡(X→Y)<1⇒X und Y sind negativ korreliertlift⁡(X→Y)=1⇒X und Y sind unabhängig

Beispiel

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

confidence⁡({Zahnbürste}→{Zahncreme})=support⁡({Zahnbürste,Zahncreme})support⁡({Zahnbürste})

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 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. Der Ansatz erlaubt es die Irrtumswahrscheinlichkeit zu schätzen.

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) aus dem der Apriori-Algorithmus entwickelt wurde. Dieser wird mehr und mehr vom wesentlich effizienteren FPGrowth-Algorithmus abgelöst.