Règles d'association

La technique des règles d'association est une technique non supervisée qui permet d'identifier des relations ( des règles ) significatives entre des variables dans un grand ensemble de données. De manière simplifiée, une règle d'association met en avant des relations sous la forme « si A, alors B » ou « si A et B alors C ».

La règle d'association est souvent assimilée à l'exemple d'un caddy de supermarché rempli de différents produits achetés par un consommateur et permet d'identifier au regard de toutes les données de tous les consommateurs que si un consommateur achète un produit Z alors il est fort possible qu'il achète également un produit Y ou du moins qu'il finisse par acheter ce produit Y si nous le mettons en évidence. La règle d'association permet donc de déterminer quels sont les produits qui sont régulièrement achetés ensemble.

Dans d'autres cas, une règle d'association nous permettrait d'identifier des actions qui sont souvent réalisées ensemble. En effet, la technique des règles d'association est fortement utilisée de nos jours et parfois intégrée avec d'autres techniques, notamment pour la détection de fraude, les systèmes de recommandation, les interactions sur les réseaux sociaux entre utilisateurs, etc.

Préparation des données

Une règle d’association se base sur un ensemble de transactions ( ou d'enregistrements ) contenant un ou plusieurs produits/services ( ou actions ) et quelques informations rudimentaires liées à l’opération. Pour plus d’efficacité, nous regroupons les informations clés dans une table.

Prenons l'exemple d'un supermarché, nous retrouverions l’ID de la transaction, l’ID du consommateur, le timestamp, la liste des produits achetés.

TimeStamp	TransactionID	CustomerID	Items
04/01/2024 17:05	45784548	145741	Orange Juice, Soda
04/01/2024 17:06	45784549	004785	Milk, Orange Juice, Window Cleaner
04/01/2024 17:08	45784550	093689	Orange Juice, Detergent
04/01/2024 17:09	45784551	457846	Orange Juice, Detergent, Soda
04/01/2024 17:10	45784552	336478	Window Cleaner, Soda
...	...	...	...

Les éléments de la table utilisés pour identifier les règles doivent impérativement être binarisés - opération notamment possible grâce à l'encodage one-hot - afin d'obtenir la table suivante :

Transaction ID	Orange Juice	Soda	Milk	Window Cleaner	Detergent
45784548	1	1	0	0	0
45784549	1	0	1	1	0
45784550	1	0	0	0	1
45784551	1	1	0	0	1
45784552	0	1	0	1	0

Règles

Une règle d'association est une technique non supervisée ce qui implique le fait que le modèle mettra en avant des règles et que c'est à nous en tant que data scientist de considérer si la règle est pertinente ou non. Nous retrouvons d'ailleurs trois types de règles :

• Les règles actionnables : les clients d'un supermarché qui achètent des poupées barbie achètent également des yaourt à la fraise
• Les règles triviales : les clients qui souscrivent un contrat de maintenance ont tendance à acheter de gros appareils
• Les règles inexplicables : dans une quincaillerie, l’un des produits les plus vendu avec un tournevis, c'est du nettoyant pour cuvette de toilette

Le concept de la règle d’association, est d’examiner toutes les règles possibles entre les produits ( utilisateurs , transactions, ... ) selon la relation IF – THEN (SI – ALORS) et ne sélectionner que celles qui représentent une dépendance vraie. Le IF signifie l’antécédent et le THEN décrit la/les conséquences. Ce qui nous donne « Si antécédent, alors conséquence ».

Dans les analyses d’association, l’antécédent et la conséquence sont un ensemble de combinaisons d’articles. Par exemple, si nous avons 4 produits (P1,P2,P3,P4), nous obtenons les combinaisons possibles suivantes : « Si P1 alors P2 ; Si P1 alors P3 ; Si P1 alors P4 ; Si P1 et P2 alors P3, Si P1 et P3 alors P2, ……Si P4 alors…,… ».

Étapes

Étapes de la définition de la règle d’association :

• Étape 1 : définir un seuil de support min (règle de support)
• Étape 2 : application de l’algorithme Apriori
• compter le nombre d’occurrences d’un article dans l’ensemble des transactions (= règle de support pour un article)
• définir les associations
• Étape 3 : calcul de la règle de support pour chaque association (et ne retenir que les éléments correspondant au seuil prédéfini).
• Étape 4 : mesurer la force de l’association (règle de confiance et lift ratio)

Règle de support

Dans n’importe quel ensemble de données transactionnelles, il existe de nombreuses combinaisons. Pour une centaine de produits, le nombre de combinaisons possibles peut rapidement se compter en millions.

Par conséquent, la règle d’association doit séparer les combinaisons « fortes » des combinaisons « faibles ».

Une solution pratique est de considérer uniquement les combinaisons qui se produisent régulièrement, c’est-à-dire qui sont fréquentes. Et cela renvoie au concept de la règle de support.

L'étape 1 - définir la règle de support - consiste donc à identifier le nombre de transactions qui contiennent les combinaisons d’articles de l’antécédent et la conséquence. Elle mesure le degré avec lequel les données « supportent » la validité de la règle.

Transaction ID	Orange Juice	Soda	Milk	Window Cleaner	Detergent
45784548	1	1	0	0	0
45784549	1	0	1	1	0
45784550	1	0	0	0	1
45784551	1	1	0	0	1
45784552	0	1	0	1	0

Dans notre exemple ci-dessus, le support de la combinaison [Orange Juice, Soda] – Si nous achetons du jus d’orange alors nous achetons du soda, est de $4$ ou $100 * \frac{2}{5} =40$ (sur 5 transactions, pour 2 transactions, le client a acheté du soda (conséquence) après avoir acheté du jus d’orange (antécédent)).

Seuil de support

La définition d'un seuil de support permet de ne retenir que les combinaisons supérieures à ce seuil. Nous pouvons définir la règle de support comme étant : « la probabilité estimée qu’une transaction sélectionnée au hasard dans la base de données contiendra tous les articles repris dans l’antécédent et la conséquence.

Nous mesurons le degré selon lequel les données « supportent » la validité de la règle. Support = $\hat{P}$ ̂(antécédent ET conséquence).

Pour 1000 transactions, 500 contiennent une pompe à vélo. Parmi les 500 transactions contenant une pompe à vélo, 400 contiennent une chambre à air. Règle de support ?

Si nous achetons une pompe à vélo, nous achetons une chambre à air. Support de la règle : 100 *(400/1000) soit 40 %.

Algorithme Apriori

Il existe plusieurs algorithmes pour générer les associations les plus fréquentes mais le plus classique est l’algorithme « Apriori ».

Le concept clé de l’algorithme est de commencer à générer les éléments les plus fréquents. À partir de l’élément le plus fréquent, il génère les combinaisons de ce premier élément avec un second élément le plus fréquent pour obtenir les deux éléments les plus fréquents, puis il génère les combinaisons avec ces deux éléments pour obtenir les trois éléments les plus fréquents et ainsi de suite jusqu’à ce que les combinaisons de toutes les tailles aient été générées.

« Si un ensemble d’éléments Z n’est pas fréquent alors ajouter un autre élément A à l’ensemble Z ne rendra pas Z plus fréquent ». Concrètement, si la règle « A alors B est faible » ; alors cela ne sert à rien de tester la combinaison si « A et B alors C ».

Mesure de la force d'association

A partir de l’abondance des règles générées par l’algorithme Apriori, nous pouvons identifier les règles de combinaisons d’éléments qui représentent une forte dépendance entre l’antécédent et la conséquence. Pour cela, nous mesurons la force d’association à l’aide de deux indicateurs : la mesure de la confiance et le lift ratio

Mesure de la confiance

La mesure de la confiance permet d’exprimer le degré d’incertitude de la règle « Si antécédent alors conséquence ». Cette mesure compare la co-occurrence d’une combinaison d’articles « si antécédent alors conséquence » dans la base de données par rapport à l’occurrence de l’antécédent dans cette même base de données.

Règle de confiance est la probabilité conditionnelle estimée qu’une transaction sélectionnée au hasard parmi les transactions contenant tous les éléments de l’antécédent, contiendra tous les éléments de l’antécédent ET la conséquence.

La règle de confiance est calculée comme suit :

$\frac{Nbre \ de \ transactions \ contenant \ les \ produits \ antécédent \ et \ conséquence}{(Nbre \ de \ transactions \ contenant \ les \ produits \ antécédent)}$.

Dans notre exemple de la combinaison [Orange Juice, Soda], le support est de $4$ ou $100 * \frac{2}{5} =40$ ( sur $5$ transactions, pour $2$ transactions, le client a acheté du soda (conséquence) après avoir acheté du jus d’orange (antécédent)).

Transaction ID	Orange Juice	Soda	Milk	Window Cleaner	Detergent
45784548	1	1	0	0	0
45784549	1	0	1	1	0
45784550	1	0	0	0	1
45784551	1	1	0	0	1
45784552	0	1	0	1	0

La confiance sera dans ce cas de $50$ soit $100 * \frac{2}{4}$. Parmi mes transactions, $4$ contiennent du Jus d’Orange. Parmi ces $4$ transactions contenant du Jus d’Orange ( antécédent ), $2$ transactions contiennent les produits antécédent et conséquence.

$\frac{2 \ transactions \ contenant \ du \ jus \ d'orange \ et \ du \ soda}{4 \ transactions \ contenant \ du \ jus \ d'orange}$

Rappel de la différence seuil de support / règle de confiance :

$Support = \frac{\hat{P}(antécédent \ ET \ conséquence)}{Total \ des \ transactions}$

$Confiance = \frac{\hat{P}(antécédent \ ET \ conséquence)}{\hat{P}(antécédent)}$

Pour 1000 transactions, 500 contiennent une pompe à vélo. Parmi les 500 transactions contenant une pompe à vélo, 400 contiennent une chambre à air. Règle : Si nous achetons une pompe à vélo, nous achetons une chambre à air. Support de la règle : $100 *(400/1000)$ soit $40$. Règle de confiance : $100 *(400/500)$ soit $80$ (ou $40$).

Lift ratio

Une règle de confiance représentant une valeur élevée suggère une règle d’association forte.

Toutefois, cette règle n’est pas suffisante car si parmi l’ensemble de nos transactions, tous nos clients ont acheté des bananes et presque tous les clients ont acheté de la crème glacée, la règle de confiance de la règle d’association « si nous achetons des bananes, nous achetons de la crème glacée » sera élevée même si à la base l’antécédent et la conséquence sont totalement indépendants.

La lift ratio va nous permettre de comparer la règle de confiance avec la valeur de confiance que nous nous attendrions à obtenir si l’antécédent et la conséquence sont indépendants.

Pour calculer le lift ratio, nous devons d'abord calculer le benchmark de confiance.

Benchmark de confiance :

$\textcolor{blue}{Benchmark \ de \ la \ confiance} = \frac{Nbre \ de \ transactions \ contenant \ les \ produits \ conséquence}{Nbre \ de \ transactions \ dans \ la \ database}$

$Ratio \ Lift = \frac{Règle \ de \ confiance}{\textcolor{blue}{Benchmark \ de \ la \ confiance}}$

La ratio lift est donc la comparaison de la règle de confiance avec la valeur de référence que nous nous attendrions à avoir comme confiance.

Un Ratio Lift supérieur à 1 suggère que la règle est utile. En d’autres mots, le niveau d’association entre l’antécédent et la conséquence est supérieur à ce que l’on s’attendrait à obtenir s’ils étaient indépendants.

Code Python

# Requirements :
#!pip install apyori
#!pip install mlxtend

import pandas as pd
import numpy as np
from mlxtend.frequent_patterns import apriori
from mlxtend.frequent_patterns import association_rules

'''
#Synthetic dataset
np.random.seed(0)
dataset = pd.DataFrame(np.random.randint(0, 2, size=(10000, 6)), columns=['A', 'B', 'C', 'D', 'E', 'F'])
dataset
'''

dataset = pd.read_csv('data.csv')
dataset = dataset[['Column_1', 'Column_2', 'Column_3', 'Column_n']]


frequent_itemsets = apriori(dataset, min_support=0.01, use_colnames=True)


rules = association_rules(frequent_itemsets, metric="lift", min_threshold=1)

rules_symmetric = rules[~rules['antecedents'].apply(frozenset).duplicated()]


selected_columns = ['antecedents', 'consequents', 'support', 'confidence', 'lift', 'leverage']


sorted_rules = rules_symmetric[selected_columns].sort_values(by='lift', ascending=False)

print(sorted_rules)