data > opinion

Tom Alby

10 Assoziationsanalyse

2021-05-02


Warenkorbanalyse / Association Rules

Der apriori-Algorithmus

Association Rules werden für eine Warenkorbanalyse verwendet. Die Ergebnisse solcher Analysen sind bekannt aus Shops, in denen bei der Auswahl eines Artikels Empfehlungen wie “Kunden, die diesen Artikel gekauft haben, haben auch diesen Artikel gekauft.” Wir der Name schon sagt, wird ein solcher Zusammenhang hier “Assoziation” genannt.

Das Package arules enthält den apriori-Algorithmus, ein Verfahren zur Assoziationsanalyse aus dem Data Mining. Mithilfe dieses Algorithmus werden Zusammenhänge in transaktionsbasierten Datenbanken identifiziert; diese Zusammenhänge werden in sogenannten Assoziationsregeln dargestellt. Der apriori-Algorithmus ist ein spezieller Ansatz, bei dem selten auftauchende Items ignoriert werden, aber auch die Transaktionen, in denen dieses seltene Item auftaucht. Dadurch wird der Umfang der durchzurechnenden Daten reduziert. Denn sobald die Datenmengen größer werden, kommt der Arbeitsspeicher wieder ins Spiel.

Stellen wir uns einmal vor, dass in 10% aller Einkäufe Bier gekauft wird und in 7% der Einkäufe Kartoffelchips. Schauen wir uns nur die Bierkäufe an und in diesen Käufen kommen Kartoffelchips auch nur zu 7% vor, dann gibt es hier keinen Zusammenhang. Werden aber bei allen Bier-Käufen zu 25% auch Kartoffelchips gekauft, dann scheint es hier eine Assoziation zu geben. Eine Assoziation ist nicht auf zwei Produkte beschränkt; so kann es sein, dass Bier mit Kartoffelchips, Wein und Käsewürfeln assoziiert ist. Diese Assoziationen müssen nicht immer stark sein.

Wir starten zunächst mit einem ganz einfachen, selbst konstruierten Beispiel, damit alle Berechnungen nachvollzogen werden können.

library(arules)
## Loading required package: Matrix
## 
## Attaching package: 'arules'
## The following objects are masked from 'package:base':
## 
##     abbreviate, write
a_list <- list( # Die Beispiel-Daten, jede Zeile hier ist sozusagen ein Kassenbon
      c("apfel", "bier", "reis", "huhn"),
      c("apfel", "bier", "reis"),
      c("apfel", "bier"),
      c("apfel", "birne"),
      c("milch", "bier", "reis", "huhn"),
      c("milch", "bier", "reis"),
      c("milch", "bier"),
      c("apfel", "birne")
      )

## Jeder Transaktion wird ein Name gegeben
names(a_list) <- paste("Tr",c(1:8), sep = "")
a_list
## $Tr1
## [1] "apfel" "bier"  "reis"  "huhn" 
## 
## $Tr2
## [1] "apfel" "bier"  "reis" 
## 
## $Tr3
## [1] "apfel" "bier" 
## 
## $Tr4
## [1] "apfel" "birne"
## 
## $Tr5
## [1] "milch" "bier"  "reis"  "huhn" 
## 
## $Tr6
## [1] "milch" "bier"  "reis" 
## 
## $Tr7
## [1] "milch" "bier" 
## 
## $Tr8
## [1] "apfel" "birne"
## Umwandlung in das Transactions-Format
trans <- as(a_list, "transactions")

Die Speicherung in der Struktur transactions ist die Voraussetzung, um den apriori-Algorithmus auf den Daten laufen zu lassen. Hierbei wird Speicher gespart.

