Big Data Analytics - Regole di associazione

Sia I = i ₁ , i ₂ , ..., i _n un insieme di n attributi binari chiamati elementi. Sia D = t ₁ , t ₂ , ..., t _m un insieme di transazioni chiamato database. Ogni transazione in D ha un ID transazione univoco e contiene un sottoinsieme degli elementi in I. Una regola è definita come un'implicazione della forma X ⇒ Y dove X, Y ⊆ I e X ∩ Y = ∅.

Gli insiemi di elementi (per insiemi di elementi brevi) X e Y sono chiamati antecedenti (lato sinistro o LHS) e conseguenti (lato destro o RHS) della regola.

Per illustrare i concetti, utilizziamo un piccolo esempio dal dominio del supermercato. L'insieme di elementi è I = {latte, pane, burro, birra} e un piccolo database contenente gli elementi è mostrato nella tabella seguente.

ID transazione	Elementi
1	latte, pane
2	Pane burro
3	birra
4	latte, pane, burro
5	Pane burro

Una regola di esempio per il supermercato potrebbe essere {latte, pane} ⇒ {burro}, il che significa che se vengono acquistati latte e pane, anche i clienti acquistano burro. Per selezionare regole interessanti dall'insieme di tutte le regole possibili, è possibile utilizzare vincoli su varie misure di significatività e interesse. I vincoli più noti sono le soglie minime di supporto e fiducia.

Il supporto (X) di un insieme di elementi X è definito come la proporzione di transazioni nel set di dati che contiene l'insieme di elementi. Nel database di esempio nella Tabella 1, l'insieme di elementi {latte, pane} ha un supporto di 2/5 = 0,4 poiché si verifica nel 40% di tutte le transazioni (2 su 5 transazioni). Trovare insiemi di oggetti frequenti può essere visto come una semplificazione del problema dell'apprendimento senza supervisione.

La confidenza di una regola è definita conf (X ⇒ Y) = supp (X ∪ Y) / supp (X). Ad esempio, la regola {latte, pane} ⇒ {burro} ha una confidenza di 0,2 / 0,4 = 0,5 nel database nella Tabella 1, il che significa che per il 50% delle transazioni contenenti latte e pane la regola è corretta. La fiducia può essere interpretata come una stima della probabilità P (Y | X), la probabilità di trovare l'RHS della regola nelle transazioni a condizione che queste transazioni contengano anche l'LHS.

Nello script situato in bda/part3/apriori.R il codice per implementare il apriori algorithm possono essere trovati.

# 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"))

Per generare regole utilizzando l'algoritmo apriori, dobbiamo creare una matrice di transazione. Il codice seguente mostra come eseguire questa operazione in R.

# 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}