Quand on parle de règles d’association on a souvent en tête l’exemple du panier de supermarché. Je suis sûre que vous avez déjà entendu qu’on avait mis en évidence que l’achat de couche pour bébé le week end impliquait aussi l’achat de bières.
En bref les règles d’association sont des règles du type A implique B. Et sont effectivement souvent utilisées dans l’analyse de paniers d’achats ou pour des outils de recommandation.
Comme toujours, pour moi rien ne vaut un exemple très simplifié pour bien comprendre le fonctionnement d’un algorithme. Pour rester dans le même thème que mon article Règles d’association avec R, nous allons prendre comme exemple un moteur de recommandation de films.
On a 10 utilisateurs d’une plateforme de VOD qui ont visionné (ou pas) 4 films / séries, notre objectif est de pouvoir recommander un film ou une série à un autre utilisateur. Nous allons définir des règles d’association du type Si l’utilisateur a regardé le film 1 et le film 2 alors il regardera surement aussi le film 4 :
Dans un premier temps nous allons transformer nos données sous forme binaire, on en profite pour associer un code à chaque film (plus lisible pour la suite) :
Pour calculer les règles de décision nous utiliserons 2 critères : le support et la confiance :
Le support : il représente la fiabilité. Ce critère permet de fixer un seuil en dessous duquel les règles ne sont pas considérées comme fiables. Le support d’une règle F1->F2 correspond à la probabilité P(F1 ∩ F2).
Par exemple, Sup ( Dark -> La casa de Papel ) = 4/10 puisque 4 utilisateurs ont vu les 2 séries.
Pour la suite on fixera un seuil de support minimal à respecter pour éviter de sélectionner des règles d’association qui seraient trop rares.
La confiance : elle représente la précision de la règle et peut être vue comme la probabilité conditionnelle Conf(F1->F2)=P(F2| F1).
Par exemple Conf( Dark -> La casa de Papel ) = 4/5 puisque 4 utilisateurs ont regardé les 2 films et 5 utilisateurs ont regardé Dark.
Plus la confiance est élevée, meilleure est la règle d’association.
Nous allons pouvoir utiliser maintenant l’algorithme apriori. On se fixe un support minimum de 20% et une confiance de 60%.
La première étape consiste à calculer le support de chaque item. Si le support de certains items est inférieur au seuil minimum, on peut les supprimer dès cette étape pour éviter de faire des calculs sur les itemset qui en découlent. 
Pas de suppression lors de cette étape de notre exemple, nous pouvons construire les itemset de niveau suivant et calculer leur support :
On constate que 2 itemsets n’ont pas obtenu un support suffisant et nous les supprimons avant de passer à la création des itemsets de niveau suivant :
La première phase de l’algorithme est terminée, nous avons identifié tous les itemsets fréquents. Nous calculons maintenant la confiance de chaque règle d’association qui en découle et nous ne conservons que celles qui satisfont notre critère de confiance.
L’algorithme apriori a terminé son travail et nous a permis de créer 8 règles d’association.
Pour apprécier plus finement ces règles, on peut encore calculer le lift : il caractérise l’intérêt de la règle, sa force.
On a : lift( F1 ->F2) =P(F2 | F1) / P(F2). Un lift supérieur à 1 indique qu’il existe bien un lien entre les 2 éléments. On calcule le lift et on classe les règles de décision en fonction de sa valeur :
Et voilà le tour est joué.
Evidemment il existe d’autres algorithmes bien plus compliqués pour les vrais moteurs de recommandation, comme celui utilisé par Netflix.
Pour aller plus loin, je vous invite à tester l’algorithme apriori avec R.