Qu’est-ce que l’algorithme Apriori ?

Introduit en 1994 par Rakesh Agrawal et Ramakrishnan Srikant, le nom « Apriori » reconnaît la connaissance antérieure des ensembles d’éléments (ou itemsets) fréquents que l’algorithme utilise dans les calculs. L’algorithme exécute des itérations sur les données pour identifier les k-itemsets, c’est-à-dire les k éléments qui se produisent fréquemment ensemble. Il utilise ensuite les k-itemsets pour identifier les k+1 itemsets. L’algorithme Apriori repose sur l’idée que l’ajout d’articles à un groupe d’achats fréquents ne peut que réduire la fréquence de ces achats, et non l’augmenter. Le processus s’appuie sur la propriété Apriori qui indique que si un ensemble d’éléments apparaît fréquemment dans un jeu de données, tous ses sous-ensembles doivent également apparaître fréquemment. Inversement, si un ensemble d’éléments est identifié comme peu fréquent, tous ses sur-ensembles sont considérés comme peu fréquents.

L’algorithme Apriori s’applique à tous les types de jeux de données, en particulier ceux générés par les bases de données transactionnelles, et il est souvent utilisé pour l’analyse du panier d’achat afin de prendre en charge les systèmes de recommandation. Par exemple, lorsqu’un consommateur recherche des chaussures sur une plateforme d’e-commerce qui vend des vêtements et des chaussures et qu’il décide d’ajouter une paire de chaussures noires élégantes à son panier, il remarque alors que l’interface lui recommande d’autres articles à acheter, comme des chaussettes. L’une des façons dont ce système de recommandation fonctionne, c’est de découvrir les habitudes d’achat des clients et d’associer des articles qui ont probablement été achetés ensemble.

L’un des principaux avantages de l’utilisation de l’algorithme Apriori est sa simplicité et son adaptabilité. Cependant, les algorithmes Apriori ne sont pas aussi efficaces lorsqu’il s’agit de gérer de grands jeux de données. Le processus multi-itération de génération de candidats aux ensembles d’éléments peut s’avérer coûteux en termes de calcul et gourmand en mémoire. Apriori est souvent combiné à d'autres techniques pour atténuer ces problèmes.

La fonction Apriori est intégrée dans de nombreux langages de programmation populaires, notamment Python, Java et R, ce qui facilite la génération de règles d'association de qualité et l'intégration dans des applications ou des systèmes existants de règles d'association de qualité et d'ensembles d'éléments fréquents.

Chacune des étapes clés de l'algorithme Apriori vise à identifier les ensembles d'éléments et tous leurs super-ensembles possibles, en recherchant les plus fréquents pour créer les règles d'association.

L’algorithme identifie d’abord les éléments uniques, parfois appelés « 1-itemsets », dans le jeu de données, ainsi que leur fréquence. Ensuite, il combine les éléments qui apparaissent ensemble avec une probabilité supérieure à un seuil spécifié dans des itemsets candidats, et il filtre les itemsets peu fréquents pour réduire le coût de calcul dans les étapes suivantes. Ce processus, connu sous le nom d’extraction des itemsets fréquents, ne recherche que les itemsets dont la fréquence est significative.

Grâce à la propriété Apriori, l’algorithme combine davantage les itemsets fréquents pour former des itemsets plus grands. Les itemsets les plus importants avec une probabilité plus faible sont éliminés. Cela réduit davantage l’espace de recherche et rend le calcul plus efficace.

L'algorithme répète les étapes 1 et 2 jusqu'à ce que tous les ensembles fréquents répondant au seuil de probabilité défini soient générés de manière exhaustive. Chaque itération génère des associations plus complexes et plus complètes dans les itemsets.

Une fois qu’Apriori a créé les itemsets, il est possible d’étudier la force des associations et des relations générées.

L’algorithme Apriori utilise les indicateurs de support, de confiance et de levage pour définir ses critères de fonctionnement et améliorer l’efficacité des performances.

La prise en charge est définie comme le rapport du nombre d’occurrences d’un élément dans les transactions par rapport au nombre total de transactions. Cet indicateur définit donc la probabilité d’occurrence de chaque élément individuel dans les transactions. La même logique peut être étendue aux itemsets.

$S\left(I_A\right)=\frac{Occ\left(I_A\right)}{TotalTransactions}$

où I_A est l'élément A, Occ(_IA) est le nombre d'occurrences de l'élément A, et S(_IA) = support de l'élément A

Par exemple, dans un magasin de détail, 250 transactions sur 2 000 effectuées par jour peuvent inclure l'achat de pommes. En utilisant la formule :

$S\left(I_{Apples}\right)=\frac{250}{2000}=0.125$

Ce résultat indique qu’il y a 12,5 % de chances que des pommes aient été achetées ce jour-là.

Vous pouvez indiquer un seuil de soutien minimal requis lors de l'application de l'algorithme Apriori. Cela signifie que tout élément ou ensemble d'éléments dont le support est inférieur au support minimum spécifié sera considéré comme peu fréquent.

L'indicateur de confiance détermine la probabilité que des éléments ou des itemsets se retrouvent ensemble dans les itemsets. Par exemple, s’il y a deux éléments dans une transaction, l’existence de l’un d’entre eux est supposée mener à l’autre. Le premier élément ou itemset est l’antécédent, et le second est le conséquent. La confiance est donc définie comme le rapport du nombre de transactions ayant à la fois l’antécédent et le conséquent, par rapport au nombre de transactions n’ayant que l’antécédent. Ce scénario est représenté comme suit :

$C(A,B)=\frac{Occ(A\cap B)}{Occ\left(A\right)}$

