Big Data Analytics - Règles d'association

Soit I = i ₁ , i ₂ , ..., i _n un ensemble de n attributs binaires appelés items. Soit D = t ₁ , t ₂ , ..., t _m un ensemble de transactions appelé base de données. Chaque transaction en D a un identifiant de transaction unique et contient un sous-ensemble des éléments en I. Une règle est définie comme une implication de la forme X ⇒ Y où X, Y ⊆ I et X ∩ Y = ∅.

Les ensembles d'éléments (pour les ensembles d'éléments courts) X et Y sont appelés antécédent (côté gauche ou LHS) et conséquents (côté droit ou RHS) de la règle.

Pour illustrer les concepts, nous utilisons un petit exemple du domaine des supermarchés. L'ensemble des éléments est I = {lait, pain, beurre, bière} et une petite base de données contenant les éléments est présentée dans le tableau suivant.

identifiant de transaction	Articles
1	lait, pain
2	Pain au beurre
3	Bière
4	lait, pain, beurre
5	Pain au beurre

Un exemple de règle pour le supermarché pourrait être {lait, pain} ⇒ {beurre}, ce qui signifie que si du lait et du pain sont achetés, les clients achètent également du beurre. Pour sélectionner des règles intéressantes parmi l'ensemble de toutes les règles possibles, des contraintes sur diverses mesures de signification et d'intérêt peuvent être utilisées. Les contraintes les plus connues sont les seuils minimaux de soutien et de confiance.

Le support supp (X) d'un ensemble d'articles X est défini comme la proportion de transactions dans l'ensemble de données qui contient l'ensemble d'articles. Dans l'exemple de base de données du tableau 1, l'ensemble d'items {lait, pain} a un support de 2/5 = 0,4 puisqu'il se produit dans 40% de toutes les transactions (2 transactions sur 5). Trouver des ensembles d'éléments fréquents peut être considéré comme une simplification du problème d'apprentissage non supervisé.

La confiance d'une règle est définie conf (X ⇒ Y) = supp (X ∪ Y) / supp (X). Par exemple, la règle {lait, pain} ⇒ {beurre} a une confiance de 0,2 / 0,4 = 0,5 dans la base de données du tableau 1, ce qui signifie que pour 50% des transactions contenant du lait et du pain, la règle est correcte. La confiance peut être interprétée comme une estimation de la probabilité P (Y | X), la probabilité de trouver l'ERS de la règle dans les transactions à la condition que ces transactions contiennent également la LHS.

Dans le script situé dans bda/part3/apriori.R le code pour implémenter le apriori algorithm peut être trouvé.

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

Afin de générer des règles à l'aide de l'algorithme apriori, nous devons créer une matrice de transaction. Le code suivant montre comment procéder dans 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}