Date de publication : 9 juin 2024
Contributeur : Joshua Noble
L’algorithme Apriori est un algorithme de machine learning non supervisé utilisé pour l’apprentissage des règles d’association. L’apprentissage des règles d’association est une technique d’exploration de données qui identifie les modèles fréquents, les connexions et les dépendances entre différents groupes d’éléments appelés jeux d’éléments dans les données. Parmi les cas d’utilisation courants, on trouve les systèmes de prédiction et de recommandation de maladies, comme l’analyse du panier d’achat pour les plateformes de commerce électronique.
Introduit en 1994 par Rakesh Agrawal et Ramakrishnan Srikant (lien externe à ibm.com), le nom « Apriori » reconnaît la connaissance antérieure des ensembles d’éléments fréquents que l’algorithme utilise dans les calculs. L’algorithme exécute des itérations sur les données pour identifier les k-éléments, 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 ensemble de données, tous ses sous-ensembles doivent également l’être. 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, lorsque vous utilisez une plateforme de commerce électronique qui vend des vêtements, et qu'un acheteur recherche des chaussures et décide d'ajouter une paire de chaussures noires à son panier. L'acheteur 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.
Étape 1 : génération fréquente itemsets
L'algorithme identifie d'abord les éléments uniques, parfois appelés « 1-itemsets », dans l'ensemble 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é en itemsets candidats et 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 d'itemsets fréquents, ne recherche que les itemsets dont la fréquence est significative.
Étape 2 : développer puis réduire les itemsets
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.
Étape 3 : répéter les étapes 1 et 2
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.
Découvrez les obstacles à l’adoption de l’IA, en particulier le manque de solutions de gouvernance de l’IA et de gestion des risques.
Obtenir le guide sur les modèles de fondation
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.
où IA 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 :
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 :
où A est l’antécédent, B est le conséquent, et C(A,B) est la confiance que A mène à B.
En reprenant l'exemple précédent, supposons qu'il y ait 150 transactions au cours desquelles des pommes et des bananes ont été achetées ensemble. La confiance est calculée comme suit :
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 des bananes, la confiance dans le fait qu'un achat de bananes entraîne un achat de pommes est calculée comme suit :
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.
Lift est le facteur avec lequel 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 aider à déterminer s'il existe une véritable relation entre les éléments dans l'itemset ou s'ils sont regroupés par coïncidence.
Où LA, B est le lift pour l’élément A menant à l’élément B, CA, B est la confiance que l’élément A mène à l’élément B, SA est le support pour l’élément A.
Dans l’exemple ci-dessus, nous pouvons voir que :
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 celle des pommes achetées seules. On peut également observer que :
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 (lien externe à ibm.com) pour 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 engendrer des problèmes 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. Deux des plus courants sont l’ algorithme FP-growth (lien externe à ibm.com) et sa variante FP-Max, qui permet de réduire les contraintes de mémoire et de calcul. L'algorithme Apriori peut également être combiné avec des decision trees, où il identifie l'itemset fréquent, et la technique de decision trees aide à identifier les règles d'association.
Une autre variante populaire de l'algorithme Apriori est le comptage dynamique des ensembles d'objets (DIC) (lien externe à ibm.com) qui commence à compter les ensembles d'objets 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é, telles que les algorithmes de clustering lorsque les données le permettent. Cela aide à 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 (lien externe à ibm.com) ou le rôle que l' alimentation ou le mode de vie joue dans la maladie (lien externe à ibm.com). Il peut également aider à 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.
Découvrez comment mettre en œuvre l’algorithme Apriori dans Python avec watsonx
Découvrez comment mettre en œuvre l’algorithme Apriori avec le langage de programmation R dans watsonx.
Découvrez le clustering, un algorithme de machine learning non supervisé qui organise et classe différents objets, points de données ou observations en groupes, ou clusters, en fonction des similitudes ou des schémas.