Extrayez des motifs fréquents et des règles d'association
Un supermarché enregistre des milliers de paniers par jour. Quels produits sont achetés ensemble ? Une plateforme de photos reçoit des images accompagnées de mots-clés (tags). Quels tags reviennent ensemble dans un même quartier ? Ces questions n’ont pas de variable cible : on cherche des régularités cachées dans des listes d’objets. C’est la fouille de motifs (pattern mining).
Dans ce chapitre, vous allez apprendre à extraire les itemsets fréquents avec l’algorithme Apriori, puis à en tirer des règles d’association du type « qui achète des oignons achète aussi des œufs », et à juger si elles sont intéressantes. Notre fil rouge est le petit jeu de cinq paniers fourni en exemple dans notre TP.
Transactions, itemsets et support
Section intitulée « Transactions, itemsets et support »Les données prennent la forme d’une base de transactions : chaque transaction est un ensemble d’items (des produits, des tags, des symptômes). Voici nos cinq paniers :
| Panier | Contenu |
|---|---|
| 1 | lait, oignon, muscade, haricots rouges, œufs, yaourt |
| 2 | aneth, oignon, muscade, haricots rouges, œufs, yaourt |
| 3 | lait, pomme, haricots rouges, œufs |
| 4 | lait, licorne, maïs, haricots rouges, yaourt |
| 5 | maïs, oignon, oignon, haricots rouges, glace, œufs |
Un itemset est un ensemble d’items, par exemple {œufs, oignon}. Son support est la proportion de transactions qui le contiennent (on le donne parfois en nombre de transactions). Ici, {œufs, oignon} apparaît dans les paniers 1, 2 et 5 : son support vaut . Un itemset est dit fréquent si son support atteint un seuil fixé, le support minimal (minsup).
Remarquez le panier 5, qui contient deux fois « oignon » : une transaction est un ensemble, la répétition ne compte pas. L’encodeur utilisé en TP transforme d’ailleurs chaque transaction en une ligne de booléens, une colonne par item :
import pandas as pdfrom mlxtend.frequent_patterns import apriorifrom mlxtend.preprocessing import TransactionEncoder
paniers = [["lait", "oignon", "muscade", "haricots", "oeufs", "yaourt"], ["aneth", "oignon", "muscade", "haricots", "oeufs", "yaourt"], ["lait", "pomme", "haricots", "oeufs"], ["lait", "licorne", "mais", "haricots", "yaourt"], ["mais", "oignon", "oignon", "haricots", "glace", "oeufs"]]
encodeur = TransactionEncoder()tableau = pd.DataFrame(encodeur.fit(paniers).transform(paniers), columns=encodeur.columns_)frequents = apriori(tableau, min_support=0.6, use_colnames=True)print(frequents)Avec un support minimal de 0,6, le TP obtient 11 itemsets fréquents : cinq items seuls (haricots rouges avec un support de 1,0, œufs 0,8, lait, oignon et yaourt 0,6 chacun), cinq paires ({haricots, œufs} à 0,8, puis {œufs, oignon}, {haricots, lait}, {haricots, oignon} et {haricots, yaourt} à 0,6) et un seul triplet, {haricots, œufs, oignon}, à 0,6.
L’explosion combinatoire et l’anti-monotonie
Section intitulée « L’explosion combinatoire et l’anti-monotonie »Pourquoi ne pas simplement compter le support de tous les itemsets possibles ? Parce qu’avec items, il y en a . Nos 11 items donnent déjà 2 047 itemsets ; un supermarché qui vend 10 000 produits en aurait un nombre à plus de 3 000 chiffres. Il faut élaguer.
La clé est une propriété toute simple, l’anti-monotonie du support : si un itemset est infréquent, tous ses sur-ensembles le sont aussi. En effet, toute transaction qui contient {lait, yaourt, haricots} contient forcément {lait, yaourt} : le support ne peut que diminuer quand on ajoute des items. Autrement dit, dès qu’un itemset est infréquent, inutile d’explorer ce qui le contient.
L’algorithme Apriori
Section intitulée « L’algorithme Apriori »Apriori exploite cette propriété en avançant niveau par niveau, par taille croissante des itemsets :
- compter le support de chaque item seul et garder les fréquents (niveau 1) ;
- à partir des itemsets fréquents de taille , générer les candidats de taille (en combinant deux itemsets qui ne diffèrent que d’un item) ;
- élaguer tout candidat dont un sous-ensemble de taille n’est pas fréquent (anti-monotonie) ;
- compter le support des candidats restants en parcourant la base, et garder les fréquents ;
- recommencer jusqu’à ce qu’il n’y ait plus de candidat.
L’étape coûteuse d’Apriori est le comptage : à chaque niveau, il faut reparcourir toute la base pour compter le support de candidats parfois très nombreux (surtout au niveau 2, avec un seuil bas). Le choix du support minimal est donc un compromis : trop haut, on ne trouve que des évidences ; trop bas, le nombre de candidats explose.
Des itemsets aux règles d’association
Section intitulée « Des itemsets aux règles d’association »Un itemset fréquent dit « ces items vont ensemble ». Une règle d’association ajoute une direction : « quand on voit , on voit souvent », avec et deux itemsets disjoints. Trois mesures l’évaluent.
- Le support de la règle est celui de : la règle concerne-t-elle beaucoup de transactions ?
- La confiance est la proportion de transactions contenant qui contiennent aussi :
- Le lift compare cette confiance à la fréquence de en général :
Un lift supérieur à 1 signale une association positive ( rend plus probable), égal à 1 une indépendance, inférieur à 1 une association négative.
On génère les règles à partir des itemsets fréquents : pour chaque itemset fréquent et chaque découpage , on calcule la confiance, et l’on garde les règles au-dessus d’un seuil. Le support est déjà connu, aucun nouveau passage sur la base n’est nécessaire. Notre TP s’arrêtait aux itemsets fréquents ; avec mlxtend, les règles s’obtiennent en une ligne :
from mlxtend.frequent_patterns import association_rules
regles = association_rules(frequents, metric="confidence", min_threshold=0.7)print(regles[["antecedents", "consequents", "support", "confidence", "lift"]])Au-delà d’Apriori
Section intitulée « Au-delà d’Apriori »FP-growth
Section intitulée « FP-growth »FP-growth évite la génération de candidats. Il compresse d’abord la base dans un arbre, le FP-tree : les items de chaque transaction sont triés par support décroissant, puis insérés dans un arbre où les transactions qui commencent de la même façon partagent le même chemin. Il extrait ensuite les motifs directement dans cet arbre, de façon récursive. Deux passages sur la base suffisent, ce qui le rend nettement plus rapide qu’Apriori sur de gros volumes (mlxtend le propose avec fpgrowth, qui s’utilise exactement comme apriori).
Motifs clos et maximaux
Section intitulée « Motifs clos et maximaux »Le nombre d’itemsets fréquents peut être énorme, et beaucoup sont redondants. Deux représentations condensées existent.
- Un itemset fréquent est clos si aucun de ses sur-ensembles n’a le même support. Les motifs clos forment une représentation sans perte : on peut en déduire tous les itemsets fréquents et leurs supports.
- Un itemset fréquent est maximal si aucun de ses sur-ensembles n’est fréquent. Les motifs maximaux sont encore plus compacts, mais on perd les supports des sous-ensembles.
Les motifs clos ont aussi une lecture élégante en analyse formelle de concepts : un concept est un couple formé d’un ensemble maximal d’objets et de l’ensemble des attributs qu’ils partagent tous ; ces concepts s’organisent en treillis, et leurs ensembles d’attributs sont exactement les itemsets clos (sans filtrage par le support).
Autres motifs
Section intitulée « Autres motifs »La fouille de motifs ne se limite pas aux ensembles :
- les motifs séquentiels tiennent compte de l’ordre (« achète un appareil photo, puis une carte mémoire ») ; l’algorithme PrefixSpan projette la base sur chaque préfixe fréquent et l’étend récursivement ;
- les sous-graphes fréquents cherchent des structures répétées dans des molécules ou des réseaux ; des algorithmes comme gSpan utilisent un code canonique pour ne pas explorer deux fois le même sous-graphe ;
- l’approche par compression (principe de longueur de description minimale, MDL, avec l’algorithme KRIMP) choisit le petit ensemble de motifs qui compresse le mieux la base : un motif très utilisé reçoit un code court, de longueur de sa fréquence d’usage. On obtient quelques motifs vraiment représentatifs au lieu de milliers de motifs fréquents.
En résumé
Section intitulée « En résumé »- Une base de transactions est une liste d’ensembles d’items ; le support d’un itemset est la part des transactions qui le contiennent.
- Le nombre d’itemsets possibles croît en ; l’anti-monotonie du support permet d’élaguer tout sur-ensemble d’un itemset infréquent.
- Apriori alterne génération de candidats, élagage et comptage, niveau par niveau ; le comptage est l’étape coûteuse.
- Une règle a une confiance et un lift ; seul un lift supérieur à 1 indique une association positive.
- FP-growth évite la génération de candidats grâce au FP-tree.
- Les motifs clos (aucun sur-ensemble de même support) et maximaux (aucun sur-ensemble fréquent) condensent le résultat ; on fouille aussi des séquences, des graphes, ou l’on sélectionne les motifs par compression (MDL).
Exercices
Section intitulée « Exercices »Exercice · Calculer support, confiance et lift
facileSix photos de Rennes portent les tags suivants : (1) rennes, thabor, parc ; (2) rennes, thabor, jardin ; (3) rennes, parc ; (4) thabor, parc, jardin ; (5) rennes, lices, marche ; (6) rennes, thabor, parc. Calculez le support, la confiance et le lift des règles thabor ⇒ parc et thabor ⇒ rennes. Commentez.
Voir la solution
Supports : {thabor} = 4/6 (photos 1, 2, 4, 6), {parc} = 4/6 (1, 3, 4, 6), {rennes} = 5/6, {thabor, parc} = 3/6 (1, 4, 6), {thabor, rennes} = 3/6 (1, 2, 6).
- thabor ⇒ parc : support 0,5 ; confiance ; lift . Association positive : le Thabor est un parc, les deux tags vont logiquement ensemble.
- thabor ⇒ rennes : support 0,5 ; confiance aussi ; mais lift . Le lift est inférieur à 1 : le tag « rennes » est un peu moins fréquent sur les photos du Thabor que sur l’ensemble des photos. Même confiance, conclusion opposée : c’est pourquoi on ne se fie pas à la seule confiance.
En code
photos = [{"rennes", "thabor", "parc"}, {"rennes", "thabor", "jardin"}, {"rennes", "parc"}, {"thabor", "parc", "jardin"}, {"rennes", "lices", "marche"}, {"rennes", "thabor", "parc"}]
def support(itemset): return sum(itemset <= p for p in photos) / len(photos) # <= : « est inclus dans »
def regle(x, y): s = support(x | y) confiance = s / support(x) return round(s, 3), round(confiance, 3), round(confiance / support(y), 3)
print(regle({"thabor"}, {"parc"})) # (0.5, 0.75, 1.125) : lift > 1print(regle({"thabor"}, {"rennes"})) # (0.5, 0.75, 0.9) : lift < 1photos <- list(c("rennes", "thabor", "parc"), c("rennes", "thabor", "jardin"), c("rennes", "parc"), c("thabor", "parc", "jardin"), c("rennes", "lices", "marche"), c("rennes", "thabor", "parc"))
support <- function(itemset) mean(sapply(photos, function(p) all(itemset %in% p)))regle <- function(x, y) { s <- support(c(x, y)) confiance <- s / support(x) round(c(support = s, confiance = confiance, lift = confiance / support(y)), 3)}regle("thabor", "parc") # 0.5 0.75 1.125 : lift > 1regle("thabor", "rennes") # 0.5 0.75 0.9 : lift < 1Exercice · Élaguer les candidats d'Apriori
moyenAu niveau 2, Apriori a trouvé les itemsets fréquents {a, b}, {a, c}, {b, c}, {b, d} et {c, d}. Quels candidats de taille 3 génère-t-il, et lesquels restent après élagage ? Combien de passages sur la base faudra-t-il encore au minimum ?
Voir la solution
En combinant deux paires fréquentes qui partagent un item, on obtient les triplets {a, b, c}, {a, b, d}, {a, c, d} et {b, c, d}. On vérifie ensuite que toutes les paires de chaque triplet sont fréquentes :
{a, b, c}:{a, b},{a, c},{b, c}sont fréquentes, gardé ;{a, b, d}:{a, d}n’est pas fréquente, élagué ;{a, c, d}:{a, d}n’est pas fréquente, élagué ;{b, c, d}:{b, c},{b, d},{c, d}sont fréquentes, gardé.
Il reste deux candidats, dont il faut compter le support : un passage sur la base. Si les deux sont fréquents, le seul candidat de taille 4 possible, {a, b, c, d}, est élagué d’office puisqu’il contient {a, d}. Un seul passage de comptage suffit donc.
En code
from itertools import combinations
frequents_2 = [{"a", "b"}, {"a", "c"}, {"b", "c"}, {"b", "d"}, {"c", "d"}]
# Génération : union de deux paires fréquentes qui partagent un itemcandidats = {frozenset(p | q) for p, q in combinations(frequents_2, 2) if len(p | q) == 3}# Élagage : toutes les paires du triplet doivent être fréquentesfor c in sorted(candidats, key=sorted): garde = all(set(paire) in frequents_2 for paire in combinations(c, 2)) print(sorted(c), "gardé" if garde else "élagué")# ['a', 'b', 'c'] gardé ; ['a', 'b', 'd'] élagué ; ['a', 'c', 'd'] élagué ; ['b', 'c', 'd'] gardéfrequents_2 <- list(c("a", "b"), c("a", "c"), c("b", "c"), c("b", "d"), c("c", "d"))cle <- function(s) paste(sort(s), collapse = "")
# Génération : union de deux paires fréquentes qui partagent un itempaires <- combn(length(frequents_2), 2)unions <- apply(paires, 2, function(i) union(frequents_2[[i[1]]], frequents_2[[i[2]]]))candidats <- unique(Filter(function(u) length(u) == 3, lapply(unions, sort)))
# Élagage : toutes les paires du triplet doivent être fréquentesconnues <- sapply(frequents_2, cle)for (c in candidats) { garde <- all(apply(combn(c, 2), 2, cle) %in% connues) cat(c, if (garde) "gardé" else "élagué", "\n")}# a b c gardé ; a b d élagué ; a c d élagué ; b c d gardéExercice · Motifs clos, maximaux et lift
difficile- Montrez que le lift est symétrique : , alors que la confiance ne l’est pas.
- Montrez que si un item est présent dans toutes les transactions, toute règle a une confiance et un lift égaux à 1.
- Dans nos cinq paniers, pourquoi
{haricots}est-il clos mais pas maximal ?
Voir la solution
- : l’expression ne change pas quand on échange et . La confiance, elle, divise par dans un sens et par dans l’autre : sur nos paniers, oignon ⇒ œufs a une confiance de 1 et œufs ⇒ oignon de 0,75.
- Si est dans toutes les transactions, toute transaction qui contient contient aussi , donc et la confiance vaut 1. Comme , le lift vaut : indépendance. C’est exactement le cas des haricots rouges, présents dans les cinq paniers.
{haricots}a un support de 1,0 ; tous ses sur-ensembles ont un support strictement plus petit (au plus 0,8 pour{haricots, œufs}) : il est donc clos. Mais il a des sur-ensembles fréquents (par exemple{haricots, œufs}, 0,8), donc il n’est pas maximal. Clos et maximal ne se confondent que pour les itemsets fréquents qui n’ont aucun sur-ensemble fréquent.
En code
from itertools import combinations
paniers = [{"lait", "oignon", "muscade", "haricots", "oeufs", "yaourt"}, {"aneth", "oignon", "muscade", "haricots", "oeufs", "yaourt"}, {"lait", "pomme", "haricots", "oeufs"}, {"lait", "licorne", "mais", "haricots", "yaourt"}, {"mais", "oignon", "haricots", "glace", "oeufs"}] # un ensemble : l'oignon compte une foissupp = lambda s: sum(set(s) <= p for p in paniers) / len(paniers)items = sorted(set().union(*paniers))
# Tous les itemsets fréquents (2 047 candidats seulement : on peut tout énumérer)freq = {frozenset(c): supp(c) for k in range(1, len(items) + 1) for c in combinations(items, k) if supp(c) >= 0.6}clos = [s for s in freq if not any(s < t and freq[t] == freq[s] for t in freq)]maximaux = [s for s in freq if not any(s < t for t in freq)]print(len(freq), len(clos), len(maximaux)) # 11 5 3print(frozenset({"haricots"}) in clos, frozenset({"haricots"}) in maximaux) # True False
# 1. Lift symétrique, confiance nonlift = lambda x, y: supp(x | y) / (supp(x) * supp(y))conf = lambda x, y: round(supp(x | y) / supp(x), 2)print(conf({"oignon"}, {"oeufs"}), conf({"oeufs"}, {"oignon"})) # 1.0 0.75print(lift({"oignon"}, {"oeufs"}), lift({"oeufs"}, {"oignon"})) # 1.25 1.25# 2. Haricots partout : confiance et lift de 1print(conf({"oeufs"}, {"haricots"}), lift({"oeufs"}, {"haricots"})) # 1.0 1.0paniers <- list(c("lait", "oignon", "muscade", "haricots", "oeufs", "yaourt"), c("aneth", "oignon", "muscade", "haricots", "oeufs", "yaourt"), c("lait", "pomme", "haricots", "oeufs"), c("lait", "licorne", "mais", "haricots", "yaourt"), c("mais", "oignon", "oignon", "haricots", "glace", "oeufs"))supp <- function(s) mean(sapply(paniers, function(p) all(s %in% p))) # doublon sans effetitems <- sort(unique(unlist(paniers)))
# Tous les itemsets fréquents (2 047 candidats seulement : on peut tout énumérer)tous <- unlist(lapply(seq_along(items), function(k) combn(items, k, simplify = FALSE)), recursive = FALSE)freq <- Filter(function(s) supp(s) >= 0.6, tous)s_freq <- sapply(freq, supp)inclus <- function(a, b) length(a) < length(b) && all(a %in% b) # a strictement dans bclos <- sapply(seq_along(freq), function(i) !any(sapply(seq_along(freq), function(j) inclus(freq[[i]], freq[[j]]) && s_freq[j] == s_freq[i])))maximal <- sapply(freq, function(s) !any(sapply(freq, function(t) inclus(s, t))))c(length(freq), sum(clos), sum(maximal)) # 11 5 3h <- which(sapply(freq, identical, "haricots"))c(clos[h], maximal[h]) # TRUE FALSE : clos mais pas maximal
lift <- function(x, y) supp(c(x, y)) / (supp(x) * supp(y))conf <- function(x, y) supp(c(x, y)) / supp(x)c(conf("oignon", "oeufs"), conf("oeufs", "oignon")) # 1 0.75 : confiance non symétriquec(lift("oignon", "oeufs"), lift("oeufs", "oignon")) # 1.25 1.25 : lift symétriquec(conf("oeufs", "haricots"), lift("oeufs", "haricots")) # 1 1