Skip to content
Retour aux résultats

Algorithme Apriori

Introduite par
Agrawal, R. & Srikant, R.
Année
1994
Type
Frequent itemset and association rule mining algorithm
Famille
Machine learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

L'algorithme Apriori, introduit par Agrawal et Srikant en 1994, est la méthode fondamentale pour découvrir des ensembles d'éléments fréquents et des règles d'association dans des bases de données transactionnelles.

Il utilise une recherche guidée par la propriété anti-monotone du support, en largeur d'abord et par niveau, pour énumérer efficacement toutes les combinaisons d'éléments qui co-apparaissent au-dessus d'un seuil minimum défini par l'utilisateur, puis extrait des règles interprétables si-alors à partir de ces motifs.

L’intuition derrière la méthode

Considérons une base de données de tickets de supermarché. L'intuition d'Apriori est la propriété anti-monotone : si une paire de produits est rarement achetée ensemble, aucun ensemble plus grand contenant cette paire ne peut être fréquent. Cela permet à l'algorithme d'élaguer l'espace de recherche exponentiellement grand des combinaisons d'éléments possibles en construisant des candidats niveau par niveau — en commençant par des éléments uniques, puis des paires, puis des triplets — et en écartant tout candidat dont les sous-ensembles sont déjà connus pour être peu fréquents, avant même de les compter dans les données.

Histoire

Rakesh Agrawal et Ramakrishnan Srikant ont introduit l'algorithme Apriori à la VLDB en 1994, en s'appuyant sur la formulation du problème de l'exploration de règles d'association par Agrawal et al. en 1993. Le nom reflète son idée clé : utiliser la connaissance préalable des ensembles d'éléments fréquents (k) pour élaguer les candidats au niveau k+1. Il est devenu le banc d'essai canonique par rapport auquel tous les algorithmes d'ensembles d'éléments fréquents ultérieurs — y compris FP-Growth (2000) et Eclat — sont mesurés, et reste un chapitre standard dans les manuels d'exploration de données et d'apprentissage automatique.

Quand l’utiliser

Utilisez Apriori lorsque l'objectif est de découvrir des motifs de co-occurrence ou des relations si-alors dans des données transactionnelles ou de présence binaire d'éléments — analyse du panier d'achat, co-endossement d'éléments d'enquête, co-occurrence de diagnostics médicaux, ou association de termes textuels. Il convient aux ensembles de données de taille modérée où la transparence et l'interprétabilité des règles de sortie sont une priorité. N'utilisez pas Apriori lorsque la base de données transactionnelle est très volumineuse (millions de lignes avec de larges catalogues d'articles), car ses balayages répétés de la base de données entière le rendent lent par rapport à FP-Growth ; dans ces cas, FP-Growth est préféré. Il est également inapproprié pour les données numériques continues sans discrétisation préalable, et il ne modélise pas la directionnalité ou la causalité.

Limites et points d’attention

  • Les balayages répétés de la base de données entière le rendent lent sur de grands ensembles de données — FP-Growth est souvent préféré à grande échelle.
  • La diminution du seuil de support peut produire un nombre exponentiel d'ensembles d'éléments candidats et de règles, rendant l'interprétation difficile.
  • Ne capture pas l'ordre temporel, la directionnalité ou les relations causales entre les éléments.
  • Les résultats sont sensibles au choix des seuils de support et de confiance, qui nécessitent une connaissance du domaine ou un réglage systématique.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Génère des règles si-alors entièrement interprétables avec support, confiance et lift quantifiés.
  • La propriété d'élagage anti-monotone rend un espace de recherche autrement exponentiel tractable.
  • Ne nécessite aucune étiquetage préalable des données ; il est entièrement non supervisé.
  • Les paramètres de seuil (support, confiance) donnent à l'analyste un contrôle direct sur la granularité des règles.
  • Les règles de sortie sont exploitables et peuvent être communiquées à des parties prenantes non techniques sans arrière-plan algorithmique.
  • Seminal, fortement cité, et implémenté dans pratiquement toutes les bibliothèques majeures d'exploration de données.

Applications

  • Analyse du panier d'achat : découvrir quels produits sont fréquemment achetés ensemble pour guider la disposition des étagères et les promotions.
  • Informatique médicale : identifier les symptômes, diagnostics ou prescriptions de médicaments co-occurrents dans les dossiers des patients.
  • Exploration de l'utilisation du Web : trouver quelles pages ou fonctionnalités les utilisateurs ont tendance à visiter ou à activer ensemble.
  • Analyse d'enquêtes et de questionnaires : détecter quels éléments ou réponses d'échelle sont systématiquement co-endossés.
  • Amorçage de systèmes de recommandation : générer des associations d'éléments candidats avant de déployer le filtrage collaboratif.
  • Détection de fraude : mettre en évidence des motifs de co-occurrence inhabituels dans les journaux de transactions qui s'écartent des paniers normaux.

Comment ça marche

Comment ça marche

1

L'analyste choisit deux seuils avant d'exécuter l'algorithme : le support minimum (la fraction de transactions qui doivent contenir un ensemble d'éléments donné pour qu'il soit considéré comme fréquent) et la confiance minimum (la probabilité conditionnelle requise pour qu'une règle si-alors soit conservée). Ces deux valeurs contrôlent le volume et la spécificité de la sortie et doivent être calibrées par la connaissance du domaine ou des exécutions exploratoires.