trans
## transactions in sparse format with
##  8 transactions (rows) and
##  6 items (columns)
as(trans,"matrix")
##     apfel  bier birne  huhn milch  reis
## Tr1  TRUE  TRUE FALSE  TRUE FALSE  TRUE
## Tr2  TRUE  TRUE FALSE FALSE FALSE  TRUE
## Tr3  TRUE  TRUE FALSE FALSE FALSE FALSE
## Tr4  TRUE FALSE  TRUE FALSE FALSE FALSE
## Tr5 FALSE  TRUE FALSE  TRUE  TRUE  TRUE
## Tr6 FALSE  TRUE FALSE FALSE  TRUE  TRUE
## Tr7 FALSE  TRUE FALSE FALSE  TRUE FALSE
## Tr8  TRUE FALSE  TRUE FALSE FALSE FALSE

Im folgenden Schritt werden die Regeln “gemined”, die Erklärungen dazu folgen gleich:

trans.rules <- apriori(trans, parameter=list(supp=0.01, conf=0.3, 
                                                target="rules"))
## Apriori
## 
## Parameter specification:
##  confidence minval smax arem  aval originalSupport maxtime support minlen
##         0.3    0.1    1 none FALSE            TRUE       5    0.01      1
##  maxlen target  ext
##      10  rules TRUE
## 
## Algorithmic control:
##  filter tree heap memopt load sort verbose
##     0.1 TRUE TRUE  FALSE TRUE    2    TRUE
## 
## Absolute minimum support count: 0 
## 
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[6 item(s), 8 transaction(s)] done [0.00s].
## sorting and recoding items ... [6 item(s)] done [0.00s].
## creating transaction tree ... done [0.00s].
## checking subsets of size 1 2 3 4 done [0.00s].
## writing ... [52 rule(s)] done [0.00s].
## creating S4 object  ... done [0.00s].

Nun schauen wir uns diese Regeln einmal an:

