Aller au contenu

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.

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 :

PanierContenu
1lait, oignon, muscade, haricots rouges, œufs, yaourt
2aneth, oignon, muscade, haricots rouges, œufs, yaourt
3lait, pomme, haricots rouges, œufs
4lait, licorne, maïs, haricots rouges, yaourt
5maï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 3/5=0,63/5 = 0{,}6. 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 pd
from mlxtend.frequent_patterns import apriori
from 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.

haricotsœufslaitoignonyaourtmaïsmuscadeanethglacelicornepomme0,00,20,40,60,81,0support1,00,80,60,60,60,40,40,20,20,20,2minsup = 0,65 items fréquents6 items éliminés,avec tous leurs sur-ensembles
Seuls cinq items atteignent le support minimal de 0,6 ; les six autres, et tous les itemsets qui les contiennent, sont écartés dès le premier niveau.

Pourquoi ne pas simplement compter le support de tous les itemsets possibles ? Parce qu’avec mm items, il y en a 2m−12^m - 1. 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.

Apriori exploite cette propriété en avançant niveau par niveau, par taille croissante des itemsets :

  1. compter le support de chaque item seul et garder les fréquents (niveau 1) ;
  2. à partir des itemsets fréquents de taille kk, générer les candidats de taille k+1k + 1 (en combinant deux itemsets qui ne diffèrent que d’un item) ;
  3. élaguer tout candidat dont un sous-ensemble de taille kk n’est pas fréquent (anti-monotonie) ;
  4. compter le support des candidats restants en parcourant la base, et garder les fréquents ;
  5. recommencer jusqu’à ce qu’il n’y ait plus de candidat.
haricots1,0œufs0,8lait0,6oignon0,6yaourt0,6harœufs0,8harlait0,6haroign0,6haryaou0,6œufslait0,4œufsoign0,6œufsyaou0,4laitoign0,2laityaou0,4oignyaou0,4harœufslaitélagué :œufs, laitinfréquentharœufsoign0,6harœufsyaouélagué :œufs, yaouinfréquentharlaitoignélagué :lait, oigninfréquentharlaityaouélagué :lait, yaouinfréquentharoignyaouélagué :oign, yaouinfréquentniveau 1niveau 2niveau 3
Apriori ne compte que ce qui peut encore être fréquent : au niveau 3, cinq candidats sont éliminés sans passage sur la base (une de leurs paires est infréquente), et seul {haricots, œufs, oignon} est compté.

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.

Un itemset fréquent dit « ces items vont ensemble ». Une règle d’association X⇒YX \Rightarrow Y ajoute une direction : « quand on voit XX, on voit souvent YY », avec XX et YY deux itemsets disjoints. Trois mesures l’évaluent.

  • Le support de la règle est celui de X∪YX \cup Y : la règle concerne-t-elle beaucoup de transactions ?
  • La confiance est la proportion de transactions contenant XX qui contiennent aussi YY :
conf(X⇒Y)=supp(X∪Y)supp(X)\mathrm{conf}(X \Rightarrow Y) = \frac{\mathrm{supp}(X \cup Y)}{\mathrm{supp}(X)}
  • Le lift compare cette confiance à la fréquence de YY en général :
lift(X⇒Y)=conf(X⇒Y)supp(Y)=supp(X∪Y)supp(X) supp(Y)\mathrm{lift}(X \Rightarrow Y) = \frac{\mathrm{conf}(X \Rightarrow Y)}{\mathrm{supp}(Y)} = \frac{\mathrm{supp}(X \cup Y)}{\mathrm{supp}(X)\,\mathrm{supp}(Y)}

Un lift supérieur à 1 signale une association positive (XX rend YY plus probable), égal à 1 une indépendance, inférieur à 1 une association négative.

oignon ⇒ œufsœufs ⇒ oignonœufs ⇒ haricots0,000,250,500,751,001,251,501,751,001,250,751,251,001,00pointillé : lift = 1 (indépendance)vraiemaisinutileconfiancelift
La confiance dépend du sens de la règle, pas le lift. La règle œufs ⇒ haricots a une confiance parfaite mais un lift de 1 : elle est vraie, mais n'apprend rien.

On génère les règles à partir des itemsets fréquents : pour chaque itemset fréquent ZZ et chaque découpage Z=X∪YZ = X \cup Y, 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"]])

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).

