Règles d'association

Question 1

Introduction - Règles d’association

Answer 1

Règles d’association : Une des principales catégories de connaissances

Objectif : Trouver des associations ou structures causales entre des ensembles d’items (d’attributs)

Algorithme le plus connu : Apriori
- Extraire l’ensemble des itemsets fréquents
- Générer les règles à partir des itemsets fréquents

Applications typiques :
- Analyse du comportement des clients et recommandation
- Analyse médicale

Question 2

Définitions - Règles d’association

Answer 2

Base : Table de données

O : Ensemble d’objets (ex.: clients, transactions)

I : Ensemble d’items (produits)

X, Y et Z : itemsets (sous-ensembles de I)

Support absolu de Z : Nombre de transactions ayant tous les items de Z

Support relatif de Z : Proportion des transactions ayant tous les items de Z

Itemset fréquent : Itemset dont le support dépasse un seul minimum minsup

k-itemset : itemset de k éléments

Règle X -> Y (s, c)
- X et Y sont des itemsets
- X union Y = ensemble vide
- s est le support de la règle = Prob(X et Y)
- c est la confiance = Prob(Y sachant X)
- Règle fort si s >= minsup(support minimum) et c >= minconf(confiance minimum)

Question 3

Algorithme Apriori

Answer 3

Principe:
- Extraction des itemsets fréquents et leur support
- Génération des règles d’association et leur confiance

Deux propriétés :
- Tous les sur-ensembles d’un itemset infréquent sont infréquents
- Tous les sous-ensembles d’un itemset fréquent sont fréquents

Limites d’Apriori :
- Génération d’un trop grand nombre d’itemsets fréquents et de règles parfois redondantes. Solutions : itemsets fermés fréquents en AFC, etc.

Deux étapes dans le calcul des itemsets fréquents :
- Parcourir la base (table) pour générer les 1-itemsets et leur support. Garder uniquement les itemsets fréquents
- Étape 1 d’auto-jointure (self-join) : Générer les candidats (k+1)-itemsets à partir des k-itemsets fréquents
- Étape 2 d’élagage (pruning) : Élaguer les itemsets non fréquents
- Arrêt : Quand aucun nouvel itemset fréquent ne peut être généré

Génération des itemsets fréquents :
- Génération des itemsets candidats à l’itération k+1
– Étape 1 : Auto-jointure des éléments de l’ensemble Lk des itemsets produits ç l’itérations k
– Étape 2 : Élagage
** Si un nouvel ensemble contient un élément (sous-ensemble) qui n’est pas fréquent, alors il faut l’élaguer

Méthode naïve de génération des règles :
- Pour chaque itemset fréquent Z, créer r : X -> Y (s, c) tel que
– X n’est pas l’ensemble vide et X fait partie de Z
– Y = Z \ X
– X union Y = ensemble vide
– s est le support relatif de l’itemset Z
– c est la confiance de la règle r = support / prob(X)

Question 4

Mesures de qualité des règles d’association

Answer 4

Support : La règle A -> B a pour support p (en %) si p des objets de l’ensemble O contiennent A et B
- Support de A -> B = Prob(A et B)

Confiance : La règle A -> B a pour confiance c si c% des objets de l’ensemble O ayant A ont également B
- Confiance de A -> B = Prob(B/A) = Prob(A et B)/Prob(A)

Attention! La confiance peut induire en erreur
La règle “jouer au basketball -> manger des céréales (40%, 67%)” induit en erreur car déjà 75% (>67%) des étudiants mangent des céréales

Mesure d’intérêt :
- Prob(A et B)/(Prob(A) * Prob(B))
- Tient compte de P(A) et P(B) à la fois
- Prob(A et B) = Prob(B)*Prob(A) si A et B sont indépendants
- A et B sont corrélés négativement si la mesure d’intérêt est inférieure à 1 et corrélés positivement si la mesure dépasse 1
- Nous permet de mesurer l’important d’une règle d’association en terme de causes à effets