head(inspect(subset(trans.rules)), 10)
##      lhs                  rhs     support confidence coverage lift     count
## [1]  {}                => {milch} 0.375   0.3750000  1.000    1.000000 3    
## [2]  {}                => {apfel} 0.625   0.6250000  1.000    1.000000 5    
## [3]  {}                => {reis}  0.500   0.5000000  1.000    1.000000 4    
## [4]  {}                => {bier}  0.750   0.7500000  1.000    1.000000 6    
## [5]  {birne}           => {apfel} 0.250   1.0000000  0.250    1.600000 2    
## [6]  {apfel}           => {birne} 0.250   0.4000000  0.625    1.600000 2    
## [7]  {huhn}            => {milch} 0.125   0.5000000  0.250    1.333333 1    
## [8]  {milch}           => {huhn}  0.125   0.3333333  0.375    1.333333 1    
## [9]  {huhn}            => {apfel} 0.125   0.5000000  0.250    0.800000 1    
## [10] {huhn}            => {reis}  0.250   1.0000000  0.250    2.000000 2    
## [11] {reis}            => {huhn}  0.250   0.5000000  0.500    2.000000 2    
## [12] {huhn}            => {bier}  0.250   1.0000000  0.250    1.333333 2    
## [13] {bier}            => {huhn}  0.250   0.3333333  0.750    1.333333 2    
## [14] {milch}           => {reis}  0.250   0.6666667  0.375    1.333333 2    
## [15] {reis}            => {milch} 0.250   0.5000000  0.500    1.333333 2    
## [16] {milch}           => {bier}  0.375   1.0000000  0.375    1.333333 3    
## [17] {bier}            => {milch} 0.375   0.5000000  0.750    1.333333 3    
## [18] {apfel}           => {reis}  0.250   0.4000000  0.625    0.800000 2    
## [19] {reis}            => {apfel} 0.250   0.5000000  0.500    0.800000 2    
## [20] {apfel}           => {bier}  0.375   0.6000000  0.625    0.800000 3    
## [21] {bier}            => {apfel} 0.375   0.5000000  0.750    0.800000 3    
## [22] {reis}            => {bier}  0.500   1.0000000  0.500    1.333333 4    
## [23] {bier}            => {reis}  0.500   0.6666667  0.750    1.333333 4    
## [24] {huhn,milch}      => {reis}  0.125   1.0000000  0.125    2.000000 1    
## [25] {huhn,reis}       => {milch} 0.125   0.5000000  0.250    1.333333 1    
## [26] {milch,reis}      => {huhn}  0.125   0.5000000  0.250    2.000000 1    
## [27] {huhn,milch}      => {bier}  0.125   1.0000000  0.125    1.333333 1    
## [28] {bier,huhn}       => {milch} 0.125   0.5000000  0.250    1.333333 1    
## [29] {bier,milch}      => {huhn}  0.125   0.3333333  0.375    1.333333 1    
## [30] {apfel,huhn}      => {reis}  0.125   1.0000000  0.125    2.000000 1    
## [31] {huhn,reis}       => {apfel} 0.125   0.5000000  0.250    0.800000 1    
## [32] {apfel,reis}      => {huhn}  0.125   0.5000000  0.250    2.000000 1    
## [33] {apfel,huhn}      => {bier}  0.125   1.0000000  0.125    1.333333 1    
## [34] {bier,huhn}       => {apfel} 0.125   0.5000000  0.250    0.800000 1    
## [35] {apfel,bier}      => {huhn}  0.125   0.3333333  0.375    1.333333 1    
## [36] {huhn,reis}       => {bier}  0.250   1.0000000  0.250    1.333333 2    
## [37] {bier,huhn}       => {reis}  0.250   1.0000000  0.250    2.000000 2    
## [38] {bier,reis}       => {huhn}  0.250   0.5000000  0.500    2.000000 2    
## [39] {milch,reis}      => {bier}  0.250   1.0000000  0.250    1.333333 2    
## [40] {bier,milch}      => {reis}  0.250   0.6666667  0.375    1.333333 2    
## [41] {bier,reis}       => {milch} 0.250   0.5000000  0.500    1.333333 2    
## [42] {apfel,reis}      => {bier}  0.250   1.0000000  0.250    1.333333 2    
## [43] {apfel,bier}      => {reis}  0.250   0.6666667  0.375    1.333333 2    
## [44] {bier,reis}       => {apfel} 0.250   0.5000000  0.500    0.800000 2    
## [45] {huhn,milch,reis} => {bier}  0.125   1.0000000  0.125    1.333333 1    
## [46] {bier,huhn,milch} => {reis}  0.125   1.0000000  0.125    2.000000 1    
## [47] {bier,huhn,reis}  => {milch} 0.125   0.5000000  0.250    1.333333 1    
## [48] {bier,milch,reis} => {huhn}  0.125   0.5000000  0.250    2.000000 1    
## [49] {apfel,huhn,reis} => {bier}  0.125   1.0000000  0.125    1.333333 1    
## [50] {apfel,bier,huhn} => {reis}  0.125   1.0000000  0.125    2.000000 1    
## [51] {bier,huhn,reis}  => {apfel} 0.125   0.5000000  0.250    0.800000 1    
## [52] {apfel,bier,reis} => {huhn}  0.125   0.5000000  0.250    2.000000 1
##          lhs        rhs support confidence coverage     lift count
## [1]       {} => {milch}   0.375  0.3750000    1.000 1.000000     3
## [2]       {} => {apfel}   0.625  0.6250000    1.000 1.000000     5
## [3]       {} =>  {reis}   0.500  0.5000000    1.000 1.000000     4
## [4]       {} =>  {bier}   0.750  0.7500000    1.000 1.000000     6
## [5]  {birne} => {apfel}   0.250  1.0000000    0.250 1.600000     2
## [6]  {apfel} => {birne}   0.250  0.4000000    0.625 1.600000     2
## [7]   {huhn} => {milch}   0.125  0.5000000    0.250 1.333333     1
## [8]  {milch} =>  {huhn}   0.125  0.3333333    0.375 1.333333     1
## [9]   {huhn} => {apfel}   0.125  0.5000000    0.250 0.800000     1
## [10]  {huhn} =>  {reis}   0.250  1.0000000    0.250 2.000000     2

Jede Zeile hier stellt eine Assoziationsregel dar. In der fünften Zeile sehen wir die Assoziation von Birne und Apfel. Man könnte es so ausdrücken: Das Auftreten von Birne (lhs für left-hand side), wenn Apfel (rhs für right-hand side) auftritt. Eine Regel bedeutet übrigens keine Kausalität (wobei eine Assoziation von Wein und Korkenzieher dies mutmaßen lassen könnte).