∅haricots : 5œufs : 4lait : 1lait : 2oignon : 2yaourt : 1oignon : 1yaourt : 1yaourt : 1items triés par support :haricots, œufs, lait,oignon, yaourtpaniers 1 et 3 partagentle chemin haricots → œufs → laitpanier 4 :haricots → lait → yaourt
Chaque panier, trié par support décroissant, suit un chemin depuis la racine ; les paniers qui commencent pareil partagent leurs nœuds, dont le compteur augmente. Les cinq paniers tiennent en neuf nœuds sous la racine.

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.
har1,0œufs0,8lait0,6oign0,6yaou0,6har, œufs0,8har, lait0,6har, oign0,6har, yaou0,6œufs, oign0,6har, œufs, oign0,6plein : clos (5)ambre : maximal (3)pointillé : ni l’un ni l’autre
Un itemset est clos si aucun sur-ensemble n'a le même support (cadre plein), maximal si aucun sur-ensemble n'est fréquent (ambre). Les 5 clos suffisent à retrouver les 11 fréquents et leurs supports.

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).

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 −log⁡2-\log_2 de sa fréquence d’usage. On obtient quelques motifs vraiment représentatifs au lieu de milliers de motifs fréquents.
  • 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 2m2^m ; 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 X⇒YX \Rightarrow Y a une confiance supp(X∪Y)/supp(X)\mathrm{supp}(X \cup Y)/\mathrm{supp}(X) et un lift conf/supp(Y)\mathrm{conf}/\mathrm{supp}(Y) ; 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).

Exercice · Calculer support, confiance et lift

facile

Six 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 3/64/6=0,75\frac{3/6}{4/6} = 0{,}75 ; lift 0,754/6=1,125\frac{0{,}75}{4/6} = 1{,}125. Association positive : le Thabor est un parc, les deux tags vont logiquement ensemble.
  • thabor ⇒ rennes : support 0,5 ; confiance 0,750{,}75 aussi ; mais lift 0,755/6=0,9\frac{0{,}75}{5/6} = 0{,}9. 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 > 1
print(regle({"thabor"}, {"rennes"})) # (0.5, 0.75, 0.9) : lift < 1

Exercice · Élaguer les candidats d'Apriori

moyen

Au 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 item
candidats = {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équentes
for 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é

Exercice · Motifs clos, maximaux et lift

difficile
  1. Montrez que le lift est symétrique : lift(X⇒Y)=lift(Y⇒X)\mathrm{lift}(X \Rightarrow Y) = \mathrm{lift}(Y \Rightarrow X), alors que la confiance ne l’est pas.
  2. Montrez que si un item hh est présent dans toutes les transactions, toute règle X⇒{h}X \Rightarrow \lbrace h \rbrace a une confiance et un lift égaux à 1.
  3. Dans nos cinq paniers, pourquoi {haricots} est-il clos mais pas maximal ?
Voir la solution
  1. lift(X⇒Y)=supp(X∪Y)supp(X) supp(Y)\mathrm{lift}(X \Rightarrow Y) = \frac{\mathrm{supp}(X \cup Y)}{\mathrm{supp}(X)\,\mathrm{supp}(Y)} : l’expression ne change pas quand on échange XX et YY. La confiance, elle, divise par supp(X)\mathrm{supp}(X) dans un sens et par supp(Y)\mathrm{supp}(Y) dans l’autre : sur nos paniers, oignon ⇒ œufs a une confiance de 1 et œufs ⇒ oignon de 0,75.
  2. Si hh est dans toutes les transactions, toute transaction qui contient XX contient aussi hh, donc supp(X∪{h})=supp(X)\mathrm{supp}(X \cup \lbrace h \rbrace) = \mathrm{supp}(X) et la confiance vaut 1. Comme supp({h})=1\mathrm{supp}(\lbrace h \rbrace) = 1, le lift vaut 1/1=11 / 1 = 1 : indépendance. C’est exactement le cas des haricots rouges, présents dans les cinq paniers.
  3. {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 fois
supp = 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 3
print(frozenset({"haricots"}) in clos, frozenset({"haricots"}) in maximaux) # True False
# 1. Lift symétrique, confiance non
lift = 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.75
print(lift({"oignon"}, {"oeufs"}), lift({"oeufs"}, {"oignon"})) # 1.25 1.25
# 2. Haricots partout : confiance et lift de 1
print(conf({"oeufs"}, {"haricots"}), lift({"oeufs"}, {"haricots"})) # 1.0 1.0