Diese Arbeit soll eine Einführung in das Themengebiet der Assoziationsanalyse bieten, bei der es darum geht, Regeln für das
gemeinsame Auftreten von Elementen in einer Datenbasis zu finden. Neben einer allgemeinen Definition werden die wichtigsten Interessantheitsmaße zur Beurteilung von Assoziationsregeln sowie einige populäre Algorithmen zur Generierung derselben, vor allem AIS und Apriori, vorgestellt. Zahlreiche Beispiele zum praktischen Einsatz, insbesondere aus der Warenkorbanalyse, sollen diese Arbeit auch für einen Leser ohne umfangreiche Statistik- und Mathematikkenntnisse verständlich machen.
Inhaltsverzeichnis
1 Einleitung
2 Interessantheitsmaße
2.1 Support
2.2 Confidence
2.3 Lift
2.4 Gain-Funktion und Piatetsky-Shapiro-Funktion
3 Algorithmen zur Assoziationsanalyse
3.1 AIS
3.2 A-priori
3.3 AprioriTid und AprioriHybrid Algorithmus
3.4 Verfahren unter Berücksichtigung von Taxonomien
3.5 Sequenzanalyse
4 Anwendung
4.1 Anwendung allgemein
4.2 Warenkorbanalyse
4.2.1 Virtuelle Items
4.2.2 Dissociation Rules
4.2.3 Transitive Regeln
5 Verfügbare Software
5.1 Überblick
5.2 arules im Detail
5.3 Weka im Detail
6 Fazit und Zusammenfassung
7 Literatur
Abbildungsverzeichnis
1 Berechnung von Support und Confidence, entnommen aus [BaVo08],
2 AIS-Algorithmus, entnommen aus [BaVo08],
3 Beispiel für eine Taxonomie, entnommen aus [HeHi03],
4 Beispiel für Berechnung von Support, Confidence und Lift bei transiti- ven Regeln, entnommen aus [HeHi03],
5 Beispiel für die Zusammenfassung transitiver Regelpaare, entnommen aus [HeHi03],
6 Weka (Screenshot), entnommen aus [EibeoJ],
1 Einleitung
Aufgabe der Assoziationsanalyse ist es, Zusammenhänge und Abhängigkeiten in einer Datenbasis zu entdecken. [BaVo08] Anders formuliert, geht es darum, Korrelationen zwischen gemeinsam auftretenden Dingen zu beschreiben. [Boll96]
Etwas technischer gesprochen betrachten wir also eine Menge, welche aus Items, also Elementen besteht. Diese Menge wird mit I bezeichnet, die darin enthaltenen Ele- mente werden von i1 bis in numeriert. Wir können also schreiben: I = { i 1,..., i n }
Eine Interpretation dieser Menge könnte zB so aussehen, dass wir damit alle Artikel, die es in einem Supermarkt zu kaufen gibt, bezeichnen.
Weiters existiert eine sogenannte
”Transaktionsmenge“T,dieeineTeilmengederItem-
menge I darstellt. Diese Transaktionsmenge könnte also zB als die Menge an Artikel
interpretiert werden, die ein bestimmter Kunde im Supermarkt in seinen Warenkorb gelegt hat.
Nun kann man alle Transaktionsmengen aller Kunden zusammenfassen und damit
die sogenannte
”Datenbasis“Dschaffen:
D = { T 1,..., T n }
Das Herz der Assoziationsanalyse stellen nun die sogenannten dar, die man sich natürlichsprachlich wie folgt denken kann:
”Assoziationsregeln“
”EnthälteineTransak-
tionsmenge den Artikel ix, dann enthält sie auch den Artikel iy.“ Der erste Teil einer
solchen Regel wird dabei auch als ”Regelrumpf“(oderauchPrämisse,engl. antece- dent) bezeichnet, der zweite Teile als ”Regelkopf“(oderauchKonklusion,engl. conse- quent). x und y müssen dabei nicht zwangsläufig einzelne Artikel sein, sondern man kann sich diese auch ganz allgemein als disjunkte Teilmengen von I vorstellen. Ziel
1 Einleitung
der Assoziationsanalyse ist es nun, möglichst viele gute Assoziationsregeln zu fin- den, d.h. jene, die möglichst oft auftretende Korrelationen gut beschreiben. [BaVo08]
Klarerweise gibt es nun Transaktionsmengen, die eine bestimmte Assoziationsregel erfüllen, und Transaktionsmengen, die eine Assoziationsregel nicht erfüllen. Das nächste Kapitel wird einige Maße vorstellen, mit denen die Güte von Assoziationsregeln bewertet werden kann.
Vorher ist es aber wohl zweckmäßig, das Prinzip der Assoziationsregeln noch ein- mal an einem Beispiel zu verdeutlichen, wobei aus Gründen der Übersichtlichkeit das oben begonnene Supermarkt-Beispiel fortgeführt werden soll, entnommen aus [BaVo08]:
Wir formulieren eine einfache Assoziationsregel zunächst natürlichsprachlich: ”Wenn ein Kunde Bier kauft, dann kauft er auch Chips.“ Richtig angeschrieben, sieht diese Regel dann so aus:
Bier → Chips = (Bier ∪ Chips) ⊂ T
Allgemein hat eine Assoziationsregel also die Form: X → Y =(X ∪ Y) ⊂ T
2 Interessantheitsmaße
Im Folgenden werden nun einige der bekanntesten Maße zur Beurteilung der Aussagekraft von Assoziationsregeln vorgestellt. Dabei handelt es sich aber nur um eine Auswahl der wichtigsten, denn in der Literatur finden sich noch eine ganze Reihe weiterer Kennzahlen. Jede weist dabei eigene Vor- und Nachteile auf, sodass es nicht zweckmäßig wäre, eine bestimmte Kennzahl generell zu präferieren. Vielmehr bietet es sich an, die jeweils interessante Kennzahl basierend auf der aktuellen Fragestellung auszuwählen bzw. mehrere Maße zu verwenden, um bei der Interpretation der Ergebnisse nicht zu eingeschränkt zu agieren. Auch kann man sich aus mehreren Interessantheitsmaßen einen Mittelwert errechnen und anschließend mit diesem verschiedene Assoziationsregeln vergleichen. [DoLi97]
2.1 Support
Der Support eines Items oder einer Itemmenge X ist definiert als die relative Häufigkeit dieses Items bzw. dieser Itemmenge in der Datenbasis. Formal angeschrieben also: sup (X) = [Abbildung in dieser Leseprobe nicht enthalten]
Der Support einer Assoziationsregel X → Y ist definiert als Anteil aller Transaktionen, die die Regel erfüllen, formal: [BaVo08]
sup (X → Y) = [Abbildung in dieser Leseprobe nicht enthalten]
Dazu wieder ein paar Beispiele, entnommen aus [BaVo08]:
In einem Supermarkt werden, kumuliertüber alle Transaktionsmengen T, insgesamt 200.000 Packungen Chips und 50.000 Flaschen Bier gekauft. In 20.000 Transaktionen kommen sowohl Chips als auch Bier vor. Insgesamt fallen 1.000.000 Transaktionen an. Verwenden wir die oben angeführten Definitionen, so errechnen wir:
- für die Chips einen Support von 20% (d.h. in 20% aller Transaktionen werden Chips gekauft)
- für das Bier einen Support von 5%
- für eine Assoziationsregel mit dem Inhalt auch Bier gekauft“ einen Support von 2%.
2.2 Confidence
”WerdenChipsgekauft,dannwird
Der Support ist also ein hilfreiches Maß, um festzustellen, ob eine Assoziationsregelüberhaupt Sinn macht, d.h. ob eine gewisse Kombination von Items in der Praxisüberhaupt von Bedeutung ist.
Wir möchten nun wissen, wie stark der Zusammenhang ist, den eine Assoziations- regel anzeigt, und dafür bietet sich die Kennzahl des Confidence an. Dabei wird im Prinzip der Support der Vereinigungsmenge zweier Items X und Y ins Verhältnis ge- setzt zum Support der Menge X selbst. Anders ausgedrückt ist Confidence also defi- niert als Anteil der Transaktionen, die sowohl X als auch Y beinhalten, an der Menge der Transaktionen, die X erfüllen. Formal angeschrieben, sieht die Definition also wie folgt aus: [BaVo08]
Abbildung in dieser Leseprobe nicht enthalten
Angemerkt sei noch, dass sowohl Support als auch Confidence Anteilswerte darstellen und sich daher immer zwischen 0 und 1 bewegen. Formal:
sup (X → Y), conf (X → Y) ∈ [0;1].
Um das Beispiel aus dem vorigen Subkapitel wieder aufzugreifen, wollen wir nun
- ausgehend von den selben Zahlen - noch den Confidence-Wert berechnen:
Um den Confidence der Assoziationsregel
”WerdenChipsgekauft,dannwirdauch Bier gekauft“ zu errechnen, setzen wir also den Support der Assoziationsregel ins Verhältnis zum Support der Chips selbst und kommen somit auf 2% dividiert durch 20%, d.h. 0,02 / 0,2. Das ergibt 0,1 oder 10%.
Nun interessiert uns noch der umgekehrte Fall, also die Regel ”WirdBiergekauft, dann werden auch Chips gekauft.“ Hier errechnen wir wieder den Support der As- soziationsregel, dividieren diesmal durch den Support des Biers und kommen im Ergebnis auf 40%. Wir werden später im Kapitel zu den Anwendungsbeispielen sehen, wie der Supermarkt diese Ergebnisse verwenden könnte, um das Ziel einer Umsatzsteigerung zu verfolgen.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: Berechnung von Support und Confidence, entnommen aus [BaVo08], S. 263
2.3 Lift
Bei der Berechnung des Confidence-Werts kann es in bestimmten Fällen nur zur Wiedergabe von bereits bekannten oder trivialen Informationen kommen. Technisch gesprochen stellt der Confidence-Wert ja nichts anderes dar als die bedingte Wahr- scheinlichkeit des Kaufs von Artikel Y, wenn Artikel X gekauft wird. Der Nachteil dabei ist allerdings, dass die Häufigkeit von Y somit nicht berücksichtigt wird. Das kann in Sonderfällen dazu führ]en, dass der Confidence-Wert einer Assoziationsregel (X → Y) letztlich der Häufigkeit von Y in der Datenbasis entspricht und somit die Assoziationsregel keine zusätzlichen Erkenntnisse mit sich bringt.
Dazu ein Beispiel, entnommen aus [BaVo08]: Wenn Joghurt und Schokolade beide jeweils in 80% aller Transaktionen enthalten sind, dann können wir in 0,8 * 0,8, also 64% aller Transaktionen einen gemeinsamen Kauf von beiden Produkten erwarten. Eine Assoziationsregel (Joghurt, Schokolade) hat dann einen Confidence-Wert von 0,64 / 0,8 = 0,8 und entspricht damit der Häufigkeit von Joghurt in der Datenbasis.
Eine daher notwendige zusätzliche Kennzahl ist die des Lift einer Assoziationsregel. Dieser ergibt sich wie folgt:
lift (X → Y) =[Abbildung in dieser Leseprobe nicht enthalten])
Hierbei wird also der Confidence-Wert einer Assoziationsregel ins Verhältnis zur re- lativen Häufigkeit von Y in der Datenbasis gesetzt. Ein Lift von 1 würde damit be- deuten, dass die Assoziationsregel keine zusätzlichen Erkenntnisse beinhaltet. Ein Lift von zB 2 hingegen würde bedeuten, dass der Artikel Y in Transaktionen, in de- nen auch X gekauft wird, doppelt so oft vorkommt, wie in Transaktionen, in denen X nicht gekauft wird. Generell gesprochen deutet also ein Lift größer als 1 auf eine positive Korrelation hin, während ein Lift kleiner als 1 auf eine negative Korrelation hinweist. Anzumerken ist noch, dass der Lift einer Regel (X → Y) immer gleich dem der Regel (Y → X) ist. [HeHi03]
2.4 Gain-Funktion und Piatetsky-Shapiro-Funktion
Die Gain-Funktion ist dem Confidence recht ähnlich und wie folgt definiert [HeHi03]: gain (X → Y) = sup (X → Y) − P ∗ sup (X)
Der Parameter P kann zwischen 0 und 1 gewählt werden, der Wertebereich der GainFunktion liegt damit zwischen -P und 1-P. Über den Parameter können Effekte auf die optimalen Regeln beobachtet werden, denn ein gain von 0 besagt, dass in jeder P-ten Transaktion, in der X enthalten ist, auch Y enthalten ist. Werteüber Null symbolisieren dann einen stärkeren Zusammenhang zwischen X und Y als durch P vorgegeben. Anders als bei der Confidence wird für die Gain-Funktion also eine Differenz anstatt eines Quotienten gebildet, wodurch verhindert werden soll, dass Regeln mit geringem Support trotzdem ein hohes Interessantheitsmaß erreichen.
Die Funktion von Piatetsky und Shapiro, kurz auch p-s Funktion, ist eine Sonderform der Gain-Funktion. Hierbei wird der Parameter P mit sup(Y) festgelegt. Ergibt also die p-s-Funktion einen Wert größer als 0, dann spiegelt die Assoziationsregel somit einen positiven Zusammenhang wider, der höher ist als der erwartete Support bei statistischer Unabhängigkeit. Analog stellen Werte kleiner als 0 einen negativen Zu- sammenhang dar. Wie für den Lift gilt auch für den p-s-Wert, dass p-s(X → Y) =p- s(Y → X). [HeHi03]
[...]
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.