Jede Regel kommt mit mehreren Metriken:

  • Support: Die Anzahl der Transaktionen mit dieser Item-Kombination geteilt durch alle Transaktionen, ungeachtet dessen, ob weitere Items in der Transaktion waren. Die Kombination {Milch,Bier} kommt drei Mal vor, einmal alleine, zwei Mal mit anderen Items.
  • Confidence: hat nichts mit der Konfidenz zu tun, die wir bereits bei dem Signifikanztest kennen gelernt haben. Hier geht es um den Support für das gleichzeitige Auftreten aller Items in einer Regel, bedingt nur durch den Support für das Left-hand Set. Dies wird so berechnet: \(confidence(X ⇒Y)=\frac{support(X ∩ Y)}{support(X)}\); in dem Beispiel für Apfel => Birne wäre das \(\frac{0,25}{0,625} = 0,4\). Dies könnte man so ausdrücken: Birnen tauchen in 40% der Fälle auf, wo auch Äpfel auftauchen.
  • Lift: Diese Metrik gibt an, wie viel häufiger ein Set auftaucht als wir erwarten würden, wenn die Items unabhängig voneinander wären. Berechnet wird der Lift wie folgt: \(lift(X ⇒Y) = \frac{support(X ∩ Y)}{(support(X) * support(Y))}\). Am Beispiel Apfel => Birne verdeutlicht: \(\frac{0,25}{(0,625 * 0,25)} = 1,6\). Die Kombination {Apfel, Birne} erscheint 1,6x häufiger als wir erwarten würde, wenn sie unabhängig voneinander wären.

Diese drei Metriken sind im Zusammenspiel wichtig, denn zum einen möchte man Items-Sets “minen”, die häufig genug auftauchen, dass sie auch geschäftlich sinnvoll sind. Zum andern möchte man eine starke Assoziation sehen, die in der Confidence abgebildet ist. Allerdings kann diese auch irreführend sein, wenn wir uns zum Beispiel die Items Apfel und Bier ansehen. Sie werden häufig zusammen gekauft, aber das kann auch einfach daran liegen, dass diese Items generell häufig gekauft werden. Diesen Effekt kann die Metrik Lift lindern.

Visualisierung von Association Rules

Zunächst wollen wir uns nur die Regeln ansehen, die einen besonders hohen Lift haben:

subrules <- head(trans.rules, n = 15, by = "lift")

Dann laden wir das Package arulesViz, das die Daten aus den Regeln visualisieren kann. Hier wählen wir die Methode “Graph” (die weiteren Methoden werden hier unterschlagen):

library(arulesViz)
plot(subrules, method = "graph")

Was sehen wir hier? Zunächst einmal sehen wir die einzelnen Regeln, die sich aus Items und Verbindungen zusammensetzen. Von einem Item geht ein Pfeil auf einen Kreis, und von dem Kreis auf ein anderes Item. Je dunkler der Kreis, desto höher der Lift. Je größer der Kreis, desto höher der Support.

Association Rules mit dem Datensatz Groceries

Wir wollen das Gelernte nun auf einen größeren Datensatz anwenden. Netterweise bringt das Package apriori auch einen Datensatz mit, Groceries. Dieser enthält knapp 10.000 Transaktionen (Einkaufskörbe oder Kassenbons) und 169 Items (Produkte). Wir schauen uns davon die ersten fünf Zeilen an. In den Spalten sind alle Items, die der Laden zu bieten hat, in den Zeilen steht TRUE, wenn eines der Items gekauft wurde.

data("Groceries")

Auch hier erstellen wir wieder Assoziations-Regeln; es empfiehlt sich, etwas mit den Parametern Support und Confidence “herumzuspielen”, um interessante Regeln zu “minen”.

groc.rules <- apriori(Groceries, parameter=list(supp=0.01, conf=0.1, 
                                                target="rules"))
