Big Data Analytics - Règles d'association
Soit I = i 1 , i 2 , ..., i n un ensemble de n attributs binaires appelés items. Soit D = t 1 , t 2 , ..., 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}