où A est l’antécédent, B est le conséquent, et C(A,B) est la confiance que A mène à B.

Pour reprendre l’exemple précédent, supposons que 150 transactions regroupent l’achat de pommes et de bananes. La confiance est calculée comme suit :

$C(Apples,Bananas)=\frac{150}{250}=0.6$

Ce résultat indique une probabilité de 60 % qu’un achat de pommes entraîne ensuite un achat de bananes. De même, en supposant un total de 500 transactions pour un achat de bananes, la confiance associée à la probabilité qu’un achat de bananes conduise à un achat de pommes est calculée comme suit :

$C(Bananas,Apples)=\frac{150}{500}=0.3$

Dans ce cas, il n'y a que 30 % de chances qu'un achat de bananes conduise à un achat de pommes.

Si la confiance est une bonne mesure de probabilité, elle ne garantit pas une association claire entre les éléments. La valeur de la confiance peut être élevée pour d’autres raisons. C’est pourquoi un seuil de confiance minimum est appliqué pour filtrer les associations faiblement probables lors de l’exploration avec des règles d’association.

Facteur lift : la probabilité que l’élément A conduise à l’élément B est plus élevée que la probabilité de l’élément A. Cette mesure quantifie la force de l’association entre A et B. Elle peut permettre de déterminer s’il existe une véritable relation entre les éléments dans l’itemset ou si leur regroupement n’est qu’une coïncidence. 

$L(A,B)=\frac{C(A,B)}{S\left(A\right)}$ 


Où L_{A, B} est le lift pour l’élément A menant à l’élément B, C_{A, B} est la confiance que l’élément A mène à l’élément B, S_A est le support pour l’élément A.

Pour l’exemple ci-dessus, nous pouvons voir que : 

$L(Apples,Bananas)=\frac{0.6}{0.125}=4.8$

La valeur de lift élevée indique que la probabilité que des pommes et des bananes soient achetées ensemble est 4,8 fois plus élevée que la probabilité que des pommes soient achetées seules. On peut également observer que : 

$L(Bananas,Apples)=\frac{0.3}{0.25}=1.2$

La faible valeur de lift indique qu'un achat de bananes qui donne lieu à un achat de pommes n'est peut-être qu'une coïncidence.

Dans de nombreux cas, l’application d’une approche par force brute, qui consiste à calculer les seuils de support et de confiance pour chaque règle puis à éliminer les règles qui n’atteignent pas un certain seuil, peut être prohibitive en matière de calcul. Pour rendre l’application de l’algorithme Apriori plus efficace, il est souvent combiné à d’autres techniques d’exploration des règles d’association. Citons comme techniques les plus courantes l’algorithme FP-growth et sa variante FP-Max, qui permettent de réduire les contraintes de mémoire et de calcul. L’algorithme Apriori peut également être combiné avec des arbres de décision, où l’algorithme identifie l’itemset fréquent, et l’arbre de décision les règles d’association.

Une autre variante populaire de l’algorithme Apriori est le comptage dynamique des itemsets (DIC) qui commence à compter les itemsets potentiels plus tôt, sans attendre que toutes les transactions soient enregistrées. Le DIC divise le jeu de données en segments plus petits et traite chaque segment séparément. Cette segmentation permet un arrêt anticipé lorsque l’algorithme n’est pas en mesure d’identifier les itemsets fréquents, mais le partitionnement des données permet également de réduire considérablement le coût de calcul.

Les algorithmes Apriori peuvent également être utiles dans les applications d’intelligence artificielle basées sur l’apprentissage non supervisé comme les algorithmes de clustering, lorsque les données le permettent. Cela permet d’identifier les relations et les associations entre des entités apparemment indépendantes, en les regroupant en clusters possibles.

La découverte et le regroupement d'itemsets ont de multiples applications et l'algorithme Apriori est parfois considéré comme la première chose que les data miners essaient en raison de sa polyvalence. Nous examinerons certains cas d’utilisation courants dans différents secteurs.

L’une des applications les plus courantes de l’algorithme Apriori est l’analyse du panier d’achat. Les détaillants analysent l’historique d’achat des clients et optimisent l’agencement des magasins en plaçant les articles fréquemment achetés à proximité les uns des autres ou sur la même étagère. Les plateformes de commerce électronique utilisent les algorithmes Apriori pour étudier les relations basées sur les produits en fonction des préférences des utilisateurs et de l’analyse des modèles d’achat afin de créer des systèmes efficaces de recommandation des clients. Le même type d’analyse peut être utilisé pour optimiser l’achat de services, par exemple, en choisissant des cours de formation dans un catalogue ou en recommandant d’autres types de couverture lors de la sélection d’une assurance.

L’algorithme Apriori peut être utilisé pour trouver des règles d’association fortes entre les symptômes et les maladies afin d’améliorer l’efficacité du diagnostic et d’élaborer des plans de traitement ciblés. Par exemple, quels patients sont susceptibles de développer un diabète ou le rôle que jouent l’alimentation ou le mode de vie dans la maladie. Il peut également permettre d’identifier les facteurs associés aux effets indésirables des médicaments.

Les algorithmes Apriori sont également applicables aux bases de données non transactionnelles. Les analystes de données emploient souvent Apriori pour interpréter le comportement des utilisateurs d’un site Web (« web usage mining ») en analysant les données des flux de clics.

Une autre application courante de l'algorithme Apriori est l'identification de schémas frauduleux dans les transactions financières. Identifier certains modèles d'achat comme étant potentiellement frauduleux permet à une institution financière d'agir rapidement pour suspendre les transactions ou contacter le titulaire d'un compte.