2

L'algorithme effectue un balayage complet de la base de données transactionnelle pour compter la fréquence d'apparition de chaque élément individuel. Seuls les éléments dont le support atteint ou dépasse le seuil de support minimum sont conservés ; les autres sont écartés. Cet ensemble d'éléments uniques fréquents forme le premier niveau de candidats.

Formule
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

Les ensembles d'éléments fréquents trouvés au niveau k sont joints par paires pour former des ensembles d'éléments candidats de taille k+1. Seules les paires partageant les mêmes k-1 premiers éléments sont jointes, une règle qui maintient le jeu de candidats compact. Un nouveau balayage de la base de données compte le support de chaque candidat.

4

Avant le comptage, chaque candidat de taille k+1 est vérifié par rapport à tous ses sous-ensembles de taille (k). Si un sous-ensemble n'était pas fréquent au niveau précédent, le candidat est immédiatement élagué sans lecture des données, exploitant la propriété anti-monotone pour réduire le calcul. Les survivants de cette étape d'élagage forment le niveau suivant d'ensembles d'éléments fréquents.

5

À partir de chaque ensemble d'éléments fréquents de taille deux ou plus, toutes les règles si-alors possibles sont générées en partitionnant les éléments en un antécédent et un conséquent. Chaque règle est évaluée en termes de confiance — la proportion de transactions antécédentes qui contiennent également le conséquent. Les règles inférieures à la confiance minimum sont écartées.

Formule
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

Les règles survivantes sont classées par lift, qui compare la confiance observée à la fréquence de base du conséquent. Un lift supérieur à 1 signale que l'antécédent et le conséquent co-apparaissent plus que par hasard ; un lift proche de 1 indique une indépendance ; un lift inférieur à 1 indique une association négative. Les règles avec le lift le plus élevé sont les découvertes les plus exploitables.

Formule
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

Pièges courants

  • Définir le support minimum trop bas et se noyer dans des milliers de règles de faible qualité sans filtrage par lift.
  • Interpréter une confiance élevée comme une causalité plutôt qu'une co-occurrence — une règle avec une confiance élevée mais un lift proche de 1 est triviale.
  • Appliquer Apriori à des caractéristiques continues sans les discrétiser au préalable, ce qui gonfle l'espace des éléments et dégrade les résultats.
  • Rapporter des règles sans vérifier si la taille des échantillons d'ensembles d'éléments est suffisamment grande pour faire confiance aux estimations de support.
  • Négliger de supprimer les règles non informatives (par exemple, les règles impliquant des articles universellement achetés comme une carte de fidélité du magasin).

Questions fréquentes

Quelle est la différence entre support, confiance et lift ?

Le support est la fraction de toutes les transactions qui contiennent l'ensemble d'éléments — il mesure la prévalence. La confiance est la probabilité conditionnelle que le conséquent apparaisse étant donné l'antécédent — elle mesure la fiabilité de la règle. Le lift est le rapport de la confiance observée à la fréquence de base du conséquent ; un lift supérieur à 1 montre une véritable association positive plutôt qu'une coïncidence due à la popularité de l'article.

Quand devrais-je choisir FP-Growth plutôt qu'Apriori ?

FP-Growth compresse la base de données dans une structure arborescente et l'explore sans balayages complets répétés, ce qui le rend considérablement plus rapide sur de grands ensembles de données ou lorsque le support minimum est faible. Apriori est plus facile à comprendre et à implémenter et fonctionne bien sur des ensembles de données petits à modérés où le temps d'exécution n'est pas un goulot d'étranglement.

Comment choisir le support et la confiance minimum ?

Il n'y a pas de règle universelle. La pratique courante consiste à exécuter l'algorithme à plusieurs niveaux de support, à tracer le nombre d'ensembles d'éléments fréquents en fonction du support, et à choisir une valeur dans le coude de la courbe. La confiance est ensuite définie en fonction de la question commerciale ou de recherche — confiance plus élevée pour les règles critiques, plus faible pour la découverte exploratoire. Validez toujours les règles principales par rapport à l'expertise du domaine.

Apriori peut-il gérer des données numériques ou continues ?

Apriori nécessite des données binaires de présence d'éléments. Les variables continues doivent être discrétisées en intervalles (par exemple, âge en bas/moyen/haut) avant d'être encodées comme des éléments. Une mauvaise discrétisation peut gravement fausser les règles découvertes, de sorte que la stratégie de regroupement mérite une réflexion approfondie.

Apriori implique-t-il une causalité entre les éléments ?

Non. Les règles d'association capturent la co-occurrence, pas la causalité ou la direction. Une règle 'pain → beurre' signifie qu'ils apparaissent souvent dans le même panier ; cela ne signifie pas que l'achat de pain amène quelqu'un à acheter du beurre, ni que la relation est asymétrique dans un sens causal.

Méthodes associées

Sources

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    Ouvrir la référence de la publication
    Copié.
  2. Apriori algorithm. Wikipedia.

    Ouvrir la référence de la publication
    Copié.