Big Data Analytics - Assoziationsregeln
Sei I = i 1 , i 2 , ..., i n eine Menge von n binären Attributen, die als Elemente bezeichnet werden. Sei D = t 1 , t 2 , ..., t m eine Menge von Transaktionen, die als Datenbank bezeichnet werden. Jede Transaktion in D hat eine eindeutige Transaktions-ID und enthält eine Teilmenge der Elemente in I. Eine Regel wird als Implikation der Form X ⇒ Y definiert, wobei X, Y ⊆ I und X ∩ Y = ∅.
Die Objektgruppen (für kurze Objektgruppen) X und Y werden als Antezedenz (linke Seite oder LHS) und als Konsequenz (rechte Seite oder RHS) der Regel bezeichnet.
Zur Veranschaulichung der Konzepte verwenden wir ein kleines Beispiel aus dem Supermarktbereich. Die Menge der Elemente ist I = {Milch, Brot, Butter, Bier}. Eine kleine Datenbank mit den Elementen ist in der folgenden Tabelle aufgeführt.
| Transaktions-ID | Artikel |
|---|---|
| 1 | Milchbrot |
| 2 | Brot Butter |
| 3 | Bier |
| 4 | Milch, Brot, Butter |
| 5 | Brot Butter |
Eine Beispielregel für den Supermarkt könnte {Milch, Brot} ⇒ {Butter} sein, was bedeutet, dass Kunden beim Kauf von Milch und Brot auch Butter kaufen. Um interessante Regeln aus dem Satz aller möglichen Regeln auszuwählen, können Einschränkungen für verschiedene Maßstäbe von Bedeutung und Interesse verwendet werden. Die bekanntesten Einschränkungen sind Mindestschwellen für Unterstützung und Vertrauen.
Das Support Supp (X) eines Item-Sets X ist definiert als der Anteil der Transaktionen im Datensatz, die das Item-Set enthalten. In der Beispieldatenbank in Tabelle 1 unterstützt der Item-Set {Milch, Brot} 2/5 = 0,4, da er in 40% aller Transaktionen (2 von 5 Transaktionen) auftritt. Das Auffinden häufiger Objektgruppen kann als Vereinfachung des unbeaufsichtigten Lernproblems angesehen werden.
Das Vertrauen einer Regel ist definiert als conf (X ⇒ Y) = supp (X ∪ Y) / supp (X). Zum Beispiel hat die Regel {Milch, Brot} ⇒ {Butter} ein Vertrauen von 0,2 / 0,4 = 0,5 in der Datenbank in Tabelle 1, was bedeutet, dass für 50% der Transaktionen, die Milch und Brot enthalten, die Regel korrekt ist. Das Vertrauen kann als Schätzung der Wahrscheinlichkeit P (Y | X) interpretiert werden, der Wahrscheinlichkeit, die RHS der Regel in Transaktionen unter der Bedingung zu finden, dass diese Transaktionen auch die LHS enthalten.
In dem Skript in bda/part3/apriori.R den Code zur Implementierung des apriori algorithm kann gefunden werden.
# Load the library for doing association rules
# install.packages(’arules’)
library(arules)
# Data preprocessing
data("AdultUCI")
AdultUCI[1:2,]
AdultUCI[["fnlwgt"]] <- NULL
AdultUCI[["education-num"]] <- NULL
AdultUCI[[ "age"]] <- ordered(cut(AdultUCI[[ "age"]], c(15,25,45,65,100)),
labels = c("Young", "Middle-aged", "Senior", "Old"))
AdultUCI[[ "hours-per-week"]] <- ordered(cut(AdultUCI[[ "hours-per-week"]],
c(0,25,40,60,168)), labels = c("Part-time", "Full-time", "Over-time", "Workaholic"))
AdultUCI[[ "capital-gain"]] <- ordered(cut(AdultUCI[[ "capital-gain"]],
c(-Inf,0,median(AdultUCI[[ "capital-gain"]][AdultUCI[[ "capitalgain"]]>0]),Inf)),
labels = c("None", "Low", "High"))
AdultUCI[[ "capital-loss"]] <- ordered(cut(AdultUCI[[ "capital-loss"]],
c(-Inf,0, median(AdultUCI[[ "capital-loss"]][AdultUCI[[ "capitalloss"]]>0]),Inf)),
labels = c("none", "low", "high"))Um Regeln mit dem Apriori-Algorithmus zu generieren, müssen wir eine Transaktionsmatrix erstellen. Der folgende Code zeigt, wie dies in R gemacht wird.
# Convert the data into a transactions format
Adult <- as(AdultUCI, "transactions")
Adult
# transactions in sparse format with
# 48842 transactions (rows) and
# 115 items (columns)
summary(Adult)
# Plot frequent item-sets
itemFrequencyPlot(Adult, support = 0.1, cex.names = 0.8)
# generate rules
min_support = 0.01
confidence = 0.6
rules <- apriori(Adult, parameter = list(support = min_support, confidence = confidence))
rules
inspect(rules[100:110, ])
# lhs rhs support confidence lift
# {occupation = Farming-fishing} => {sex = Male} 0.02856148 0.9362416 1.4005486
# {occupation = Farming-fishing} => {race = White} 0.02831579 0.9281879 1.0855456
# {occupation = Farming-fishing} => {native-country 0.02671881 0.8758389 0.9759474
= United-States}