## Apriori
## 
## Parameter specification:
##  confidence minval smax arem  aval originalSupport maxtime support minlen
##         0.1    0.1    1 none FALSE            TRUE       5    0.01      1
##  maxlen target  ext
##      10  rules TRUE
## 
## Algorithmic control:
##  filter tree heap memopt load sort verbose
##     0.1 TRUE TRUE  FALSE TRUE    2    TRUE
## 
## Absolute minimum support count: 98 
## 
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 transaction(s)] done [0.00s].
## sorting and recoding items ... [88 item(s)] done [0.00s].
## creating transaction tree ... done [0.00s].
## checking subsets of size 1 2 3 4 done [0.00s].
## writing ... [435 rule(s)] done [0.00s].
## creating S4 object  ... done [0.00s].

Und schauen uns dann diese Regeln an:

my_rules <- inspect(subset(groc.rules, lift > 3))
##     lhs                                  rhs                  support   
## [1] {beef}                            => {root vegetables}    0.01738688
## [2] {root vegetables}                 => {beef}               0.01738688
## [3] {whole milk,yogurt}               => {curd}               0.01006609
## [4] {other vegetables,yogurt}         => {whipped/sour cream} 0.01016777
## [5] {citrus fruit,root vegetables}    => {other vegetables}   0.01037112
## [6] {citrus fruit,other vegetables}   => {root vegetables}    0.01037112
## [7] {tropical fruit,root vegetables}  => {other vegetables}   0.01230300
## [8] {tropical fruit,other vegetables} => {root vegetables}    0.01230300
##     confidence coverage   lift     count
## [1] 0.3313953  0.05246568 3.040367 171  
## [2] 0.1595149  0.10899847 3.040367 171  
## [3] 0.1796733  0.05602440 3.372304  99  
## [4] 0.2341920  0.04341637 3.267062 100  
## [5] 0.5862069  0.01769192 3.029608 102  
## [6] 0.3591549  0.02887646 3.295045 102  
## [7] 0.5845411  0.02104728 3.020999 121  
## [8] 0.3427762  0.03589222 3.144780 121
library(tidyverse)
## ── Attaching packages ─────────────────────────────────────── tidyverse 1.3.0 ──
## ✓ ggplot2 3.3.3     ✓ purrr   0.3.4
## ✓ tibble  3.1.0     ✓ dplyr   1.0.5
## ✓ tidyr   1.1.3     ✓ stringr 1.4.0
## ✓ readr   1.4.0     ✓ forcats 0.5.1
## ── Conflicts ────────────────────────────────────────── tidyverse_conflicts() ──
## x tidyr::expand() masks Matrix::expand()
## x dplyr::filter() masks stats::filter()
## x dplyr::lag()    masks stats::lag()
## x tidyr::pack()   masks Matrix::pack()
## x dplyr::recode() masks arules::recode()
## x tidyr::unpack() masks Matrix::unpack()
myRules_Direct <- as(groc.rules, "data.frame");
myRules_Direct %>%
  filter(lift > 1.1) %>%
  arrange(desc(lift)) %>%
  head()
##                                                    rules    support confidence
## 1                          {whole milk,yogurt} => {curd} 0.01006609  0.1796733
## 2   {citrus fruit,other vegetables} => {root vegetables} 0.01037112  0.3591549
## 3      {other vegetables,yogurt} => {whipped/sour cream} 0.01016777  0.2341920
## 4 {tropical fruit,other vegetables} => {root vegetables} 0.01230300  0.3427762
## 5                            {root vegetables} => {beef} 0.01738688  0.1595149
## 6                            {beef} => {root vegetables} 0.01738688  0.3313953
##     coverage     lift count
## 1 0.05602440 3.372304    99
## 2 0.02887646 3.295045   102
## 3 0.04341637 3.267062   100
## 4 0.03589222 3.144780   121
## 5 0.10899847 3.040367   171
## 6 0.05246568 3.040367   171

Auch hier plotten wir wieder:

subrules <- head(groc.rules, n = 10, by = "lift")
plot(subrules, method = "graph")

Was kann ein Händler mit diesen Regeln anfangen?